PL-21-QU-0021
Limits of Short-Time Quantum Annealing
Ali Hamed Moosavian, Seyed Sajad Kahani, Salman Beigi
Abstract
Quantum annealing is a general purpose optimization algorithm that is based on the quantum adiabatic theorem. Quantum annealing involves an evolving Hamiltonian that is local. Thus, we expect that short-time quantum annealing algorithms to be inherently local and limited as well. In this paper, we validate this intuition by proving some limitations of short-time quantum annealing algorithms. We show that the distribution of the measurement output of short-time (at most logarithmic) quantum annealing computations are \emph{concentrated} and satisfy an \emph{isoperimetric inequality}. To showcase explicit applications, we also study the \textsc{MaxCut} problem and conclude that quantum annealing needs at least a run-time that scales logarithmically in the problem size to beat classical algorithms. To establish our results, we also prove a Lieb-Robinson bound that works for time-dependent Hamiltonians which might be of independent interest.
Meta Data
Doc ID | PL-21-QU-0021 |
Type | Paper |
Title | Limits of Short-Time Quantum Annealing |
Authors | Ali Hamed Moosavian, Seyed Sajad Kahani, Salman Beigi |
Year | 2021 |
Published | – |
Eprint | https://arxiv.org/abs/2104.12808 |
DoI | – |
Citation | arXiv:2104.12808v1 |