Techniques for lower bounding spectral gaps in the quantum adiabatic algorithm

Question

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.

Answer 1

You might find the techniques here useful too: http://arxiv.org/abs/1203.5801

A generalization of the above is on its way.

There are various references that give bounds for mixing times of Markov chains. Sometimes the gap of the quantum systems can be related to a the gap (largest to second largest) of a Markov chain, in which case the techniques such as rapidly mixing, high conductivity, gap upper bounds of Markov chains become relevant . Eg. Persi Diaconis and Laurent Saloff-Coste, 'comparison theorems for reversible markov chains'

RM