BACKGROUND

Adiabatic quantum optimization, quantum annealing, and classical annealing all can be formalized as stochastic motion over a “Thouless-Anderson-Palmer [‘TAP’ for short] free energy landscape”.

To briefly get technical, for a system of N spin-1/2 particles with given sets of individual fields $\{ h_i \}$ and pairwise couplings $\{ J_{ij} \}$ that are at a given temperature $\beta \equiv 1/T$, the TAP free energy is a real-valued function of the *magnetizations* of the spins (i.e., their individual expectation values along the x-, y-, and z-axes $\{ m_{1x}, m_{1y}, m_{1z}, \ldots, m_{Nx}, m_{Ny}, m_{Nz} \}$).

Namely, the TAP free energy is defined such that the probability of the system exhibiting a given set of magnetizations when it has the aforementioned fields, couplings, and temperature is directly proportional to

$$
\exp[- \beta F_{TAP}(m_{1x}, m_{1y}, m_{1z}, \ldots, m_{Nx}, m_{Ny}, m_{Nz}; \{ h_i \}, \{ J_{ij} \}, \beta)]
$$

As such, the equilibrium *phases* of the spin system correspond to the global minima of $F_{TAP}$. *Metastable* states are local minima of $F_{TAP}$.Note that the TAP landscape corresponding to an algorithm, be it classical or quantum, is *dynamic*. $F_{TAP}$ with respect to the magnetizations varies as you vary the fields, couplings, and temperature.

For example, the starting point of classical annealing is a high-temperature landscape taking the form of a simple “funnel” landscape to one global minimum, and the starting point of quantum annealing / adiabatic quantum optimization is a low-or-zero-temperature-but-high-transverse-fields landscape also taking the form of a simple “funnel” to one global minimum. As temperature is reduced in the classical case and as transverse field is reduced in the quantum case, this one initial global minimum can furcate into global “daughter” minima (a continuous, aka “2nd order” phase transition).

Alternatively, it can be overtaken by a minimum that nucleated somewhere else on the landscape then subsequently decreased in free energy faster than it (a discontinuous, aka “1st order”, phase transition). And there’s also more complicated situations, like when the global minimum furcates, but the “daughters” grow to have different free energies (an initally continuous phase transition that’ll require a subsequent discontinuous phase transition if you want to move between the daughter phases).**In any case, the hope for quantum annealing / adiabatic quantum optimization is really that by building a quantum annealer, you get to move on a TAP landscape is *qualitatively simpler* than the one’s you’re able to move on classically** By “qualitatively simpler,” I mean a landscape where you can take many fewer and shorter discontinuous jumps in between simple, greedy continuous gradient descents on your way to the global minimum at the algorithm endpoint (i.e., essentially zero temperature and zero transverse fields.)

MY CONTRIBUTION (which I’ll merely assert without proof… so take with a sizable grain of skeptic’s salt)

This hope is misplaced. Transverse Ising models which are “densely connected” (i.e., each spin is coupled to a finite fraction of all the others) permit one to calculate $F_{TAP}$ via a convergent series expansion with 1/(# of coupled-neighbors) as your small parameter.

Now, on the one hand, densely connected Ising models (with or without transverse field) possess ground states complicated enough to pose NP-complete problems. In other words, finding the location of a global minimum of $F_{TAP}$ for such densely connected Ising models is NP-complete. Yet on the other hand, thanks to the aforementioned convergent series expansion, finding merely the $F_{TAP}$ associated with some given set of magnetizations, fields, couplings, and temperature to some necessary level of accuracy is quite classically tractable.

**Thus, you don’t need to build a quantum computer to be able to move on such a quantum TAP landscape!**

One can efficiently make what I’d call a “meta” stochastic *classical* algorithm that directly moves about on the quantum TAP landscape (i.e., one that stochastically over magnetizations according to$ F_{TAP}$’s that are accounting for quantum fluctuations), even if one could never efficiently make what I’d call a “direct” classical simulation of the quantum algorithm by, say, Path-Integral Monte Carlo, because the Monte Carlo paths would never sample the relevant low energy portion of configuration space efficiently.