Southwest Quantum Information and Technology

Efficient tunnelling in quantum adiabatic optimization and its quantum Monte Carlo simulations

Presenting Author: Lucas Brady, van Dam group (UC Santa Barbara)
Contributing Author(s): Wim van Dam

We explore the behavior of Quantum Adiabatic Optimization (QAO) and path-integral Quantum Monte Carlo (QMC) methods while tunneling through potential barriers of varying size. We focus on n-qubit systems with a symmetric cost function where the annealing algorithms must tunnel through a barrier that has (width x height) proportional to (n^a x n^b). By tuning the exponents a and b it is possible to make a successful QAO algorithm take constant, polynomial, or exponential time in n. First we examine for which values of a and b these complexity transitions occur and numerically compare the run times of QAO with QMC which we find are correlated. Furthermore we find evidence that the time complexities of these two algorithms scale with each other in a way that suggests that QMC algorithms tunnel efficiently in the same setting as where QAO is efficient. See the linked manuscript for more details. Next, we look at the behavior of QAO in the polynomial scaling region of a and b. To do this, we compare our system to several similar toy models, and using these we rederive a folklore result by Goldstone that says that asymptotically the spectral gap scales as n^(1/2-a-b) for a+b>1/2 and 2a+b<1. We show numerically that our problem approaches the same asymptotic scaling limit as these toy problems, but in both cases, extremely large n are needed to realize the asymptotic limit.

Read this article online: http://arxiv.org/abs/1509.02562

(Session 10 : Saturday from 9:45 am - 10:15 am)