Shor's algorithm is a quantum algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor. It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (that is, non-quantum) algorithms. On the other hand, factoring numbers of practical significance requires far more qubits than available in the near future. Another concern is that noise in quantum circuits may undermine results, requiring additional qubits for quantum error correction.
Shor proposed multiple similar algorithms solving the factoring problem, the discrete logarithm problem, and the period finding problem. "Shor's algorithm" usually refers to his algorithm solving factoring, but may also refer to each of the three. The discrete logarithm algorithm and the factoring algorithm are instances of the period finding algorithm, and all three are instances of the hidden subgroup problem.
On a quantum computer, to factor an integer , Shor's algorithm runs in polynomial time, meaning the time taken is polynomial in , the size of the integer given as input. Specifically, it takes quantum gates of order using fast multiplication, or even utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and Van Der Hoven, thus demonstrating that the integer factorization problem can be efficiently solved on a quantum computer and is consequently in the complexity class BQP. This is significantly faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time: .
Feasibility and impact edit
If a quantum computer with a sufficient number of qubits could operate without succumbing to quantum noise and other quantum-decoherence phenomena, then Shor's algorithm could be used to break public-key cryptography schemes, such as
- The RSA scheme
- The Finite Field Diffie-Hellman key exchange
- The Elliptic Curve Diffie-Hellman key exchange
RSA is based on the assumption that factoring large integers is computationally intractable. As far as is known, this assumption is valid for classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time. However, Shor's algorithm shows that factoring integers is efficient on an ideal quantum computer, so it may be feasible to defeat RSA by constructing a large quantum computer. It was also a powerful motivator for the design and construction of quantum computers, and for the study of new quantum-computer algorithms. It has also facilitated research on new cryptosystems that are secure from quantum computers, collectively called post-quantum cryptography.
Physical implementation edit
Given the high error rates of contemporary quantum computers and too few qubits to use quantum error correction, laboratory demonstrations obtain correct results only in a fraction of attempts.
In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored into , using an NMR implementation of a quantum computer with seven qubits. After IBM's implementation, two independent groups implemented Shor's algorithm using photonic qubits, emphasizing that multi-qubit entanglement was observed when running the Shor's algorithm circuits. In 2012, the factorization of was performed with solid-state qubits. Later, in 2012, the factorization of was achieved. In 2019, an attempt was made to factor the number using Shor's algorithm on an IBM Q System One, but the algorithm failed because of accumulating errors. Though larger numbers have been factored by quantum computers using other algorithms, these algorithms are similar to classical brute-force checking of factors, so unlike Shor's algorithm, they are not expected to ever perform better than classical factoring algorithms.
Theoretical analyses of Shor's algorithm assume a quantum computer free of noise and errors. However, near-term practical implementations will have to deal with such undesired phenomena (when more qubits are available, Quantum error correction can help). In 2023, Jin-Yi Cai studied the impact of noise and concluded that "Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise."
To achieve this, Shor's algorithm consists of two parts:
- A classical reduction of the factoring problem to the problem of order-finding. This reduction is similar to that used for other factoring algorithms, such as the quadratic sieve.
- A quantum algorithm to solve the order-finding problem.
Classical reduction edit
A complete factoring algorithm is possible if we're able to efficiently factor arbitrary into just two integers and greater than 1, since if either or are not prime then the factoring algorithm can in turn be run on those until only primes remain.
A basic observation is that, using Euclid's algorithm, we can always compute the GCD between two integers efficiently. In particular, this means we can check efficiently whether is even, in which case 2 is trivially a factor. Let us thus assume that is odd for the remainder of this discussion. Afterwards, we can use efficient classical algorithms to check if is a prime power. For prime powers, efficient classical factorization algorithms exist, hence the rest of the quantum algorithm may assume that is not a prime power.
If those easy cases do not produce a nontrivial factor of , the algorithm proceeds to handle the remaining case. We pick a random integer . A possible nontrivial divisor of can be found by computing , which can be done classically and efficiently using the Euclidean algorithm. If this produces a nontrivial factor (meaning ), the algorithm is finished, and the other nontrivial factor is . If a nontrivial factor was not identified, then that means that and the choice of are coprime. Here, the algorithm runs the quantum subroutine, which will return the order of , meaning
The quantum subroutine requires that and are coprime, which is true since at this point in the algorithm, did not produce a nontrivial factor of . It can be seen from the equivalence that divides , written . This can be factored using difference of squares:
The algorithm restated shortly follows: let be odd, and not a prime power. We want to output two nontrivial factors of .
- Pick a random number .
- Compute , the greatest common divisor of and .
- If , then is a nontrivial factor of , with the other factor being and we are done.
- Otherwise, use the quantum subroutine to find the order of .
- If is odd, then go back to step 1.
- Compute . If is nontrivial, the other factor is , and we're done. Otherwise, go back to step 1.
It has been shown that this will be likely to succeed after a few runs. In practice, a single call to the quantum order-finding subroutine is enough to completely factor with very high probability of success if one uses a more advanced reduction.
Quantum order-finding subroutine edit
The goal of the quantum subroutine of Shor's algorithm is, given coprime integers and , to find the order of modulo , which is the smallest positive integer such that . To achieve this, Shor's algorithm uses a quantum circuit involving two registers. The second register uses qubits, where is the smallest integer such that . The size of the first register determines how accurate of an approximation the circuit produces. It can be shown that using qubits gives sufficient accuracy to find . The exact quantum circuit depends on the parameters and , which define the problem. In what follows, bra–ket notation will be used to denote quantum states, and will denote the tensor product rather than logical OR or logical XOR.
The algorithm consists of two main steps:
- Use quantum phase estimation with unitary representing the operation of multiplying by (modulo ), and input state (where the second register is made from qubits). The eigenvalues of this encode information about the period, and can be seen to be writable as a sum of its eigenvectors. Thanks to these properties, the quantum phase estimation stage gives as output a random integer of the form for random .
- Use the continued fractions algorithm to extract the period from the measurement outcomes obtained in the previous stage. This is a procedure to post-process (with a classical computer) the measurement data obtained from measuring the output quantum states, and retrieve the period.
Quantum phase estimation edit
In general the quantum phase estimation algorithm, for any unitary and eigenstate such that , sends inputs states into output states close to , where is an integer close to . In other words, it sends each eigenstate of into a state close to the associated eigenvalue. For the purposes of quantum order-finding, we employ this strategy using the unitary defined by the action
where the last identity follows from the geometric series formula, which implies .
Using quantum phase estimation on an input state would result in an output with each representing a superposition of integers that approximate , with the most accurate measurement having a chance of of being measured (which can be made arbitrarily high using extra qubits). Thus using as input instead, the output is a superposition of such states with . In other words, using this input amounts to running quantum phase estimation on a superposition of eigenvectors of . More explicitly, the quantum phase estimation circuit implements the transformation
Continued fraction algorithm to retrieve the period edit
Then, we apply the continued fractions algorithm to find integers and , where gives the best fraction approximation for the approximation measured from the circuit, for and coprime and . The number of qubits in the first register, , which determines the accuracy of the approximation, guarantees that
Choosing the size of the first register edit
Phase estimation requires choosing the size of the first register to determine the accuracy of the algorithm, and for the quantum subroutine of Shor's algorithm, qubits is sufficient to guarantee that the optimal bitstring measured from phase estimation (meaning the where is the most accurate approximation of the phase from phase estimation) will allow the actual value of to be recovered.
Each before measurement in Shor's algorithm represents a superposition of integers approximating . Let represent the most optimal integer in . The following theorem guarantees that the continued fractions algorithm will recover from :
Theorem — If and are bit integers, and
 As is the optimal bitstring from phase estimation, is accurate to by bits. Thus,
