<h2>Question.</h2>

<p>In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is crucial that there is always some measurable eigenvalue gap.</p>

<ol>
<li><p>How badly do things go wrong if there is a single eigenvalue crossing with the ground state &mdash; where there can be any number of crossings between other energy eigenvalues, but which are well-separated from the crossing of the ground state with the first excited state?</p></li>
<li><p>Does the answer to the above question depend crucially on details of the physical system involved? Are there special cases for which the "error" is known to be bounded by constants (<em>i.e.</em>&nbsp;the state still has a substantial overlap with the ground state after the level crossing, though the overlap may be bounded away from 1)? Are there special cases for which the overlap with the ground state, after the crossing, is almost certainly going to be nearly zero?</p></li>
<li><p>Are there systems for which the question of whether the system is in the "bounded error" regime or the "unbounded error" regime will depend very sensitively on certain factors?</p></li>
</ol>

<h2>Details.</h2>

<p><a href="http://en.wikipedia.org/wiki/Adiabatic_quantum_computation">Adiabatic Quantum Computation</a> is a model of computation which is meant to exploit adiabatic evolution to perform possibly quite difficult computations. The idea is as follows: if you prepare an initial state which is the unique ground state of an initial Hamiltonian <em>H</em><sub>0</sub>, and slowly vary the Hamiltonian of the system until it is another Hamiltonian <em>H</em><sub>1</sub> which also has a unique ground state, then the final state of the system is that ground state. There are all sorts of details:</p>

<p><strong>Interpolation of Hamiltonians.</strong> The most common way to describe how the Hamiltonian varies is as a time-varying Hamiltonian which interpolates between <em>H</em><sub>0</sub> and <em>H</em><sub>1</sub>, that is <em>H(s)</em>&nbsp;=&nbsp;(1&nbsp;&minus;&nbsp;<em>s</em>)<em>H</em><sub>0</sub>&nbsp;+&nbsp;<em>sH</em><sub>1</sub>, although any parameterization of a continuous curve in the space of Hamiltonians, from <em>H</em><sub>0</sub> to <em>H</em><sub>1</sub>, is in principle allowable (subject to the considerations below).</p>

<p><strong>Adiabatic Theorems.</strong> The reliability of obtaining the ground state is guaranteed by Adiabatic Theorems (often called "the" adiabatic theorem, though there is more than one and they seem to be incomparable). For instance, <a href="http://arxiv.org/abs/quant-ph/0411152">Ambainis and Regev</a> show that if:</p>

<ul>
<li>the Hamiltonian function <em>H(s)</em> is at least twice-differentiable,</li>
<li>there is a continuously varying energy function <em>E(s)</em>, such that <em>E(s)</em> is an energy eigenvalue for the corresponding Hamiltonian <em>H(s)</em>,</li>
<li>the <em>E(s)</em>-eigenstate of <em>H(s)</em> is unique, and furthermore all other eigenstates of <em>H(s)</em> have energy separated away from <em>E(s)</em> by at least some constant &lambda;,</li>
<li>the initial state of the system is the <em>E</em>(0)-eigenstate of <em>H</em><sub>0</sub>, </li>
</ul>

<p>then for any error parameter &delta;&gt;0, evolving the system under the Hamiltonian <em>H(t/T)</em>, from time <em>t</em>&nbsp;=&nbsp;0 to time <em>t</em>&nbsp;=&nbsp;<em>T</em>, suffices to ensure that the final state of the system is within &delta; (in the Euclidean norm) of the <em>E</em>(1)-eigenstate of the Hamiltonian <em>H</em><sub>1</sub>, provided that</p>

