An introduction to quantum computing for non-physicists
Authors:
- Wolfgang PolakWPWolfgang Polak
Open Access
- 1 September 2000
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 32 (3) , 300-335
Abstract
Richard Feynman's observation that certain quantum mechanical effects cannot be simulated efficiently on a computer led to speculation that computation in general could be done more efficiently if it used these quantum effects. This speculation proved justified when Peter Shor described a polynomial time quantum algorithm for factoring intergers. In quantum systems, the computational space increases exponentially with the size of the system, which enables exponential parallelism. This parallelism could lead to exponentially faster quantum algorithms than possible classically. The catch is that accessing the results, which requires measurement, proves tricky and requires new nontraditional programming techniques. The aim of this paper is to guide computer scientists through the barriers that separate quantum computing from conventional computing. We introduce basic principles of quantum mechanics to explain where the power of quantum computers comes from and why it is difficult to harness. We describe quantum cryptography, teleportation, and dense coding. Various approaches to exploiting the power of quantum parallelism are explained. We conclude with a discussion of quantum error correction.Keywords
This publication has 42 references indexed in Scilit:
- Realization of Logically Labeled Effective Pure States for Bulk Quantum ComputationPhysical Review Letters, 1999
- Unconditional Security of Quantum Key Distribution over Arbitrarily Long DistancesScience, 1999
- Implementation of a quantum algorithm on a nuclear magnetic resonance quantum computerThe Journal of Chemical Physics, 1998
- Highly Structured Searches with Quantum ComputersPhysical Review Letters, 1998
- Experimental Realization of Teleporting an Unknown Pure Quantum State via Dual Classical and Einstein-Podolsky-Rosen ChannelsPhysical Review Letters, 1998
- Quantum CryptographyScientific American, 1992
- Practical quantum cryptography based on two-photon interferometryPhysical Review Letters, 1992
- Quantum cryptography using any two nonorthogonal statesPhysical Review Letters, 1992
- Quantum public key distribution reinventedACM SIGACT News, 1987
- The Feynman Lectures on Physics; Vol. IAmerican Journal of Physics, 1965