The bottleneck edit
The runtime bottleneck of Shor's algorithm is quantum modular exponentiation, which is by far slower than the quantum Fourier transform and classical pre-/post-processing. There are several approaches to constructing and optimizing circuits for modular exponentiation. The simplest and (currently) most practical approach is to mimic conventional arithmetic circuits with reversible gates, starting with ripple-carry adders. Knowing the base and the modulus of exponentiation facilitates further optimizations. Reversible circuits typically use on the order of gates for qubits. Alternative techniques asymptotically improve gate counts by using quantum Fourier transforms, but are not competitive with fewer than 600 qubits owing to high constants.
Period finding and discrete logarithms edit
Shor's algorithms for the discrete log and the order finding problems are instances of an algorithm solving the period finding problem.. All three are instances of the hidden subgroup problem.
Shor's algorithm for discrete logarithms edit
Given a group with order and generator , suppose we know that , for some , and we wish to compute , which is the discrete logarithm: . Consider the abelian group , where each factor corresponds to modular addition of values. Now, consider the function
This gives us an abelian hidden subgroup problem, where corresponds to a group homomorphism. The kernel corresponds to the multiples of . So, if we can find the kernel, we can find . A quantum algorithm for solving this problem exists. This algorithm is, like the factor-finding algorithm, due to Peter Shor and both are implemented by creating a superposition through using Hadamard gates, followed by implementing as a quantum transform, followed finally by a quantum Fourier transform. Due to this, the quantum algorithm for computing the discrete logarithm is also occasionally referred to as "Shor's Algorithm."
The order-finding problem can also be viewed as a hidden subgroup problem. To see this, consider the group of integers under addition, and for a given such that: , the function
For any finite abelian group , a quantum algorithm exists for solving the hidden subgroup for in polynomial time.
See also edit
- Shor, P.W. (1994). "Algorithms for quantum computation: Discrete logarithms and factoring". Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE Comput. Soc. Press. pp. 124–134. doi:10.1109/sfcs.1994.365700. ISBN 0818665807. S2CID 15291489.
- Shor, Peter W. (October 1997). "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing. 26 (5): 1484–1509. arXiv:quant-ph/9508027. doi:10.1137/S0097539795293172. ISSN 0097-5397. S2CID 2337707.
- Nielsen, Michael A.; Chuang, Isaac L. (9 December 2010). Quantum Computation and Quantum Information (PDF) (7th ed.). Cambridge University Press. ISBN 978-1-107-00217-3. Archived (PDF) from the original on 2019-07-11. Retrieved 24 April 2022.
- Gidney, Craig; Ekerå, Martin (2021). "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits". Quantum. 5: 433. arXiv:1905.09749. Bibcode:2021Quant...5..433G. doi:10.22331/q-2021-04-15-433. S2CID 162183806.
- cai, Jin-Yi (June 15, 2023). "Shor's Algorithm Does Not Factor Large Integers in the Presence of Noise". arXiv:2306.10072 [quant-ph].
- See also pseudo-polynomial time.
- Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (1996). "Efficient Networks for Quantum Factoring" (PDF). Physical Review A. 54 (2): 1034–1063. arXiv:quant-ph/9602016. Bibcode:1996PhRvA..54.1034B. doi:10.1103/PhysRevA.54.1034. PMID 9913575. S2CID 2231795.
- Harvey, David; van Der Hoeven, Joris (2020). "Integer multiplication in time O(n log n)". Annals of Mathematics. doi:10.4007/annals.2021.193.2.4. S2CID 109934776.
- "Number Field Sieve". wolfram.com. Retrieved 23 October 2015.
- Roetteler, Martin; Naehrig, Michael; Svore, Krysta M.; Lauter, Kristin E. (2017). "Quantum resource estimates for computing elliptic curve discrete logarithms". In Takagi, Tsuyoshi; Peyrin, Thomas (eds.). Advances in Cryptology – ASIACRYPT 2017 – 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3–7, 2017, Proceedings, Part II. Lecture Notes in Computer Science. Vol. 10625. Springer. pp. 241–270. arXiv:1706.06752. doi:10.1007/978-3-319-70697-9_9.
- Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H. & Chuang, Isaac L. (2001), "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance" (PDF), Nature, 414 (6866): 883–887, arXiv:quant-ph/0112176, Bibcode:2001Natur.414..883V, CiteSeerX 10.1.1.251.8799, doi:10.1038/414883a, PMID 11780055, S2CID 4400832
- Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao & Pan, Jian-Wei (2007), "Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits" (PDF), Physical Review Letters, 99 (25): 250504, arXiv:0705.1684, Bibcode:2007PhRvL..99y0504L, doi:10.1103/PhysRevLett.99.250504, PMID 18233508, S2CID 5158195
- Lanyon, B. P.; Weinhold, T. J.; Langford, N. K.; Barbieri, M.; James, D. F. V.; Gilchrist, A. & White, A. G. (2007), "Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement" (PDF), Physical Review Letters, 99 (25): 250505, arXiv:0705.1398, Bibcode:2007PhRvL..99y0505L, doi:10.1103/PhysRevLett.99.250505, hdl:10072/21608, PMID 18233509, S2CID 10010619
- Lucero, Erik; Barends, Rami; Chen, Yu; Kelly, Julian; Mariantoni, Matteo; Megrant, Anthony; O'Malley, Peter; Sank, Daniel; Vainsencher, Amit; Wenner, James; White, Ted; Yin, Yi; Cleland, Andrew N.; Martinis, John M. (2012). "Computing prime factors with a Josephson phase qubit quantum processor". Nature Physics. 8 (10): 719. arXiv:1202.5707. Bibcode:2012NatPh...8..719L. doi:10.1038/nphys2385. S2CID 44055700.
- Martín-López, Enrique; Martín-López, Enrique; Laing, Anthony; Lawson, Thomas; Alvarez, Roberto; Zhou, Xiao-Qi; O'Brien, Jeremy L. (12 October 2012). "Experimental realization of Shor's quantum factoring algorithm using qubit recycling". Nature Photonics. 6 (11): 773–776. arXiv:1111.4147. Bibcode:2012NaPho...6..773M. doi:10.1038/nphoton.2012.259. S2CID 46546101.
- Amico, Mirko; Saleem, Zain H.; Kumph, Muir (2019-07-08). "An Experimental Study of Shor's Factoring Algorithm on IBM Q". Physical Review A. 100 (1): 012305. arXiv:1903.00768. doi:10.1103/PhysRevA.100.012305. ISSN 2469-9926. S2CID 92987546.
- Karamlou, Amir H.; Simon, William A.; Katabarwa, Amara; Scholten, Travis L.; Peropadre, Borja; Cao, Yudong (2021-10-28). "Analyzing the performance of variational quantum factoring on a superconducting quantum processor". npj Quantum Information. 7 (1): 156. arXiv:2012.07825. Bibcode:2021npjQI...7..156K. doi:10.1038/s41534-021-00478-z. ISSN 2056-6387. S2CID 229156747.
- "Quantum computing motte-and-baileys". Shtetl-Optimized. 2019-12-28. Retrieved 2021-11-15.
- Bernstein, Daniel (1998). "Detecting perfect powers in essentially linear time". Mathematics of Computation. 67 (223): 1253–1283. doi:10.1090/S0025-5718-98-00952-1. ISSN 0025-5718.
- e.g., computing the first roots of , e.g., with the Newton method and checking each integer result for primality (AKS primality test).
- Ekerå, Martin (2021). "On completely factoring any integer efficiently in a single run of an order-finding algorithm". Quantum Information Processing. 20 (6) 205: 1–14. arXiv:2007.10044. Bibcode:2021QuIP...20..205E. doi:10.1007/s11128-021-03069-1. ISSN 1570-0755.
- Kitaev, A. Yu (1995-11-20). "Quantum measurements and the Abelian Stabilizer Problem". arXiv:quant-ph/9511026.
- Markov, Igor L.; Saeedi, Mehdi (2012). "Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation". Quantum Information and Computation. 12 (5–6): 361–394. arXiv:1202.6614. Bibcode:2012arXiv1202.6614M. doi:10.26421/QIC12.5-6-1. S2CID 16595181.
- Markov, Igor L.; Saeedi, Mehdi (2013). "Faster Quantum Number Factoring via Circuit Synthesis". Phys. Rev. A. 87 (1): 012310. arXiv:1301.3210. Bibcode:2013PhRvA..87a2310M. doi:10.1103/PhysRevA.87.012310. S2CID 2246117.
- Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017). "Post-quantum RSA" (PDF). Post-Quantum Cryptography. Lecture Notes in Computer Science. Vol. 10346. pp. 311–329. doi:10.1007/978-3-319-59879-6_18. ISBN 978-3-319-59878-9. Archived (PDF) from the original on 2017-04-20.
Further reading edit
- Nielsen, Michael A. & Chuang, Isaac L. (2010), Quantum Computation and Quantum Information, 10th Anniversary Edition, Cambridge University Press, ISBN 9781107002173.
- Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN 0-19-857049-X
- "Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). An alternate metaphor for the QFT was presented in one of the comments. Scott Aaronson suggests the following 12 references as further reading (out of "the 10105000 quantum algorithm tutorials that are already on the web."):
- Shor, Peter W. (1997), "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer", SIAM J. Comput., 26 (5): 1484–1509, arXiv:quant-ph/9508027v2, Bibcode:1999SIAMR..41..303S, doi:10.1137/S0036144598347011. Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
- Quantum Computing and Shor's Algorithm, Matthew Hayward's Quantum Algorithms Page, 2005-02-17, imsa.edu, LaTeX2HTML version of the original LaTeX document, also available as PDF or postscript document.
- Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
- Shor's Factoring Algorithm, Notes from Lecture 9 of Berkeley CS 294–2, dated 4 Oct 2004, 7 page postscript document.
- Chapter 6 Quantum Computation Archived 2020-04-30 at the Wayback Machine, 91 page postscript document, Caltech, Preskill, PH229.
- Quantum computation: a tutorial by Samuel L. Braunstein.
- The Quantum States of Shor's Algorithm, by Neal Young, Last modified: Tue May 21 11:47:38 1996.
- III. Breaking RSA Encryption with a Quantum Computer: Shor's Factoring Algorithm, Lecture notes on Quantum computation, Cornell University, Physics 481–681, CS 483; Spring, 2006 by N. David Mermin. Last revised 2006-03-28, 30 page PDF document.
- Lavor, C.; Manssur, L. R. U.; Portugal, R. (2003). "Shor's Algorithm for Factoring Large Integers". arXiv:quant-ph/0303175.
- Lomonaco, Jr (2000). "Shor's Quantum Factoring Algorithm". arXiv:quant-ph/0010034. This paper is a written version of a one-hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
- Chapter 20 Quantum Computation, from Computational Complexity: A Modern Approach, Draft of a book: Dated January 2007, Sanjeev Arora and Boaz Barak, Princeton University. Published as Chapter 10 Quantum Computation of Sanjeev Arora, Boaz Barak, "Computational Complexity: A Modern Approach", Cambridge University Press, 2009, ISBN 978-0-521-42426-4
- A Step Toward Quantum Computing: Entangling 10 Billion Particles Archived 2011-01-20 at the Wayback Machine, from "Discover Magazine", Dated January 19, 2011.
- Josef Gruska - Quantum Computing Challenges also in Mathematics unlimited: 2001 and beyond, Editors Björn Engquist, Wilfried Schmid, Springer, 2001, ISBN 978-3-540-66913-5
- Version 1.0.0 of libquantum: contains a C language implementation of Shor's algorithm with their simulated quantum computer library, but the width variable in shor.c should be set to 1 to improve the runtime complexity.
- PBS Infinite Series created two videos explaining the math behind Shor's algorithm, "How to Break Cryptography" and "Hacking at Quantum Speed with Shor's Algorithm".