Quantum Hyper Computation - Hype or Computation

Quantum Hypercomputation--Hype or
Computation?
Amit Hagar, Alex Korolev
February 19, 2007
Abstract
A recent attempt to compute a (recursion-theoretic) non-computable func-
tion using the quantum adiabatic algorithm is criticized and found wanting.
Quantum algorithms may outperform classical algorithms in some cases, but
so far they retain the classical (recursion-theoretic) notion of computability.
A speculation is then offered as to where the putative power of quantum
computers may come from.
HPS Department, Indiana University, Bloomington, IN, 47405. hagara@indiana.edu
Philosophy Department, University of BC, Vancouver, BC. korolev@interchange.ubc.ca
1

---

1
Introduction
Combining physics, mathematics and computer science, quantum computing has
developed in the past two decades from a visionary idea (Feynman 1982) to one of
the most exciting areas of quantum mechanics (Nielsen and Chuang 2000). The
recent excitement in this lively and fashionable domain of research was triggered
by Peter Shor (1994) 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 the-
oretical study of quantum systems serving as computational devices has achieved
tremendous progress. According to one authority in the field (Aharonov 1998,
Abstract),
we now have strong theoretical evidence that quantum computers, if
built, might be used as powerful computational tool, capable of per-
forming tasks which seem intractable for classical computers.
The common view is that quantum algorithms such as Shor's may help to re-
describe the complexity space of computational problems, but recently it has been
suggested that they may even re-write the abstract notion of computability itself
by "computing the (recursion-theoretic) non computable". Here we address one
such suggestion that rests on the quantum adiabatic algorithm, pointing out its
failure to perform the purported hypercomputation,1 and use this negative result
to speculate further on the so-called `superiority' of quantum computers.
That recursive may not be a natural physical property and that physical pro-
cesses may not necessarily preserve it has been argued in the past (see, e.g., Pour-
el and Richards 1981, Moore 1990, Pitowsky 1990, Hogarth 1994), but this note
intends to add nothing new to the general debate on the physical possibility of hy-
percomputers (Copeland 2002, Shagrir and Pitowsky 2003, Davis 2003). Agnos-
tic as we are with respect to the question whether the club of physical hypercom-
puters is empty or not, we direct our criticism here at the claim that the quantum
adiabatic algorithm is another member of this distinguished, hypothetical or not,
club.
The paper is structured as follows. In section (2) we describe the quantum
adiabatic "hypercomputer". In sections (3) we flesh out the mistake upon which
1The term Hypercomputer was coined by Copeland (1998) to denote a machine that can com-
pute non-recursive functions by performing infinite number computational steps in a finite time.
2

---

the proposed hypercomputer rests. Section (4) concludes with a speculation on
where might the putative power of quantum computers 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 4 years, in 10 papers posted to the quant-ph section of the Los
Alamos preprints archive (some of which were also published in printed journals
such as Kieu 2002; 2003; 2004; 2005) 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 (See, e.g., Messiah
1961, pp. 739-746), was recently harnessed by a group of physicists from MIT
(Farhi et al. 2000) to develop a novel quantum algorithm. Their aim was to solve
in polynomial time certain decision problems that are believed to be NP-hard, and
in so doing to vindicate the putative exponential superiority of quantum algorithms
over their classical counterparts.2
The crux of the quantum adiabatic algorithm lies in the possibility of encod-
ing a specific instance of a given decision problem in a certain Hamiltonian.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 which is easy to
construct, and slowly evolves the system in time towards the interpolated and de-
sired Hamiltonian. According to the quantum adiabatic theorem and given certain
2Irrespective of the criticism presented here, one should bear in mind that it is still an open
question whether the proposed quantum adiabatic algorithm does indeed yield an exponential
speed-up. See. e.g., Van Dam, Mosca and Vazirani (2002) and Reichardt (2004). We return
to this point in section 4.
3This can be done by capitalizing on the well-known fact that any decision problem can be
derived from an optimiztion problem by incorporating into it a numerical bound as an additional
parameter.
3

---

conditions (See Appendix), the result of such 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 HP which is diagonal in the computational basis and is
a member of a one-parameter family of Hamiltonians
H(s) varying smoothly for
0 s 1, and then sets H(t) =
H(t/T ) so that T (the run-time of the algorithm)
governs how slowly H varies. One now defines the instantaneous eigenstates and
eigenvalues of
H(s) by
H(s)|j; s = Ej(s)|j; s ,
(1)
with
E0(s) E1(s) * * * EN-1(s) ,
(2)
where N is the dimension of the Hilbert space. Suppose |(0) is the ground state
of
H(0), that is,
|(0) = |j = 0; s = 0 .
(3)
According to the adiabatic theorem, if the gap gmin between the two lowest levels,
E1(s) - E0(s), is strictly greater than zero for all 0 s 1, then
lim
j = 0; s = 1|(T )
= 1 .
(4)
T
where |(t) is the state at time t.
One next chooses an Hamiltonian HI which is easy to construct and which
does not commute with HP (otherwise one would have to encode the solution
already in the initial Hamiltonian!) and defines the interpolating Hamiltonian to
be

H(s) = (1 - s)HI + sHP ,
(5)
so that
t
t
H(t) =
1 -
HI +
HP .
(6)
T
T
Under these conditions, and in the adiabatic limit, i.e., for T long enough, the
evolution from t = 0 to t = T (starting in the ground state of HI) will lead to the
ground state of HP 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
4

---

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 as 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 Hamil-
tonian is zero, and has no integer solution otherwise. Next, Kieu claimed to have
proven an ingenious probabilistic criterion that allows one, by measuring HP, to
identify whether the quantum system has indeed reached its ground state, no mat-
ter what T is.4 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 HP) is achieved.
Let us consider a particular example, say, the equation
D = (x + 1)3 + (y + 1)3 - (z + 1)3 + cxyz = 0,
c Z ,
(7)
with unknowns x, y, and z. To find out whether this equation has any non-negative
integer solution by quantum algorithms, it requires the realisation of a Fock space.
Upon this Hilbert space, we construct the Hamiltonian corresponding to (7)
2
HP =
(a a
a
a
a
a
a
,
x x + 1)3 + (a
y y + 1)3 - (a
z z + 1)3 + c(a
x x)(a
y y )(a
z z )
which has a spectrum bounded from below--semidefinite, in fact.5 Note that
the operators Nj = aa
j
j have only non-negative integer eigenvalues nj , and that
[Nj, HP] = 0 = [Ni, Nj] so these observables are simultaneously measurable. For
some (nx, ny, nz) the ground state |g of the Hamiltonian so constructed has the
properties
Nj|g
= nj|g ,
2
HP|g
=
(nx + 1)3 + (ny + 1)3 - (nz + 1)3 + cnxnynz
|g Eg|g ,
4According to Kieu (e.g., in his 2005, 178), this criterion amounts to excluding any state other
than the ground state from occupying the energy spectrum of HP with probability > 1/2 for any
T > 0. It is noteworthy that in all of his papers Kieu offered no analytic proof for this criterion,
only a simple example in which such criterion is indeed satisfied.
5The creation operators ax, ay and az are similar to those of the 3D simple harmonic oscillator.
[aj, a] = 1
for j = x, y, z,
(8)
j
[ak, aj] = [ak, a] = 0
for j = k .
j
5

---

Thus, after enough iterations, a projective measurement of the energy Eg of the
ground state |g will yield the answer for the decision problem: the Diophantine
equation has at least one integer solution if and only if Eg = 0, and has no solu-
tions otherwise. (If c = 0 in our example, we know that Eg > 0 from Fermat's
last theorem.)
If there is one unique solution then the projective measurements of the ob-
servables corresponding to the operators Nj will reveal the values of various un-
knowns. If there are many solutions, finitely or infinitely as in the case of the
Pythagoras theorem, x2 + y2 - z2 = 0, the ground state |g will be a linear super-
position of states of the form |nx |ny |nz , where (nx, ny, nz) 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 Nj of the ground state would always
yield some values (nx, ny, nz) and a straightforward substitution would confirm
if the equation has a solution or not. Thus the measurement on 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
HP), 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 algo-
rithm purports to find a global energy minimum, "all" one needs to do in order
to compute the (recursion-theoretic) non-computable 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) non-computable function.
6

---

3.1
Mind the Gap
A crucial ingredient in the adiabatic algorithm is the energy gap between the
ground state E0 and the next excited state E1:
gmin = min (E1(t) - E0(t)).
(9)
0tT
This gap controls the evolution time of the algorithm, in the exact following way
(see Appendix):
T
1/g2
.
(10)
min
The problem is that in the absence of a detailed spectral analysis, in general no-
body 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 HP, 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 2005.
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 that 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 T (k) steps. But of course we don't really know, because T (k) is not
computable, growing faster than any recursive function.
What Kieu is doing is to define an adiabatic process whose time is of that order
(and whose gap g is therefore incomputably small). The fact that there is some
T which will do the job is not a big deal (nor is, therefore, the fact that we can
use finite but unbounded dimensional 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 mea-
sure 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
7

---

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 us 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 HP. His idea seems to be the following: In general, when one
performs such an adiabatic cooling, one doesn't meet this probabilistic criterion
(that ensures that it is only the ground state which will appear with probability >
1/2 upon measuring HP) 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 achieve-
ment. 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, i.e., when T . By claiming that, no matter what T is, no sin-
gle state other than the ground state will occupy the energy spectrum with prob-
ability > 1/2 , Kieu is in fact claiming to have proven a theorem much stronger
than the adiabatic theorem, which, all by itself, says nothing about non-adiabatic
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 ) and, for a finite T , even
in very special (and very simple) cases of two- and three-dimensional Hamilto-
nians (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
8

---

HP in dimensions higher than three.6 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 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 determin-
istic 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 for-
mer are the global minimum candidates. Note that, if we proceed systematically,
sooner or later, after a finite number of steps (number of 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, obvi-
ously, is that, even if we have just reached an actual (non-zero) 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 due to our prin-
cipal inability to identify a global minimum as such. Logically, the reason for
this undecidability is that defining the property of being a global minimum in-
volves quantification over an infinite domain: we say that the function f reaches
its global minimum at a point n0 N iff n N : f (n0) f (n). Trying to
6Smith (2005) constructs 3 counterexamples to the HALF CLAIM, thus proving its falsity. We
thank Andrew Hodges for pointing out Smith's result to us when writing the final version of this
paper.
9

---

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 po-
tential 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 un-
bounded degree of accuracy with different measurement instances. Kieu's algo-
rithm involves both notions: First, it purports to perform a brute-force search on
the entire infinite domain in a finite time.7 Second, it involves a decision proce-
dure that iterates unboundedly in order to decide whether the brute-force search
was done correctly. For those who incline to reject the physical possibility of
hypercomputers, e.g., Davis (2003), the first feature is sufficient to rule out the
algorithm. But since we have declared agnostics with respect to the question of
the physical existence of hypercomputers, the issue at stake is, in our view, not
actual infinity, but rather potential infinity, or unboundedness.
Put differently, to our mind the reason behind the failure of Kieu's algorithm
lies not just in its requirement for infinite precision.8 Moreover, the fact that the
global minimum for the `computed' function exists by construction (which en-
sures a non-zero energy gap and hence a finite evolution time) is of no conse-
quence. Rather, it is the fact that this finite time is unbounded which kills the
algorithm. 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 than any other corresponding classical case of
undecidability, and quantum mechanics adds nothing to its solution.
Put another way, the gist behind the adiabatic algorithm is that after a suf-
ficiently 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 non-zero energy reading upon a
measurement of a final state can be interpreted in two very different ways. On one
hand, it may be said to be an eigenvalue of an excited state. In such case, clearly,
7As an anonymous referee has correctly remarked, if the evolution of the algorithm took place
in a Hilbert space with a fixed finite number of dimensions, then gmin would in principle be
computed to any desired accuracy.
8For a criticism based on this objection see Hodges (2005). Although we agree with Hodges
that Kieu's hypercomputer may require infinite precision to be actually manufactured, we prefer
to focus here on what is or is not possible in theory.
10

---