Elimination of Perturbative Crossings in Adiabatic Quantum Optimization
arXiv:1104.2349 · doi:10.1088/1367-2630/13/7/073011
Abstract
It was recently shown that, for solving NP-complete problems, adiabatic paths always exist without finite-order perturbative crossings between local and global minima, which could lead to anticrossings with exponentially small energy gaps if present. However, it was not shown whether such a path could be found easily. Here, we give a simple construction that deterministically eliminates all such anticrossings in polynomial time, space, and energy, for any Ising models with polynomial final gap. Thus, in order for adiabatic quantum optimization to require exponential time to solve any NP-complete problem, some quality other than this type of anticrossing must be unavoidable and necessitate exponentially long runtimes.
7 pages, 3 figures
References in corpus (4)
Cited by in corpus (12)
- Adiabatic Quantum Computing
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Role of Non-stoquastic Catalysts in Quantum Adiabatic Optimization
- Degeneracy, degree, and heavy tails in quantum annealing
- Theory of open quantum dynamics with hybrid noise
- The Effects of the Problem Hamiltonian Parameters on the Minimum Spectral Gap in Adiabatic Quantum Optimization
- Speedup of the Quantum Adiabatic Algorithm using Delocalization Catalysis
- Bounding first-order quantum phase transitions in adiabatic quantum computing
- Eigenvalue-invariant transformation of Ising problem for anti-crossing mitigation in quantum annealing
- The effect of quantum fluctuations on the coloring of random graphs
- Enhancing the efficiency of adiabatic quantum computations
- Fighting Exponentially Small Gaps by Counterdiabatic Driving