Effect of Local Minima on Adiabatic Quantum Optimization
arXiv:0709.0528 · doi:10.1103/PhysRevLett.100.130503
Abstract
We present a perturbative method to estimate the spectral gap for adiabatic quantum optimization, based on the structure of the energy levels in the problem Hamiltonian. We show that for problems that have exponentially large number of local minima close to the global minimum, the gap becomes exponentially small making the computation time exponentially long. The quantum advantage of adiabatic quantum computation may then be accessed only via the local adiabatic evolution, which requires phase coherence throughout the evolution and knowledge of the spectrum. Such problems, therefore, are not suitable for adiabatic quantum computation.
4 pages, published version
References in corpus (13)
- Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
- Quantum Mechanics helps in searching for a needle in a haystack
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Simulated Quantum Computation of Molecular Energies
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Search by Local Adiabatic Evolution
- Robustness of adiabatic quantum computation
- Simple proof of equivalence between adiabatic quantum computation and the circuit model
- Thermally assisted adiabatic quantum computation
- Noise resistance of adiabatic quantum computation using random matrix theory
- Adiabatic quantum algorithms as quantum phase transitions: first versus second order
- Exponential complexity of an adiabatic algorithm for an NP-complete problem
- Scaling of running time of quantum adiabatic algorithm for propositional satisfiability
Cited by in corpus (16)
- Shortcuts to adiabaticity: concepts, methods, and applications
- Consistency of the Adiabatic Theorem
- A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
- First Order Quantum Phase Transition in Adiabatic Quantum Computation
- Adiabatic optimization versus diffusion Monte Carlo
- Degeneracy, degree, and heavy tails in quantum annealing
- Error suppression in adiabatic quantum computing with qubit ensembles
- Symmetry-Protected Quantum Adiabatic Evolution in Spontaneous Symmetry-Breaking Transitions
- Non-Hermitian Quantum Annealing in the Ferromagnetic Ising Model
- Quantum search using non-Hermitian adiabatic evolution
- Non-Hermitian Quantum Annealing in the Antiferromagnetic Ising Chain
- Why adiabatic quantum annealing is unlikely to yield speed-up
- Fighting Exponentially Small Gaps by Counterdiabatic Driving
- Learning-Driven Annealing with Adaptive Hamiltonian Modification for Solving Large-Scale Problems on Quantum Devices
- Non-Hermitian Adiabatic Quantum Optimization
- Energy Spectrum and Exact Cover in an Extended Quantum Ising Model