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.
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?
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?
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 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 H0, and slowly vary the Hamiltonian of the system until it is another Hamiltonian H1 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 H0 and H1, that is H(s) = (1 − s)H0 + sH1, although any parameterization of a continuous curve in the space of Hamiltonians, from H0 to H1, 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 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 H0,
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 H1, 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?
