Open AccessZero-temperature quantum annealing bottlenecks in the spin-glass phase
Author(s) -
Sergey Knysh
Publication year - 2016
Publication title -
nature communications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 5.559
H-Index - 365
ISSN - 2041-1723
DOI - 10.1038/ncomms12370
Subject(s) - quantum annealing , superposition principle , spin glass , gaussian , qubit , physics , adiabatic process , quantum phase transition , quantum , excited state , condensed matter physics , quadratic unconstrained binary optimization , quantum critical point , phase transition , statistical physics , quantum mechanics , ground state , simulated annealing , quantum computer , mathematics , algorithm
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.