Southwest Quantum Information and Technology

Necessary adiabatic run times in quantum optimization

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

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.

Read this article online: https://arxiv.org/abs/1611.02585

(Session 9c : Friday from 4:45pm - 5:15pm)