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

Can quantum computing solve classically unsolvable problems?

Andrew Hodges

Published Dec 29, 2005• 25 citations
arXivHTMLPDF

Abstract

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.
DOI
10.48550/arxiv.quant-ph/0512248

Related papers

The quantum algorithm of Kieu does not solve the Hilbert's tenth problem

Boris S. Tsirelson

Recently T. Kieu (arXiv:quant-ph/0110136) claimed a quantum algorithm computing some functions beyond the Church-Turing class. He notes that "it is in fact widely believed that quantum computation cannot offer anything new about computability" and claims the opposite. However, his quantum algorithm does not work, which is the point of my short note. I still believe that quantum computation leads to new complexity but retains the old computability.

arXiv:quant-ph/0111009•Nov 1, 2001•14 citations

A Review on Recent Trends in Quantum Computation Technology

A. V. Susindhar, Gulshan Soni, Amit Kumar Tyagi

Quantum technologies' processing capacity is built on quantum mechanics foundations, including superposition, the no-cloning theorem, and quantum entanglement. Quantum computing seeks to understand and embrace quantum effects, as well as techniques to improve and sustain them in order to achieve old computational goals in novel ways. It accomplishes this by utilising quintessentially quantum phenomena. We can't get equivalent findings using traditional computation because these processes don't have a classical analogue. There have been significant claims that quantum computers can surpass the Turing limit, however these assertions have been debunked. The Church-Turing thesis, which states that all realisable physical and dynamical systems cannot be more powerful than classical models of computation, has been the subject of numerous intensive attempts. However, quantum computing technologies' experimental insights have already been proved, and various studies are currently underway. In this article, the authors look at the most current quantum computation results and claims.

Advances in systems analysis, software engineering, and high performance computing book series•Mar 3, 2023•4 citations

Quantum Computation and the Church–Turing Hypothesis

Christopher G. Timpson

Some of the philosophical questions raised by the theory of quantum computation are discussed. First it is considered whether the possibility of exponential speed-up in quantum computation provides an argument for a more substantive notion of quantum information than so far allowed. It is concluded that this is not so. Then some questions regarding the status of the Church-Turing hypothesis in the light of quantum computation are considered. In particular, Deutsch’s claim that a physical principle, the Turing Principle, underlies the Church-Turing hypothesis is rebutted. Finally, the question of whether the Church-Turing hypothesis might serve as a constraint on the laws of physics is briefly considered.

Oxford University Press eBooks•Apr 25, 2013•0 citations

Quantum Computation

Cristopher Moore, Stephan Mertens

Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.

Oxford University Press eBooks•Aug 11, 2011•0 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

Quantum computing

Peter W. Shor

The Church-Turing thesis says that a digital computer is a universal computational device; that is, it is able to simulate any physically realizable computational device. It has generally been believed that this simulation can be made efficient so that it entails at most a polynomial increase in computation time. This may not be true if quantum mechanics is taken into consideration. A quantum computer is a hypothetical machine based on quantum mechanics. We explain quantum computing, and give an algorithm for prime factorization on a quantum computer that runs asymptotically much faster than the best known algorithm on a digital computer. It is not clear whether it will ever be possible to build large-scale quantum computers. One of the main difficulties is in manipulating coherent quantum states without introducing errors or losing coherence. We discuss quantum error-correcting codes and fault-tolerant quantum computing, which can guarantee highly reliable quantum computation, given only moderately reliable quantum computing hardware.

EMS Press eBooks•Jan 1, 1998•77 citations
Quantum technologies' processing capacity is built on quantum mechanics foundations, including superposition, the no-cloning theorem, and quantum entanglement. Quantum computing seeks to understand and embrace quantum effects, as well as techniques to improve and sustain them in order to achieve old computational goals in novel ways. It accomplishes this by utilising quintessentially quantum phenomena. We can't get equivalent findings using traditional computation because these processes don't have a classical analogue. There have been significant claims that quantum computers can surpass the Turing limit, however these assertions have been debunked. The Church-Turing thesis, which states that all realisable physical and dynamical systems cannot be more powerful than classical models of computation, has been the subject of numerous intensive attempts. However, quantum computing technologies' experimental insights have already been proved, and various studies are currently underway. In this article, the authors look at the most current quantum computation results and claims.
Some of the philosophical questions raised by the theory of quantum computation are discussed. First it is considered whether the possibility of exponential speed-up in quantum computation provides an argument for a more substantive notion of quantum information than so far allowed. It is concluded that this is not so. Then some questions regarding the status of the Church-Turing hypothesis in the light of quantum computation are considered. In particular, Deutsch’s claim that a physical principle, the Turing Principle, underlies the Church-Turing hypothesis is rebutted. Finally, the question of whether the Church-Turing hypothesis might serve as a constraint on the laws of physics is briefly considered.
Abstract According to the Church-Turing Thesis, a Turing machine, and thus the programming languages and computers in existence, can simulate any reasonable computing device. However, there are physical devices that are exponentially more efficient than a Turing machine, and hence would prove exponentially difficult to simulate using such a machine. This chapter explores the concept of quantum computers and their potential not only to simulate quantum physics exponentially faster than classical computers but also to solve other problems exponentially faster. It considers algorithms that break cryptosystems, find needles in haystacks, and predict who can win a game. It first describes particles, waves, and amplitudes in quantum computation before turning to states and operators. It then examines how interference lets a quantum computer learn some things about a function, how quantum computers can solve factoring in polynomial time, the link between factoring and modern cryptography, graph isomorphism and the hidden subgroup problem, and quantum walks and scattering.
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.
The Church-Turing thesis says that a digital computer is a universal computational device; that is, it is able to simulate any physically realizable computational device. It has generally been believed that this simulation can be made efficient so that it entails at most a polynomial increase in computation time. This may not be true if quantum mechanics is taken into consideration. A quantum computer is a hypothetical machine based on quantum mechanics. We explain quantum computing, and give an algorithm for prime factorization on a quantum computer that runs asymptotically much faster than the best known algorithm on a digital computer. It is not clear whether it will ever be possible to build large-scale quantum computers. One of the main difficulties is in manipulating coherent quantum states without introducing errors or losing coherence. We discuss quantum error-correcting codes and fault-tolerant quantum computing, which can guarantee highly reliable quantum computation, given only moderately reliable quantum computing hardware.