Computational Bottlenecks of Quantum Annealing

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 $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(\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.

9 pages of main text + 3 pages of supplementary info, 5 figures; added discussion, updated references

References in corpus (5)

• Computational Role of Multiqubit Tunneling in a Quantum Annealer
• Simple Glass Models and their Quantum Annealing
• Temperature and Disorder Chaos in Three-Dimensional Ising Spin Glasses
• The quantum adiabatic algorithm and scaling of gaps at first order quantum phase transitions
• On the relevance of avoided crossings away from quantum critical point to the complexity of quantum adiabatic algorithm

Cited by in corpus (3)

• Scaling overhead of embedding optimization problems in quantum annealing
• Quantum annealing speedup over simulated annealing on random Ising chains
• Noise amplification at spin-glass bottlenecks of quantum annealing: a solvable model