Quantum computation and Shor's factoring algorithm
Abstract
Current technology is beginning to allow us to manipulate rather than just observe individual quantum phenomena. This opens up the possibility of exploiting quantum effects to perform computations beyond the scope of any classical computer. Recently Peter Shor discovered an efficient algorithm for factoring whole numbers, which uses characteristically quantum effects. The algorithm illustrates the potential power of quantum computation, as there is no known efficient classical method for solving this problem. The authors give an exposition of Shor's algorithm together with an introduction to quantum computation and complexity theory. They discuss experiments that may contribute to its practical implementation. [S0034-6861(96)00303-0]
Integrity signals
Registry
Cites
Statistics
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
Modular exponentiation and the inverse quantum Fourier transform take only O(l^3) operations.
“The two main components of the algorithm, modular exponentiation (computation of a x mod N ) and the inverse quantum Fourier transform (QFT) take only O ( l 3 ) operations [4, 5, 6].”
From Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance (2001) · cites this paper as [6]
Cites
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691 · see citing works
B., T. A. A. (1946) · The Mathematical Gazette · doi:10.2307/3609182 · Cited by 7,192 · see citing works
Irreversibility and heat generation in the computing process
Landauer, R. (1961) · IBM Journal of Research and Development · doi:10.1147/rd.53.0183 · Cited by 4,980 · see citing works
Quantum 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 · see citing works
Scheme for reducing decoherence in quantum computer memory
Shor, P. W. (1995) · Physical Review A · doi:10.1103/physreva.52.r2493 · Cited by 4,479 · see citing works
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 · see citing works
The Art of Computer Programming. Volume 2: Seminumerical Algorithms.
Taussky, O., & Knuth, D. E. (1970) · American Mathematical Monthly · doi:10.2307/2317055 · Cited by 3,863 · see citing works
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 · see citing works
An introduction to the theory of numbers
Hardy, G. H., & Wright, E. M. (1960) · Journal of the Franklin Institute · doi:10.1016/0016-0032(60)90676-1 · Cited by 3,686 · see citing works
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679 · see citing works
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 · see citing works
Self-citationDecoherence and the Transition from Quantum to Classical
Zurek, W. H. (1991) · Physics Today · doi:10.1063/1.881293 · Cited by 2,634 · see citing works
Brucker, P. (1995) · Springer eBooks · doi:10.1007/978-3-662-03088-2_3 · Cited by 2,296 · see citing works
The Emperor's New Mind: Concerning Computers, Minds, and The Laws of Physics
Penrose, R., & Gardner, M. (1989) · doi:10.1093/oso/9780198519737.001.0001 · Cited by 2,007 · see citing works
The thermodynamics of computation—a review
Bennett, C. H. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02084158 · Cited by 2,006 · see citing works
Feynman, R. P. (1986) · Foundations of Physics · doi:10.1007/bf01886518 · Cited by 1,770 · see citing works
DiVincenzo, D. P. (1995) · Science · doi:10.1126/science.270.5234.255 · Cited by 1,651 · see citing works
Demonstration of a Fundamental Quantum Logic Gate
Monroe, C., Meekhof, D. M., King, B. E., Itano, W. M., & Wineland, D. J. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.4714 · Cited by 1,586 · see citing works
Complexity, Entropy And The Physics Of Information
Zurek, W. H. (2018) · CRC Press eBooks · doi:10.1201/9780429502880 · Cited by 1,451 · see citing works
Measurement of Conditional Phase Shifts for Quantum Logic
Turchette, Q. A., Hood, C. J., Lange, W., Mabuchi, H., & Kimble, H. J. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.4710 · Cited by 1,409 · see citing works
Quantum computational networks
Deutsch, D. E. (1989) · Proceedings of the Royal Society of London. A. Mathematical and Physical Sciences · doi:10.1098/rspa.1989.0099 · Cited by 1,270 · see citing works
Benioff, P. (1980) · Journal of Statistical Physics · doi:10.1007/bf01011339 · Cited by 1,244 · see citing works
Proceedings 35th Annual Symposium on Foundations of Computer Science
(1994) · doi:10.1109/sfcs.1994 · Cited by 1,133 · see citing works
Schumacher, B. (1995) · Physical Review A · doi:10.1103/physreva.51.2738 · Cited by 1,090 · see citing works
Two-bit gates are universal for quantum computation
DiVincenzo, D. P. (1995) · Physical Review A · doi:10.1103/physreva.51.1015 · Cited by 1,069 · see citing works
Feynman, R. P. (1985) · Optics News · doi:10.1364/on.11.2.000011 · Cited by 1,023 · see citing works
Conditional Quantum Dynamics and Logic Gates
Barenco, A., Deutsch, D., EKERT, A. K., & Jozsa, R. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4083 · Cited by 966 · see citing works
Self-citationQuantum computers and dissipation
(1996) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1996.0029 · Cited by 899 · see citing works
Self-citationProbabilistic algorithm for testing primality
Rabin, M. O. (1980) · Journal of Number Theory · doi:10.1016/0022-314x(80)90084-0 · Cited by 878 · see citing works
Landauer, R. W. (1991) · Physics Today · doi:10.1063/1.881299 · Cited by 804 · see citing works
Quantum networks for elementary arithmetic operations
Vedral, V., Barenco, A., & EKERT, A. K. (1996) · Physical Review A · doi:10.1103/physreva.54.147 · Cited by 799 · see citing works
Self-citationAlmost Any Quantum Logic Gate is Universal
Lloyd, S. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.346 · Cited by 690 · see citing works
A Potentially Realizable Quantum Computer
Lloyd, S. (1993) · Science · doi:10.1126/science.261.5128.1569 · Cited by 649 · see citing works
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 607 · see citing works
Maintaining coherence in quantum computers
Unruh, W. G. (1995) · Physical Review A · doi:10.1103/physreva.51.992 · Cited by 594 · see citing works
Realizable Universal Quantum Logic Gates
Sleator, T., & Weinfurter, H. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4087 · Cited by 515 · see citing works
Chuang, I. L., & Yamamoto, Y. (1995) · Physical Review A · doi:10.1103/physreva.52.3489 · Cited by 437 · see citing works
Time/Space Trade-Offs for Reversible Computation
Bennett, C. H. (1989) · SIAM Journal on Computing · doi:10.1137/0218053 · Cited by 405 · see citing works
Synthesis of arbitrary quantum states via adiabatic transfer of Zeeman coherence
Parkins, A. S., Marte, P., Zoller, P., & Kimble, H. J. (1993) · Physical Review Letters · doi:10.1103/physrevlett.71.3095 · Cited by 396 · see citing works
Teleportation of an atomic state between two cavities using nonlocal microwave fields
Davidovich, L., Zagury, N., Brune, M., et al. (1994) · Physical Review A · doi:10.1103/physreva.50.r895 · Cited by 385 · see citing works
Prime Numbers and Computer Methods for Factorization
Riesel, H. (1985) · Birkhäuser Boston eBooks · doi:10.1007/978-1-4757-1089-2 · Cited by 385 · see citing works
Universality in quantum computation
Deutsch, D. E., Barenco, A., & Ekert, A. (1995) · Proceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences · doi:10.1098/rspa.1995.0065 · Cited by 346 · see citing works
Self-citationPrecision Measurement of the Proton Spin Structure Function g1p
Abe, K., Akagi, T., Anthony, P. L., et al. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.346 · Cited by 337 · see citing works
Universality in Quantum ComputationPreprint
Deutsch, D., Barenco, A., & Ekert, A. (1995) · Cited by 322 · see citing works
Self-citationBrune, M., Nussenzveig, P., Schmidt‐Kaler, F., Bernardot, F., Maali, A., Raimond, J. M., & Haroche, S. (1994) · Physical Review Letters · doi:10.1103/physrevlett.72.3339 · Cited by 251 · see citing works
A universal two-bit gate for quantum computation
Barenco, A. (1995) · Proceedings of the Royal Society of London Series A Mathematical and Physical Sciences · doi:10.1098/rspa.1995.0066 · Cited by 217 · see citing works
Number Theory in Science and Communication
Schroeder, M. R. (1984) · Springer series in information sciences · doi:10.1007/978-3-662-02395-2 · Cited by 207 · see citing works
Welsh, D. (1988) · Cited by 199 · see citing works
On Digital Signatures and Public-Key Cryptosystems.
Rivest, R. L., Adi Shamir, Z., & Adleman, L. (1977) · Defense Technical Information Center (DTIC) · Cited by 179 · see citing works
Proceedings of the 42nd ACM symposium on Theory of computing
Mitzenmacher, M., & Schulman, L. J. (2010) · Cited by 160 · see citing works
The multiple polynomial quadratic sieve
Silverman, R. D. (1987) · Mathematics of Computation · doi:10.1090/s0025-5718-1987-0866119-8 · Cited by 150 · see citing works
Lloyd, S. (1995) · Scientific American · doi:10.1038/scientificamerican1095-140 · Cited by 150 · see citing works
Computation: A Fundamental Physical View
Landauer, R. W. (1987) · Physica Scripta · doi:10.1088/0031-8949/35/1/021 · Cited by 106 · see citing works
(1989) · Choice Reviews Online · doi:10.5860/choice.26-5690a · Cited by 102 · see citing works
Berthiaume, A., & Brassard, G. (1994) · Journal of Modern Optics · doi:10.1080/09500349414552351 · Cited by 99 · see citing works
Hecht, J., & Peckham, D. C. (1987) · Physics Today · doi:10.1063/1.2820035 · Cited by 93 · see citing works
The Complexity of Boolean Networks
Dunne, P. E. S. (1988) · Medical Entomology and Zoology · Cited by 85 · see citing works
Structural basis of multistationary quantum systems. II. Effective few-particle dynamics
Teich, W. G., Obermayer, K., & Mahler, G. (1988) · Physical Review B · doi:10.1103/physrevb.37.8111 · Cited by 64 · see citing works
Characterizing classes of functions computable by quantum parallelism
Jozsa, R. (1991) · Proceedings of the Royal Society of London Series A Mathematical and Physical Sciences · doi:10.1098/rspa.1991.0161 · Cited by 59 · see citing works
Self-citationStructural basis of multistationary quantum systems. I. Effective single-particle dynamics
Obermayer, K., Teich, W. G., & Mahler, G. (1988) · Physical Review B · doi:10.1103/physrevb.37.8096 · Cited by 48 · see citing works
Quantum Mechanical Hamiltonian Models of Computersa
Benioff, P. A. (1986) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.1986.tb12450.x · Cited by 39 · see citing works
Quantum Computation <sup>a</sup>
MARGOLUS, N. (1986) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.1986.tb12451.x · Cited by 38 · see citing works
Quantum-mechanical computers and uncomputability
Lloyd, S. (1993) · Physical Review Letters · doi:10.1103/physrevlett.71.943 · Cited by 31 · see citing works
Quantum Error Correction by CodingPreprint
Chuang, I., & Laflamme, R. (1995) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9511003 · Cited by 21 · see citing works
Necessary and Sufficient Conditions for Quantum Computation
Lloyd, S. (1994) · Journal of Modern Optics · doi:10.1080/09500349414552341 · Cited by 19 · see citing works
Leutwyler, K. (1995) · Scientific American · doi:10.1038/scientificamerican1195-44 · Cited by 16 · see citing works
Flagged first, then by citations
Cited by
Sorted by citations
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 · see citing works
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Shor, P. W. (1999) · SIAM Review · doi:10.1137/s0036144598347011 · Cited by 3,904 · see citing works
A silicon-based nuclear spin quantum computer
Kane, B. E. (1998) · Nature · doi:10.1038/30156 · Cited by 3,779 · see citing works
Quantum information and computation
Bennett, C. H., & DiVincenzo, D. P. (2000) · Nature · doi:10.1038/35005001 · Cited by 3,263 · see citing works
Quantum dynamics of single trapped ions
Leibfried, D., Blatt, R., Monroe, C., & Wineland, D. (2003) · Reviews of Modern Physics · doi:10.1103/revmodphys.75.281 · Cited by 2,739 · see citing works
Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
Vandersypen, L. M. K., Steffen, M., Breyta, G., Yannoni, C. S., Sherwood, M. H., & Chuang, I. L. (2001) · Nature · doi:10.1038/414883a · Cited by 1,738 · see citing works
Bulk Spin-Resonance Quantum Computation
Gershenfeld, N. A., & Chuang, I. L. (1997) · Science · doi:10.1126/science.275.5298.350 · Cited by 1,528 · see citing works
The quantum-jump approach to dissipative dynamics in quantum optics
Plenio, M. B., & Knight, P. L. (1998) · Reviews of Modern Physics · doi:10.1103/revmodphys.70.101 · Cited by 1,515 · see citing works
Zanardi, P., & Rasetti, M. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.3306 · Cited by 1,315 · see citing works
Multiple-particle interference and quantum error correction
(1996) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1996.0136 · Cited by 1,284 · see citing works
NMR techniques for quantum control and computation
Vandersypen, L. M. K., & Chuang, I. L. (2005) · Reviews of Modern Physics · doi:10.1103/revmodphys.76.1037 · Cited by 1,217 · see citing works
Quantum computing with trapped ions
HAFFNER, H., ROOS, C., & BLATT, R. (2008) · Physics Reports · doi:10.1016/j.physrep.2008.09.003 · Cited by 1,154 · see citing works
Simulation of Many-Body Fermi Systems on a Universal Quantum Computer
Abrams, D. S., & Lloyd, S. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.2586 · Cited by 745 · see citing works
<i>Colloquium</i> : Quantum annealing and analog quantum computation
Das, A., & Chakrabarti, B. K. (2008) · Reviews of Modern Physics · doi:10.1103/revmodphys.80.1061 · Cited by 700 · see citing works
Dynamics of Loschmidt echoes and fidelity decay
Gorin, T., Prosen, T., Seligman, T. H., & Žnidarič, M. (2006) · Physics Reports · doi:10.1016/j.physrep.2006.09.003 · Cited by 623 · see citing works
Experimental realization of a quantum algorithm
Chuang, I. L., Vandersypen, L. M. K., Zhou, X., Leung, D. W., & Lloyd, S. (1998) · Nature · doi:10.1038/30181 · Cited by 604 · see citing works
Macroscopically distinct quantum-superposition states as a bosonic code for amplitude damping
Cochrane, P. T., Milburn, G. J., & Munro, W. J. (1999) · Physical Review A · doi:10.1103/physreva.59.2631 · Cited by 470 · see citing works
Optimal creation of entanglement using a two-qubit gate
Kraus, B., & Cirac, J. I. (2001) · Physical Review A · doi:10.1103/physreva.63.062309 · Cited by 432 · see citing works
Codes for the quantum erasure channel
Grassl, M., Beth, T., & Pellizzari, T. (1997) · Physical Review A · doi:10.1103/physreva.56.33 · Cited by 374 · see citing works
Quantum algorithms for algebraic problems
Childs, A. M., & van Dam, W. (2010) · Reviews of Modern Physics · doi:10.1103/revmodphys.82.1 · Cited by 344 · see citing works
Quantum systems with finite Hilbert space
Vourdas, A. (2004) · Reports on Progress in Physics · doi:10.1088/0034-4885/67/3/r03 · Cited by 321 · see citing works
Cooling the Collective Motion of Trapped Ions to Initialize a Quantum Register
King, B. E., Wood, C. S., Myatt, C. J., Turchette, Q. A., Leibfried, D., Itano, W. M., Monroe, C., & Wineland, D. J. (1998) · Physical Review Letters · doi:10.1103/physrevlett.81.1525 · Cited by 275 · see citing works
Efficient networks for quantum factoring
Beckman, D., Chari, A. N., Devabhaktuni, S., & Preskill, J. (1996) · Physical Review A · doi:10.1103/physreva.54.1034 · Cited by 268 · see citing works
Effective pure states for bulk quantum computation
Knill, E., Chuang, I., & Laflamme, R. (1998) · Physical Review A · doi:10.1103/physreva.57.3348 · Cited by 245 · see citing works
Quantum computing for healthcare: a review
Ur Rasool, R., Ahmad, H. F., Rafique, W., Qayyum, A., Qadir, J., & Anwar, Z. (2023) · Future Internet · doi:10.3390/fi15030094 · Cited by 242 · see citing works
Jones, J. A. (2001) · Progress in Nuclear Magnetic Resonance Spectroscopy · doi:10.1016/s0079-6565(00)00033-9 · Cited by 177 · see citing works
Yao.jl: Extensible, Efficient Framework for Quantum Algorithm Design
Luo, X.-Z., Liu, J.-G., Zhang, P., & Wang, L. (2020) · Quantum · doi:10.22331/q-2020-10-11-341 · Cited by 157 · see citing works
Parker, S., & Plenio, M. B. (2000) · Physical Review Letters · doi:10.1103/physrevlett.85.3049 · Cited by 130 · see citing works
Calculating the thermal rate constant with exponential speedup on a quantum computer
Lidar, D. A., & Wang, H. (1999) · Physical Review E · doi:10.1103/physreve.59.2429 · Cited by 115 · see citing works
Gerjuoy, E. (2005) · American Journal of Physics · doi:10.1119/1.1891170 · Cited by 76 · see citing works
Entanglement and the speed of evolution of multi-partite quantum systems
Zander, C., Plastino, A. R., Plastino, A., & Casas, M. (2007) · Journal of Physics A: Mathematical and Theoretical · doi:10.1088/1751-8113/40/11/020 · Cited by 52 · see citing works
Experimental and theoretical challenges for the trapped electron quantum computer
Marzoli, I., Tombesi, P., Ciaramicoli, G., Werth, G., Bushev, P., Stahl, S., Schmidt-Kaler, F., Hellwig, M., Henkel, C., Marx, G., et al. (2009) · Journal of Physics B: Atomic, Molecular and Optical Physics · doi:10.1088/0953-4075/42/15/154010 · Cited by 33 · see citing works
Barbieri, M., Cinelli, C., Martini, F., & Mataloni, P. (2006) · Laser Physics · doi:10.1134/s1054660x06100069 · Cited by 5 · see citing works
- Authors
- Ekert, A., & Jozsa, R.
- Affiliations
- University of Oxford (GB)
- Venue
- Reviews of Modern Physics
- Publisher
- American Physical Society (APS)
- Published
- 1996-07-01
- Volume
- 68
- Issue
- 3
- Pages
- 733-753
- ISSN
- 0034-6861 (ISSN-L)
- 1539-0756
- OpenAlex
- W1979260239
- Semantic Scholar
- 80d41e9c585cfb3eded63fee863f1ddcc9f5a3f3
- Cited by
- 1,354
- References
- 66
- Citations by year
- 2026: 26 · 2025: 52 · 2024: 42 · 2023: 40 · 2022: 35 · 2021: 37 · 2020: 35 · 2019: 26 · 2018: 15 · 2017: 25 · 2016: 36 · 2015: 19 · 2014: 24 · 2013: 40 · 2012: 28
- FWCI
- 81.72
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Reviews of Modern Physics (publishedVersion)
- Explore Bristol Research (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Information and Cryptography
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Mechanics and Applications
- Keywords
- quantum computing, Shor's algorithm, integer factorization, quantum algorithms, computational complexity theory, quantum computing hardware
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
