B. Tsirelson

The quantum algorithm of Kieu does not solve the Hilbert's tenth problem

Recent works

Boris Tsirelson,
"The quantum algorithm of Kieu does not solve the Hilbert's tenth problem."
Available online (free of charge) from e-print archive (USA):
or its Israeli mirror:

A short note, 4 pages, bibl. 1 ref.

Recently T. Kieu (arXiv:quant-ph/0110136) claimed a quantum algorithm computing some functions beyond the Church-Turing class. He notes that "it is in fact widely believed that quantum computation cannot offer anything new about computability" and claims the opposite. However, his quantum algorithm does not work, which is the point of my short note. I still believe that quantum computation leads to new complexity but retains the old computability.

  1. The algorithm of Kieu.
  2. The goal of the algorithm.
  3. The goal is not achieved.

My note (of 1 Nov 2001) is a response to the first version (of 24 Oct 2001) of the preprint by Kieu. The second version (of 9 Nov 2001) of his preprint mitigates the claim:
"We propose that quantum computation may be able to compute the noncomputables" (version 2, Introduction) instead of "I show that quantum computation can indeed compute the noncomputables" (version 1).
"This algorithm ultimately links to the halting problem" instead of "This algorithm can ultimately solve the halting problem".

More examples (from his last section):
"This attempt of broadening of the concept of effecive computability" instead of "This broadening of the concept of effecive computability".
"Our decidability study" instead of "Our decidability result".

On the other hand, his new section "Why should this work?" expresses his hope that the `ground state oracle' can be implemented somehow. I do not share the hope.

You may also look at other relevant preprints by Kieu: quant-ph/0111020, 0111062, 0111063.

back to my homepage