An anatomy of a quantum adiabatic algorithm that transcends Turing computability - Tien Kieu

We point out [1, 2, 3] the fallacies in the common belief that Cantor¹s diagonal arguments, employed for the proof of recursive noncomputability of the Turing halting problem, could be used to further rule out all computation beyond the Turing barrier. We then present and analyse the general settings of a quantum adiabatic algorithm [4] for the Turing-noncomputable Hilbert¹s tenth problem, which is also equivalent to the Turing halting problem. The algorithm is made possible by the quantum adiabatic theorem, thanks to the exploitation of which we can impose a universal structure on suitably constructed dimensionally infinite Hilbert spaces. Our ability to erect such a structure, namely that of the spectral flows without level crossings of energy-ordered states, is in direct contrast to the structurelessness in recursive computation that has otherwise led to the Turing noncomputability of the problems under consideration. Such imposed structure and other quantum properties of coherence and tunnelling are the reasons why our quantum algorithm can probabilistically perform what seems to be an impossible task of searching through the positive integers in a finite time! More explicitly, our algorithm can probabilistically locate a particular single energy eigenstate in a dimensionally infinite Hilbert space in a finite time^Ëa task equivalent to finding a needle in an infinite haystack, but also a task obviously beyond the ability of deterministic Turing machines. [1] T. Ord and T.D. Kieu, The diagonal method and hypercomputation, to appear in British Journal for the Philosophy of Science, 2004. [3] E.S. Santos, Computability by probabilistic Turing machines, Trans. Am. Math. Soc. 159:165-184, 1971. [4] T. Ord and T.D. Kieu, Using biased coins as oracles, cs.OH/0401019, 2004. [2] T.D. Kieu, Quantum adiabatic algorithm for Hilbert\'s tenth problem: I. The algorithm, quant-ph/0310052, 2003.