Quantum computing

Stanford Encyclopedia of Philosophy (2015)
Michael Cuffaro
University of Western Ontario
Combining physics, mathematics and computer science, quantum computing has developed in the past two decades from a visionary idea to one of the most fascinating areas of quantum mechanics. The recent excitement in this lively and speculative domain of research was triggered by Peter Shor (1994) who showed how a quantum algorithm could exponentially "speed up" classical computation and factor large numbers into primes much more rapidly (at least in terms of the number of computational steps involved) than any known classical algorithm. Shor's algorithm was soon followed by several other algorithms that aimed to solve combinatorial and algebraic problems, and in the last few years theoretical study of quantum systems serving as computational devices has achieved tremendous progress. Common belief has it that the implementation of Shor's algorithm on a large scale quantum computer would have devastating consequences for current cryptography protocols which rely on the premiss that all known classical worst case algorithms for factoring take time exponential in the length of their input (see, e.g., Preskill 2005). Consequently, experimentalists around the world are engaged in tremendous attempts to tackle the technological difficulties that await the realization of such a large scale quantum computer. But regardless whether these technological problems can be overcome (Unruh 1995, Ekert and Jozsa 1996, Haroche and Raimond 1996), it is noteworthy that no proof exists yet for the general superiority of quantum computers over their classical counterparts.
Keywords quantum computation  algorithms  computational complexity  Church-Turing thesis
Categories (categorize this paper)
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 35,457
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

No references found.

Add more references

Citations of this work BETA

Add more citations

Similar books and articles

A Quantum Computer Only Needs One Universe.A. M. Steane - 2003 - Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 34 (3):469-478.
Quantum Algorithms: Philosophical Lessons.Amit Hagar - 2007 - Minds and Machines 17 (2):233-247.
Quantum Hypercomputation—Hype or Computation?Amit Hagar & Alex Korolev - 2007 - Philosophy of Science 74 (3):347-363.
Quantum Mechanics and Computation.Bart D’Hooghe & Jaroslaw Pykacz - 2004 - Foundations of Science 9 (4):387-404.
Quantum Computation in Brain Microtubules.Stuart R. Hameroff - 2002 - Physical Review E 65 (6):1869--1896.
Quantum Hypercomputation.Tien D. Kieu - 2002 - Minds and Machines 12 (4):541-561.


Added to PP index

Total downloads
58 ( #110,347 of 2,285,669 )

Recent downloads (6 months)
10 ( #44,819 of 2,285,669 )

How can I increase my downloads?

Monthly downloads

My notes

Sign in to use this feature