Quantum adiabatic algorithm for Hilbert's tenth problem: I. The algorithm
Abstract
Description
We review the proposal of a quantum algorithm for Hilbert's tenth problem and provide further arguments towards the proof that: (i) the algorithm terminates after a finite time for any input of Diophantine equation; (ii) the final ground state which contains the answer for the Diophantine equation can be identified as the component state having better-than-even probability to be found by measurement at the end time--even though probability for the final ground state in a quantum adiabatic process need not monotonically increase towards one in general. Presented finally are the reasons why our algorithm is outside the jurisdiction of no-go arguments previously employed to show that Hilbert's tenth problem is recursively non-computable.
Typos fixed, substantial results added in Section III, new reference and footnotes added. Now 22 pages, one figure
Typos fixed, substantial results added in Section III, new reference and footnotes added. Now 22 pages, one figure