Indexed on: 08 Nov '16Published on: 08 Nov '16Published in: arXiv - Quantum Physics
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.
Join Sparrho today to stay on top of science
Discover, organise and share research that matters to you