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/0309198

Computing a Turing-Incomputable Problem from Quantum Computing

Andrés Sicard, Mario E. Vélez, Juan Ospina

Published Sep 26, 2003• 2 citations
arXivHTMLPDF

Abstract

A hypercomputation model named Infinite Square Well Hypercomputation Model (ISWHM) is built from quantum computation. This model is inspired by the model proposed by Tien D. Kieu quant-ph/0203034 and solves an Turing-incomputable problem. For the proposed model and problem, a simulation of its behavior is made. Furthermore, it is demonstrated that ISWHM is a universal quantum computation model.

DOI
10.48550/arxiv.quant-ph/0309198

Related papers

Hypercomputation based on quantum computing

Andrés Sicard, Mario E. Vélez, Juan Ospina

Abstract. We present a quantum algorithm for a (classically) incomputable decision problem: the Hilbert’s tenth problem; namely, we present a hypercomputation model based on quantum computation. The model is inspired by the one proposed by Tien D. Kieu. Our model exploits the quantum adiabatic process and the characteristics of the representation of the dynamical algebra su(1, 1) associated to the infinite square well. Furthermore, it is demonstrated that the model proposed is a universal quantum computation model.

•Jun 18, 2004•2 citations

A possible hypercomputational quantum algorithm

Andrés Sicard, Mario E. Vélez, Juan Ospina

The term 'hypermachine' denotes any data processing device (theoretical or that can be implemented) capable of carrying out tasks that cannot be performed by a Turing machine. We present a possible quantum algorithm for a classically non-computable decision problem, Hilbert's tenth problem; more specifically, we present a possible hypercomputation model based on quantum computation. Our algorithm is inspired by the one proposed by Tien D. Kieu, but we have selected the infinite square well instead of the (one-dimensional) simple harmonic oscillator as the underlying physical system. Our model exploits the quantum adiabatic process and the characteristics of the representation of the dynamical Lie algebra su(1,1) associated to the infinite square well.

arXiv:quant-ph/0406137•Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE•May 25, 2005•7 citations

Poschl-Teller potentials based solution to Hilbert's tenth problem

Mario E. Vélez, Andrés Sicard, Juan Ospina

Hypercomputers compute functions or numbers, or more generally solve problems or carry out tasks, that cannot be computed or solved by a Turing machine. An adaptation of Tien D. Kieu¿s quantum hypercomputational algorithm is carried out for the dynamical algebra su(1, 1) of the Poschl-Teller potentials. The classically incomputable problem that is resolved with this hypercomputational algorithm is Hilbert¿s tenth problem. We indicated that an essential mathematical condition of these algorithms is the existence of infinitedimensional unitary irreducible representations of low dimensional dynamical algebras that allow the construction of coherent states of the Barut-Girardello type. In addition, we presented as a particular case of our hypercomputational algorithm on Poschl-Teller potentials, the hypercomputational algorithm on an infinite square well presented previously by the authors.

Ingeniería y Ciencia•Jan 1, 2006•2 citations

A computable formulation of quantum theory

Mike Stannett

According to the Church-Turing Thesis (CTT), effective formal behaviours can be simulated by Turing machines; this has naturally led to speculation that physical sys- tems can also be simulated computationally. But is this wider claim true, or do behaviours exist which are strictly hypercomputational? Several idealised computational models are known which suggest the possibility of hypercomputation, some Newtonian, some based on cosmology, some on quantum theory. While these models' physicality is debatable, they nonetheless throw into question the validity of extending CTT to include all physical systems. We consider the physicality of hypercomputational behaviour from first princi- ples, by showing that quantum theory can be reformulated in a way that explains why physical behaviours can be regarded as 'computing something' in the standard compu- tational state-machine sense. While this does not rule out the physicality of hypercomputation, it strongly limits the forms it can take. Our model also has physical consequences; in particular, the continuity of motion and arrow of time become theorems within the basic model.

•Jan 1, 2009•0 citations

Can quantum computing solve classically unsolvable problems?

Andrew Hodges

T. D. Kieu has claimed that a quantum computing procedure can solve a classically unsolvable problem. Recent work of W. D. Smith has shown that Kieu's central mathematical claim cannot be sustained. Here, a more general critique is given of Kieu's proposal and some suggestions are made regarding the Church-Turing thesis.

arXiv:quant-ph/0512248•Dec 29, 2005•25 citations

Undecidable, Unrecognizable, and Quantum Computing

Michael Siomau

