Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:quant-ph/0110136 · International Journal of Theoretical Physics

Quantum Algorithm for Hilbert's Tenth Problem

Tien D. Kieu

Published Jul 1, 2003• 94 citations
arXivHTMLPDF
DOI
10.1023/a:1025780028846

Related papers

On quantum algorithms

Richard Cleve, ARTUR K. EKERT, Leah Henderson +2 more

Complexity•Sep 1, 1998•28 citations

Quantum algorithms for the Hilbert's tenth problem

Tien D. Kieu

A quantum algorithm is presented for the classically non-computable Hilbert's tenth problem, which ultimately links to the Turing halting problem.

•Oct 24, 2001•7 citations

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

Tien D. Kieu

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.

arXiv:quant-ph/0310052•Oct 8, 2003•34 citations

On quantum algorithms

CleveRichard, EkertArtur, HendersonLea +2 more

Complexity•Sep 1, 1998•0 citations

Quantum Algorithms II

Masanori Ohya, Igor Vasil'evich Volovich

Theoretical and mathematical physics•Jan 1, 2011•0 citations

Hilbert's Incompleteness, Chaitin's ΩΩΩ number and Quantum Physics

Tien D. Kieu

To explore the limitation of a class of quantum algorithms originally proposed for the Hilbert's tenth problem, we consider two further classes of mathematically non-decidable problems, those of a modified version of the Hilbert's tenth problem and of the computation of the Chaitin's $Ω$ number, which is a representation of the Gödel's Incompletness theorem. Some interesting connection to Quantum Field Theory is pointed out.

arXiv:quant-ph/0111062•Nov 10, 2001•8 citations
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.
To explore the limitation of a class of quantum algorithms originally proposed for the Hilbert's tenth problem, we consider two further classes of mathematically non-decidable problems, those of a modified version of the Hilbert's tenth problem and of the computation of the Chaitin's ΩΩΩ number, which is a representation of the Gödel's Incompletness theorem. Some interesting connection to Quantum Field Theory is pointed out.