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

Philosophy of Science

Quantum Hypercomputation—Hype or Computation?

Amit Hagar, Alexandre Korolev

Published Jul 1, 2007• 14 citations
Publisher

Abstract

A recent attempt to compute a (recursion-theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion-theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.

DOI
10.1086/521969

Related papers

Computing the Noncomputable

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 which is equivalent to the Turing halting problem and known to be mathematically noncomputable. Generalised quantum algorithms are also considered for some other mathematical noncomputables in the same and of different noncomputability classes. The key element of all these algorithms is the measurability of both the values of physical observables and of the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of Mathematics, ought to be determined not

•Mar 7, 2002•55 citations

Hypercomputability of quantum adiabatic processes

Tien D. Kieu

We give an overview of a quantum adiabatic algorithm for Hilbert's tenth problem, including some discussions on its fundamental aspects and the emphasis on the probabilistic correctness of its findings. For the purpose of illustration, the numerical simulation results of some simple Diophantine equations are presented. We also discuss some prejudicial misunderstandings as well as some plausible difficulties faced by the algorithm in its physical implementations. We also point out a surprising connection between quantum computability and quantum phase transitions through some instances of our quantum adiabatic algorithm.

International journal of unconventional computing•Jan 1, 2009•3 citations

How powerful is adiabatic quantum computation?

W. van Dam, M. Mosca, U. Vazirani

The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.

arXiv:quant-ph/0206003•Annual Symposium on Foundations of Computer Science•Jan 1, 2001•175 citations

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

Hypercomputability of quantum adiabatic processes: Fact versus Prejudices

Tien D. Kieu

We give an overview of a quantum adiabatic algorithm for Hilbert's tenth problem, including some discussions on its fundamental aspects and the emphasis on the probabilistic correctness of its findings. For the purpose of illustration, the numerical simulation results of some simple Diophantine equations are presented. We also discuss some prejudicial misunderstandings as well as some plausible difficulties faced by the algorithm in its physical implementation.

arXiv:quant-ph/0504101•Apr 14, 2005•7 citations

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
A recent attempt to compute a (recursion-theoretic) noncomputable function using the quantum adiabatic algorithm is criticized and found wanting. Quantum algorithms may outperform classical algorithms in some cases, but so far they retain the classical (recursion-theoretic) notion of computability. A speculation is then offered as to where the putative power of quantum computers may come from.
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 which is equivalent to the Turing halting problem and known to be mathematically noncomputable. Generalised quantum algorithms are also considered for some other mathematical noncomputables in the same and of different noncomputability classes. The key element of all these algorithms is the measurability of both the values of physical observables and of the quantum-mechanical probability distributions for these values. It is argued that computability, and thus the limits of Mathematics, ought to be determined not
We give an overview of a quantum adiabatic algorithm for Hilbert's tenth problem, including some discussions on its fundamental aspects and the emphasis on the probabilistic correctness of its findings. For the purpose of illustration, the numerical simulation results of some simple Diophantine equations are presented. We also discuss some prejudicial misunderstandings as well as some plausible difficulties faced by the algorithm in its physical implementations. We also point out a surprising connection between quantum computability and quantum phase transitions through some instances of our quantum adiabatic algorithm.
The authors analyze the computational power and limitations of the recently proposed 'quantum adiabatic evolution algorithm'. Adiabatic quantum computation is a novel paradigm for the design of quantum algorithms; it is truly quantum in the sense that it can be used to speed up searching by a quadratic factor over any classical algorithm. On the question of whether this new paradigm may be used to efficiently solve NP-complete problems on a quantum computer, we show that the usual query complexity arguments cannot be used to rule out a polynomial time solution. On the other hand, we argue that the adiabatic approach may be thought of as a kind of 'quantum local search'. We design a family of minimization problems that is hard for such local search heuristics, and establish an exponential lower bound for the adiabatic algorithm for these problems. This provides insights into the limitations of this approach. It remains an open question whether adiabatic quantum computation can establish an exponential speed-up over traditional computing or if there exists a classical algorithm that can simulate the quantum adiabatic process efficiently.
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.