Quantum computing allows us to solve some problems much faster than existing classical algorithms. Yet, the quantum computer has been believed to be no more powerful than the most general computing model—the Turing machine. Undecidable problems, such as the halting problem, and unrecognizable inputs, such as the real numbers, are beyond the theoretical limit of the Turing machine. I suggest a model for a quantum computer, which is less general than the Turing machine, but may solve the halting problem for any task programmable on it. Moreover, inputs unrecognizable by the Turing machine can be recognized by the model, thus breaking the theoretical limit for a computational task. A quantum computer is not just a successful design of the Turing machine as it is widely perceived now, but is a different, less general but more powerful model for computing, the practical realization of which may need different strategies than those in use now.

Quantum Reports•Jul 1, 2020•3 citations
A hypercomputation model named Infinite Square Well Hypercomputation Model (ISWHM) is built from quantum computation. This model is inspired by the model proposed by Tien D. Kieu quant-ph/0203034 and solves an Turing-incomputable problem. For the proposed model and problem, a simulation of its behavior is made. Furthermore, it is demonstrated that ISWHM is a universal quantum computation model.
Abstract. We present a quantum algorithm for a (classically) incomputable decision problem: the Hilbert’s tenth problem; namely, we present a hypercomputation model based on quantum computation. The model is inspired by the one proposed by Tien D. Kieu. Our model exploits the quantum adiabatic process and the characteristics of the representation of the dynamical algebra su(1, 1) associated to the infinite square well. Furthermore, it is demonstrated that the model proposed is a universal quantum computation model.
The term 'hypermachine' denotes any data processing device (theoretical or that can be implemented) capable of carrying out tasks that cannot be performed by a Turing machine. We present a possible quantum algorithm for a classically non-computable decision problem, Hilbert's tenth problem; more specifically, we present a possible hypercomputation model based on quantum computation. Our algorithm is inspired by the one proposed by Tien D. Kieu, but we have selected the infinite square well instead of the (one-dimensional) simple harmonic oscillator as the underlying physical system. Our model exploits the quantum adiabatic process and the characteristics of the representation of the dynamical Lie algebra su(1,1) associated to the infinite square well.
Hypercomputers compute functions or numbers, or more generally solve problems or carry out tasks, that cannot be computed or solved by a Turing machine. An adaptation of Tien D. Kieu¿s quantum hypercomputational algorithm is carried out for the dynamical algebra su(1, 1) of the Poschl-Teller potentials. The classically incomputable problem that is resolved with this hypercomputational algorithm is Hilbert¿s tenth problem. We indicated that an essential mathematical condition of these algorithms is the existence of infinitedimensional unitary irreducible representations of low dimensional dynamical algebras that allow the construction of coherent states of the Barut-Girardello type. In addition, we presented as a particular case of our hypercomputational algorithm on Poschl-Teller potentials, the hypercomputational algorithm on an infinite square well presented previously by the authors.
According to the Church-Turing Thesis (CTT), effective formal behaviours can be simulated by Turing machines; this has naturally led to speculation that physical sys- tems can also be simulated computationally. But is this wider claim true, or do behaviours exist which are strictly hypercomputational? Several idealised computational models are known which suggest the possibility of hypercomputation, some Newtonian, some based on cosmology, some on quantum theory. While these models' physicality is debatable, they nonetheless throw into question the validity of extending CTT to include all physical systems. We consider the physicality of hypercomputational behaviour from first princi- ples, by showing that quantum theory can be reformulated in a way that explains why physical behaviours can be regarded as 'computing something' in the standard compu- tational state-machine sense. While this does not rule out the physicality of hypercomputation, it strongly limits the forms it can take. Our model also has physical consequences; in particular, the continuity of motion and arrow of time become theorems within the basic model.
Quantum computing allows us to solve some problems much faster than existing classical algorithms. Yet, the quantum computer has been believed to be no more powerful than the most general computing model—the Turing machine. Undecidable problems, such as the halting problem, and unrecognizable inputs, such as the real numbers, are beyond the theoretical limit of the Turing machine. I suggest a model for a quantum computer, which is less general than the Turing machine, but may solve the halting problem for any task programmable on it. Moreover, inputs unrecognizable by the Turing machine can be recognized by the model, thus breaking the theoretical limit for a computational task. A quantum computer is not just a successful design of the Turing machine as it is widely perceived now, but is a different, less general but more powerful model for computing, the practical realization of which may need different strategies than those in use now.