A promising approach to solving hard binary optimization problems is quantum adiabatic annealing in a transverse magnetic field. An instantaneous ground state-initially a symmetric superposition of all possible assignments of N qubits-is closely tracked as it becomes more and more localized near the global minimum of the classical energy. Regions where the energy gap to excited states is small (for instance at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log N) bottlenecks inside the spin-glass phase, where the gap scales as a stretched exponential. For smaller N, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield model. Qualitative comparison with the Sherrington-Kirkpatrick model leads to similar conclusions.
A promising approach to solving hard binary optimization problems is quantum adiabatic annealing in a transverse magnetic field. An instantaneous ground state-initially a symmetric superposition of all possible assignments of N qubits-is closely tracked as it becomes more and more localized near the global minimum of the classical energy. Regions where the energy gap to excited states is small (for instance at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(log N) bottlenecks inside the spin-glass phase, where the gap scales as a stretched exponential. For smaller N, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield model. Qualitative comparison with the Sherrington-Kirkpatrick model leads to similar conclusions.
A promising approach to solving hard binary optimisation problems is quantum adiabatic annealing (QA) in a transverse magnetic field. An instantaneous ground state --- initially a symmetric superposition of all possible assignments of N qubits --- is closely tracked as it becomes more and more localised near the global minimum of the classical energy. Regions where the energy gap to excited states is small (e.g. at the phase transition) are the algorithm's bottlenecks. Here I show how for large problems the complexity becomes dominated by O(logN) bottlenecks inside the spin glass phase, where the gap scales as a stretched exponential. For smaller N, only the gap at the critical point is relevant, where it scales polynomially, as long as the phase transition is second order. This phenomenon is demonstrated rigorously for the two-pattern Gaussian Hopfield Model. Qualitative comparison with the Sherrington-Kirkpatrick Model leads to similar conclusions.
The performance of quantum annealing for combinatorial optimization is fundamentally limited by the minimum energy gap Δ encountered at quantum phase transitions. We investigate the scaling of Δ with system size N for two paradigmatic quantum spin-glass models: the two-dimensional Edwards-Anderson (2D-EA) and the all-to-all Sherrington-Kirkpatrick (SK) models. Utilizing a newly proposed unbiased energy-gap estimator for continuous-time projection quantum Monte Carlo simulations, complemented by high-performance sparse eigenvalue solvers, we characterize the gap distributions across disorder realizations. It is found that, in the 2D-EA case, the inverse-gap distribution develops a fat tail with infinite variance as N increases. This indicates that the unfavorable super-algebraic scaling of Δ, recently reported for binary couplings [Nature 631, 749 (2024)], persists for the Gaussian disorder considered here, pointing to a universal feature of 2D spin glasses. Conversely, the SK model retains a finite-variance distribution, with the disorder-averaged gap following a rather slow power law, close to Δ∝N−1/3. This finding provides a promising outlook for the potential efficiency of quantum annealers for optimization problems with dense connectivity.
Abstract Quantum annealers are commercial devices that aim to solve very hard computational problems1, typically those involving spin glasses2,3. Just as in metallurgic annealing, in which a ferrous metal is slowly cooled4, quantum annealers seek good solutions by slowly removing the transverse magnetic field at the lowest possible temperature. Removing the field diminishes the quantum fluctuations but forces the system to traverse the critical point that separates the disordered phase (at large fields) from the spin-glass phase (at small fields). A full understanding of this phase transition is still missing. A debated, crucial question regards the closing of the energy gap separating the ground state from the first excited state. All hopes of achieving an exponential speed-up, compared to classical computers, rest on the assumption that the gap will close algebraically with the number of spins5–9. However, renormalization group calculations predict instead that there is an infinite-randomness fixed point10. Here we solve this debate through extreme-scale numerical simulations, finding that both parties have grasped parts of the truth. Although the closing of the gap at the critical point is indeed super-algebraic, it remains algebraic if one restricts the symmetry of possible excitations. As this symmetry restriction is experimentally achievable (at least nominally), there is still hope for the quantum annealing paradigm11–13.
We review our earlier studies on the order parameter distribution of the quantum Sherrington-Kirkpatrick (SK) model. Through Monte Carlo technique, we investigate the behavior of the order parameter distribution at finite temperatures. The zero temperature study of the spin glass order parameter distribution is made by the exact diagonalization method. We find in low-temperature (high-transverse-field) spin glass region, the tail (extended up to zero value of order parameter) and width of the order parameter distribution become zero in thermodynamic limit. Such observations clearly suggest the existence of a low-temperature (high-transverse-field) ergodic region. We also find in high-temperature (low-transverse-field) spin glass phase the order parameter distribution has nonzero value for all values of the order parameter even in infinite system size limit, which essentially indicates the nonergodic behavior of the system. We study the annealing dynamics by the paths which pass through both ergodic and nonergodic spin glass regions. We find the average annealing time becomes system size independent for the paths which pass through the quantum-fluctuation-dominated ergodic spin glass region. In contrast to that, the annealing time becomes strongly system size dependent for annealing down through the classical-fluctuation-dominated nonergodic spin glass region. We investigate the behavior of the spin autocorrelation in the spin glass phase. We observe that the decay rate of autocorrelation towards its equilibrium value is much faster in the ergodic region with respect to the nonergodic region of the spin glass phase.
The correspondence between long-range interacting quantum spin glasses and combinatorial optimization problems underpins the physical motivation for adiabatic quantum computing. On one hand, in disordered (quantum) spin systems, the focus is on exact methods such as the replica trick that allow the calculation of system quantities in the limit of infinite system and ensemble size. On the other hand, when solving a given instance of an optimization problem, disorder-averaged quantities are of no relevance, as one is solely interested in instance-specific, finite-size properties, in particular the optimal solution. Here, we apply the nonequilibrium Green's function formalism to the spin coherent-state path integral to obtain the statistical fluctuations and the collective-excitation spectrum along the annealing path. For the example of the quantum Sherrington-Kirkpatrick spin glass, by comparing to extensive numerically exact results, we show that this method provides access to the instance-specific bottlenecks of the annealing protocol.
Quantum annealers promise to solve practical optimization problems potentially faster than conventional classical computers. One of the major ongoing debates in this context pertains to their robustness against the decohering effects of finite temperature and interactions with the environment. We argue that even in an ideal setting of very low temperatures and in the absence of a decohering environment, quantum annealers do not necessarily perform better than classical heuristic solvers. Here, we numerically study the performance of the quantum adiabatic algorithm (QAA) on a variety of constraint satisfaction problems and a spin glass problem by studying the size dependence of the minimum energy gap during the evolution of the QAA. We do so by employing Quantum Monte Carlo schemes as these allow us to study these problems at much larger scales than exact methods would allow. We find that in all cases a quantum phase transition occurs and the minimum gap decreases exponentially with system size, leading to an exponentially large running time for the QAA. Based on these and other results, we briefly discuss potential modifications to the QAA that may improve the scaling of the minimum gap, leading to faster quantum adiabatic algorithms.