[FOM] Tien Kieu and the Quantum Adiabatic Theorem

[Toby Ord]

On 11 Feb 2004, at 01:04, Martin Davis wrote:

> 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.

I am not familiar with this MIT group, so I can't really comment on 
this. However, there are numerous reasons for them to remain 
unconvinced by the account, even if it does represent a real 
possibility according to QM. For example, I doubt that Kieu's method is 
one to focus on if one wants to have a real-life quantum computer in 
any immediate time frame and no doubt there are pertinent issues of 
interpretation in what techniques are allowed in the computational 
setup (such as the one below), which may be the subject of unsettled 
philosophical disagreement.

> 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.

This does indeed appear to be a significant concern. The fact that the 
infinitely precise quantity only needs to be an integer does seem to 
give some plausibility: one could, for example, have access to 17 
electrons, representing exactly 17 times the charge on a single 
electron, however it seems that this 17 must be embedded in a 
continuous context where infinite precision is an issue (possibly 
insurmountable). Still, if correct, Kieu's account points out that in 
QM it suffices to have infinitely precise reals that take on integer 
values in order to solve the halting problem, which is not merely the 
assertion that given uncomputable initial conditions we get 
uncomputable outputs.

I should also point out that even assuming that the initial conditions 
(including values of dimensionless constants) somehow code, say, the 
halting problem, QM does not make it all that easy to get that 
information out in the form of, say, discrete symbols on a piece of 
paper. Indeed, in this sense, those that assume all such clear cases of 
physical computation (reliable machines with macroscopic digital input 
and output) are recursive may even be on safer ground than they first 
assumed.

Toby Ord.