[FOM] Tien Kieu and the Quantum Adiabatic Theorem

[Martin Davis]

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
                          (Add 1 and get 0)
                        http://www.eipye.com