<p>You might find the techniques here useful too:
<a href="http://arxiv.org/abs/1203.5801" rel="nofollow">http://arxiv.org/abs/1203.5801</a></p>

<p>A generalization of the above is on its way.</p>

<p>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'</p>

<p>RM</p>

CC BY-SA 3.0
2016-06-05T23:02:44.043Z
@RM, I was wondering if you have come across any better resource over last three years.
Omar Shehab
CC BY-SA 3.0
2013-12-21T19:03:51.310Z
2013-12-21T19:03:51.310Z
user20801
<p>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}$.</p>

<p>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.</p>

<p>My question is:</p>

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

<p>I'm aware of two results in this area:</p>

<ul>
<li>In some cases the gap can be found analytically, as is the case for adiabatic Grover search. Reference: <a href="http://arxiv.org/abs/quant-ph/0206003" rel="nofollow">http://arxiv.org/abs/quant-ph/0206003</a></li>
<li>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: <a href="http://arxiv.org/abs/quant-ph/0405098" rel="nofollow">http://arxiv.org/abs/quant-ph/0405098</a></li>
</ul>

<p>I'd appreciate pointers to any other results in this area. </p>

CC BY-SA 3.0
2016-06-05T23:03:02.327Z
I was wondering if you have come across any better resource over last three years.
Omar Shehab
<reference-request><quantum-computing>
Techniques for lower bounding spectral gaps in the quantum adiabatic algorithm
Adam Bouland
# Techniques for lower bounding spectral gaps in the quantum adiabatic algorithm

(Asked by: username_0 on 2013-11-19)

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.

**Tags:** reference-request, quantum-computing

> **Comments:**
> **username_1**: I was wondering if you have come across any better resource over last three years.  

---

## 1 answers

### Answer by username_2 on 2013-12-21. Score: 4

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

> **Comments:**
> **username_1**: @RM, I was wondering if you have come across any better resource over last three years.  

---

