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

ResearchSpace/Manakin Repository

Show simple item record

dc.contributor.author Calude, C.S en
dc.contributor.author Pavlov, B en
dc.date.accessioned 2009-04-16T23:13:43Z en
dc.date.available 2009-04-16T23:13:43Z en
dc.date.issued 2001-06 en
dc.identifier.citation CDMTCS Research Reports CDMTCS-156 (2001) en
dc.identifier.issn 1178-3540 en
dc.identifier.uri http://hdl.handle.net/2292/3664 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 https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htm en
dc.source.uri http://www.cs.auckland.ac.nz/staff-cgi-bin/mjd/secondcgi.pl?serial 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 http://purl.org/eprint/accessRights/OpenAccess en


Full text options

This item appears in the following Collection(s)

Show simple item record

Share

Search ResearchSpace


Advanced Search

Browse