a

r
X
i
v
:
q
u
a
n
t
-
p
h
/
0
1
1
0
1
3
6
v
3


8

O
c
t

2
0
0
3
Quantum Algorithm for Hilberts Tenth Problem
Tien D Kieu

Centre for Atom Optics and Ultrafast Spectroscopy,
Swinburne University of Technology, Hawthorn 3122, Australia
February 1, 2008
Abstract
We explore in the framework of Quantum Computation the notion of Computabil-
ity, which holds a central position in Mathematics and Theoretical Computer Sci-
ence. A quantum algorithm for Hilberts tenth problem, which is equivalent to the
Turing halting problem and is known to be mathematically noncomputable, is pro-
posed where quantum continuous variables and quantum adiabatic evolution are
employed. If this algorithm could be physically implemented, as much as it is valid
in principlethat is, if certain hamiltonian and its ground state can be physically
constructed according to the proposalquantum computability would surpass clas-
sical computability as delimited by the Church-Turing thesis. It is thus argued that
computability, and with it the limits of Mathematics, ought to be determined not
solely by Mathematics itself but also by Physical Principles.
1 Introduction
Computation based on the principles of Quantum Mechanics [1] has been shown to oer
better performances over classical computation, ranging from the square-root improvement
in an unstructured search [2] to the exponential gain in the factorisation of integers [3].
However superior in reducing the complexity of hard computation, these quantum algo-
rithms and all the others discovered so far are only applicable to the classically computable
functions. That leaves untouched the class of classically noncomputable functions, such as
the halting problem for Turing machines [4]. It is in fact widely believed that quantum
computation cannot oer anything new about computability [5]. Contrary to this, we pro-
pose that quantum computation may be able to compute the noncomputables, provided
certain hamiltonian and its ground state can be physically constructed. We propose a
quantum algorithm for the classically noncomputable Hilberts tenth problem [6] which

kieu@swin.edu.au
1
ultimately links to the halting problem for Turing machines in the computation of partial
recursive functions.
The practical details of implementation the quantum algorithm for this class of problems
are not considered in this conceptual study, and will be investigated elsewhere.
2 Hilberts tenth problem
At the turn of the last century, David Hilbert listed 23 important problems, among which
the problem number ten could be rephrased as:
Given any polynomial equation with any number of unknowns and with in-
teger coecients: To devise a universal process according to which it can be
determined by a nite number of operations whether the equation has integer
solutions.
This decision problem for such polynomial equations, which are also known as Diophan-
tine equations, has eventually been shown in 1970 by Matiyasevich to be undecidable [6, 7]
in the Turing sense. It is consequently noncomputable/undecidable in the most general
sense if one accepts, as almost everyone does, the Church-Turing thesis of computability.
Since exponential Diophantine, with the unknowns in the exponents as in the example of
the Fermats last theorem, can be shown to be Diophantine with supplementary equations,
the study of Diophantine equations essentially covers the class of partial recursive func-
tions, which is at the foundations of classical algorithms. The undecidability result is thus
singularly important: Hilberts tenth problem could be solved if and only if the Turing
halting problem could be.
3 Turing halting problem
The halting problem for Turing machines is also a manifestation of undecidability: a Turing
computation is equivalent to the computation of a partial recursive function, which is only
dened for a subset of the integers; as this domain is classically undecidable, one cannot
always tell in advance whether the Turing machine will halt (that is, whether the input
is in the domain of the partial recursive function) or not (when the input is not in the
domain).
A version of the proof of the unsolvability of the halting problem based on the Cantor
diagonal argument goes as follows. The proof is by contradiction with the assumption of
the existence of a computable halting function h(p, i) which has two integer arguments - p
is the Godel encoded integer number for the algorithm and i is its (encoded) integer input:
h(p, i) =
_
0 if p halts on input i
1 if p does not
(1)
2
One can then construct a program r(n) having one integer argument n in such a way that
it calls the function h(n, n) and
_
r(n) halts if h(n, n) = 1
r(n) loops innitely (i.e., never stops) otherwise.
The application of the halting function h on the program r and input n results in
h(r, n) =
_
0 if h(n, n) = 1
1 if h(n, n) = 0
(2)
A contradiction is clearly manifest once we put n = r in the last equation above.
The construction of such program r is transparently possible, unless the existence of a
computable h is wrongly assumed. Thus the contradiction discounts the assumption that
there is a classically algorithmic way to determine whether any arbitrarily given program
with arbitrary input will halt or not.
This contradiction argument might be side stepped if we distinguish and separate the
two classes of quantum and classical algorithms. A quantum function qh(p, i), similar to
eq. (1), can conceivably exist to determine whether any classical program p will halt on
any classical input i or not. The contradiction in eq. (2) would be avoided if the quantum
halting qh cannot take as argument the modied program r, which is now of quantum
character because it now has quantum qh as a subroutine. This will be the case if qh can
only accept integer while quantum algorithms, with proper denitions, cannot in general
be themselves encoded as integers. It is clear even in the case of a single qubit that the
state [0) +[1) cannot be encoded as integers for all and - simply because of dierent
cardinalities. In fact, the no-cloning theorem [8] of quantum mechanics does restrict the
type of operations available to quantum algorithms.
In essence, the way we will break the self-referential reasoning here by the dierentiation
between quantum and classical algorithms is similar to the way John von Neumann and
Bertrand Russell resolved the set theory paradox (to do with The set of all sets which
are not members of themselves) by the introduction of classes as distinct from sets. (For
other lines of arguments, see [9].)
4 An observation
It suces to consider nonnegative solutions, if any, of a Diophantine equation. Let us
consider the example
(x + 1)
3
+ (y + 1)
3
(z + 1)
3
+ cxyz = 0, c Z, (3)
with unknowns x, y, and z. To nd out whether this equation has any nonnegative integer
solution by quantum algorithms, it requires the realisation of a Fock space built out of the
3
vacuum [0
a
) by repeating applications of the creation operators a

