[FOM] Tien Kieu and the Quantum Adiabatic Theorem
Toby Ord
toby.ord at philosophy.oxford.ac.uk
Wed Feb 11 08:45:52 EST 2004
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.
More information about the FOM
mailing list