Question

Do systems of fermions take longer to equilibrate than systems of bosons for complexity-theoretic reasons?

Answer 1

This excellent paper by Scott Aaronson persuasively argues that computational complexity can be relevant for physical processes. In particular, what's hard for a hypothetical Turing machine to do may well also be hard for nature to do, and we should be skeptical of any claim that a real-world physical process could be exploited to perform computations which are extremely difficult in the theoretical-computer-science sense.

A textbook example of a calculation so difficult that even nature has difficulty solving it is that of finding the ground state (or in general, the Gibbs ensemble at any temperature) of a large Ising spin glass. This problem (or more precisely, a closely related decision problem) is known to be NP-complete, and therefore extremely difficult from a complexity-theoretic perspective, because the strong frustration effectively requires figuring out how to best satisfy many conflicting constraints. And indeed, real-life spin glasses take an extremely long time to reach their ground state when cooled (see here, here, and here). Indeed, this extremely slow equilibration is exactly the motivation behind adiabatic quantum computation: it's the reason why we need to first cool down an unfrustrated Hamiltonian and then adiabatically deform it to the frustrated one of interest, rather than simply cooling down the frustrated Hamiltonian directly (which would take far too long to reach the ground state, as discussed here).

My question is whether we need to go to something as exotic as a spin glass in order to see this complexity-induced equilibration slowdown. Many physically realistic systems have a sign problem which makes them exponentially difficult to simulate using Quantum Monte Carlo (QMC). (The sign problem is sometimes called the "fermionic sign problem," but this name is misleading, because there are fermionic systemsthat do not have a sign problem and bosonic systems that do.) The sign problem is also NP-complete, so from a complexity-theoretic perspective, solving the sign problem is equally as difficult as solving an Ising spin glass, in the sense that either problem has a polynomial-time reduction to the other. (I'm referring to solutions to the general problem; obviously there are specific instances of fermionic systems with a sign problem that are easier to solve than specific instances of Ising spin glasses, and vice versa.)

Of course, physical thermalization in the real world is very different from QMC. There may be algorithms that solve a many-body fermionic system (where by "solve" I mean something like "extract sufficiently accurate thermal expectation values of arbitrary local observables") which do not require solving the general sign problem - e.g. the density-matrix renormalization group. Nevertheless, Monte Carlo seems like a rough but decent model for the real-world physical process of equilibration. (Admittedly, this may hold true more for classical Monte Carlo, where the idea of the environment constantly imposing tiny perturbations on the system - some of which "take" and some of which don't - is probably a vaguely realistic model.)

So it seems plausible that the amount of time it takes for a QMC simulation to converge might very roughly correspond to the amount of time for a real system to actually equilibrate. Since the sign problem is generally associated with fermionic systems (although there are exceptions, as described above), this conjecture would seem to imply that fermionic systems tend to take qualitatively longer to equilibrate than bosonic systems.