Unstructured Adiabatic Quantum Optimization: Optimality with Limitations

Abstract

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on $n$-bits in time $\text{poly}(n)2^{n/2}$. In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of $\Omega (2^{n/2})$ has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is \#P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

54 pages, 3 figures. Accepted in Quantum

References in corpus (27)

• Ising formulations of many NP problems
• A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
• Adiabatic Quantum Computing
• Spatial search by quantum walk
• Quantum Search by Local Adiabatic Evolution
• Bounds for the adiabatic approximation with applications to quantum computation
• Quantum Supremacy and the Complexity of Random Circuit Sampling
• Anderson localization casts clouds over adiabatic quantum optimization
• Achieving quantum supremacy with sparse and noisy commuting quantum computations
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Quantum Speedup by Quantum Annealing
• Near-optimal ground state preparation
• How Powerful is Adiabatic Quantum Computation?
• Spatial search by quantum walk is optimal for almost all graphs
• Time-dependent Hamiltonian simulation with $L^1$-norm scaling
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems
• Adiabatic quantum algorithm for search engine ranking
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation
• Exponential complexity of an adiabatic algorithm for an NP-complete problem
• Finding spin-glass ground states using quantum walks
• On the optimality of spatial search by continuous-time quantum walk
• A note on the switching adiabatic theorem
• Implementing any Linear Combination of Unitaries on Intermediate-term Quantum Computers
• On the adiabatic condition and the quantum hitting time of Markov chains
• Continuous-Time Quantum Algorithms for Unstructured Problems
• Mind the gap: Achieving a super-Grover quantum speedup by jumping to the end
• Eigenpath traversal by Poisson-distributed phase randomisation