Necessary Adiabatic Run Times in Quantum Optimization

Abstract

Quantum annealing is guaranteed to find the ground state of optimization problems in the adiabatic limit. Recent work [Phys. Rev. X 6, 031010 (2016)] has found that for some barrier tunneling problems, quantum annealing can be run much faster than is adiabatically required. Specifically, an $n$-qubit optimization problem was presented for which a non-adiabatic, or diabatic, annealing algorithm requires only constant runtime, while an adiabatic annealing algorithm requires a runtime polynomial in $n$. Here we show that this non-adiabatic speed-up is a direct result of a specific symmetry in the studied problems. In the more general case, no such non-adiabatic speed-up occurs. We furthermore show why the special case achieves this speed-up compared to the general case. We conclude with the observation that the adiabatic annealing algorithm has a necessary and sufficient runtime that is quadratically better than the standard quantum adiabatic condition suggests.

arXiv comment5 pages, 5 figures

References in corpus (6)

• Bounds for the adiabatic approximation with applications to quantum computation
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Necessary Condition for the Quantum Adiabatic Approximation
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization
• The performance of the quantum adiabatic algorithm on spike Hamiltonians

Cited by in corpus (13)

• Adiabatic Quantum Computing
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Dynamics of reverse annealing for the fully-connected $p$-spin model
• Prospects and challenges of quantum finance
• Relation between quantum fluctuations and the performance enhancement of quantum annealing in a nonstoquastic Hamiltonian
• Variationally Scheduled Quantum Simulation
• Lower Bounds on Quantum Annealing Times
• Practical designs for permutation symmetric problem Hamiltonians on hypercubes
• A double-slit proposal for quantum annealing
• Quantum annealing with twisted fields
• Excited state search using quantum annealing
• Hardware-efficient quantum annealing with error mitigation via classical shadow
• Improving adiabatic quantum factorization via chopped random-basis optimization