1. Introduction
Combining physics, mathematics, and computer science, quantum computing has developed in the past two decades from a visionary idea (Feynman Reference Feynman1982) to one of the most exciting areas of quantum mechanics (Nielsen and Chuang Reference Nielsen and Chuang2000). The recent excitement in this lively and fashionable domain of research was triggered by Peter Shor (Reference Shor1994), who showed how a quantum computer could exponentially speed up classical computation and factor numbers much more rapidly (at least in terms of the number of computational steps involved) than any known classical algorithm. Shor's algorithm was soon followed by several other algorithms that aimed to solve combinatorial and algebraic problems, and in the last few years theoretical study of quantum systems serving as computational devices has achieved tremendous progress. According to one authority in the field (Aharonov Reference Aharonov1998, Abstract), “We now have strong theoretical evidence that quantum computers, if built, might be used as a dramatically powerful computational tool, capable of performing tasks which seem intractable for classical computers.”
The common view is that quantum algorithms such as Shor's may help to redescribe the complexity space of computational problems, but recently it has been suggested that they may even rewrite the abstract notion of computability itself by “computing the (recursion-theoretic) noncomputable.” Here we address one such suggestion that rests on the quantum adiabatic algorithm, pointing out its failure to perform the purported hypercomputation,Footnote 1 and use this negative result to speculate further on the so-called superiority of quantum computers.
That “recursiveness” may not be a natural physical property and that physical processes may not necessarily preserve it has been argued in the past (see, e.g., Pour-el and Richards Reference Pour-el and Richards1981; Moore Reference Moore1990; Pitowsky Reference Pitowsky1990; Hogarth Reference Hogarth, Hull, Forbes and Burian1994), but this note intends to add nothing new to the general debate on the physical possibility of hypercomputers (Copeland Reference Copeland2002; Davis Reference Davis and Teuscher2003; Shagrir and Pitowsky Reference Shagrir and Pitowsky2003). Agnostic as we are with respect to the question whether there are any physical hypercomputers, we argue here that the quantum adiabatic theorem is not a basis for hypercomputation.
The paper is structured as follows. In Section 2 we describe the quantum adiabatic ‘hypercomputer’. In Section 3 we flesh out the mistake on which the proposed hypercomputer rests. Section 4 concludes with a speculation on where the putative power of quantum computers might come from.
2. The Quantum Adiabatic ‘Hypercomputer’
At the 1900 International Congress of Mathematicians, held that year in Paris, the German mathematician David Hilbert put forth a list of 23 unsolved problems that he saw as being the greatest challenges for twentieth-century mathematics. Hilbert's tenth problem, to find a method (what we now call an algorithm) for deciding whether an arbitrary Diophantine equation has an integral solution, was shown by Yuri Matiyasevich in 1970 to be Turing undecidable. If (and only if) one could solve it, one could also solve the Halting problem.
For the last six years, in 10 papers posted to the quantum physics section of the Los Alamos preprint archive (http://xxx.archiv.org), some of which were published in printed journals (Kieu Reference Kieu2002, Reference Kieu2003, Reference Kieu2004, Reference Kieu2005), Tien D. Kieu has been claiming to have a scheme according to which, in principle, physical quantum systems could be used to solve this prototypical computationally undecidable problem in finite time.
In order to appreciate Kieu's scheme, let us first set the stage. A well-known theorem of quantum mechanics, namely, the adiabatic theorem (Born and Fock Reference Born and Fock1928; for a more recent proof, see, e.g., Messiah [Reference Messiah1961, 739–746]), was recently harnessed by a group of physicists from MIT (Farhi et al. Reference Farhi2000) to develop a novel quantum algorithm. Their aim was to solve in polynomial time certain decision problems that are believed to be nondeterministic polynomial time–hard, and in so doing to vindicate the putative exponential superiority of quantum algorithms over their classical counterparts.Footnote 2
The crux of the quantum adiabatic algorithm lies in the possibility of encoding a specific instance of a given decision problem in a certain Hamiltonian.Footnote 3 One then starts the system in a certain quantum state—the lowest energy state of the system, known as the ground state—of another Hamiltonian that is easy to construct and slowly evolves the system in time toward the interpolated and desired Hamiltonian. According to the quantum adiabatic theorem and given certain conditions (see the Appendix), the result of such a physical process is another energy ground state that encodes the solution to the desired decision problem.
More precisely, one encodes the solution to a decision problem in the ground state of a Hamiltonian
$H_{P}$
that is diagonal in the computational basis and is a member of a one-parameter family of Hamiltonians
$\tilde{H}(s) $
varying smoothly for
$0\leq s\leq 1$
, and then sets
$H(t) =\tilde{H}(t/ T) $
so that T (the run time of the algorithm) governs how slowly H varies. Now denote the instantaneous eigenstates and eigenvalues of
$\tilde{H}(s) $
as
with
where N is the dimension of the Hilbert space.Footnote 4 Suppose that
$\vert \psi (0) \rangle $
is the ground state of
$\tilde{H}(0) $
, that is,
According to the adiabatic theorem, if the gap
$g_{\mathrm{min}\,}$
between the two lowest levels,
$E_{1}(s) -E_{0}(s) $
, is strictly greater than zero for all
$0\leq s\leq 1$
, then
where
$\vert \psi (t) \rangle $
is the state at time t.
One next chooses a Hamiltonian
$H_{I}$
that is easy to construct and does not commute with
$H_{P}$
(otherwise one would have to encode the solution already in the initial Hamiltonian!) and defines the interpolating Hamiltonian to be
so that
Under these conditions, and in the adiabatic limit, that is, for T long enough, the evolution from
$t=0$
to
$t=T$
(starting in the ground state of
$H_{I}$
) will lead to the ground state of
$H_{P}$
and to the solution of the problem.
Kieu's insight was to harness the novel quantum adiabatic algorithm to solve another decision problem, namely, Hilbert's tenth. His idea was that one can capitalize on the infinite dimensionality of the Hilbert space that ‘accompanies’ every quantum system in order to perform in parallel infinite computational steps in a finite time—a task that a hypercomputer, whether classical or quantum, is supposed to be capable of performing.
Kieu designed the target (interpolated) Hamiltonian to mimic the form of the left-hand side squared of the original Diophantine equation. This, in turn, guaranteed the existence of a global minimum: The Diophantine equation has at least one integer solution if and only if the final ground state of the target Hamiltonian is zero and has no integer solution otherwise. Next, Kieu claimed to have proved an ingenious probabilistic criterion that allows one, by measuring
$H_{P}$
, to identify whether the quantum system has indeed reached its ground state, no matter what T is.Footnote 5 If not, according to Kieu, one needs only to enlarge the evolution time T and iterate the algorithm until the ground state (which is ensured to exist through the boundedness of
$H_{P}$
) is achieved.
Let us consider a particular example, say the equation
with unknowns x, y, and z. Finding out whether this equation has any nonnegative integer solution by Kieu's algorithm requires the realization of a Fock space. On this Hilbert space, we construct the Hamiltonian corresponding to (7):
which has a spectrum bounded from below—semidefinite, in fact.Footnote 6 Note that the operators
$N_{j}=a^{\dagger }_{j}a_{j}$
have only nonnegative integer eigenvalues
$n_{j}$
and that
$[ N_{j},\,H_{P}] =0=[ N_{i},\,N_{j}] $
, so these observables are simultaneously measurable. For some
$(n_{x},\,n_{y},\,n_{z}) $
the ground state
$\vert g\rangle $
of the Hamiltonian so constructed has the properties
Thus, after enough iterations, a projective measurement of the energy
$E_{g}$
of the ground state
$\vert g\rangle $
will yield the answer for the decision problem: the Diophantine equation has at least one integer solution if and only if
$E_{g}=0$
and has no solutions otherwise. (If
$c=0$
in our example, we know that
$E_{g}> 0$
from Fermat's last theorem.)
If there is one unique solution, then the projective measurements of the observables corresponding to the operators
$N_{j}$
will reveal the values of various unknowns. If there are many solutions, finitely or infinitely as in the case of the Pythagoras theorem,
$x^{2}+y^{2}-z^{2}=0$
, the ground state
$\vert g\rangle $
will be a linear superposition of states of the form
$\vert n_{x}\rangle \vert n_{y}\rangle \vert n_{z}\rangle $
, where
$(n_{x},\,n_{y},\,n_{z}) $
are the solutions. In such a situation, the measurement may not yield all the solutions. However, finding all the solutions is not the aim of a decision procedure for this kind of problem.
Notwithstanding this, measurements of
$N_{j}$
in the ground state would always yield some values
$(n_{x},\,n_{y},\,n_{z}) $
, and a straightforward substitution would confirm if the equation has a solution or not. Thus the measurement in the ground state either of the energy or of the number operators will be sufficient to give the result for the decision problem.
Since the final Hamiltonian (designed as to mimic the form of the left-hand side squared of the original Diophantine equation) has an integer spectrum and is bounded from below (i.e., there exists, by construction, a global minimum for
$H_{P}$
), the evolution time of Kieu's algorithm is finite. Thus it appears that, at least in theory, Kieu's hypercomputer does indeed work: Given that the algorithm purports to find a global energy minimum, ‘all’ one needs to do in order to compute the (recursion-theoretic) noncomputable is to let the system evolve slowly enough, measure its energy, and iterate this procedure until a ground state is achieved with probability >
$1/ 2$
and an answer to the decision problem is found.
A major breakthrough in computer science? A vindication of the superiority of quantum computers over their classical counterparts? Unfortunately, neither is true. The next section explains why.
3. How Slow Is Slowly Enough?
We now proceed to show that the proposed quantum adiabatic algorithm cannot compute a (recursion-theoretic) noncomputable function.
3.1. Mind the Gap
A crucial ingredient in the adiabatic algorithm is the energy gap between the ground state
$E_{0}$
and the next excited state
$E_{1}$
:
This gap controls the evolution time of the algorithm, in the exact following way (see the Appendix):
The problem is that in the absence of a detailed spectral analysis, in general nobody knows what g is, how it behaves, or how to compute it!
Now some of the fanfare in Kieu's papers is built around the idea that there always exists such a gap and that the computation halts in any case (since the final Hamiltonian
$H_{P}$
, by construction, has an integer spectrum and is bounded from below). We set aside the issue of the feasibility of the manufacturing of such a Hamiltonian, which appears to require infinite precision (Hodges Reference Hodges2005; see also below), but even if we grant such (possibly unfeasible) manufacturing capacities, their merit is still questionable: Classically too there may always exist a halting time, only it is not computable. This is easiest to appreciate in the case of Turing's halting problem: Consider all Turing machines with k states; throw away all those that fail to stop on the input 1; among the others take the one that runs longest; call the number of steps of that machine
$T(k) $
. Now we ‘know’ that in order to decide whether a machine with k states stops on the input 1, we have to wait at most
$T(k) $
steps. But of course we don't really know anything about when the machine will halt, because
$T(k) $
is not computable, growing faster than any recursive function.
What Kieu is doing is defining an adiabatic process whose time is of that order (and whose gap g is therefore incomputably small). The fact that there is some T that will do the job is not a big deal (nor is, therefore, the fact that we can use finite-dimensional but unboundedly increasing Hilbert spaces for each instance). Indeed, if someone told us what
$T(k) $
is, we would not have needed infinitely many steps to complete the job classically.
With this gap in mind, we can now think of the following problem: For each given running time of the algorithm T, we have to come up with a process whose rate of change is ≈
$T^{-1}$
. Question: How do we know that we are implementing the correct rate of change while
$H(t) $
is evolving? Apparently, by being able to measure differences of order
$T^{-1}$
, that is, having a sensitive ‘speedometer’. When the going gets rough we approach very slow speeds of the order of ∼
$T^{-1}(k) $
, which begs the question, since we can then compute
$T(k) $
using our ‘speedometer’; no fancy quantum computer is needed. If we don't have a ‘speedometer’, then even if we decided to increase the running time from T to, say,
$T+7$
, we will have no clue that the machine is indeed doing
$(T+7) ^{-1}$
km/h and not
$T^{-1}$
km/h. In this case, clearly, Kieu's algorithm cannot be implemented since we will never know how slowly we should evolve our physical system. But then we will also fail to fulfill the adiabatic condition, which ensures that once we have reached the desired final Hamiltonian, its ground state encodes the solution.
Kieu may argue in response that his (allegedly proven) ingenious probabilistic criterion (along with the iteration of the algorithm) allows him to detect whether the ground state was achieved, that is, whether the algorithm has indeed evolved adiabatically in order to ensure a meaningful result when reading of the energy eigenstate of
$H_{P}$
. His idea seems to be the following: In general, when one performs such an adiabatic cooling, one doesn't meet this probabilistic criterion (which ensures that it is only the ground state that will appear with probability >
$1/ 2$
upon measuring
$H_{P}$
) for any state: applying the number operator gives lots of different answers when one repeats the experiment, and none of them comes up more than half of the time. In this case one simply doubles the running time and tries again, and so on. Kieu's claim, call it the HALF CLAIM, is that because there exists (by construction) a global minimum and some respective correct value of T that makes the evolution slow enough, one is bound to have success eventually.
Now if the HALF CLAIM were true, it would have been a remarkable achievement. To see this, recall that the adiabatic theorem is a necessary condition for tracking the ground state. In other words, it ensures that the system's evolution will track the ground state only when certain conditions are met, and only in the adiabatic limit, that is, when
$T\rightarrow \infty $
. By claiming that, no matter what T is, no single state other than the ground state will occupy the energy spectrum with probability >
$1/ 2$
, Kieu is in fact claiming to have proved a theorem much stronger than the adiabatic theorem, which, all by itself, says nothing about nonadiabatic evolutions.
Intuitively, then, it would not be at all surprising if the HALF CLAIM turned out to be false. And unfortunately, as it turns out, the HALF CLAIM is false! Although it is true in the adiabatic limit (when
$T\rightarrow \infty $
) and, for a finite T, even in very special (and very simple) cases of two-dimensional and three-dimensional Hamiltonians (which happen to be those picked up by Kieu in his so-called numerical simulations that accompanied the HALF CLAIM), in general it appears that for a finite T, ‘decoy’ excited states will occupy the energy spectrum with much higher probability (sometimes even greater than 97%!) than the desired ground state of
$H_{P}$
in dimensions higher than three.Footnote 7 But if the HALF CLAIM is false, then the dream of the quantum adiabatic hypercomputer evaporates.
3.2. The Same Old Story (Told Quantum Mechanically)
In order to see what is left of the quantum adiabatic hypercomputer, stripped as it is from the HALF CLAIM, let us first remind ourselves what `undecidability' means in a typical classical setting.
Suppose that we have a black box implementing some function (unknown to us) with a global minimum; it takes natural numbers as input and produces natural numbers as output according to some rule hidden inside the box. Assuming that all we can do is to call this function (use the black box) as many times as we wish (plus some thinking), is it possible to find the function's global minimum? The answer is clearly no, but it is important to see exactly why.
In trying to locate a global minimum, we can proceed either systematically, by going over each consecutive natural number starting from 0, feeding it into the box, and recording the corresponding output, or in some more complicated deterministic or probabilistic manner. At each step, out of all arguments we have checked so far we keep those that minimize the function and discard the others; the former are the global minimum candidates. Note that if we proceed systematically, sooner or later, after a finite number of steps (number of the function's callings), we will always reach a function's global minimum (as we know a global minimum exists). This knowledge (of the fact that we will eventually stumble upon a global minimum), however, adds next to nothing to solving our task. The problem, obviously, is that, even if we have just reached an actual (nonzero) global minimum, there is no way for us to identify it as such. Given the resources we have, we can never be sure whether the function does not take a yet smaller value on the next step.
Thus the fact that we will always reach a global minimum in a finite number of steps is of no help to us. The problem is undecidable only because of our principal inability to identify a global minimum as such. Logically, the reason for this undecidability is that defining the property of being a global minimum involves quantification over an infinite domain: we say that the function f reaches its global minimum at a point
$n_{0}\in \mathstrut{\Bbb N} $
iff
$\forall n\in \mathstrut{\Bbb N} \thinspace{:}\thinspace f(n_{0}) \leq f(n) $
. Trying to identify a global minimum as such by brute-force search would require checking the inequality infinitely many times; thus undecidability.
Note, however, that one has to distinguish between actual infinity and potential infinity (i.e., unboundedness). In the context of measurement accuracy, for example, the former calls for a measurement of all the binary digits of a real number “at once,” as it were. The latter, by contrast, calls for an increasing unbounded degree of accuracy with different measurement instances. Kieu's algorithm involves both notions: First, it purports to perform a brute-force search on the entire infinite domain in a finite time.Footnote 8 Second, it involves a decision procedure that iterates unboundedly in order to decide whether the brute-force search was done correctly. For those who are inclined to reject the physical possibility of hypercomputers, for example, Davis (Reference Davis and Teuscher2003), the first feature is sufficient to rule out the algorithm. But since we are agnostic about the physical existence of hypercomputers, the issue at stake is, in our view, not actual infinity, but rather potential infinity, or unboundedness.
To our mind the reason behind the failure of Kieu's algorithm goes beyond its need for infinite precision.Footnote 9 Rather, it is the fact that this (admittedly finite) time is unbounded that kills the algorithm. In other words, the fact that the global minimum for the ‘computed’ function exists by construction (which ensures a nonzero energy gap and a finite evolution time) is of no consequence. And since Kieu, while guaranteeing that the brute-force search will eventually halt, fails to supply a criterion that would allow one to identify whether or not the algorithm has halted on the global minimum, the whole construction, despite his aspirations, lacks the ability to identify a global minimum as such. The problem is thus no different from any other corresponding classical case of undecidability, and quantum mechanics adds nothing to its solution.
The gist behind the adiabatic algorithm is that after a sufficiently long evolution time, one is certain to have retrieved the correct result of the decision problem just by performing a measurement on the ground state. However, when the evolution time is unknown, a nonzero energy reading on a measurement of a final state can be interpreted in two very different ways. On the one hand, it may be said to be an eigenvalue of an excited state. In such a case, clearly, the evolution was nonadiabatic; hence one must iterate the algorithm with another, longer, evolution time. On the other hand, it may be said to be an eigenvalue of the ground state. In such cases, clearly, the algorithm has performed correctly and one has a (negative) answer to the decision problem. But since one cannot check a negative answer to a classically undecidable problem, how can one tell, without knowing T in advance, that this negative ‘answer’ is indeed correct, that is, that no iterations are needed anymore? Without a criterion for distinguishing a ground state from all other excited states that is independent of the knowledge of the adiabatic evolution time T, one simply can't.
4. What Is `Quantum' in Quantum Computing?
In summary, Kieu's quantum adiabatic ‘hypercomputer’ fails for a simple reason: As one should intuitively expect from an algorithm that relies on the adiabatic theorem alone, and as shown by Smith (Reference Smith2005a, Reference Smith2005b), even if the adiabatic conditions are satisfied, then for a finite running time
$t< T$
, there is in general no guarantee that the final energy state will be the ground state. Consequently, there is no way to distinguish a ‘decoy’ excited state from a nonzero ground state; that is, there is no way to identify a global minimum as such. Repairing this failure requires knowing in advance the exact adiabatic running time T (or, equivalently, the precise behavior of the energy gap throughout the time evolution of the algorithm), which in Kieu's case is just another undecidable problem.
It is crucial to note, however, that since we have distinguished here between actual infinity and potential infinity, or unboundedness, our criticism is directed not at the possibility of physical hypercomputation per se, but rather at the claim that Kieu's quantum adiabatic algorithm can be harnessed to compute the (recursion-theoretic) noncomputable. Contrary to other cases of physical hypercomputation (e.g., Hogarth Reference Hogarth, Hull, Forbes and Burian1994), arriving at the solution here requires solving the same type of undecidable problem Kieu has originally set forth to solve with his algorithm.
We would like to conclude with a speculation about the so-called superiority of quantum computers over their classical counterparts. As mentioned in the introduction, quantum computing has become an industry and one of the most fascinating domains of quantum theory. Notwithstanding this excitement, and apart from the extremely difficult problem of practically realizing and implementing a large-scale quantum computer (Unruh Reference Unruh1995; Haroche and Raimond Reference Haroche and Raimond1996), a crucial theoretical question remains open, namely, what physical resources are responsible for the putative power of quantum computing? Put another way, what are the essential features of quantum mechanics that allow one to solve problems or simulate certain systems far more efficiently than on a classical computer? It is also remarkable that the relevance of features commonly thought essential to the superiority of quantum computers, for example, entanglement and interference (Jozsa Reference Jozsa and Hugget1997), has recently been questioned (Linden and Popescu Reference Linden and Popescu1999; Biham et al. Reference Biham2004). Moreover, even if these features do play an essential role in the putative quantum speedup, it is still unclear how they do so (Fortnow Reference Fortnow2003).Footnote 10
The question “what is `quantum' in quantum computing?”—theoretical as it may seem—has an enormous practical consequence. One of the embarrassments of quantum computing is the fact that, so far, only one algorithm has been discovered, namely Shor's quantum Fourier transform, for which a quantum computer is significantly faster than any known classical one.Footnote 11 It is almost certain that one of the reasons for this scarcity of quantum algorithms is related to the lack of our understanding of what makes a quantum computer quantum.
It is often said that ‘quantum parallelism’ is behind the potential speedup of quantum computing. But things are not that simple. The elusive character of the physical resource responsible for the quantum speedup can be nicely demonstrated with the following example. Consider a solution of a decision problem, say SATISFIABILITY, with a quantum algorithm based on a Fourier transform. What we are given here as input is a proposition in the propositional calculus, and we have to decide whether it has a satisfying truth assignment. As Pitowsky (Reference Pitowsky2002) shows, the quantum algorithm appears to solve this problem by testing all
$2^{n}$
assignments ‘at once’. Yet this quantum ‘miracle’ helps us very little since any measurement performed on the output state collapses it. If there is one possible truth assignment that solves this decision problem, the probability of retrieving it is
$2^{-n}$
, just as in the case of a probabilistic classical Turing machine, which guesses the solution and then checks it.
Pitowsky's conclusion is that in order to enhance computation with quantum mechanics, we must construct ‘clever’ superpositions the measurement of which increases the probability of successfully retrieving the result far more than that of a pure guess. Shor's algorithm is a (unique?) example of both a `construction' of such a ‘clever’ superposition and a `retrieval' of the solution that can be done in polynomial time.Footnote 12 The quantum adiabatic algorithm (Farhi et al. Reference Farhi2000) may give us similar results, contingent on the existence of an energy gap that decreases polynomially with the input.
Generalizing Pitowsky's example, we would like to conjecture that the putative power of quantum computers, at least in the quantum circuit model, lies in the quantum state rather than in its dynamical evolution.Footnote 13 Since most of the quantum circuit computation (at least up to the measurement itself) can be simply represented as a single unitary transformation from the input state to the output state, the quantum speedup is unlikely to result from Schrödinger's equation. Rather, the quantum speedup might result from a very specific quantum state (the ‘clever’ superposition, to use Pitowsky's term) that can store retrievable information in its phase relations much more efficiently than any classical state.
Another argument in favor of this conjecture (Unruh, personal communication) is that the Hilbert subspace ‘visited’ during a quantum computational process is, at any moment, a linear space spanned by all the vectors in the total Hilbert space that have been created by the computational process up to that moment. But this Hilbert subspace is thus a subspace spanned by a polynomial number of vectors and is thus at most a polynomial subspace of the total Hilbert space (i.e., a Hilbert space spanned by a number of basis vectors, which is polynomial in the number of qubits involved in the computation). A classical simulation of the quantum evolution on a Hilbert space with a polynomial number of dimensions, however, can be carried out prima facie in a polynomial number of classical computations. Were quantum dynamics important to the efficiency of quantum computing, the latter could be mimicked in a polynomial number of steps with a classical computer.
Of course, anybody familiar with the standard quantum computational model would reasonably interpret this statement as saying that polynomial time quantum computation is no more powerful than classical polynomial time computation. We do not claim this, but instead would like to stress the following point: One does not end a quantum computation with an arbitrary superposition, but aims for a very special, ‘clever’ state. Quantum computations cannot always be mimicked with a classical computer because the characterization of the computational subspace of certain quantum states is difficult, and it seems that certain special quantum states cannot be classically represented as vectors derivable via a quantum computation in an optimal basis, or at least that one cannot do so in such a way that would allow one to calculate the outcome of the final measurement made on those states.
If our conjecture holds, then in the quantum circuit model one should count the number of computational steps in the computation not by counting the number of global transformations of the state, but rather by counting the number of one-qubit or two-qubit local transformations that are required for the creation of the ‘clever’ quantum states that ensures computation speedup in Pitowsky's sense (i.e., states that would allow an efficient retrieval of the result in polynomial time). The trick would then be to perform these local one-qubit or two-qubit transformations in polynomial time and, more important, to find a physically realizable Hamiltonian that can simulate them. It is here where the physical power of quantum computing may be found.
There is, however, an important caveat. As our criticism of the quantum adiabatic hypercomputer shows, the construction of ‘clever’ quantum states for the purpose of solving an intractable computational task, or the retrieval of the solution that is ‘hidden’ in these quantum states, may sometimes require solving another task, equally intractable. Indeed, in the case of the adiabatic algorithm, Reichardt (Reference Reichardt2004) has shown that there are simple problems for which the algorithm will get stuck in a local minimum, in which there are exponentially many eigenvalues, all exponentially close to the ground state energy, and applying the adiabatic theorem, even for these simple problems, will take exponential time. Thus as much as the detection of a global minimum as such is an undecidable task, escaping local minima may be yet another NP-hard task, and we are back to square one.Footnote 14
Appendix: The Adiabatic Theorem
Consider a quantum system described in a Hilbert space
$\mathstrut{\cal H} $
by a smoothly time-dependent Hamiltonian,
$H=H(t) $
, for t ranging over
$[ t_{0},\,t_{1}] $
. Let
$U(t) $
be the time-evolution operator from time
$t_{0}$
to
$t\in [ t_{0},\,t_{1}] $
. We denote
$T=t_{1}-t_{0}$
. If the following conditions are satisfied:
1. For any
$t\in [ t_{0},\,t_{1}] $
,
$H(t) $
has a purely discrete spectrum with eigenvalues denoted
$E^{1}(t),\,E^{2}(t),\,\ldots,\,E^{i}(t),\,\ldots $
. We denote
$P^{1}(t),\,P^{2}(t),\,\ldots,\,P^{i}(t),\,\ldots $
, respectively, the projection operators on the eigenspaces.2. The eigenvalues and the projectors are assumed to be continuous functions of t, and there is no level crossing throughout the transition; that is, the instantaneous eigenvalues remain distinct:
3.
$(d/ dt) P^{i}$
,
$(d^{2}/ dt^{2}) P^{i}$
exist and are bounded and are piecewise continuous in the whole interval
$[ t_{0},\,t_{1}] $
.
Then if the system is initially in the energy state
that is,
then
That is, for
$T\rightarrow \infty $
, if the system starts at
$t_{0}$
in an eigenstate corresponding to the energy
$E^{i}(t_{0}) $
, it will evolve (up to a phase) to an eigenstate corresponding to
$E^{i}(t) $
at t.
In the special case in which
$E^{i}(t_{0}) $
is the ground state, the adiabatic theorem ensures that in the limit
$T\rightarrow \infty $
the system will remain in the ground state through its time evolution. Although in practice T is always finite, the more it satisfies a minimum ‘energy gap’ condition, the less the system will deviate from the ground state. The energy gap condition states that there must exist a nonzero gap, g, between the ground state and the first excited state in any given time.
How does one construct a quantum algorithm on the basis of this theorem? A quantum system evolves according to the Schrödinger equation
and the adiabatic theorem tells us how to follow this evolution in the case in which
$H(t) $
is slowly varying. Consider a smooth one-parameter family of Hamiltonians
$\tilde{H}(s) $
,
$0\leq s\leq 1$
, and take
so that T controls the rate at which
$H(t) $
varies. Define the instantaneous eigenstates and eigenvalues of
$\tilde{H}(s) $
by
with
where N is the dimension of the Hilbert space. Suppose that
$\vert \psi (0) \rangle $
is the ground state of
$\tilde{H}(0) $
, that is,
According to the adiabatic theorem, if the gap between the two lowest levels,
$E_{1}(s) -E_{0}(s) $
, is strictly greater than zero for all
$0\leq s\leq 1$
, then
This means that the existence of a nonzero gap guarantees that
$\vert \psi (t) \rangle $
obeying (A5) remains very close to the instantaneous ground state of
$H(t) $
of the form (A6) for all t from 0 to T if T is big enough. Let us define the minimum gap by
A closer look at the adiabatic theorem tells us that taking
where
can make
arbitrarily close to 1. For most of the problems that so far have been studied with this algorithm,
$\mathstrut{\cal E} $
is of order of a typical eigenvalue of H and is not too big, so the size of T is governed by
$g^{-2}_{\mathrm{min}\,}$
alone. What governs the efficiency of the quantum adiabatic algorithm is thus the rate at which the energy gap between the ground state and the next excited state decreases with the increasing dimension of the Hamiltonian, that is, with the size of the input.