<p>$$ T \geqslant \frac{10^5 \| H&#39; \|}{\delta^2 \lambda^3} \,\max \Bigl\{ \tfrac{1}{\lambda}\!\| H&#39; \|^2\,,\; \| H&#39;&#39; \| \Bigr\} \;. $$ </p>

<p>In particular, the smaller the desired error &mdash; and the smaller the guaranteed eigenvalue gap &lambda; about the energy eigenvalue &mdash; the larger <em>T</em> must be and therefore the longer the evolution must take for this Theorem to guarantee an error less than &delta;. By slowing the rate of evolution of the Hamiltonian in regimes where the eigenvalue gap is small, and increasing the rate where the eigenvalue gap is large, we can try to optimize the evolution of the Hamiltonian in order to achieve a minimum evolution time for any given error precision.
The usual notion of adiabatic evolution follows for the case that <em>E(s)</em> is the ground energy for the Hamiltonians <em>H(s)</em>. </p>

<p><strong>Level Crossings.</strong> A non-negotiable feature of the Hamiltonian evolution, if we are to apply an adiabatic theorem, is that there <em>exist</em> an eigenvalue gap. I suppose that if the final Hamiltonian is degenerate because some number of excited states converge upon the ground-state energy &mdash; but that there is a gap between these <em>cold convergent</em> energy eigenvalues and the <em>warm non-convergent</em> eigenvalues &mdash; then things will still be okay; the cold-but-not-ground energies might become populated, but as these states converge to the ground-state manifold of the final Hamiltonian anyhow, nothing is lost. However, if there is a <em>level crossing</em> &mdash; where the ground state's energy intersects the first excited state's energy at one time <em>t</em>, and separate again &mdash; then the adiabatic theorems say nothing.</p>

<p>In the context of Adiabatic Quantum Computation, everything that I have heard is in the regime where one assumes (or strives to ensure) that there are no level crossings, and one tries to make the eigenvalue gap as large as possible wherever possible. This corresponds naturally to a model of computation with very tightly bounded error. However, if one is content to repeat the computation several times, then constant error suffices; and so if at a level crossing half of the amplitude leaks into the first excited energy state, with the remainder remaining in the ground state manifold of the Hamiltonians <em>H(s)</em>, this is no terrible loss. Of course, the question is then: what <em>actually does</em> happen to the amplitude of the ground-state manifold at a level crossing? How much does it depend on the particular system or the details of the evolution of the Hamiltonian? Can the responses be applied to the regime where there is always a gap, but it is inconveniently small?</p>

CC BY-SA 3.0
2012-02-13T13:45:46.047Z
@Jon: thanks for the link, it seems the first step to answering the question from scratch. I'm curious about [the formula for the probability of diabatic transition](http://en.wikipedia.org/wiki/Landau%E2%80%93Zener_formula#The_Landau.E2.80.93Zener_formula)... it seems to still require the presence of a gap, and tends to certainty in the limit of a vanishing gap; which is confusing when the approximation in how the energies change with time is itself meant to be exactly linear so that they must cross. Could you clarify this, or perhaps point to a good reference with a careful treatment?
Niel de Beaudrap
CC BY-SA 3.0
2012-05-07T11:31:08.533Z
@jonas. The link on one of the comments (the ones that are duplicated) is broken.
Juan Bermejo Vega
CC BY-SA 3.0
2013-04-03T07:02:25.053Z
You seem to be missing something here. The ground state of an adiabatic computation does not have to be unique, and considering what happens in this case, should give you an idea what happens with a single level crossing. If an observable O commutes with the all Hamiltonians that the evolution passes through, then the expetation value of O is preserved. Thus if O is an observable which distinguishes different orthogonal states in the ground state manifold, then it's value is preserved and hence fixes the mapping between ground states in the initial and final ground state manifolds.
Joe Fitzsimons
CC BY-SA 3.0
2013-04-03T07:09:33.510Z
You can then ask what happens if you purturb the system slightly by adding some $\epsilon O$ to all Hamiltonians. This lifts the degeneracy of the ground state, but can be chosen so that it does not affect the rest of the level structure. Now, potentially you have level crossings in the newly non-degenerate low energy space, but as long as it is still gapped from the remaining levels, all that is changing is the probability to cross into one of the other states which were previously in the ground state manifold, which then you can calculate from Landau-Zener or similar.
Joe Fitzsimons
CC BY-SA 3.0
2013-04-03T13:04:27.407Z
@JoeFitzsimons: I'm not sure what you're getting at here. If the lowest and second-lowest energy levels only cross with each other, then it's not at all surprising that a sufficiently slow time-evolution will preserve the space spanned by the two lowest eigenvectors. The question is: how much of the population could shift from the lower to the higher within this space?
Niel de Beaudrap
CC BY-SA 3.0
2013-04-03T13:06:43.587Z
@JoeFitzsimons: The article [Quantum Speedup by Quantum Annealing](http://arxiv.org/pdf/1202.6257v1.pdf) linked to by `jonas` seems to suggest, at a glance, that the transition probability is 100% when the gap vanishes. Although the conditions under which it applies is not yet clear to me, the same seems to be suggested by a quick reading of the Landau-Zener Wikipedia page. I haven't gotten around to distilling the argument to stand on its own. If you would like to post an answer encapsulating how to apply Landau-Zener to resolve the question, it stands a good chance of being the best answer.
Niel de Beaudrap
CC BY-SA 3.0
2013-04-03T15:40:23.910Z
@NieldeBeaudrap: You can make it close to 100%. If you have a level crossing, that alone does not guarantee 100% shift, since if you move to quickly, you can jump back when the gap is small.
Joe Fitzsimons
CC BY-SA 3.0
2013-04-03T16:08:21.743Z
@JoeFitzsimons: do you mean that you can jump back if you have a second (possibly avoided) crossing? That's also used by the linked paper. Obviously it depends not just on a gap, but on the number of probable diabatic transitions (where the truly adiabatic regime has none at all, and the gap theorem simply states when you are in that regime). If you could write up something clear for a CS audience about the probability of a diabatic transition in any one level crossing, or in any one avoided crossing through which one evolves too quickly to be truly adiabatic, I would happily accept.
Niel de Beaudrap
CC BY-SA 3.0
2013-04-03T17:19:20.833Z
@NieldeBeaudrap: You don't need a second one. You run the risk of jumping levels whenever you move too fast relative to the gap at that point. As you approach a crossing, if you are moving to quickly, you can jump between levels before and after the crossing, where the gap is small. In principal, you can jump back and forth a bunch of times in a single evolution, so if you run the evolution very quickly compared to the average gap between the low lying levels, but slow enough not to transition to the higher levels, you'll end up with some random distribution across the lower levels.
Joe Fitzsimons
CC BY-SA 3.0
2014-04-23T12:54:43.647Z
@JoeFitzsimons: re-reading this now... you seem to say that there's significant amplitude transfer (albeit maybe <100%) before or after the crossing, if you badly violate the adiabatic conditions. The same holds even without level crossings of course: but perhaps you might **have** to violate the adiabatic conditions badly, to reach the crossing in finite time. My question might then be phrased: if you pass the crossing in finite time, how much transfer occurs? How sensitive is it to how you approach the crossing? Can you *control* the ratio of amplitude transfer? What general results exist?
Niel de Beaudrap
<quantum-computing><machine-models><adiabatic>
Adiabatic quantum computing with level crossings
Niel de Beaudrap
# Adiabatic quantum computing with level crossings

(Asked by: username_0 on 2012-02-11)

## Question.

In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is crucial that there is always some measurable eigenvalue gap.

1. How badly do things go wrong if there is a single eigenvalue crossing with the ground state — where there can be any number of crossings between other energy eigenvalues, but which are well-separated from the crossing of the ground state with the first excited state?
2. Does the answer to the above question depend crucially on details of the physical system involved? Are there special cases for which the "error" is known to be bounded by constants (*i.e.* the state still has a substantial overlap with the ground state after the level crossing, though the overlap may be bounded away from 1)? Are there special cases for which the overlap with the ground state, after the crossing, is almost certainly going to be nearly zero?
3. Are there systems for which the question of whether the system is in the "bounded error" regime or the "unbounded error" regime will depend very sensitively on certain factors?

## Details.

[Adiabatic Quantum Computation](http://en.wikipedia.org/wiki/Adiabatic_quantum_computation) is a model of computation which is meant to exploit adiabatic evolution to perform possibly quite difficult computations. The idea is as follows: if you prepare an initial state which is the unique ground state of an initial Hamiltonian *H*0, and slowly vary the Hamiltonian of the system until it is another Hamiltonian *H*1 which also has a unique ground state, then the final state of the system is that ground state. There are all sorts of details:

**Interpolation of Hamiltonians.** The most common way to describe how the Hamiltonian varies is as a time-varying Hamiltonian which interpolates between *H*0 and *H*1, that is *H(s)* = (1 − *s*)*H*0 + *sH*1, although any parameterization of a continuous curve in the space of Hamiltonians, from *H*0 to *H*1, is in principle allowable (subject to the considerations below).

**Adiabatic Theorems.** The reliability of obtaining the ground state is guaranteed by Adiabatic Theorems (often called "the" adiabatic theorem, though there is more than one and they seem to be incomparable). For instance, [Ambainis and Regev](http://arxiv.org/abs/quant-ph/0411152) show that if:

* the Hamiltonian function *H(s)* is at least twice-differentiable,
* there is a continuously varying energy function *E(s)*, such that *E(s)* is an energy eigenvalue for the corresponding Hamiltonian *H(s)*,
* the *E(s)*-eigenstate of *H(s)* is unique, and furthermore all other eigenstates of *H(s)* have energy separated away from *E(s)* by at least some constant λ,
* the initial state of the system is the *E*(0)-eigenstate of *H*0,

then for any error parameter δ>0, evolving the system under the Hamiltonian *H(t/T)*, from time *t* = 0 to time *t* = *T*, suffices to ensure that the final state of the system is within δ (in the Euclidean norm) of the *E*(1)-eigenstate of the Hamiltonian *H*1, provided that

$$ T \geqslant \frac{10^5 \| H' \|}{\delta^2 \lambda^3} \,\max \Bigl\{ \tfrac{1}{\lambda}\!\| H' \|^2\,,\; \| H'' \| \Bigr\} \;. $$

In particular, the smaller the desired error — and the smaller the guaranteed eigenvalue gap λ about the energy eigenvalue — the larger *T* must be and therefore the longer the evolution must take for this Theorem to guarantee an error less than δ. By slowing the rate of evolution of the Hamiltonian in regimes where the eigenvalue gap is small, and increasing the rate where the eigenvalue gap is large, we can try to optimize the evolution of the Hamiltonian in order to achieve a minimum evolution time for any given error precision.
The usual notion of adiabatic evolution follows for the case that *E(s)* is the ground energy for the Hamiltonians *H(s)*.

**Level Crossings.** A non-negotiable feature of the Hamiltonian evolution, if we are to apply an adiabatic theorem, is that there *exist* an eigenvalue gap. I suppose that if the final Hamiltonian is degenerate because some number of excited states converge upon the ground-state energy — but that there is a gap between these *cold convergent* energy eigenvalues and the *warm non-convergent* eigenvalues — then things will still be okay; the cold-but-not-ground energies might become populated, but as these states converge to the ground-state manifold of the final Hamiltonian anyhow, nothing is lost. However, if there is a *level crossing* — where the ground state's energy intersects the first excited state's energy at one time *t*, and separate again — then the adiabatic theorems say nothing.

In the context of Adiabatic Quantum Computation, everything that I have heard is in the regime where one assumes (or strives to ensure) that there are no level crossings, and one tries to make the eigenvalue gap as large as possible wherever possible. This corresponds naturally to a model of computation with very tightly bounded error. However, if one is content to repeat the computation several times, then constant error suffices; and so if at a level crossing half of the amplitude leaks into the first excited energy state, with the remainder remaining in the ground state manifold of the Hamiltonians *H(s)*, this is no terrible loss. Of course, the question is then: what *actually does* happen to the amplitude of the ground-state manifold at a level crossing? How much does it depend on the particular system or the details of the evolution of the Hamiltonian? Can the responses be applied to the regime where there is always a gap, but it is inconveniently small?

**Tags:** quantum-computing, machine-models, adiabatic
> **Comments:**
> **username_0**: @Jon: thanks for the link, it seems the first step to answering the question from scratch. I'm curious about [the formula for the probability of diabatic transition](http://en.wikipedia.org/wiki/Landau%E2%80%93Zener_formula#The_Landau.E2.80.93Zener_formula)... it seems to still require the presence of a gap, and tends to certainty in the limit of a vanishing gap; which is confusing when the approximation in how the energies change with time is itself meant to be exactly linear so that they must cross. Could you clarify this, or perhaps point to a good reference with a careful treatment?  
> **username_1**: @jonas. The link on one of the comments (the ones that are duplicated) is broken.  
> **username_2**: You seem to be missing something here. The ground state of an adiabatic computation does not have to be unique, and considering what happens in this case, should give you an idea what happens with a single level crossing. If an observable O commutes with the all Hamiltonians that the evolution passes through, then the expetation value of O is preserved. Thus if O is an observable which distinguishes different orthogonal states in the ground state manifold, then it's value is preserved and hence fixes the mapping between ground states in the initial and final ground state manifolds.  
> **username_2**: You can then ask what happens if you purturb the system slightly by adding some $\epsilon O$ to all Hamiltonians. This lifts the degeneracy of the ground state, but can be chosen so that it does not affect the rest of the level structure. Now, potentially you have level crossings in the newly non-degenerate low energy space, but as long as it is still gapped from the remaining levels, all that is changing is the probability to cross into one of the other states which were previously in the ground state manifold, which then you can calculate from Landau-Zener or similar.  
> **username_0**: @JoeFitzsimons: I'm not sure what you're getting at here. If the lowest and second-lowest energy levels only cross with each other, then it's not at all surprising that a sufficiently slow time-evolution will preserve the space spanned by the two lowest eigenvectors. The question is: how much of the population could shift from the lower to the higher within this space?  
> **username_0**: @JoeFitzsimons: The article [Quantum Speedup by Quantum Annealing](http://arxiv.org/pdf/1202.6257v1.pdf) linked to by `jonas` seems to suggest, at a glance, that the transition probability is 100% when the gap vanishes. Although the conditions under which it applies is not yet clear to me, the same seems to be suggested by a quick reading of the Landau-Zener Wikipedia page. I haven't gotten around to distilling the argument to stand on its own. If you would like to post an answer encapsulating how to apply Landau-Zener to resolve the question, it stands a good chance of being the best answer.  
> **username_2**: @NieldeBeaudrap: You can make it close to 100%. If you have a level crossing, that alone does not guarantee 100% shift, since if you move to quickly, you can jump back when the gap is small.  
> **username_0**: @JoeFitzsimons: do you mean that you can jump back if you have a second (possibly avoided) crossing? That's also used by the linked paper. Obviously it depends not just on a gap, but on the number of probable diabatic transitions (where the truly adiabatic regime has none at all, and the gap theorem simply states when you are in that regime). If you could write up something clear for a CS audience about the probability of a diabatic transition in any one level crossing, or in any one avoided crossing through which one evolves too quickly to be truly adiabatic, I would happily accept.  
> **username_2**: @NieldeBeaudrap: You don't need a second one. You run the risk of jumping levels whenever you move too fast relative to the gap at that point. As you approach a crossing, if you are moving to quickly, you can jump between levels before and after the crossing, where the gap is small. In principal, you can jump back and forth a bunch of times in a single evolution, so if you run the evolution very quickly compared to the average gap between the low lying levels, but slow enough not to transition to the higher levels, you'll end up with some random distribution across the lower levels.  
> **username_0**: @JoeFitzsimons: re-reading this now... you seem to say that there's significant amplitude transfer (albeit maybe <100%) before or after the crossing, if you badly violate the adiabatic conditions. The same holds even without level crossings of course: but perhaps you might **have** to violate the adiabatic conditions badly, to reach the crossing in finite time. My question might then be phrased: if you pass the crossing in finite time, how much transfer occurs? How sensitive is it to how you approach the crossing? Can you *control* the ratio of amplitude transfer? What general results exist?  

---

## 0 answers

