# [FOM] Tien Kieu and the Quantum Adiabatic Theorem

Martin Davis martin at eipye.com
Tue Feb 10 20:04:28 EST 2004

```Toby Ord wrote:

<<Tien Kieu is such a specialist whom I have worked with extensively on
this topic and cannot see any reason at all as to why QM would prohibit
non-recursive computation. Indeed, he has suggested how it can allow the
solving of hilbert's tenth problem (and thus all Sigma_1 and Pi_1 problems)
via the Quantum Adiabatic Theorem. There has been a technical criticism of
Kieu's method, but he believes it to be satisfactorily answered. See Kieu,
'Computing the Noncomputable'.>>

I have met Tien Kieu and he is clearly a well-intentioned sincere
physicist. The fact remains that he has failed to convince experts in the
use of the Quantum Adiabatic Theorem, including the group at MIT that
pioneered its use for computation, that his method can indeed, as he
claims, compute with arbitrarily high probability the minimum of a
countably infinite sequence of natural numbers.

His method would test the Diophantine equation x^2 - 17 y^2 = 0 for having
integer solutions by replacing each of x and y in the form
(x^2 - 17 y^2)^2
by a suitable operator multiplied by its adjoint. He would then apply
adiabatic cooling to a physical system enjoying that form as its
Hamiltonian to get the system into its ground state. The energy of the
system in this ground state will then be 0 just in case the equation has a
natural number solution. I like to point out (following a suggestion of
Andrew Hodges) that although the equation as given has no solutions,
because sqrt(17) is irrational, there are rational numbers q arbitrarily
close to 17 for which the equation
x^2 - q y^2 = 0 does have solutions. So the physical system would need to
be constructed with such exquisite accuracy that the number 17 is given
with infinite precision.

Martin

Martin Davis
Visiting Scholar UC Berkeley
Professor Emeritus, NYU
martin at eipye.com