The DOI matches its Crossref record; 59 of the 59 references it cites were found in a registry or an index.
An introduction to quantum computing for non-physicists
Open accessAbstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A fast quantum mechanical algorithm for database search
Grover, L. K. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237866 · Cited by 8,830
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539795293172 · Cited by 8,472
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
B., T. A. A. (1946) · The Mathematical Gazette · doi:10.1017/s0025557200071461 · Cited by 7,129
Experimental quantum teleportation
Bouwmeester, D., Pan, J.-W., Mattle, K., Eibl, M., Weinfurter, H., & Zeilinger, A. (1997) · Nature · doi:10.1038/37539 · Cited by 5,545
The Principles of Quantum Mechanics
Dirac, P. A. M., & Polkinghorne, J. C. (1958) · Physics Today · doi:10.1063/1.3062610 · Cited by 5,409
A single quantum cannot be cloned
Wootters, W. K., & Zurek, W. H. (1982) · Nature · doi:10.1038/299802a0 · Cited by 5,406 · cited 1×
“The no cloning proof given here, originally due to Wootters and Zurek [Wootters and Zurek 1982], is a simple application of the linearity of unitary transformations.”
BackgroundQuantum theory, the Church–Turing principle and the universal quantum computer
Deutsch, D. (1985) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1985.0070 · Cited by 4,597
Elementary gates for quantum computation
Barenco, A., Bennett, C. H., Cleve, R., DiVincenzo, D. P., Margolus, N., Shor, P., Sleator, T., Smolin, J. A., & Weinfurter, H. (1995) · Physical Review A · doi:10.1103/physreva.52.3457 · Cited by 4,311
Quantum Computations with Cold Trapped Ions
Cirac, J. I., & Zoller, P. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4091 · Cited by 3,733
An introduction to the theory of numbers
(1960) · Journal of the Franklin Institute · doi:10.1016/0016-0032(60)90676-1 · Cited by 3,574
Quantum cryptography using any two nonorthogonal states
Bennett, C. H. (1992) · Physical Review Letters · doi:10.1103/physrevlett.68.3121 · Cited by 3,028
Rapid solution of problems by quantum computation
Deutsch, D., & Jozsa, R. (1992) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1992.0167 · Cited by 2,700
Unconditional Security of Quantum Key Distribution over Arbitrarily Long Distances
Lo, H.-K., & Chau, H. F. (1999) · Science · doi:10.1126/science.283.5410.2050 · Cited by 1,858
Boschi, D., Branca, S., De Martini, F., Hardy, L., & Popescu, S. (1998) · Physical Review Letters · doi:10.1103/physrevlett.80.1121 · Cited by 1,777
Feynman, R. P. (1986) · Foundations of Physics · doi:10.1007/bf01886518 · Cited by 1,770
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
(2024) · doi:10.1145/3618260 · Cited by 1,730
Bulk Spin-Resonance Quantum Computation
Gershenfeld, N. A., & Chuang, I. L. (1997) · Science · doi:10.1126/science.275.5298.350 · Cited by 1,528
Bernstein, E., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300921 · Cited by 1,503
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., & Vazirani, U. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796300933 · Cited by 1,470
Steane, A. (1998) · Reports on Progress in Physics · doi:10.1088/0034-4885/61/2/002 · Cited by 1,391
On the Power of Quantum Computation
Simon, D. R. (1997) · SIAM Journal on Computing · doi:10.1137/s0097539796298637 · Cited by 1,295
Bernstein, E., & Vazirani, U. (1993) · Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 · doi:10.1145/167088.167097 · Cited by 1,284
Unconditional security in quantum cryptography
Mayers, D. (2001) · Journal of the ACM · doi:10.1145/382780.382781 · Cited by 1,033
Feynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023
Quantum networks for elementary arithmetic operations
Vedral, V., Barenco, A., & Ekert, A. (1996) · Physical Review A · doi:10.1103/physreva.54.147 · Cited by 806
Grover’s quantum searching algorithm is optimal
Zalka, C. (1999) · Physical Review A · doi:10.1103/physreva.60.2746 · Cited by 635
The Feynman Lectures on Physics; Vol. I
Feynman, R. P., Leighton, R. B., Sands, M., & Hafner, E. M. (1965) · American Journal of Physics · doi:10.1119/1.1972241 · Cited by 607
An introduction to the theory of numbers
Hardy, G. H. (1929) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1929-04793-1 · Cited by 603
Experimental Quantum Error Correction
Cory, D. G., Price, M. D., Maas, W., Knill, E., Laflamme, R., Zurek, W. H., Havel, T. F., & Somaroo, S. S. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.2152 · Cited by 581
The development of the number field sieve
(1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091534 · Cited by 574
Complete quantum teleportation using nuclear magnetic resonance
Nielsen, M. A., Knill, E., & Laflamme, R. (1998) · Nature · doi:10.1038/23891 · Cited by 548
Feynman Lectures on Computation
Feynman, R. P. (2018) · CRC Press eBooks · doi:10.1201/9780429500442 · Cited by 522
Complete quantum teleportation using nuclear magnetic resonance
Nielsen, M. A., Knill, E., & Laflamme, R. (1998) · RePEc: Research Papers in Economics · Cited by 437
Principles of Quantum Mechanics
Basdevant, J.-L. (2016) · Graduate Texts in Physics · doi:10.1007/978-3-319-43479-7_6 · Cited by 434
Practical quantum cryptography based on two-photon interferometry
Ekert, A. K., Rarity, J. G., Tapster, P. R., & Massimo Palma, G. (1992) · Physical Review Letters · doi:10.1103/physrevlett.69.1293 · Cited by 340
Implementation of a quantum algorithm on a nuclear magnetic resonance quantum computer
Jones, J. A., & Mosca, M. (1998) · The Journal of Chemical Physics · doi:10.1063/1.476739 · Cited by 324
Bennett, C. H., Brassard, G., & Ekert, A. K. (1992) · Scientific American · doi:10.1038/scientificamerican1092-50 · Cited by 322
The ion trap quantum information processor
Steane, A. (1997) · Applied Physics B: Lasers and Optics · doi:10.1007/s003400050225 · Cited by 321
Algorithms for quantum computation: Discrete log and factoring
Shor, P. W. (1994) · Medical Entomology and Zoology · Cited by 272
Nonlinear Quantum Mechanics Implies Polynomial-Time Solution forNP-Complete and #PProblems
Abrams, D. S., & Lloyd, S. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.3992 · Cited by 249
Explorations in Quantum Computing
Williams, C. P., & Bennett, C. (1999) · Physics Today · doi:10.1063/1.882526 · Cited by 248
(2017) · Quantum Methods in Social Science · doi:10.1142/9781786342782_0004 · Cited by 245
A framework for fast quantum mechanical algorithms
Grover, L. K. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276712 · Cited by 240
EKERT, A. K., Gisin, N., Hüttner, B., Inamori, H., & Weinfurter, H. (2000) · Springer eBooks · doi:10.1007/978-3-662-04209-0_2 · Cited by 123
Nested quantum search and structured problems
Cerf, N. J., Grover, L. K., & Williams, C. P. (2000) · Physical Review A · doi:10.1103/physreva.61.032303 · Cited by 115
A general number field sieve implementation
Bernstein, D. J., & Lenstra, A. K. (1993) · Lecture notes in mathematics · doi:10.1007/bfb0091541 · Cited by 95
Generalized Grover Search Algorithm for Arbitrary Initial Amplitude Distribution
Biron, D., Biham, O., Biham, E., Grassl, M., & Lidar, D. A. (1999) · Lecture notes in computer science · doi:10.1007/3-540-49208-9_10 · Cited by 91
Scalable NMR Quantum ComputationPreprint
Schulman, L. J., & Vazirani, U. V. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9804060 · Cited by 77
NMR GHZPreprint
Laflamme, R., Knill, E. H., Zurek, W. H., Catasti, P., & Mariappan, S. (1997) · arXiv (Cornell University) · Cited by 74
Single quantum querying of a database
Terhal, B. M., & Smolin, J. A. (1998) · Physical Review A · doi:10.1103/physreva.58.1822 · Cited by 62
Highly Structured Searches with Quantum Computers
Hogg, T. (1998) · Physical Review Letters · doi:10.1103/physrevlett.80.2473 · Cited by 58
Berthiaume, A. (1997) · Springer eBooks · doi:10.1007/978-1-4612-1872-2_2 · Cited by 57
Realization of Logically Labeled Effective Pure States for Bulk Quantum Computation
Vandersypen, L. M. K., Yannoni, C. S., Sherwood, M., & Chuang, I. L. (1999) · Physical Review Letters · doi:10.1103/physrevlett.83.3085 · Cited by 56
Quantum Computing and Phase Transitions in Combinatorial Search
Hogg, T. (1996) · Journal of Artificial Intelligence Research · doi:10.1613/jair.204 · Cited by 30
Secure communications using quantum cryptography
Hughes, R., Buttler, W. T., Kwiat, P. G., Luther, G. G., Morgan, G. L., Nordholt, J. E., Peterson, C. G., & Simmons, C. M. (1997) · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · doi:10.1117/12.277644 · Cited by 24
Practical quantum cryptography for secure free-space communicationsPreprint
Hughes, R., Buttler, W. T., Kwiat, P. G., Lamoreaux, S. K., Morgan, G. L., Nordholt, J. E., & Peterson, C. G. (1999) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9905009 · Cited by 20
Relationships between quantum and classical space-bounded complexity classes
Watrous, J. (2002) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.1998.694607 · Cited by 13
Quantum Cryptography for Secure Communications to Low-Earth Orbit Satellites
Hughes, R., Buttler, W. T., Kwiat, P. G., Lamoreaux, S. K., Morgan, G. L., Peterson, C. G., Twyeffort, E., Simmons, C. M., & Nordholt, J. E. (1999) · doi:10.2172/763912 · Cited by 2
Cited by
Quantum walks: a comprehensive review
Venegas-Andraca, S. E. (2012) · Quantum Information Processing · doi:10.1007/s11128-012-0432-5 · Cited by 934
Computational Intelligence: An Introduction
Fulcher, J. (2008) · Studies in Computational Intelligence · doi:10.1007/978-3-540-78293-3_1 · Cited by 629
Information and computation: Classical and quantum aspects
Galindo, A., & Martín-Delgado, M. A. (2002) · Reviews of Modern Physics · doi:10.1103/revmodphys.74.347 · Cited by 552
Quantum computing: A taxonomy, systematic review and future directions
Gill, S. S., Kumar, A., Singh, H., Singh, M., Kaur, K., Usman, M., & Buyya, R. (2022) · Software: Practice and Experience · doi:10.1002/spe.3039 · Cited by 476
Habbal, A., Ali, M. K., & Abuzaraida, M. A. (2024) · Expert Systems with Applications · doi:10.1016/j.eswa.2023.122442 · Cited by 407
Metadata
- Authors
- Rieffel, E., & Polak, W.
- Venue
- ACM Computing Surveys
- Published
- 2000-09
- Volume
- 32
- Issue
- 3
- Pages
- 300-335
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W1597479987
- Cited by
- 407
- References
- 59
- FWCI
- 10.83
- Type
- journal article
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.