Coins, Quantum Measurements, and Turing's Barrier: Preliminary Version

Abstract

For over fifty years the Turing machine model of computation has defined what it means to “compute” something; the foundations of the modern theory of computing are based on it. Computers are reading text, recognizing speech, and robots are driving themselves across Mars. Yet this exponential race will not produce solutions to many intractable/undecidable problems. Are there alternatives? Quantum computing offers one realistic alternative (see [8,10,2]). To date, quantum computing has been very successful in “beating” Turing machines in the race of solving intractable problems, with Shor and Grover algorithms achieving the most impressive successes. Is there any hope for quantum computing to challenge the Turing barrier, i.e. to solve an undecidable problem, to compute an uncomputable function? See Feynman’s argument (see [6], a paper reproduced also in [7]),regarding the possibility of simulating a quantum system on a (probabilistic) Turing machine.1 simulation. The current paper discusses solutions of a few simple problems, which suggest that quantum computing might be capable of computing uncomputable functions. In what follows a “silicon” solution is a solution tailored for a silicon (classical) computer; a “quantum” solution is a solution designed to work on a quantum computer.