x
, a

y
and a

z
, similarly
to that of the 3-D simple harmonic oscillators.
[a
j
, a

j
] = 1 for j = x, y, z, (4)
[a
k
, a
j
] = [a
k
, a

j
] = 0 for j ,= k.
Upon this Hilbert space, we construct the hamiltonian corresponding to (3)
H
P
=
_
(a

x
a
x
+ 1)
3
+ (a

y
a
y
+ 1)
3
(a

z
a
z
+ 1)
3
+ c(a

x
a
x
)(a

y
a
y
)(a

z
a
z
)
_
2
,
which has a spectrum bounded from below semidenite, in fact.
Note that the operators N
j
= a

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 compatible they are simultaneously
measurable. The ground state [g) of the hamiltonian so constructed has the properties
N
j
[g) = n
j
[g),
H
P
[g) =
_
(n
x
+ 1)
3
+ (n
y
+ 1)
3
(n
z
+ 1)
3
+ cn
x
n
y
n
z
_
2
[g) E
g
[g),
for some (n
x
, n
y
, n
z
).
Thus a projective measurement of the energy E
g
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 E
g
= 0, and has not otherwise. (If c = 0 in our example, we know
that E
g
> 0 from Fermats 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, nitely or innitely as in the case of x
2
+y
2
z
2
= 0, the ground state [g)
will be a linear superposition of states of the form [n
x
) [n
y
) [n
z
), where (n
x
, n
y
, n
z
) are
the solutions. In such situation, the measurement may not yield all the solutions. However,
nding all the solutions is not the aim of a decision procedure for this kind of problem.
Notwithstanding this, measurements of N
j
of the ground state would always yield some
values (n
x
, n
y
, n
z
) and a straightforward substitution would conrm if the equation has a
solution or not. Thus the measurement on the ground state either of the energy, provided
the zero point can be calibrated, or of the number operators will be sucient to give the
result for the decision problem.
The quantum algorithm with the ground-state oracle is thus clear:
1. Given a Diophantine equation with K unknowns xs
D(x
1
, , x
K
) = 0, (5)
we need to simulate on some appropriate Fock space the quantum hamiltonian
H
P
=
_
D(a

1
a
1
, , a

K
a
K
)
_
2
. (6)
4
2. If the ground state could be obtained with high probability, measurements of appro-
priate observables would provide the answer for our decision problem.
The key ingredients are the availability of a countably innite number of Fock states,
the ability to construct/simulate a suitable hamiltonian and to obtain/identify its ground
state via quantum measurements. As a counterpart of the semi-innite tape of a Turing
machine, the Fock space is employed here instead of the qubits of the more well-known
model of quantum computation. Its advantage over the innitely many qubits which would
otherwise be required is obvious.
5 Some preliminary comments
We do not look for the zeroes of the polynomial, D(x
1
, , x
K
), which may not exist, but
instead search for the absolute minimum of its square which exists,
0 min (D(x
1
, , x
K
))
2
(D(0, , 0))
2
,
and is nite because lim
x
(D(x
1
, , x
K
))
2
diverges.
While it is equally hard to nd either the zeroes or the absolute minimum in classical
computation, we have converted the problem to the realisation of the ground state of
a quantum hamiltonian and there is no known quantum principle against such act. In
fact, there is no known physical principles against it. Let us consider the three laws
of thermodynamics concerning energy conservation, entropy of closed systems and the
unattainability of absolute zero temperature. The energy involved in our algorithm is nite,
being the ground state energy of some hamiltonian. The entropy increase which ultimately
connects to decoherence eects is a technical problem for all quantum computation in
general, and we will discuss this further below. As we will never obtain the absolute
zero temperature, we only need to satisfy ourselves that the required ground state can be
achieved with a more-than-even chance. Then there is a probability boosting technique,
see later, to bring that chance to as closed to unity as one pleases.
It may appear that even the quantum process can only explore a nite domain in a
nite time and is thus no better than a classical machine in terms of computability. But
there is a crucial dierence.
In a classical search even if the global minimum is come across, it cannot generally be
proved that it is the global minimum (unless it is a zero of the Diophantine equation).
Armed only with mathematical logic, we would still have to compare it with all other
numbers from the innite domain yet to come, but we obviously can never complete this
comparison in nite time thus, mathematical noncomputability.
In the quantum case, the global minimum is encoded in the ground state. Then, by
energy tagging, the global minimum can be found in nite time and conrmed, if it is the
ground state that is obtained at the end of the computation. And the ground state may
be identied and/or veried by physical principles. These principles are over and above
the mathematics which govern the logic of a classical machine and help dierentiating
5
the quantum from the classical. Quantum mechanics could explore an innite domain,
but only in the sense that it can select, among an innite number of states, one single
state (or a subspace in case of degeneracy) to be identied as the ground state of some
given hamiltonian (which is bounded from below). This sorting can be done because
of energetic reason, which is a physical principle and is not available to mathematical
computability.
On the other hand, our proposal is apparently in contrast to the claim in [5] that quan-
tum Turing machines compute exactly the same class of functions as do Turing machines,
albeit perhaps more eciently. We could only oer here some speculations about this
apparent discrepancy. The quantum Turing machine approach is a direct generalisation of
that of the classical Turing machines but with qubits and some universal set of one-qubit
and two-qubit unitary gates to build up, step by step, dimensionally larger, but still di-
mensionally nite unitary operations. This universal set is chosen on its ability to evaluate
any desirable classical logic function. Our approach, on the other hand, is from the start
based on innite-dimension hamiltonians acting on some Fock space and also based on the
special properties and unique status of their ground states. The unitary operations are
then followed as the Schrodinger time evolutions. Even at the hamiltonian level higher
orders of the operators a and a

, i.e. not just two-body but many-body interactions in a

sense, are already present. This proliferation, which is even more pronounced at the level
of the time-evolution operators, together with the innite dimensionality and the unique
energetic status of the vacuum could be the reasons behind the ability to compute, in a
nite number of steps, what the dimensionally nite unitary operators of the standard
quantum Turing computation cannot do in a nite number of steps. Note that it was the
general hamiltonian computation that was discussed by Benio and Feynman [10, 11] in
the conception days of quantum computation.
Indeed, Nielsen [12] has also found no logical contradiction in applying the most general
quantum mechanical principles to the computation of the classical noncomputable, unless
certain Hermitean operators cannot somehow be realised as observables or certain unitary
processes cannot somehow be admitted as quantum dynamics. And up to now we do
not have any evidence nor any principles that prohibit these kinds of observables and
dynamics. (Ozawa [13] has produced some counter arguments but we think they are not
quite applicable here. See [9].)
Our general algorithm above could be realised by, but in no way restricted to, the
following methods to simulate the required hamiltonian and to obtain the ground state
adiabatically.
6 Simulating the hamiltonians
One way to construct any suitable hamiltonian so desired is through the technique of
ref. [14]. We consider the hermitean operators, where j is the index of the unknowns of
6
the Diophantine equation,
X
j
=
1

2
(a
j
+ a

j
),
P
j
=
i

2
(a
j
a

j
), (7)
[P
j
, X
k
] = i
jk
.
Together with the availability of the fundamental hamiltonians
X
j
, P
j
, (X
2
j
+ P
2
j
), (X
k
P
j
+ P
j
X
k
), and (X
2
j
+ P
2
j
)
2
(8)
one could construct the unitary time evolutions corresponding to hamiltonians of arbitrary
hermitean polynomials in X
j
, P
j
, and hence in a

j
a
j
, to an arbitrary degree of accuracy.
These fundamental hamiltonians correspond to translations, phase shifts, squeezers, beam
splitters and Kerr nonlinearity.
With the polynomial hamiltonian constructed, we need to obtain its ground state. Any
approach that allows us to access the ground state will suce. One way is perhaps to
use that of quantum annealing or cooling [15]. Another way is to employ the quantum
computation method of adiabatic evolution [16].
7 Adiabatic quantum evolution
In the adiabatic approach, one starts with a hamiltonian H
I
whose ground state [g
I
) is
readily achievable. Then one forms the slowly varying hamiltonian H(s), s =
t
T
, which
interpolates between H
I
and H
P
in the time interval t [0, T]
H(s) = (1 s) H
I
+ sH
P
. (9)
Note that we can replace this linear interpolation by some non-linear one provided the
conditions of the adiabatic theorem are observed. According to this theorem, the initial
ground state will evolve into our desirable ground state [g) up to a phase:
lim
T
T exp
_
iT
_
1
0
H()d
_
[g
I
) = e
i
[g). (10)
For the hamiltonian (9), an estimate of the time T after which the system remains with
high probability in the ground state is
T
| H
I
H
P
|
g
2
, (11)
with
| H
I
H
P
| max
0tT
[e(t)[(H
I
H
P
)[g(t))[ , (12)
7
and
g min
0tT
(E
e
(t) E
g
(t)) , (13)
where [g(t)) and [e(t)) are respectively the instantaneous ground state and the rst excited
state of (9) with instantaneous eigenvalues E
g
(t), E
e
(t).
The time-ordering operator on the left hand side of (10) can be approximated as
expiTH(
N
) expiTH(
1
)
for [16]
N = 1,
| H
I
H
P
| 1. (14)
Note that we have employed here the norm | . | as dened in (12) for the various
hamiltonians which are unbounded from above. This norm is the relevant measure for
the problem is only concerned with the lowest states of the interpolating hamiltonian (9).
In each interval , the unitary operators expiH(
k
)T, for k = 1, , N, can be
expressed through the subdivision of T into m subintervals of suciently small size s
satisfying ms = T,
expiH(
k
)T = (expiH(
k
)s)
m
.
Each of the m factors on the right hand side of the last expression can be now simulated
through the approach of [14], where it was shown that the number of steps M grows as a
small polynomial in the order of the polynomial in the hamiltonian H(
k
) to be simulated,
the accuracy to be enacted, and the time interval T over which it is to be applied.
In this way, the requirements of the adiabatic conditions on the one hand and of, on the
other hand, the simulations of the hamiltonians in the time interval T can be satised.
8 An adiabatic algorithm
In order to solve Hilberts tenth problem we need on the one hand such time-dependent
physical (adiabatic) processes. On the other hand, the theory of Quantum Mechanics
can be used to identify the ground state through the usual statistical predictions from
the Schrodinger equation with a nitely truncated number of energy states of the time-
dependent Hamiltonian H(t/T). This way, we can overcome the problem of which states
are to be included in the truncated basis for a numerical study of Quantum Mechanics.
This also reconciles with the Cantor diagonal arguments which state that the problem
could not be solved entirely in the framework of classical computation.
Below is an algorithm [17] based on this philosophy of exploiting the interplay between
the presumably innite physical world and the theory of Quantum Mechanics calculated
8
in a nite manner on Turing machines. The algorithm presented may not be the most
ecient; there could be many other variations making better use of the same philosophy.
It is in general easier to implement some Hamiltonian than to obtain its ground state.
We thus should start the computation in yet a dierent and readily obtainable initial ground
state, [g
I
), of some initial Hamiltonian, H
I
, then deform this Hamiltonian in a time T into
the Hamiltonian whose ground state is the desired one, through a time-dependent process
represented by the interpolating Hamiltonian H(t/T).
In this approach, inspired by the quantum adiabatic approach, one starts, for example,
with a Hamiltonian H
I
,
H
I
=
K

i=1
(a

i
)(a
i

i
), (15)
which admits the readily achievable coherent state [g
I
) = [
1

K
) as the ground state.
Then, one forms the time-dependent Hamiltonian H(t/T) in (9), which interpolates in the
time interval t [0, T] between the initial H
I
and H
P
.
Step 0: Choose an evolution time T, a probability p which can be made arbitrarily
closed to unity, and an accuracy 0 < < 1 which can be made arbitrarily small.
Step 1 (on the physical apparatus): Perform the physical quantum time-dependent
process which is governed by the time-dependent Hamiltonian H(t/T) and terminates
after a time T. Then, by projective measurement (either of the observable H
p
or
the number operators N
1
, . . . , N
K
) we obtain some state of the form [ n
i
),
i = 1, , K.
Step 2 (on the physical apparatus): Repeat the physical process in Step 1 a number of
times, L(, p), to build up a histogram of measurement frequencies (for all the states
obtained by measurement) until we get a probability distribution P(T; ) at the time
T with an accuracy for all the measured states. The convergence of this repetition
process is ensured by the Weak Law of Large Numbers in probability theory [18].
(An overestimate of the number of repetitions is L 1/(
2
(1 p)).) Note the lowest
energy state so obtained, [n
c
), as the candidate ground state.
Step 3 (on the classical computer): Choose a truncated basis of M vectors made up of
[
1

K
) and its excited states by successive applications of the displaced creation
operators b

i
(a

i
) on the initial state.
Step 4 (on the classical computer): Solve the Schrodinger equation in this basis for
(T), with the initial state (0) = [
1

K
), to derive a probability distribution
P
est
(T; M) (through [(T)[ n
i
)[
2
) which is similar to that of Step 2 and which
depends on the total number M of vectors in the truncated basis.
Step 5 (on the classical computer): If the two probability distributions are not uni-
formly within the desired accuracy, that is, [P
est
(T; M) P(T; )[ > , we enlarge
the truncated basis by increasing the size M and go back to the Step 4 above.
9
Step 6 (on the classical computer): If the two probability distributions are uniformly
within the desired accuracy, that is, [P
est
(T; M)P(T; )[ < , then use this truncated
basis to diagonalise H
P
to yield, within an accuracy which can be determined from
, the approximated ground state [g

) and its energy E

g
.
Step 7 (on the classical computer): We can now estimate in this truncated basis the
gap between the ground state and the rst excited state. From this gap, we can make
use of the quantum adiabatic theorem and choose a time T such that the system has
a high probability to be in the ground state

[g

[(T))[
2
1

< .
We then go back to Step 1 with this choice of T, which is to amplify and thus conrm
the candidate ground state as the real ground state.
Our point is on computability and not on computational complexity, which depends on
individual polynomials. Computability is based on the arguments that the adiabatic time
T is nite [19, 20] (for a high probability of achieving the ground state) and that the
ground state can be veried by employing the theory of Quantum Mechanics. As long as
the energy gap is nite so is the computational time. In contrast, the most general classical
algorithm for Hilberts tenth problem (by systematic substituting in integers of larger and
larger magnitudes) cannot solve it in principle even allowing for exponentially grown, but
nite, amount of time unless innite amount of time were available, which it is not.
Given a Diophantine equation, the substitution in integers of larger and larger magni-
tudes is not satisfactory as we do not know when the substitution should be terminated.
Likewise, if we want to numerically simulate the quantum algorithm proposed, we would
have to use a nitely truncated having M vectors. But we face the same problem of not
knowing which M to choose in general. That is why the problem is noncomputable on
classical computers.
Even we can estimate T, as in the appendix, for some starting point of the adiabatic
computation as we might not be able in general to exactly know T a priori. Were the re-
quired adiabatic time T somehow known exactly within classical computation and without
the help of quantum computation then the problem might be solved classically. But as
Hilberts tenth problem cannot be solved by classical computation, we will have to resort to
quantum computation without a priori knowing exactly the time T, except the knowledge
that it is nite. Constructive logicians [21] allow for this algorithmic situation under the
so-called Markovs Principle.
9 Discussion of the algorithm
The quantum algorithm above can be proved to terminate (even though it could be after
a very long time) and give us the decision result for Hilberts tenth problem.
The real spectrum of H
p
is of integer values (in suitable units), and that is what we
also get from measurement. But the spectrum calculated from a nitely truncated basis
10
is not of integer values and will uctuate with uctuation size depends on the size of the
truncated basis employed. The accuracy size of the measured probability distribution
is chosen such that the o-set of the ground state energy should allow us to conclude
whether the ground state energy E
g
is zero or not. ( is in general a function of and T.)
E
g
= g

[H
P
[g

),
= E
c
+r[H
P
[r) + 2Rer[H
P
[n
c
),
= E
c
+r[H
P
[r) + 2E
c
(Rer[n
c
)),
E
c
+ (), (16)
where [r) [g

) [n
c
) and H
P
[n
c
) = E
c
[n
c
).
The termination of our algorithm is obtained if and when the adding of higher b-number
states (those created from the coherent state by the application of the creation operator
b

i
(a

i
)) to the truncated basis does not change the approximated ground state of
H
P
beyond certain range of accuracy,
[()[ E
c
,= 0. (17)
Even we can prove that the approximated ground state [g

) and its energy will eventually

converge to its true values, the mathematical noncomputability results from the fact that
their rates of convergence are unknown. Thus, we might not be able to use mathematical
reasoning alone to determine when to stop adding more states to the truncated basis in
order to approximate the ground state correctly. Dierent truncated bases would give some
estimates for the ground state but we have no control over these estimates and no idea
how good they are. They could be anywhere in relation to the true values. This is nothing
but mathematical noncomputability. (However, this quantum algorithm has inspired us to
reformulate Hilberts tenth problem with continuous variables [20], and the mathematical
computibility of this reformulation, or lack of it, should be investigated further.)
To know when the truncated basis is suciently large to have the estimated ground
state values within any given accuracy, that is, to regain computability, we have to exploit
the measurability of physical processes. Because of this measurability we can estimate the
true accuracy of our measured values. Then a comparison of results from the Schrodinger
equation to these measurable quantities will help determining the accuracy of results from
the equation, that is, regaining the lost computability through the physical world, presum-
ably innite.
10 Decoherence and error correction
Our approach above is in fact a combination of the quantum computation of continu-
ous variables and of adiabatic evolution. There exists some error correction protocol for
continuous variables [22] which could be of help here to protect the wave functions from
decoherence. However, the adiabatic computation we exploit is quite robust in general [23].
An imperfect conventional quantum algorithm might have dierent sorts of errors than an
11
imperfect adiabatic process, where the system is kept close to the instantaneous ground
state over time. Decoherence by the environment inducing transition between levels could
be controlled in principle at a temperature that is small compared to the gap (13), given
its estimate. Errors introduced by the hamiltonian simulation may result in a hamiltonian
dierent from (9) but in a form H(t/T) + K(t). Recent numerical study [23] of small
systems has in fact indicated that the adiabatic computation is interestingly robust even
for fairly large K(t), provided K(t) varies either suciently slowly or suciently rapidly
(which is more likely to be the case considered here due to the nature of our hamiltonian
simulations).
11 Probability boosting
Due to the particular nature of the present scheme, the various approximations result in
some probability that the nal measurement will not nd the system in the desired ground
state; but appropriate choices of the various time parameters could increase the success
probability of the algorithm to more than even. We spell out explicitly here the probability
boosting technique, as mentioned in [5], that one could subsequently apply.
In our computation, adiabatic or otherwise, the end result, starting from some initial
state [g
I
), may be contaminated with some excited states other than the desirable ground
state [g),
[g
I
)
time
a[g) + b[e). (18)
If [a[ > [b[, that is, if there is a better-than-even chance to obtain [g) by measurement
then one can boost the success probability to arbitrarily closed to unity by performing a
concatenated computation over l Hilbert spaces
[g
I
)
1
[g
I
)
l
time
^
l

p=0
a
p
b
lp
[e)
1
[g)
k
1
[g)
kp
[e)
l
, (19)
where ^ is the normalising factor. Let us consider the majority amplitudes, when more
than half of the l Hilbert spaces return the correct results, ^a
p
b
lp
, p >
l
2
; and the minority
amplitudes, ^a
q
b
lq
, q <
l
2
. The ratio of the majority over the minority, (a/b)
pq
, is clearly
boosted for suciently large l and for p O(l) and q O(1). The probability distribution
for a measurement of the end state in (19), as a consequence, is exponentially dominated
by the majority results. In other words, the probability to obtain a majority result which
contains the true ground state can be made arbitrarily closed to unity, (1

), provided
[a[ > [b[ and l > C log

. However, the decoherence control for such l concatenated

Hilbert spaces will be more crucial.
12 Concluding remarks
In this paper, we consider and emphasise on the issue of computability in principle, not
that of computational complexity. This attempt of broadening of the concept of eective
12
computability, taken into account the quantum mechanical principles, has been argued to
be able in principle to decide the classically/Turing undecidables, Hilberts tenth problem
and thus the Turing halting problem in this instance. If this is realisable, and we dont
have any evidence of fundamental nature to the contrary, the Church-Turing thesis should
be modied accordingly.
In summary, we have encoded the answer to the question about the existence or lack
of non-negative integer solutions for any Diophantine equation into the of ground state of
some relevant Hamiltonian. The key factor in the ground state verication is the prob-
ability distributions, which not only can be calculated in numerical Quantum Mechanics
(with a truncated basis) but also are measurable in practice. After all, probability dis-
tributions are also physical observables. However, in using the probability distributions
as the identication criteria, we have to assume that Quantum Mechanics is able to de-
scribe Nature correctly to the precision required. Note also that we have here a peculiar
situation in which the computational complexity, that is, the computation time, might
not be known exactly before carrying out the quantum computation although it can be
estimated approximately (see the appendix below).
On the other hand, if for any reasons the algorithm is not implementable because of
physical principles and/or physical resources then it would be an example of information
being limited by physics, rather than by logical arguments alone.
Our study is an illustration of Information is physical (see [24] for another quantum
mechanical approach and [25] for where the theory of General Relativity is also exploited
for the computation of Turing noncomputables).
That some generalisation of the notion of computation could help solving the previous
undecidability/noncomputability has been recognised in mathematics and was considered
by Kleene as quoted in [4]. But this has not been realisable until now simply because of
the non-recognition of quantum physics as the missing ingredient. Our quantum algorithm
could in fact be regarded as an innite search through the integers in a nite amount of
time, the type of search required by Kleene to solve the Turing halting problem.
Our decidability study here only deals with the property of being Diophantine, which
does not cover the property of being arithmetic in general, and as such has no direct
consequences on the Godels Incompleteness theorem [26]. However, it is conceivable that
the Godels theorem may lose its restrictive power once the concept of proof is suitably
generalised with quantum principles.
Note added in proof
The author has recently obtained a criterion based on the nal propbability distribution,
which can be measured to arbitrary precision, for identifying the ground state of H
P
at
time T. See [28] for more details.
13
Acknowledgements
I am indebted to Alan Head for discussions, comments and suggestions. I would also like to
thank Cristian Calude, John Markham, Boris Pavlov, Andrew Rawlinson and Khai Vu for
discussions; Gregory Chaitin, Bryan Dalton, Ray Sawyer, Boris Tsirelson and Ray Volkas
for email correspondence; and K. Svozil, G. Etesi and I. Nemeti for bringing their works
to my attention.
Appendix: Gap estimation
The question of computational complexity, i.e. how large the adiabatic computational time
T is for a high probability of measurement success, is dependent on H
P
, i.e. on the specic
Diophantine equation in question, and on the initial hamiltonian H
I
. Some estimate for
the energy gap (13) is desirable, but not necessary as discussed above. In this appendix
we propose such an estimate for the Step 0 of the quantum algorithm.
It has been shown elsewhere [19, 20] that in general there should be no level crossing for
the ground state except at the end points t = 0, T where the adiabatic process can start or
end with some obvious symmetry. Furthermore, the freedom in choosing the initial hamil-
tonians H
I
and their ground states and in performing dierent adiabatic interpolations,
not just as linear as in (9), might be exploited to enable the gap enlargement and to speed
up the computation.
We shall employ the simple harmonic oscillators, i.e. gaussian approximations, to obtain
an estimate for the energy gap.
For the various a
i
, a

i
appearing in the interpolating hamiltonian H(s) (9) at the time
instant s, we use the Bogoliubov ansatz, with real u
i
(s) and v
i
(s),
c
i
= u
i
(s)a
i
+ v
i
(s)a

i
,
a
i
= u
i
(s)b
i
v
i
(s)c

i
. (i)
The c
i
-zero occupation state is denoted by [0
c
), where the s-dependence of the state is
implicit. The canonicity [c
i
, c

j
] =
ij
demands
u
2
i
(s) v
2
i
(s) = 1, (ii)
upon which
a

i
a
j
) = v
2
i
(s)
ij
,
a

i
a

j
) = a
i
a
j
) = u
i
(s)v
i
(s)
ij
, (iii)
where
A
k
i
A
k
j
) 0
c
[A
k
i
A
k
j
[0
c
), (iv)
14
We pay particular attention to the following terms
: a

i
a
i
:
c
=
_
u
2
i
(s) + v
2
i
(s)
_
c

i
c
i
u
i
(s)v
i
(s)
_
c
2
i
+ c
2
i
_
,
: a
i
a
i
:
c
= 2u
i
(s)v
i
(s)c

i
c
i
+ v
2
i
(s)c
2
i
+ u
2
i
(s)c
2
i
. (v)
Needed next is a version of the Wick theorem [27] for the ordinary product involving the
operators A
1
, ..., A
n
,
A
1
A
n
=
[n/2]

p=0
: A
1


A
k
1


A
k
2p
A
n
:
c

_
A
k
1
A
k
2
) A
k
2p1
A
k
2p
) + permutations
_
, (vi)
where the normal ordering : :
c
is done with respect to some annihilation operators c
i
which annihilate some common state [0
c
) for various i, c
i
[0
b
) = 0. The equation (vi), in
which the hatted operators are omitted from the normal ordering, is an exact result and
can be proved by induction.
We can now list the various steps of our estimation:
1. We apply the Wick theorem, with respect to c
i
s, to the hamiltonian H(s) (9)
H(s) = E
b
(s)I
+

i
terms linear in c
i
and c

i
+

i
_
G
i
(s)c

i
c
i
+ K
i
(s)c
2
i
+ K

i
(s)c
2
i
_
+

i=j
terms involving c

i
c
j
, c
i
c
j
, c

i
c

j
+

ijk
higher-order, normal-ordered terms of c and c

. (vii)
Note that in this process the higher-order terms contribute to the coecients of
lower-order ones through products of various expectation values in (iii). With help
from (iii) and (v), the various coecients E
b
(s), G
i
(s), K
i
(s), ... in the right hand
side above can be expressed as polynomials in (u
i
(s), v
i
(s)).
2. We next x u
i
(s), and v
i
(s) numerically from (ii) and from the imposition that the
coecients K
i
(s) = 0 in (vii). Then we can evaluate the coecients G
i
(s) from their
polynomial expressions in (u
i
(s), v
i
(s)). From (vii), on the other hand, we see also
that
G
i
(s) = 1
c
i
[H(s)[1
c
i
) 0
c
[H(s)[0
c
), (viii)
where [1
c
i
) = c

i
[0
c
). Mathematically, min
i
[G
i
(s)[ thus provides some indication of
the size of the energy gaps of H(s) around the energy level E
b
(s) = 0
c
[H(s)[0
c
). Even
though [0
c
), obtained from the linear Bogoliubov transformations (i), in general may
not be the true ground state of H(s), we could use min
i
[G
i
(s)[ as some indicator for
the gap g in (13) in order to estimate T from the adiabaticity condition (11).
15
Some variations of the above method might yield a better estimate. For instance, one
could numerically obtain (u
i
(s), v
i
(s)), and thus min
i
[G
i
(s)[, by minimising the energy
E
b
(s) subjected to the constraints (ii) with or without the constraints K
i
(s) = 0. The
aim of this minimisation, if possible, is to select a state [0
c
) whose energy expectation
value at the time s is as closed to that of the ground state at that instant as allowed by
the linear Bogoliubov transformations. Other variations might be involving, instead of (i),
some non-linear relations, for the canonicity only requires that a and c are to be unitarily
transformed, c = U

(a

, a)aU(a

, a).
The accuracy of the estimation and its higher order corrections can be evaluated sys-
tematically from the higher order terms in the last line of (vii). Numerical diagonalisation
of (vii) with a series of truncated bases in [n
c
i
) of increasing sizes could further provide us
more information about the gap thus obtained.
References
[1] See for example M. Nielsen, I. L. Chuang, Quantum Computation and Quantum In-
formation (Cambridge University Press, 2000).
[2] L. K. Grover, Quantum mechanics helps in searching for a needle in a haystack. Phys.
Rev. Lett. 79, 325-328 (1997).
[3] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete loga-
rithms on a quantum computer. SIAM J. Comput. 26, 1484-1509 (1997).
[4] H. Jr. Rogers, Theory of Recursive Functions and Eective Computability (MIT Press,
1987).
[5] E. Bernstein, U. Vazirani, Quantum complexity theory. SIAM J. Comput. 26, 1411
(1997).
[6] Y. V. Matiyasevich, Hilberts Tenth Problem (MIT Press, 1993).
[7] M. Davis, Computability and Unsolvability (Dover, 1982).
[8] W. K. Wooters, W. H. Zurek, A single quantum cannot be cloned. Nature 299, 802-803
(1982).
[9] T. Ord and T. D. Kieu, The diagonal method and hypercomputation,
math-lo/0307020 (2003).
[10] P. Benio, The computer as a physical system. J. Stat. Phys. 22, 563-591(1980).
[11] R. P. Feynman, Simulating physics with computers. Int. J. Theor. Phys. 21, 467
(1982).
16
[12] M. A. Nielsen, Computable functions, quantum measurements, and quantum dynam-
ics, Phys. Rev. Lett. 79 (1997) 2915-8.
[13] M. Ozawa, Measurability and computability, quant-ph/9809048 (1998).
[14] S. Lloyd, S. L. Braunstein, Quantum computation over continuous variables. Phys.
Rev. Lett 82, 1784 (1999).
[15] T. Kadowaki, H. Nishimori, Quantum annealing in the transverse Ising model. Phys.
Rev. E 58, 5355 (1998).
[16] E. Farhi, J. Goldstone, S. Gutmann, M. Sipser, Quantum computation by adiabatic
evolution, quant-ph/0001106 (2000).
[17] Kieu, T. D., Computing the noncomputable. Contemporary Physics 44 51-71 (2003).
[18] A. Renyi, Probability Theory (North-Holland, 1970).
[19] M. B. Ruskai, Comments on adiabatic quantum algorithms, quant-ph/0203127
(2002).
[20] T. D. Kieu, A reformulation of Hilberts tenth problem through Quantum Mechanics,
quant-ph/0111063 (2001).
[21] D. Bridges, as privately communicated by Cristian Calude.
[22] S. Braunstein, Error correction for continuous variables. Phys. Rev. Lett. 80, 4084
(1998).
[23] A. M. Childs, E. Farhi, J. Preskill, Robustness of adiabatic quantum computation,
quant-ph/0108048 (2001).
[24] C. S. Calude and B. Pavlov, Coins, quantum measurements and Turings barrier,
quant-ph/0112087 (2001).
[25] G. Etesi and I. Nemeti, Non-Turing computations via Malament-Hogarth space-times,
gr-qc/0104023 (2001).
[26] T.D. Kieu, Godels Indompleteness, Chaitins and Quantum Physics,
quant-ph/0111062 (2001).
[27] C. Itzykson, J.-B. Zuber, Quantum Field Theory (McGraw-Hill, 1985).
[28] T. D. Kieu, Numerical simulations of a quantum algorithm for Hilberts tenth problem,
quant-ph/0304114 (2003).
17