Computational Bottlenecks of Quantum Annealing
arXiv:1506.08608
Abstract
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 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 bottlenecks inside the spin glass phase, where the gap scales as a stretched exponential. For smaller , 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.
arXiv comment9 pages of main text + 3 pages of supplementary info, 5 figures; added discussion, updated references
References in corpus (19)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Quantum annealing with more than one hundred qubits
- Quantum Annealing and Analog Quantum Computation
- Anderson localization casts clouds over adiabatic quantum optimization
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- First order phase transition in the Quantum Adiabatic Algorithm
- Landau theory of quantum spin glasses of rotors and Ising spins
- Zero--Temperature Quantum Phase Transition of a Two--Dimensional Ising Spin--Glass
- A Solvable Spin-Glass of Quantum Rotors
- Simple Glass Models and their Quantum Annealing
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Temperature and Disorder Chaos in Three-Dimensional Ising Spin Glasses
- The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
- Chaos in temperature in the Sherrington-Kirkpatrick model
- Stochastic symmetry-breaking in a gaussian Hopfield model
- On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm
- Against temperature chaos in naive Thouless-Anderson-Palmer equations
- Rare events analysis of temperature chaos in the Sherrington-Kirkpatrick model
- Dynamics of quantum adiabatic evolution algorithm for Number Partitioning