Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
The DOI matches its Crossref record; 118 of the 118 references it cites were found in a registry or an index.
Abstract
A digital computer is generally believed to be an efficient universal computing device; that is, it is believed to be able to simulate any physical computing device with an increase in computation time by at most a polynomial factor. This may not be true when quantum mechanics is taken into consideration. This paper considers factoring integers and finding discrete logarithms, two problems that are generally thought to be hard on classical computers and that have been used as the basis of several proposed cryptosystems. Efficient randomized algorithms are given for these two problems on a hypothetical quantum computer. These algorithms take a number of steps polynomial in the input size, for example, the number of digits of the integer to be factored.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
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?
In the citing paper
“Further, in the presently employed cryptography algorithms, this algorithm [52] has potential use in performing cryptanalysis where public-key cryptography could be broken.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [52]
In the citing paper
“Researchers developed the algorithm to determine the prime factors of an integer N and executed it in polynomial time.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [52]
In the citing paper
“challenged this theory and demonstrated a quantum algorithm with polynomial time.”
From Quantum Computing in the Next-Generation Computational Biology Landscape: From Protein Folding to Molecular Dynamics (2024) · cites this paper as [52]
In the citing paper
“we know of problems that are believed to be hard for classical computers, but for which quantum algorithms have been discovered that could solve these problems easily.”
From Quantum Computing in the NISQ era and beyond (2018) · cites this paper as [1]
In the citing paper
“In practice, attackers can harvest encrypted traffic today and defer decryption until future computational breakthroughs render current schemes obsolete [1,2].”
From Harvest-Now, Decrypt-Later: A Temporal Cybersecurity Risk in the Quantum Transition (2025) · cites this paper as [2]
4 more claims about this paper
Create a free account to see every claim other papers make about this one.
Citations
Cites
The Art of Computer Programming
Knuth, D. E. (1968) · Cited by 16,337
Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels
Bennett, C. H., Brassard, G., Crépeau, C., Jozsa, R., Peres, A., & Wootters, W. K. (1993) · Physical Review Letters · doi:10.1103/physrevlett.70.1895 · Cited by 13,703
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1978) · Communications of the ACM · doi:10.1145/359340.359342 · Cited by 13,462
A method for obtaining digital signatures and public-key cryptosystems
Rivest, R. L., Shamir, A., & Adleman, L. (1983) · Communications of the ACM · doi:10.1145/357980.358017 · Cited by 13,012
Algorithms for quantum computation: discrete logarithms and factoring
Shor, P. W. (2002) · Proceedings 35th Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365700 · Cited by 8,713
Self-citationQuantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2020) · arXiv · doi:10.48550/arxiv.2003.06557 · Cited by 8,299
Quantum cryptography: Public key distribution and coin tossing
Bennett, C. H., & Brassard, G. (2014) · Theoretical Computer Science · doi:10.1016/j.tcs.2014.05.025 · Cited by 8,299
On computable numbers, with an application to the entscheidungsproblem
Turing, A. M. (1937) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-42.1.230 · Cited by 8,283
Simulating physics with computers
Feynman, R. P. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf02650179 · Cited by 7,691
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238
B., T. A. A. (1946) · The Mathematical Gazette · doi:10.1017/s0025557200071461 · Cited by 7,129
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
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
Self-citationElementary 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
Self-citationQuantum Mechanics Helps in Searching for a Needle in a Haystack
Grover, L. K. (1997) · Physical Review Letters · doi:10.1103/physrevlett.79.325 · Cited by 4,306
A silicon-based nuclear spin quantum computer
Kane, B. E. (1998) · Nature · doi:10.1038/30156 · Cited by 3,779
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
Logical Reversibility of Computation
Bennett, C. H. (1973) · IBM Journal of Research and Development · doi:10.1147/rd.176.0525 · Cited by 3,679
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
Lloyd, S. (1996) · Science · doi:10.1126/science.273.5278.1073 · Cited by 3,088
Purification of Noisy Entanglement and Faithful Teleportation via Noisy Channels
Bennett, C. H., Brassard, G., Popescu, S., Schumacher, B., Smolin, J. A., & Wootters, W. K. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.722 · Cited by 2,961
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
Error Correcting Codes in Quantum Theory
Steane, A. M. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.793 · Cited by 2,677
Quantum Theory: Concepts and Methods
Peres, A., & Ballentine, L. E. (1995) · American Journal of Physics · doi:10.1119/1.17946 · Cited by 2,561
Good quantum error-correcting codes exist
Calderbank, A. R., & Shor, P. W. (1996) · Physical Review A · doi:10.1103/physreva.54.1098 · Cited by 2,516
Self-citationAn Introduction to the Theory of Numbers.
LeVeque, W. J., Niven, I., & Zuckerman, H. S. (1961) · The American Mathematical Monthly · doi:10.2307/2311171 · Cited by 1,907
Fredkin, E., & Toffoli, T. (1982) · International Journal of Theoretical Physics · doi:10.1007/bf01857727 · Cited by 1,896
Feynman, R. P. (1986) · Foundations of Physics · doi:10.1007/bf01886518 · Cited by 1,770
An Unsolvable Problem of Elementary Number Theory
Church, A. (1936) · American Journal of Mathematics · doi:10.2307/2371045 · Cited by 1,763
Quantum error correction via codes over GF(4)
Calderbank, A. R., Rains, E. M., Shor, P. M., & Sloane, N. J. A. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.681315 · Cited by 1,742
Self-citationTheory of quantum error-correcting codes
Knill, E., & Laflamme, R. (1997) · Physical Review A · doi:10.1103/physreva.55.900 · Cited by 1,593
Bulk Spin-Resonance Quantum Computation
Gershenfeld, N. A., & Chuang, I. L. (1997) · Science · doi:10.1126/science.275.5298.350 · Cited by 1,528
Toffoli, T. (1980) · Lecture Notes in Computer Science · doi:10.1007/3-540-10003-2_104 · Cited by 1,523
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
Quantum computations: algorithms and error correction
Kitaev, A. Y. (1997) · Russian Mathematical Surveys · doi:10.1070/rm1997v052n06abeh002155 · Cited by 1,424
Quantum computation and Shor's factoring algorithm
Ekert, A., & Jozsa, R. (1996) · Reviews of Modern Physics · doi:10.1103/revmodphys.68.733 · Cited by 1,354
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
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
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
Benioff, P. (1980) · Journal of Statistical Physics · doi:10.1007/bf01011339 · Cited by 1,244
Class of quantum error-correcting codes saturating the quantum Hamming bound
Gottesman, D. (1996) · Physical Review A · doi:10.1103/physreva.54.1862 · Cited by 1,227
Schnelle Multiplikation großer Zahlen
Schönhage, A., & Strassen, V. (1971) · Computing · doi:10.1007/bf02242355 · Cited by 1,107
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
Unconditional security in quantum cryptography
Mayers, D. (2001) · Journal of the ACM · doi:10.1145/382780.382781 · Cited by 1,033
Conditional Quantum Dynamics and Logic Gates
Barenco, A., Deutsch, D., Ekert, A., & Jozsa, R. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4083 · Cited by 971
Ensemble quantum computing by NMR spectroscopy
Cory, D. G., Fahmy, A. F., & Havel, T. F. (1997) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.94.5.1634 · Cited by 964
Quantum 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
Fault-tolerant quantum computation
Shor, P. W. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548464 · Cited by 892
Self-citationMultiple particle interference and quantum error correction
Steane, A. M. (1996) · Cited by 871
Quantum Error Correction and Orthogonal Geometry
Calderbank, A. R., Rains, E. M., Shor, P. W., & Sloane, N. J. A. (1997) · Physical Review Letters · doi:10.1103/physrevlett.78.405 · Cited by 811
Self-citationMultiplication of Multidigit Numbers on Automata
Karatsuba, A. A., & Ofman, Y. (1963) · Soviet physics. Doklady · Cited by 792
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
Riemann's hypothesis and tests for primality
Miller, G. L. (1976) · Journal of Computer and System Sciences · doi:10.1016/s0022-0000(76)80043-8 · Cited by 709
Almost Any Quantum Logic Gate is Universal
Lloyd, S. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.346 · Cited by 690
Quantum Theory: Concepts and Methods
Peres, A., & Mayer, M. E. (1994) · Physics Today · doi:10.1063/1.2808757 · Cited by 672
Knill, E., Laflamme, R., & Zurek, W. H. (1998) · Science · doi:10.1126/science.279.5349.342 · Cited by 663
A Potentially Realizable Quantum Computer
Lloyd, S. (1993) · Science · doi:10.1126/science.261.5128.1569 · Cited by 649
Chi-Chih Yao, A. (2002) · Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science · doi:10.1109/sfcs.1993.366852 · Cited by 633
Fault-tolerant quantum computation with constant error
Aharonov, D., & Ben-Or, M. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258579 · Cited by 631
On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
Turing, A. M. (1938) · Proceedings of the London Mathematical Society · doi:10.1112/plms/s2-43.6.544 · Cited by 600
Maintaining coherence in quantum computers
Unruh, W. G. (1995) · Physical Review A · doi:10.1103/physreva.51.992 · Cited by 594
The development of the number field sieve
(1993) · Lecture Notes in Mathematics · doi:10.1007/bfb0091534 · Cited by 574
New lower bound techniques for robot motion planning problems
Canny, J., & Reif, J. (1987) · 28th Annual Symposium on Foundations of Computer Science (sfcs 1987) · doi:10.1109/sfcs.1987.42 · Cited by 538
Simple quantum error-correcting codes
Steane, A. M. (1996) · Physical Review A · doi:10.1103/physreva.54.4741 · Cited by 522
Finite combinatory processes—formulation
Post, E. L. (1936) · Journal of Symbolic Logic · doi:10.2307/2269031 · Cited by 516
Realizable Universal Quantum Logic Gates
Sleator, T., & Weinfurter, H. (1995) · Physical Review Letters · doi:10.1103/physrevlett.74.4087 · Cited by 515
Chuang, I. L., & Yamamoto, Y. (1995) · Physical Review A · doi:10.1103/physreva.52.3489 · Cited by 434
Semiclassical Fourier Transform for Quantum Computation
Griffiths, R. B., & Niu, C.-S. (1996) · Physical Review Letters · doi:10.1103/physrevlett.76.3228 · Cited by 431
Substituting quantum entanglement for communication
Cleve, R., & Buhrman, H. (1997) · Physical Review A · doi:10.1103/physreva.56.1201 · Cited by 416
Time/Space Trade-Offs for Reversible Computation
Bennett, C. H. (1989) · SIAM Journal on Computing · doi:10.1137/0218053 · Cited by 405
Quantum mechanical Hamiltonian models of Turing machines
Benioff, P. (1982) · Journal of Statistical Physics · doi:10.1007/bf01342185 · Cited by 402
Simulating quantum systems on a quantum computer
Zalka, C. (1998) · Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences · doi:10.1098/rspa.1998.0162 · Cited by 390
Quantum vs. classical communication and computation
Buhrman, H., Cleve, R., & Wigderson, A. (1998) · Proceedings of the thirtieth annual ACM symposium on Theory of computing - STOC '98 · doi:10.1145/276698.276713 · Cited by 389
Quantum cryptography with imperfect apparatus
Mayers, D., & Yao, A. (2002) · Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280) · doi:10.1109/sfcs.1998.743501 · Cited by 381
Bennett, C. H., & Shor, P. W. (1998) · IEEE Transactions on Information Theory · doi:10.1109/18.720553 · Cited by 370
Self-citationUniversality 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
Discrete Logarithms in $GF ( P )$ Using the Number Field Sieve
Gordon, D. M. (1993) · SIAM Journal on Discrete Mathematics · doi:10.1137/0406010 · Cited by 322
Universality in Quantum Computation
Deutsch, D., Barenco, A., & EKERT, A. K. (1995) · CERN Document Server (European Organization for Nuclear Research) · Cited by 322
Quantum Mechanical Models of Turing Machines That Dissipate No Energy
Benioff, P. (1982) · Physical Review Letters · doi:10.1103/physrevlett.48.1581 · Cited by 295
Quantum Computers, Factoring, and Decoherence
Chuang, I. L., Laflamme, R., Shor, P. W., & Zurek, W. H. (1995) · Science · doi:10.1126/science.270.5242.1633 · Cited by 289
Self-citationLenstra, A. K., Lenstra, H. W., Manasse, M. S., & Pollard, J. M. (1990) · Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90 · doi:10.1145/100216.100295 · Cited by 285
Quantum Error Correction for Communication
Ekert, A., & Macchiavello, C. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.2585 · Cited by 271
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
Machine Models and Simulations
van EMDE BOAS, P. (1990) · Algorithms and Complexity · doi:10.1016/b978-0-444-88071-0.50006-0 · Cited by 248
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
Bennett, C. H. (2018) · Feynman and Computation · doi:10.1201/9780429500459-13 · Cited by 218
The complexity of analog computation
Vergis, A., Steiglitz, K., & Dickinson, B. (1986) · Mathematics and Computers in Simulation · doi:10.1016/0378-4754(86)90105-9 · Cited by 183
Machine Models and Simulation.
Boas, P. V. E. (1990) · Cited by 181
Quantum Cryptanalysis of Hidden Linear Functions
Boneh, D., & Lipton, R. J. (1995) · Lecture Notes in Computer Science · doi:10.1007/3-540-44750-4_34 · Cited by 161
(1999) · Chaos, Solitons & Fractals · doi:10.1016/s0960-0779(98)00218-5 · Cited by 145
On the power of multiplication in random access machines
Hartmanis, J., & Šimon, J. (1974) · Annual Symposium on Switching & Automata Theory · doi:10.1109/swat.1974.20 · Cited by 126
Landauer, R. (1995) · Philosophical Transactions of the Royal Society of London. Series A: Physical and Engineering Sciences · doi:10.1098/rsta.1995.0106 · Cited by 124
Efficient Simulation of Quantum Systems by Quantum Computers
Zalka, C. (1998) · Fortschritte der Physik · doi:10.1002/(sici)1521-3978(199811)46:6/8<877::aid-prop877>3.0.co;2-a · Cited by 110
Berthiaume, A., & Brassard, G. (1994) · Journal of Modern Optics · doi:10.1080/09500349414552351 · Cited by 99
Fast, Rigorous Factorization and Discrete Logarithm Algorithms
Pomerance, C. B. (1987) · Elsevier eBooks · doi:10.1016/b978-0-12-386870-1.50014-9 · Cited by 97
Schönhage, A. (1982) · Lecture notes in computer science · doi:10.1007/3-540-11607-9_1 · Cited by 93
Open problems in number theoretic complexity, II
Adleman, L. M., & McCurley, K. S. (1994) · Lecture notes in computer science · doi:10.1007/3-540-58691-1_70 · Cited by 86
Digital simulation of analog computation and Church's thesis
Rubel, L. A. (1989) · Journal of Symbolic Logic · doi:10.2307/2274761 · Cited by 79
Fast algorithms: A multitape Turing machine implementation
Schönhage, A., Grotefeld, A. F. W., & Vetter, E. (1994) · Medical Entomology and Zoology · Cited by 75
Landauer, R. W. (1995) · Springer eBooks · doi:10.1007/978-94-011-0041-0_33 · Cited by 75
The quantum challenge to structural complexity theory
Berthiaume, A., & Brassard, G. (2003) · [1992] Proceedings of the Seventh Annual Structure in Complexity Theory Conference · doi:10.1109/sct.1992.215388 · Cited by 73
A Note on Bennett’s Time-Space Tradeoff for Reversible Computation
Levine, R. Y., & Sherman, A. T. (1990) · SIAM Journal on Computing · doi:10.1137/0219046 · Cited by 71
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
Envisioning a Quantum Supercomputer
Lloyd, S. (1994) · Science · doi:10.1126/science.263.5147.695 · Cited by 60
Error Correction in Quantum Communication
EKERT, A. K., & Macchiavello, C. (1996) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9602022 · Cited by 41
MARGOLUS, N. (1986) · Annals of the New York Academy of Sciences · doi:10.1111/j.1749-6632.1986.tb12451.x · Cited by 38
Unconditional security in Quantum CryptographyPreprint
Mayers, D. (1998) · arXiv (Cornell University) · doi:10.48550/arxiv.quant-ph/9802025 · Cited by 36
The stabilisation of quantum computations
Berthiaume, A., Deutsch, D., & Jozsa, R. (2002) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1994.363698 · Cited by 35
Precision-Sensitive Euclidean Shortest Path in 3-Space
Sellen, J., Choi, J., & Yap, C.-K. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539798340205 · Cited by 28
Strengths and Weaknesses of Quantum Computing
Bennett, C. H., Bernstein, E., Brassard, G., et al. (1997) · doi:10.48550/arxiv.quant-ph/9701001 · Cited by 23
Algorithmic number theory-the complexity contribution
Adleman, L. M. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1994.365702 · Cited by 22
Goodrich, M. T. (1993) · ACM SIGACT News · doi:10.1145/164996.165002 · Cited by 14
Precision-sensitive Euclidean shortest path in 3-space (extended abstract)
Choi, J., Sellen, J., & Yap, C.-K. (1995) · Annual Symposium on Computational Geometry (SoCG) · doi:10.1145/220279.220317 · Cited by 14
Can quantum computers have simple Hamiltonians?
Biafore, M. (2002) · Workshop on Physics and Computation (PhysComp) · doi:10.1109/phycmp.1994.363697 · Cited by 11
Motional quantum error correction
Steinbach, J., & Twamley, J. (2000) · Journal of Modern Optics · doi:10.1080/09500340008244053 · Cited by 6
Two Non-Standard Paradigms for Computation: Analog Machines and Cellular Automata
Steiglitz, K. (1988) · Springer eBooks · doi:10.1007/978-94-009-2794-0_11 · Cited by 3
Research works printed but not linked: 10
- Brassard G., 1993, SIGACT News, 24, 16
- R. Cleve (1994), A note on computing Fourier transforms by quantum programs , preprint.
- originally published in Optics News (February 1985), pp. 11–20.
- Karatsuba A., 1962, Dokl. Akad. Nauk SSSR, 145, 293
- 1963, Sov. Phys. Dokl., 7, 595
- R. Landauer (1997), Is quantum mechanically coherent computation useful? , in Proc. Drexel‐4 Symposium on Quantum Nonintegrability—Quantum Classical Correspondence, D. H. Feng and B‐L. Hu, eds., International Press, Cambridge, MA, to appear.
- Lecerf Y., 1963, C. R. Acad. Française Sci., 257, 2597
- N. Margolus (1990), Parallel quantum computation , in Complexity, Entropy and the Physics of Information, Santa Fe Institute Studies in the Sciences of Complexity, Vol. VIII, W. H. Zurek, ed., Addison‐Wesley, Reading, MA, pp. 273–287.
- P. W. Shor (1998) Quantum computing Documenta Mathematica, Extra Volume Proceedings ICM, Vol. I, pp. 305–324.
- 10.1112/plms/s2-43.6.544 · DOI · Paper page
Cited by
Quantum Computing in the NISQ era and beyond
Preskill, J. (2018) · Quantum · doi:10.22331/q-2018-08-06-79 · Cited by 8,830
Noisy intermediate-scale quantum algorithms
Bharti, K., Cervera-Lierta, A., Kyaw, T. H., Haug, T., Alperin-Lea, S., Anand, A., Degroote, M., Heimonen, H., Kottmann, J. S., Menke, T., et al. (2022) · Reviews of Modern Physics · doi:10.1103/revmodphys.94.015004 · Cited by 2,231
Advances in quantum cryptography
Pirandola, S., Andersen, U. L., Banchi, L., Berta, M., Bunandar, D., Colbeck, R., Englund, D., Gehring, T., Lupo, C., Ottaviani, C., et al. (2020) · Advances in Optics and Photonics · doi:10.1364/aop.361502 · Cited by 2,033
Quantum random walks: An introductory overview
Kempe, J. (2003) · Contemporary Physics · doi:10.1080/00107151031000110776 · Cited by 1,413
Suppressing quantum errors by scaling a surface code logical qubit
Google Quantum, A. I., Acharya, R., Aleiner, I., Allen, R., Andersen, T. I., Ansmann, M., Arute, F., Arya, K., Asfaw, A., Atalaya, J., et al. (2023) · Nature · doi:10.1038/s41586-022-05434-1 · Cited by 1,103
Metadata
- Authors
- Shor, P. W.
- Corresponding author
- Shor, Peter W.
- ORCID
- Shor, Peter W.
- Venue
- SIAM Review
- Published
- 1999-01
- Volume
- 41
- Issue
- 2
- Pages
- 303-332
- ISSN
- 0036-1445 (ISSN-L)
- 1095-7200
- OpenAlex
- W2137147061
- Cited by
- 3,904
- References
- 115
- Citations by year
- 2026: 326 · 2025: 550 · 2024: 481 · 2023: 463 · 2022: 405 · 2021: 355 · 2020: 271 · 2019: 195 · 2018: 151 · 2017: 124 · 2016: 70 · 2015: 47 · 2014: 40 · 2013: 56 · 2012: 44
- FWCI
- 21.03
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- SIAM Review (publishedVersion)
- CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Physics and Astronomy › Atomic and Molecular Physics, and Optics › Quantum Information and Cryptography
- Physical Sciences › Computer Science › Information Systems › Cryptography and Residue Arithmetic
- Keywords
- quantum computing, integer factorization, discrete logarithm problem, polynomial-time algorithms, randomized algorithms, ciphers, computational complexity, quantum algorithms
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.