Adiabatic Optimization and The Fundamental Gap Theorem
The quantum adiabatic theorem upper bounds the runtime of an adiabatic optimization algorithm by O(1/γ^3). Here, γ represents the minimal difference between the two lowest eigenvalues (the gap) of the associated Hamiltonian over the course of its evolution. Thus, the problem of upper bounding the runtime of an adiabatic algorithm reduces to that of lower bounding the eigenvalue gap. Despite some notable successes, this has historically proven to be a very difficult problem. In a recent breakthrough result, Andrews and Clutterbuck proved such a bound -- the longstanding Fundamental Gap Conjecture -- for continuum Hamiltonians. Unlike their result, however, we are interested in developing gap-bounding tools for the discrete setting. Of particular interest is the case of graph Laplacians with "convex" potentials.
In this talk I will present a brief overview of adiabatic algorithms and history of the Fundamental Gap Theorem. I will then introduce the concept of a graph Laplacian with a "convex" potential and the linear equations solved by such a Hamiltonian. Using the Hellman-Feynman theorem and variational techniques, I will sketch a proof of the gap bound of the path graph (a discrete analogue of the one dimensional Fundamental Gap Theorem) and the Hypercube graph.
In both of the above cases, from the perspective of runtime, the gap is demonstrably "large." One is then tempted to conjecture that all graphs with "convex" potentials have correspondingly large gaps. I will demonstrate that, at least under a naive definition of convexity, this is false and present a case where a convex potential results in an exponentially small gap. Using methods originally employed in the analysis of Markov chains, I will show that the gaps of general graphs can be bounded, provided that the ground-state is "single-peaked."
This is joint work with Stephen Jordan