Searching for quantum speedup in quasistatic quantum annealers

We argue that a quantum annealer at very long annealing times is likely to experience a quasistatic evolution, returning a final population that is close to a Boltzmann distribution of the Hamiltonian at a single (freeze-out) point during the annealing. Such a system is expected to correlate with classical algorithms that return the same equilibrium distribution. These correlations do not mean that the evolution of the system is classical or can be simulated by these algorithms. The computation time extracted from such a distribution reflects the equilibrium behavior with no information about the underlying quantum dynamics. This makes the search for quantum speedup problematic.

Figure 1

(a) A sketch of computation time as a function of $\sqrt{N}$ for different annealing times $t_{a1}<t_{a2}<t_{a3}$. Similar behavior has been observed in SA and SQA and conjectured for QA [8, 9]. The blue line shows scaling of an optimized solver. The red line represents the region accessible by a quantum annealer with $t_a\ge t_{a3}$ and $N\le 512$. (b) The success probability for the same system. The optimal curve in panel (b) is plotted by connecting the corresponding tangency points in panel (a). We have assumed $T>0$ to correspond better with a realistic quantum annealer. At $T=0$, the asymptotic probability is flat at $P_0=1$.

Figure 2

(a) Envelope functions $A\left(s\right)$ and $B\left(s\right)$ for a DW2 quantum annealer. (b) The lowest 12 energy levels of a randomly generated 16-qubit problem. Dashed black lines are classical energies. Notice that the quantum energy eigenvalues are close to the classical ones at $s^{*}$. (c) Occupation probabilities during the annealing calculated by using the Redfield formalism (circles) and the Boltzmann distribution (solid lines), assuming $T=40\mathrm{mK}$ and $t_a=20\mu \mathrm{s}$. All probabilities follow the Boltzmann distribution in the quasistatic region (green) until they start freezing in the freezing region (yellow) and stay constant in the frozen region (blue). All final probabilities are close to the Boltzmann probabilities at the freeze-out point $s^{*}$, marked by the vertical (red) dashed line.

Figure 3

Ground-state probability as a function of $t_a$ for the problem instance studied in Fig. 2. The circles are calculated by using the Redfield master equation calculation with the same parameters as in Fig. 2. The squares are results of closed-system calculations. Three regions are distinguished: Coherent, where the environment does not have enough time to affect the system hence the open- and closed-system probabilities coincide. Nonequilibrium, in which the environment starts to occupy the excited states during the evolution but does not have enough time to establish equilibrium. Quasistatic, where the evolution is so slow that the system follows equilibrium during most of the evolution [as in Fig. 2] and $P_0$ depends on $t_a$ according to Eq. (4).

Figure 4

(a) $P_0$ and (b) $t_c$ as a function of $\sqrt{N}$ assuming a nonmonotonic $P_0\left(t_a\right)$. The probabilities at $t_{a2}$ exceed the asymptotic line. The optimal curve in panel (a) is plotted by connecting the corresponding tangency points in panel (b).