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 |