Adiabatic Optimization and Dirichlet Graph Spectra
Several previous works have investigated the circumstances under which quantum adiabatic optimization algorithms can tunnel out of local energy minima that trap simulated annealing or other classical local search algorithms. Here we pursue two particular questions: (1) do adiabatic optimization algorithms always succeed in polynomial time for trivial optimization problems in which there is only one local minimum and (2) what characterizes the boundary between large- and small- gapped Hamiltonians? In addressing the first, we surprisingly find a counterexample in which the potential is a single basin on a graph, but the eigenvalue gap is exponentially small as a function of the number of vertices. For the second, we discover an equivalence between adiabatic interpolation Hamiltonians and the Dirichlet spectrum of weighted graphs. From this observation, we derive a number of bounds on the eigenvalue gap based on well-studied graph quantities. Additionally, in the context of quantum systems exhibiting path- and hypercube-like connectivity, we obtain a discrete analogue to the "fundamental gap theorem," yielding a tight lower bound to the eigenvalue gap in the presence of convex potentials.
Subscribe to A Quantum Bit
Quantum physics began with revolutionary discoveries in the early twentieth century and continues to be central in today’s physics research. Learn about quantum physics, bit by bit. From definitions to the latest research, this is your portal. Subscribe to receive regular emails from the quantum world. Previous Issues...
Sign Up Now
Sign up to receive A Quantum Bit in your email!