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

Show simple item record Calude, C.S en Pavlov, B en 2009-04-16T23:13:43Z en 2009-04-16T23:13:43Z en 2001-06 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-156 (2001) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri en
dc.description.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. en
dc.publisher Department of Computer Science, The University of Auckland, New Zealand en
dc.relation.ispartofseries CDMTCS Research Report Series en
dc.rights.uri en
dc.source.uri en
dc.title Coins, Quantum Measurements, and Turing's Barrier: Preliminary Version en
dc.type Technical Report en
dc.subject.marsden Fields of Research::280000 Information, Computing and Communication Sciences en
dc.rights.holder The author(s) en
dc.rights.accessrights en

Files in this item

Find Full text

This item appears in the following Collection(s)

Show simple item record


Search ResearchSpace