Why adiabatic quantum annealing is unlikely to yield speed-up
arXiv:2212.13649 · doi:10.1088/1751-8121/ad0439
Abstract
We study quantum annealing for combinatorial optimization with Hamiltonian where is diagonal, is the equal superposition state projector and the annealing parameter. We analytically compute the minimal spectral gap as with the total number of states and its location . We show that quantum speed-up requires an annealing schedule which demands a precise knowledge of , which can be computed only if the density of states of the optimization problem is known. However, in general the density of states is intractable to compute, making quadratic speed-up unfeasible for any practical combinatoric optimization problems. We conjecture that it is likely that this negative result also applies for any other instance independent transverse Hamiltonians such as .
arXiv comment23 pages, 6 figures, updated to published version
References in corpus (41)
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum Annealing in the Transverse Ising Model
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- Adiabatic Quantum Computing
- Tight bounds on quantum searching
- Theory of Quantum Annealing of an Ising Spin Glass
- Quantum Search by Local Adiabatic Evolution
- Defining and detecting quantum speedup
- Quantum Computation by Adiabatic Evolution
- Bounds for the adiabatic approximation with applications to quantum computation
- Fixed-point quantum search with an optimal number of queries
- Quantum versus Classical Annealing of Ising Spin Glasses
- Survey propagation: an algorithm for satisfiability
- First order phase transition in the Quantum Adiabatic Algorithm
- How Powerful is Adiabatic Quantum Computation?
- Quantum Adiabatic Brachistochrone
- Prospects for Quantum Enhancement with Diabatic Quantum Annealing
- Size dependence of the minimum excitation gap in the Quantum Adiabatic Algorithm
- The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
- Simple Glass Models and their Quantum Annealing
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- Adiabatic Quantum Computing for Random Satisfiability Problems
- Exponential Complexity of the Quantum Adiabatic Algorithm for certain Satisfiability Problems
- Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
- Tunneling and speedup in quantum optimization for permutation-symmetric problems
- Adiabatic quantum algorithms as quantum phase transitions: first versus second order
- Quantum Adiabatic Evolution Algorithms with Different Paths
- Different Strategies for Optimization Using the Quantum Adiabatic Algorithm
- Exponential complexity of an adiabatic algorithm for an NP-complete problem
- Quantum versus classical annealing: insights from scaling theory and results for spin glasses on 3-regular graphs
- 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
- Adiabatic Spectroscopy and a Variational Quantum Adiabatic Algorithm
- Quantum annealing with longitudinal bias fields
- The Power of Adiabatic Quantum Computation with No Sign Problem
- Effect of Local Minima on Adiabatic Quantum Optimization
- Adiabatic quantum optimization fails for random instances of NP-complete problems
- Analog Nature of Quantum Adiabatic Unstructured Search
- Analytical solution for nonadiabatic quantum annealing to arbitrary Ising spin Hamiltonian
- Fixed-Point Adiabatic Quantum Search
- How Much Structure Is Needed for Huge Quantum Speedups?
- How Quantum is the Speedup in Adiabatic Unstructured Search?