Quantum Algorithm for Hilbert's Tenth Problem

Abstract

We explore in the framework of Quantum Computation the notion of {\em Computability}, which holds a central position in Mathematics and Theoretical Computer Science. A quantum algorithm for Hilbert's tenth problem, which is equivalent to the Turing halting problem and is known to be mathematically noncomputable, is proposed where quantum continuous variables and quantum adiabatic evolution are employed. If this algorithm could be physically implemented, as much as it is valid in principle--that is, if certain hamiltonian and its ground state can be physically constructed according to the proposal--quantum computability would surpass classical computability as delimited by the Church-Turing thesis. It is thus argued that computability, and with it the limits of Mathematics, ought to be determined not solely by Mathematics itself but also by Physical Principles.

References in corpus (9)

• Quantum Mechanics helps in searching for a needle in a haystack
• Quantum Annealing in the Transverse Ising Model
• Quantum computation over continuous variables
• Robustness of adiabatic quantum computation
• Computable functions, quantum measurements, and quantum dynamics
• Non-Turing computations via Malament-Hogarth space-times
• A reformulation of Hilbert's tenth problem through Quantum Mechanics
• The Church-Turing thesis as a guiding principle for physics
• Measurability and Computability

Cited by in corpus (9)

• Solving the subset-sum problem with a light-based device
• Physically-Relativized Church-Turing Hypotheses
• Coins, Quantum Measurements, and Turing's Barrier
• Can quantum computing solve classically unsolvable problems?
• Does Quantum Mechanics allow for Infinite Parallelism?
• Transcending the Limits of Turing Computability
• A possible hypercomputational quantum algorithm
• Incompleteness, Complexity, Randomness and Beyond
• Geometric Control Methods for Quantum Computations