Quantum adiabatic algorithm for Hilbert's tenth problem: I. The algorithm

Abstract

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

References in corpus (4)

• Quantum Computation by Adiabatic Evolution
• A reformulation of Hilbert's tenth problem through Quantum Mechanics
• The Diagonal Method and Hypercomputation
• Computing a Turing-Incomputable Problem from Quantum Computing

Cited by in corpus (9)

• Can quantum computing solve classically unsolvable problems?
• Hypercomputability of quantum adiabatic processes: Fact versus Prejudices
• Reply to Andrew Hodges
• On the identification of the ground state based on occupation probabilities: An investigation of Smith's apparent counterexamples
• Quantum Adiabatic Computation and the Travelling Salesman Problem
• A possible hypercomputational quantum algorithm
• Finiteness of the universe and computation beyond Turing computability
• Mathematical computability questions for some classes of linear and non-linear differential equations originated from Hilbert's tenth problem
• Hypercomputation: Towards an extension of the classical notion of Computability?