Michael Jarret, Perimeter Institute for Theoretical Physics
The runtime of Adiabatic optimization algorithms are typically characterized by the size of the spectral gap of the corresponding Hamiltonian. Gap analysis nonetheless remains a challenging problem with few general approaches.
I present new Cheeger inequalities for "stoquastic" Hamiltonians, real matrices (including those with so-called sign problems), and Hermitian matrices. I prove that in many of these cases, a matrix with spectral gap γ and off-diagonal row-sum at least -Q admits a standard weighted Cheeger constant h obeying the inequality 2h ≥ γ ≥ √h2 + Q2 - Q. I will also discuss the implications of these inequalities on adiabatic algorithms, classically simulating these processes, and problems with the folklore assumption that the spectral gap correctly assesses the quality of an adiabatic process.