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.
arXiv comment7 pages, 3 figures
References in corpus (8)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Anderson localization casts clouds over adiabatic quantum optimization
- First order phase transition in the Quantum Adiabatic Algorithm
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- First-order transitions and the performance of quantum algorithms in random optimization problems
- Does Adiabatic Quantum Optimization Truly Fail for NP-complete problems?
- Exponential complexity of an adiabatic algorithm for an NP-complete problem
- Quantum Annealing of Hard Problems
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