Can quantum computing solve classically unsolvable problems?

2005/12/29 by Andrew Hodges, Hodges, Andrew
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0512248

arxiv created 2005/12/29 · arxiv updated 2009/12/01

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.

Related

• The quantum algorithm of Kieu does not solve the Hilbert's tenth problem
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Coins, Quantum Measurements, and Turing's Barrier
• Limits on Efficient Computation in the Physical World
• Quantum vs classical computation: a proposal opening a new perspective