Spectral Gap Analysis for Efficient Tunneling in Quantum Adiabatic Optimization

Abstract

We investigate the efficiency of Quantum Adiabatic Optimization when overcoming potential barriers to get from a local to a global minimum. Specifically we look at n qubit systems with symmetric cost functions f:{0, 1}^n->R where the ground state must tunnel through a potential barrier of width n^a and height n^b. By the quantum adiabatic theorem the time delay sufficient to ensure tunneling grows quadratically with the inverse spectral gap during this tunneling process. We analyze barrier sizes with 1/2 < a + b and a < 1/2 and show that the minimum gap scales polynomially as n^{1/2-a-b} when 2a+b < 1 and exponentially as n^{-b/2} exp(-C n^{(2a+b-1)/2} ) when 1 < 2a+b. Our proof uses elementary techniques and confirms and extends an unpublished folklore result by Goldstone, which used large spin and instanton methods. Parts of our result also refine recent results by Kong and Crosson and Jiang et al. about the exponential gap scaling.

11 pages, 4 figures

References in corpus (3)

• Bounds for the adiabatic approximation with applications to quantum computation
• Tunneling and speedup in quantum optimization for permutation-symmetric problems
• Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization

Cited by in corpus (13)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Adiabatic Quantum Computing
• Simulated Quantum Annealing Can Be Exponentially Faster than Classical Simulated Annealing
• Prospects and challenges of quantum finance
• Lower Bounds on Quantum Annealing Times
• Necessary Adiabatic Run Times in Quantum Optimization
• A double-slit proposal for quantum annealing
• Diffusion Monte Carlo approach versus adiabatic computation for local Hamiltonians
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• Polynomial Time Algorithms for Estimating Spectra of Adiabatic Hamiltonians
• Discrepancies between Asymptotic and Exact Spectral Gap Analyses of Quantum Adiabatic Barrier Tunneling
• Simulated Quantum Annealing is Efficient on the Spike Hamiltonian