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

Quantum algorithms for the Hilbert's tenth problem

Tien D. Kieu

Published Oct 24, 2001• 5 citations
OpenAlex

Abstract

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

Related papers

AN ANATOMY OF A QUANTUM ADIABATIC ALGORITHM THAT TRANSCENDS THE TURING COMPUTABILITY

Tien D. Kieu

We give an update on a quantum adiabatic algorithm for the Turing noncomputable Hilbert's tenth problem, and briefly go over some relevant issues and misleading objections to the algorithm.

arXiv:quant-ph/0407090•International Journal of Quantum Information•Dec 17, 2004•18 citations

Quantum Algorithm for Hilbert's Tenth Problem

Tien D. Kieu

arXiv:quant-ph/0110136•International Journal of Theoretical Physics•Jul 1, 2003•81 citations

On the Halting Problem for Quantum Turing Machines

正直 小澤

数理解析研究所講究録•Oct 1, 1998•0 citations

Numerical simulations of a quantum algorithm for Hilbert's tenth problem

Kieu, T D

We employ quantum mechanical principles in the computability exploration of the class of classically noncomputable Hilbert's tenth problem which is equivalent to the Turing halting problem in Computer Science. The Quantum Adiabatic Theorem enables us to establish a connection between the solution for this class of problems and the asymptotic behaviour of solutions of a particular type of time-dependent Schr\\"odinger equations. We then present some preliminary numerical simulation results for the quantum adiabatic processes corresponding to various Diophantine equations.

•Apr 16, 2003•12 citations

Numerical simulations of a quantum algorithm for Hilbert's tenth problem

Tien D. Kieu

We employ quantum mechanical principles in the computability exploration of the class of classically noncomputable Hilbert's tenth problem which is equivalent to the Turing halting problem in Computer Science. The Quantum Adiabatic Theorem enables us to establish a connection between the solution for this class of problems and the asymptotic behavior of solutions of a particular type of time-dependent Schrodinger equations. We then present some preliminary numerical simulation results for the quantum adiabatic processes corresponding to various Diophantine equations.

arXiv:quant-ph/0304114•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•Aug 5, 2003•5 citations

Computing the non-computable

Tien D. Kieu

We explore in the framework of quantum computation the notion of computability, which holds a central position in mathematics and theoretical computer science. A quantum algorithm that exploits the quantum adiabatic processes is considered for Hilbert's tenth problem, which is equivalent to the Turing halting problem and known to be mathematically non-computable. Generalized quantum algorithms are also considered for some other mathematical non-computables in the same and in different non-computability classes. The key element of all these algorithms is the measurability of both the values of physical observables and the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of mathematics, ought to be determined not solely by mathematics itself but also by physical principles.

arXiv:quant-ph/0203034•Contemporary Physics•Jan 1, 2003•30 citations
We employ quantum mechanical principles in the computability exploration of the class of classically noncomputable Hilbert's tenth problem which is equivalent to the Turing halting problem in Computer Science. The Quantum Adiabatic Theorem enables us to establish a connection between the solution for this class of problems and the asymptotic behaviour of solutions of a particular type of time-dependent Schr\\"odinger equations. We then present some preliminary numerical simulation results for the quantum adiabatic processes corresponding to various Diophantine equations.
We employ quantum mechanical principles in the computability exploration of the class of classically noncomputable Hilbert's tenth problem which is equivalent to the Turing halting problem in Computer Science. The Quantum Adiabatic Theorem enables us to establish a connection between the solution for this class of problems and the asymptotic behavior of solutions of a particular type of time-dependent Schrodinger equations. We then present some preliminary numerical simulation results for the quantum adiabatic processes corresponding to various Diophantine equations.
We explore in the framework of quantum computation the notion of computability, which holds a central position in mathematics and theoretical computer science. A quantum algorithm that exploits the quantum adiabatic processes is considered for Hilbert's tenth problem, which is equivalent to the Turing halting problem and known to be mathematically non-computable. Generalized quantum algorithms are also considered for some other mathematical non-computables in the same and in different non-computability classes. The key element of all these algorithms is the measurability of both the values of physical observables and the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of mathematics, ought to be determined not solely by mathematics itself but also by physical principles.