# Techniques for lower bounding spectral gaps in the quantum adiabatic algorithm

In the quantum adiabatic algorithm, one prepares the ground state of a Hamiltonian $H_{i}$, and then evolves the Hamiltonian slowly over time to a target Hamiltonian $H_{f}$ via the interpolation $H(s)=(1-s)H_{i}+sH_{f}$.

Let $\Delta(s)$ denote the gap between the two smallest eigenvalues of $H(s)$. The Adiabatic Theorem states that if $s$ changes at a rate proportional to $\frac{1}{\Delta(s)^2}$, then the system will remain in the ground state of $H(s)$ at all times with high probability. Thus proving a lower bound on $\Delta(s)$ implies an upper bound on the runtime of the adiabatic algorithm.

My question is:

What proof techniques are know to place lower bounds on the size of the spectral gap $\Delta(s)$?

I'm aware of two results in this area:

• In some cases the gap can be found analytically, as is the case for adiabatic Grover search. Reference: http://arxiv.org/abs/quant-ph/0206003
• In some cases the gap can be be bounded using results from the mixing times of Markov chains, as is the case when preparing the Kitaev clock state for a poly-size quantum circuit. Reference: http://arxiv.org/abs/quant-ph/0405098

I'd appreciate pointers to any other results in this area.

• I was wondering if you have come across any better resource over last three years. Jun 5 '16 at 23:03