This is not my field and I've been plenty wrong before, but this:
Establishing an obstruction to a classical simulation is a rather ill-defined task. A related, yet more concrete, goal is to find an obstruction to an efficient quantum Monte Carlo (QMC), which is one of the chief numerical workhorses in the field. In the QMC, one considers the Euclidean (or thermal) partition function of a quantum system in d dimensions as a statistical mechanical (SM) model in d + 1 dimensions with the extra dimension being imaginary time (5). If this can be carried out such that the resulting SM model has Boltzmann weights that are local and non-negative, then efficient QMC sampling is possible (6).
Indicates to me that the method is not "can we do this with our current models" but "if this model can be done, it indicates that the approach is physically possible." Do you read that differently?
Although QMC offers essentially numerically exact solutions for a wide variety of many-body quantum problems, in the case of aforementioned systems, the Boltzmann weights seem to be unavoidably negative or complex. Notably, signs and phases in the Euclidean partition function can sometimes be a matter of representation. Having a “sign problem” thus means that no local transformation that removes the signs and phases is possible. Notably, the definition of a sign problem must involve the notion of locality [see also the study of Hastings (7)]. By performing a nonlocal transformation on the physical degrees of freedom, one can always diagonalize the Hamiltonian and obtain a classical partition function. However, such a transformation requires computational resources that scale exponentially with the system size. Therefore, for a meaningful definition of the sign problem, one has to add an additional requirement, that is, that the degrees of freedom σ, that enter the Boltzmann weights must be expressed as local combinations of the physical ones or, more precisely, that σ are given by finite depth local quantum circuits acting on the physical degrees of freedom.
In other words, the argument isn't "the way we do the computation doesn't scale" the argument is "we can tell we're working on an nth order model of an n^2th order problem which indicates that any interpretation of the problem leads to kaboom."
They do give you kinda-sorta an out:
For the sake of clarity in this work, we do not address the possibility of nonlocal approaches to QMC, such as determinant QMC or cluster algorithms (8–10).
Which, by my read, means "we didn't also club it down by eliminating it through this other approach." However, if "determinant QMC" disproved their hypothesis I expect they would have addressed it.
But then, I went all the way to Diff EQ. I'm well out of my depth.
For the sake of clarity in this work, we do not address the possibility of nonlocal approaches to QMC, such as determinant QMC or cluster algorithms |