View source for Shor's algorithm

{{Short description|Quantum algorithm for integer factorization}}'''Shor's algorithm''' is a [[quantum algorithm]] for finding the [[prime factor]]s of an integer. It was developed in 1994 by the American mathematician [[Peter Shor]].<ref>{{cite book |doi=10.1109/sfcs.1994.365700 |chapter=Algorithms for quantum computation: Discrete logarithms and factoring |title=Proceedings 35th Annual Symposium on Foundations of Computer Science |date=1994 |last1=Shor |first1=P.W. |pages=124–134 |isbn=978-0-8186-6580-6 }}</ref><ref name="siam">{{Cite journal |last=Shor |first=Peter W. |date=October 1997 |title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer |journal=SIAM Journal on Computing |volume=26 |issue=5 |pages=1484–1509 |arxiv=quant-ph/9508027 |doi=10.1137/S0097539795293172 |s2cid=2337707 }}</ref> It is one of the few known quantum algorithms with compelling potential applications and strong evidence of superpolynomial speedup compared to best known classical (non-quantum) algorithms.<ref name=":0" /> On the other hand, factoring numbers of practical significance requires far more [[qubit|qubits]] than available in the near future.<ref name="q2000">{{cite journal|arxiv=1905.09749| title = 
How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits |
first1 = Craig | last1 = Gidney | first2 = Martin | last2 = Ekerå| journal=Quantum | year=2021 | volume=5 | page=433 | doi=10.22331/q-2021-04-15-433 | bibcode = 
2021Quant...5..433G | s2cid=162183806 }}
</ref> Another concern is that noise in quantum circuits may undermine results,<ref name="noise"/> requiring additional qubits for [[quantum error correction]].

Shor proposed multiple similar algorithms for solving the [[Integer factorization|factoring problem]], the [[Discrete logarithm|discrete logarithm problem]], and the period-finding problem. "Shor's algorithm" usually refers to the factoring algorithm, but may refer to any of the three algorithms. 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 <math> N </math>, Shor's algorithm runs in [[polynomial time]], meaning the time taken is polynomial in <math> \log N </math>.<ref>See also [[pseudo-polynomial time]].</ref> It takes [[quantum logic gate|quantum gates]] of order <math> O \! \left((\log N)^{2} (\log \log N) (\log \log \log N) \right) </math> using fast multiplication,<ref name="Beckman">{{cite journal |last1=Beckman |first1=David |last2=Chari |first2=Amalavoyal N. |last3=Devabhaktuni |first3=Srikrishna |last4=Preskill |first4=John |title=Efficient networks for quantum factoring |journal=Physical Review A |date=August 1996 |volume=54 |issue=2 |pages=1034–1063 |doi=10.1103/physreva.54.1034 |pmid=9913575 |arxiv=quant-ph/9602016 |bibcode=1996PhRvA..54.1034B }}</ref> or even <math> O \! \left((\log N)^{2} (\log \log N) \right) </math> utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and [[Van Der Hoven]],<ref name="Integer multiplication in time <math">{{cite journal |last1=Harvey |first1=David |last2=van der Hoeven |first2=Joris |title=Integer multiplication in time O (n log n) |journal=Annals of Mathematics |date=March 2021 |volume=193 |issue=2 |doi=10.4007/annals.2021.193.2.4 |url=https://hal.science/hal-02070778v2/file/nlogn.pdf }}</ref> 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 [[Time complexity#Sub-exponential time|sub-exponential time]]: <math> O \! \left(e^{1.9 (\log N)^{1/3} (\log \log N)^{2/3}} \right) </math>.<ref>{{cite web|url = http://mathworld.wolfram.com/NumberFieldSieve.html|title = Number Field Sieve|work = wolfram.com|access-date = 23 October 2015}}</ref>

== Feasibility and impact ==

If a quantum computer with a sufficient number of [[qubit]]s could operate without succumbing to [[quantum noise]] and other [[quantum decoherence|quantum-decoherence]] phenomena, then Shor's algorithm could be used to break [[public-key cryptography]] schemes, such as

* The [[RSA (cryptosystem)|RSA]] scheme
* The Finite Field [[Diffie-Hellman]] key exchange
* The Elliptic Curve Diffie-Hellman key exchange<ref>{{cite conference
 | last1 = Roetteler | first1 = Martin
 | last2 = Naehrig | first2 = Michael
 | last3 = Svore | first3 = Krysta M. | author3-link = Krysta Svore
 | last4 = Lauter | first4 = Kristin E. | author4-link = Kristin Lauter
 | editor1-last = Takagi | editor1-first = Tsuyoshi
 | editor2-last = Peyrin | editor2-first = Thomas
 | arxiv = 1706.06752
 | contribution = Quantum resource estimates for computing elliptic curve discrete logarithms
 | doi = 10.1007/978-3-319-70697-9_9
 | pages = 241–270
 | publisher = Springer
 | series = Lecture Notes in Computer Science
 | title = 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
 | volume = 10625
 | year = 2017| isbn = 978-3-319-70696-2
 }}</ref>

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 ===
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 <math> 15 </math> into <math> 3 \times 5 </math>, using an [[Nuclear magnetic resonance quantum computer|NMR implementation]] of a quantum computer with seven qubits.<ref name = "VSBYSC01">{{cite journal |last1=Vandersypen |first1=Lieven M. K. |last2=Steffen |first2=Matthias |last3=Breyta |first3=Gregory |last4=Yannoni |first4=Costantino S. |last5=Sherwood |first5=Mark H. |last6=Chuang |first6=Isaac L. |title=Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance |journal=Nature |date=December 2001 |volume=414 |issue=6866 |pages=883–887 |doi=10.1038/414883a |pmid=11780055 |arxiv=quant-ph/0112176 |bibcode=2001Natur.414..883V }}</ref> After IBM's implementation, two independent groups implemented Shor's algorithm using [[Photonics|photonic]] qubits, emphasizing that multi-qubit [[quantum entanglement|entanglement]] was observed when running the Shor's algorithm circuits.<ref name = "LBYP07">{{cite journal |last1=Lu |first1=Chao-Yang |last2=Browne |first2=Daniel E. |last3=Yang |first3=Tao |last4=Pan |first4=Jian-Wei |title=Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits |journal=Physical Review Letters |date=19 December 2007 |volume=99 |issue=25 |page=250504 |doi=10.1103/PhysRevLett.99.250504 |pmid=18233508 |arxiv=0705.1684 |bibcode=2007PhRvL..99y0504L }}</ref><ref name = "LWLBJGW07">{{cite journal |last1=Lanyon |first1=B. P. |last2=Weinhold |first2=T. J. |last3=Langford |first3=N. K. |last4=Barbieri |first4=M. |last5=James |first5=D. F. V. |last6=Gilchrist |first6=A. |last7=White |first7=A. G. |title=Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement |journal=Physical Review Letters |date=19 December 2007 |volume=99 |issue=25 |page=250505 |doi=10.1103/PhysRevLett.99.250505 |pmid=18233509 |arxiv=0705.1398 |bibcode=2007PhRvL..99y0505L }}</ref> In 2012, the factorization of <math> 15 </math> was performed with solid-state qubits.<ref>{{Cite journal|last1 = Lucero|first1 = Erik|last2 = Barends|first2 = Rami|last3 = Chen|first3 = Yu|last4 = Kelly|first4 = Julian|last5 = Mariantoni|first5 = Matteo|last6 = Megrant|first6 = Anthony|last7 = O'Malley|first7 = Peter|last8 = Sank|first8 = Daniel|last9 = Vainsencher|first9 = Amit|last10 = Wenner|first10 = James|last11 = White|first11 = Ted|last12 = Yin|first12 = Yi|last13 = Cleland|first13 = Andrew N.|last14 = Martinis|first14 = John M.|title = Computing prime factors with a Josephson phase qubit quantum processor|journal = Nature Physics|volume = 8|issue = 10|pages = 719|year = 2012|doi = 10.1038/nphys2385|bibcode = 2012NatPh...8..719L|arxiv = 1202.5707|s2cid = 44055700}}</ref> Later, in 2012, the factorization of <math> 21 </math> was achieved.<ref>{{cite journal|last1 = Martín-López|first1 = Enrique|last2 = Martín-López|first2 = Enrique|last3 = Laing|first3 = Anthony|last4 = Lawson|first4 = Thomas|last5 = Alvarez|first5 = Roberto|last6 = Zhou|first6 = Xiao-Qi|last7 = O'Brien|first7 = Jeremy L.|title = Experimental realization of Shor's quantum factoring algorithm using qubit recycling|journal = Nature Photonics|volume =6|issue = 11|pages = 773–776|date = 12 October 2012|doi = 10.1038/nphoton.2012.259|arxiv = 1111.4147|bibcode = 2012NaPho...6..773M|s2cid = 46546101}}</ref> In 2016, the factorization of <math> 15 </math> was performed again using trapped-ion qubits with a recycling technique.<ref>{{cite journal|last1 = Monz|first1 = Thomas |last2 = Nigg|first2 = Daniel|last3 = Martinez|first3 = Esteban A.|last4 = Brandl|first4 = Matthias F.|last5 = Schindler|first5 = Philipp|last6 = Rines|first6 = Richard|last7 = Wang|first7 = Shannon X.|last8 = Chuang|first8 = Isaac L.|last9 = Blatt|first9 = Rainer|title = Realization of a scalable Shor algorithm|journal = Science|volume =351|issue = 6277|pages = 1068–1070|date = 4 March 2016|doi = 10.1126/science.aad9480|pmid = 26941315 |arxiv = 1507.08852|bibcode = 2016Sci...351.1068M|s2cid = 17426142}}</ref> In 2019, an attempt was made to factor the number <math> 35 </math> using Shor's algorithm on an IBM [[IBM Q System One|Q System One]], but the algorithm failed because of accumulating errors.<ref>{{cite journal |last1=Amico |first1=Mirko |last2=Saleem |first2=Zain H. |last3=Kumph |first3=Muir |title=Experimental study of Shor's factoring algorithm using the IBM Q Experience |journal=Physical Review A |date=8 July 2019 |volume=100 |issue=1 |page=012305 |doi=10.1103/PhysRevA.100.012305 |arxiv=1903.00768 |bibcode=2019PhRvA.100a2305A |s2cid=92987546 }}</ref> However, all these demonstrations have compiled the algorithm by making use of prior knowledge of the answer, and some have even oversimplified the algorithm in a way that makes it equivalent to coin flipping.<ref>{{cite journal |last1=Smolin |first1=John A. |last2=Smith |first2=Graeme |last3=Vargo |first3=Alexander |title=Oversimplifying quantum factoring |journal=Nature |date=July 2013 |volume=499 |issue=7457 |pages=163–165 |doi=10.1038/nature12290 |pmid=23846653 |arxiv=1301.7007 |bibcode=2013Natur.499..163S }}</ref> Furthermore, attempts using quantum computers with other algorithms have been made.<ref>{{cite journal |last1=Karamlou |first1=Amir H. |last2=Simon |first2=William A. |last3=Katabarwa |first3=Amara |last4=Scholten |first4=Travis L. |last5=Peropadre |first5=Borja |last6=Cao |first6=Yudong |title=Analyzing the performance of variational quantum factoring on a superconducting quantum processor |journal=npj Quantum Information |date=28 October 2021 |volume=7 |issue=1 |page=156 |doi=10.1038/s41534-021-00478-z |arxiv=2012.07825 |bibcode=2021npjQI...7..156K }}</ref> However, 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.<ref>{{Cite web|date=2019-12-28|title=Quantum computing motte-and-baileys|url=https://scottaaronson.blog/?p=4447|access-date=2021-11-15|website=Shtetl-Optimized|language=en-US}}</ref>

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]] showed that in the presence of noise, Shor's algorithm fails [[asymptotically almost surely]] for large semiprimes that are products of two primes in {{OEIS el|A073024}}.<ref name="noise">{{cite journal |arxiv=2306.10072 |last1=Cai |first1=Jin-Yi |date=2024 |title=Shor's algorithm does not factor large integers in the presence of noise |journal=Science China Information Sciences |volume=67 |issue=7 |doi=10.1007/s11432-023-3961-3 }}</ref> These primes <math>p</math> have the property that <math>p-1</math> has a prime factor larger than <math>p^{2/3}</math>, and have a positive density in the set of all primes. Hence error-correction will be needed to be able to factor all numbers with Shor's algorithm.

== Algorithm ==
The problem that we are trying to solve is: ''given an odd [[composite number]] <math> N </math>, find its [[Integer factorization|integer factors]]''.

To achieve this, Shor's algorithm consists of two parts:

# A classical reduction of the factoring problem to the problem of [[Order (group theory)|order]]-finding. This reduction is similar to that used for other [[integer factorization|factoring algorithms]], such as the [[quadratic sieve]].
# A quantum algorithm to solve the order-finding problem.

=== Classical reduction ===
A complete factoring algorithm is possible if we're able to efficiently factor arbitrary <math> N </math> into just two integers <math> p </math> and <math> q </math> greater than 1, since if either <math> p </math> or <math> q </math> are not prime then the factoring algorithm can in turn be run on those until only primes remain.

A basic observation is that, using [[Euclidean algorithm|Euclid's algorithm]], we can always compute the [[Greatest common divisor|GCD]] between two integers efficiently. In particular, this means we can check efficiently whether <math> N </math> is even, in which case 2 is trivially a factor. Let us thus assume that <math> N </math> is odd for the remainder of this discussion. Afterwards, we can use efficient classical algorithms to check if <math> N </math> is a [[prime power]].<ref>{{cite journal |last1=Bernstein |first1=Daniel |title=Detecting perfect powers in essentially linear time |journal=Mathematics of Computation |date=1998 |volume=67 |issue=223 |pages=1253–1283 |doi=10.1090/S0025-5718-98-00952-1 }}</ref> For prime powers, efficient classical factorization algorithms exist,<ref>e.g., computing the first <math>\log_2(N)</math> roots of <math>N</math>, e.g., with the [[Nth_root#Computing_principal_roots|Newton method]] and checking each integer result for primality ([[AKS primality test]]).</ref> hence the rest of the quantum algorithm may assume that <math> N </math> is not a prime power.

If those easy cases do not produce a nontrivial factor of <math> N </math>, the algorithm proceeds to handle the remaining case. We pick a random integer <math> 2 \leq a < N </math>. A possible nontrivial divisor of <math> N </math> can be found by computing <math> \gcd(a, N) </math>, which can be done classically and efficiently using the [[Euclidean algorithm]]. If this produces a nontrivial factor (meaning <math> \gcd(a, N) \ne 1 </math>), the algorithm is finished, and the other nontrivial factor is <math display="inline"> \frac{N}{\gcd(a,N)} </math>. If a nontrivial factor was not identified, then that means that <math> N </math> and the choice of <math> a </math> are [[coprime]], so <math>a</math> is contained in the [[multiplicative group of integers modulo n|multiplicative group of integers modulo <math>N</math>]], having a [[multiplicative inverse]] modulo <math>N</math>. Thus, <math>a</math> has a [[multiplicative order]] <math> r </math> modulo <math>N</math>, meaning
:<math>
a^{r} \equiv 1 \bmod N
</math>
and <math>r</math> is the smallest positive integer satisfying this congruence.

The quantum subroutine finds <math>r</math>. It can be seen from the congruence that <math> N </math> [[divides]] <math> a^{r} - 1 </math>, written <math> N \mid a^{r} - 1 </math>. This can be factored using [[difference of squares]]:<math display="block"> N \mid (a^{r/2} - 1)(a^{r/2} + 1)</math> Since we have factored the expression in this way, the algorithm doesn't work for odd <math> r </math> (because <math> a^{r/2} </math> must be an integer), meaning the algorithm would have to restart with a new <math> a </math>. Hereafter we can therefore assume <math> r </math> is even. It cannot be the case that <math> N \mid a^{r/2} - 1 </math>, since this would imply <math>
a^{r/2} \equiv 1 \bmod N
</math>, which would contradictorily imply that <math display="inline"> \frac{r}{2} </math> would be the order of <math> a </math>, which was already <math> r </math>. At this point, it may or may not be the case that <math> N \mid a^{r/2} + 1 </math>. If it is not true that <math> N \mid a^{r/2} + 1 </math>, then that means we are able to find a nontrivial factor of <math> N </math>. We compute<math display="block"> d = \gcd(N, a^{r/2} - 1) </math>If <math> d = 1 </math>, then that means <math> N \mid a^{r/2} + 1 </math> was true, and a nontrivial factor of <math> N </math> cannot be achieved from <math> a </math>, and the algorithm must restart with a new <math> a </math>. Otherwise, we have found a nontrivial factor of <math> N </math>, with the other being <math display="inline"> \frac{N}{d} </math>, and the algorithm is finished. For this step, it is also equivalent to compute <math> \gcd(N, a^{r/2} + 1) </math>; it will produce a nontrivial factor if <math> \gcd(N, a^{r/2} - 1) </math> is nontrivial, and will not if it's trivial (where <math> N \mid a^{r/2} + 1 </math>).

The algorithm restated shortly follows: let <math display="inline"> N </math> be odd, and not a prime power. We want to output two nontrivial factors of <math  display="inline"> N </math>.
{{ordered list|Pick a random number <math  display="inline"> 1 < a < N </math>.|Compute <math> K=\gcd(a,N) </math>, the [[greatest common divisor]] of <math> a </math> and <math> N </math>.|If <math> K \neq 1 </math>, then <math>K</math> is a [[nontrivial]] factor of <math> N </math>, with the other factor being <math display="inline">\frac{N}{K}</math> and we are done.|Otherwise, use the quantum subroutine to find the order <math> r </math> of <math>a</math>.|If <math> r </math> is odd, then go back to step 1.|Compute <math>g = \gcd(N, a^{r/2} + 1)</math>. If <math>g </math> is nontrivial, the other factor is <math display="inline">\frac{N}{g}</math>, 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.<ref name="siam"/> In practice, a single call to the quantum order-finding subroutine is enough to completely factor <math>N</math> with very high probability of success if one uses a more advanced reduction.<ref name="Ekerå21">{{cite journal |last1=Ekerå |first1=Martin |title=On completely factoring any integer efficiently in a single run of an order-finding algorithm |journal=Quantum Information Processing |date=June 2021 |volume=20 |issue=6 |page=205 |doi=10.1007/s11128-021-03069-1 |arxiv=2007.10044 |bibcode=2021QuIP...20..205E |doi-access=free }}</ref>

=== Quantum order-finding subroutine ===
The goal of the quantum subroutine of Shor's algorithm is, given [[coprime integers]] <math> N </math> and <math> 1< a<N </math>, to find the [[Multiplicative order|order <math> r </math> of <math>a</math> modulo <math>N</math>]], which is the smallest positive integer such that <math>a^r \equiv 1 \pmod N</math>. To achieve this, Shor's algorithm uses a quantum circuit involving two registers. The second register uses <math> n </math> qubits, where <math> n </math> is the smallest integer such that <math> N\le 2^n </math>, i.e., <math> n = \left \lceil {\log_2N} \right \rceil </math>. The size of the first register determines how accurate of an approximation the circuit produces. It can be shown that using <math> 2n </math> qubits gives sufficient accuracy to find <math> r </math>. The exact quantum circuit depends on the parameters <math>a</math> and <math>N</math>, which define the problem. The following description of the algorithm uses [[bra–ket notation]] to denote quantum states, and <math>\otimes</math> to denote the [[tensor product]], rather than [[logical AND]].

The algorithm consists of two main steps:

# Use [[Quantum phase estimation algorithm|quantum phase estimation]] with unitary <math>U</math> representing the operation of multiplying by <math>a</math> (modulo <math>N</math>), and input state <math>|0\rangle^{\otimes 2 n}\otimes|1\rangle</math> (where the second register is <math>|1\rangle</math> made from <math>n</math> qubits). The eigenvalues of this <math>U</math> encode information about the period, and <math>|1\rangle</math> 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 <math>\frac{j}{r} 2^{2n}</math> for random <math>j=0,1,...,r-1</math>.
# Use the [[simple continued fraction|continued fractions algorithm]] to extract the period <math>r</math> 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.

The connection with quantum phase estimation was not discussed in the original formulation of Shor's algorithm,<ref name="siam" /> but was later proposed by Kitaev.<ref>{{cite arXiv |eprint=quant-ph/9511026 |last1=Kitaev |first1=A. Yu |date=1995 |title=Quantum measurements and the Abelian Stabilizer Problem }}</ref>

==== Quantum phase estimation ====
[[File:Shor's algorithm.svg|426x426px|thumb|center|Quantum subroutine in Shor's algorithm]]
In general the [[quantum phase estimation algorithm]], for any unitary <math>U</math> and eigenstate <math>|\psi\rangle</math> such that <math>U|\psi\rangle=e^{2\pi i\theta} |\psi\rangle</math>, sends input states <math>|0\rangle|\psi\rangle</math> to output states close to <math>|\phi\rangle|\psi\rangle</math>, where <math>\phi</math> is an integer close to <math>2^{2n} \theta</math>. In other words, it sends each eigenstate <math>|\psi_j\rangle</math> of <math>U</math> to 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<math display="block">U|k\rangle = \begin{cases} |ak \pmod N\rangle & 0 \le k < N, \\ |k\rangle & N \le k < 2^n.\end{cases}</math>The action of <math>U</math> on states <math>|k\rangle</math> with <math> N \leq k < 2^n </math> is not crucial to the functioning of the algorithm, but needs to be included to ensure the overall transformation is a well-defined quantum gate. Implementing the circuit for quantum phase estimation with <math>U</math> requires being able to efficiently implement the gates <math> U^{2^j} </math>. This can be accomplished via [[modular exponentiation]], which is the slowest part of the algorithm.
The gate thus defined satisfies <math>U^r=I</math>, which immediately implies that its eigenvalues are the <math>r</math>-th [[Root of unity|roots of unity]] <math>\omega_r^k=e^{2\pi ik/r} </math>. Furthermore, each eigenvalue <math>\omega_r^j</math> has an eigenvector of the form <math display="inline">|\psi_j\rangle=r^{-1/2}\sum_{k=0}^{r-1}\omega_r^{-kj}|a^k\rangle </math>, and these eigenvectors are such that<math display="block">\begin{align}
\frac{1}{\sqrt{r}} \sum_{j = 0}^{r - 1} |\psi_j\rangle &= \frac{1}{r} \sum_{j = 0}^{r - 1} \sum_{k = 0}^{r - 1} \omega_r^{jk}|a^k\rangle \\
&= |1\rangle + \frac{1}{r} \sum_{k = 1}^{r - 1} \left(\sum_{j = 0}^{r - 1} \omega_r^{jk} \right) |a^k\rangle =|1\rangle,
\end{align} </math>


where the last identity follows from the [[geometric series]] formula, which implies <math display="inline">\sum_{j = 0}^{r - 1} \omega_r^{jk} = 0</math>.

Using [[Quantum phase estimation algorithm|quantum phase estimation]] on an input state <math>|0\rangle^{\otimes 2 n}|\psi_j\rangle</math> would then return the integer <math>2^{2n} j/r  </math> with high probability. More precisely, the quantum phase estimation circuit sends <math>|0\rangle^{\otimes 2 n}|\psi_j\rangle</math> to <math>|\phi_j\rangle|\psi_j\rangle  </math> such that the resulting probability distribution <math>p_k \equiv|\langle k|\phi_j\rangle|^2     </math> is peaked around <math display="inline">k=2^{2n} j/r </math>, with <math display="inline">p_{2^{2n}j/r}\ge \frac{4}{\pi^2} \approx 0.4053 </math>. This probability can be made arbitrarily close to 1 using extra qubits.

Applying the above reasoning to the input <math>|0\rangle^{\otimes 2 n}|1\rangle</math>, quantum phase estimation thus results in the evolution<math display="block">|0\rangle^{\otimes 2 n}|1\rangle = \frac{1}{\sqrt{r}} \sum_{j = 0}^{r - 1} |0\rangle^{\otimes 2 n} |\psi_j\rangle \to \frac{1}{\sqrt{r}} \sum_{j = 0}^{r - 1} |\phi_j\rangle|\psi_j\rangle. </math>Measuring the first register, we now have a balanced probability <math>1/r</math> to find each <math>|\phi_j\rangle</math>, each one giving an integer approximation to <math>2^{2 n} j/r</math>, which can be divided by <math>2^{2n}</math> to get a decimal approximation for <math>j/r</math>.

==== Continued fraction algorithm to retrieve the period ====
Then, we apply the [[continued fraction]]s algorithm to find integers <math display="inline">b</math> and <math display="inline">c</math>, where <math display="inline">\frac{b}{c}</math> gives the best fraction approximation for the approximation measured from the circuit, for <math display="inline">b, c < N</math> and [[Coprime integers|coprime]] <math display="inline">b</math> and <math display="inline">c</math>. The number of qubits in the first register, <math>2n</math>, which determines the accuracy of the approximation, guarantees that<math display="block">\frac{b}{c} = \frac{j}{r}</math>given the best approximation from the superposition of <math display="inline">|\phi_j\rangle</math> was measured<ref name="siam"/> (which can be made arbitrarily likely by using extra bits and truncating the output). However, while <math display="inline">b</math> and <math display="inline">c</math> are coprime, it may be the case that <math display="inline">j</math> and <math display="inline">r</math> are not coprime. Because of that, <math display="inline">b</math> and <math display="inline">c</math> may have lost some factors that were in <math display="inline">j</math> and <math display="inline">r</math>. This can be remedied by rerunning the quantum order-finding subroutine an arbitrary number of times, to produce a list of fraction approximations<math display="block">\frac{b_1}{c_1}_{\textstyle ,} \; \frac{b_2}{c_2}_{\textstyle ,} \ldots \vphantom{\frac{b_1}{c_1}}_{\textstyle ,} \; \frac{b_s}{c_s}</math>where <math display="inline">s</math> is the number of times the subroutine was run. Each <math display="inline">c_k</math> will have different factors taken out of it because the circuit will (likely) have measured multiple different possible values of <math display="inline">j</math>. To recover the actual <math display="inline">r</math> value, we can take the [[least common multiple]] of each <math display="inline">c_k</math>:<math display="block">\mathrm{lcm}(c_1, c_2, \ldots, c_s)</math>The least common multiple will be the order <math display="inline">r</math> of the original integer <math display="inline">a</math> with high probability. In practice, a single run of the quantum order-finding subroutine is in general enough if more advanced post-processing is used.<ref name="Ekerå24">{{cite journal |last1=Ekerå |first1=Martin |title=On the Success Probability of Quantum Order Finding |journal=ACM Transactions on Quantum Computing |date=May 2024 |volume=5 |issue=2 |pages=1–40 |doi=10.1145/3655026 |doi-access=free |arxiv=2201.07791 }}</ref>
==== Choosing the size of the first register ====
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, <math>2n</math> qubits is sufficient to guarantee that the optimal bitstring measured from phase estimation (meaning the <math>|k\rangle</math> where <math display="inline">k / 2^{2n}</math> is the most accurate approximation of the phase from phase estimation) will allow the actual value of <math>r</math> to be recovered.

Each <math>|\phi_j\rangle</math> before measurement in Shor's algorithm represents a superposition of integers approximating <math>2^{2 n} j/r</math>. Let <math>|k\rangle</math> represent the most optimal integer in <math>|\phi_j\rangle</math>. The following theorem guarantees that the continued fractions algorithm will recover <math>j/r</math> from <math>k/2^{2 {n}}</math>:
{{Math theorem
| math_statement = If <math>j</math> and <math>r</math> are <math>n</math> bit integers, and
<math display="block">\left\vert \frac{j}{r} - \phi\right\vert \leq \frac{1}{2 r^2}</math>
then the continued fractions algorithm run on <math>\phi</math> will recover both <math display="inline">\frac{j}{\gcd(j,\; r)}</math> and <math display="inline">\frac{r}{\gcd(j,\; r)}</math>.
}}
<ref name=":0" /> As <math>k</math> is the optimal bitstring from phase estimation, <math>k/2^{2 {n}}</math> is accurate to <math>j/r</math> by <math>2n</math> bits. Thus,<math display="block">\left\vert\frac{j}{r} - \frac{k}{2^{2n}}\right\vert \leq \frac{1}{2^{2 {n} + 1}} \leq \frac{1}{2N^2} \leq \frac{1}{2r^2}</math>which implies that the continued fractions algorithm will recover <math>j</math> and <math>r</math> (or with their greatest common divisor taken out).

=== The bottleneck ===
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 computing|reversible gates]], starting with [[Adder (electronics)#Ripple-carry adder|ripple-carry adders]]. Knowing the base and the modulus of exponentiation facilitates further optimizations.<ref>{{cite journal |first1=Igor L. |last1=Markov |first2=Mehdi |last2=Saeedi |title=Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation |journal=Quantum Information and Computation |volume=12 |issue=5–6 |pages=361–394 |year=2012 |doi=10.26421/QIC12.5-6-1 |arxiv=1202.6614 |bibcode = 2012arXiv1202.6614M |s2cid=16595181 }}</ref><ref>{{cite journal |first1=Igor L. |last1=Markov |first2=Mehdi |last2=Saeedi |title=Faster Quantum Number Factoring via Circuit Synthesis |journal=Phys. Rev. A |volume=87 |issue= 1|pages=012310 |year=2013 |arxiv=1301.3210 |bibcode = 2013PhRvA..87a2310M |doi = 10.1103/PhysRevA.87.012310 |s2cid=2246117 }}</ref> Reversible circuits typically use on the order of <math>n^3</math> gates for <math>n</math> qubits. Alternative techniques asymptotically improve gate counts by using [[quantum Fourier transform]]s, but are not competitive with fewer than 600 qubits owing to high constants.

== Period finding and discrete logarithms ==
Shor's algorithms for the [[Discrete logarithm|discrete log]] and the order finding problems are instances of an algorithm solving the period finding problem.{{Citation needed|date=August 2023}}. All three are instances of the [[hidden subgroup problem]].<!-- It would be good to add the period finding algorithm here -->

=== Shor's algorithm for discrete logarithms ===
Given a [[Group (mathematics)|group]] <math>G</math> with order <math> p </math> and [[Generator (mathematics)|generator]] <math> g \in G </math>, suppose we know that <math> x = g^{r} \in G </math>, for some <math> r \in \mathbb{Z}_p </math>, and we wish to compute <math> r </math>, which is the [[discrete logarithm]]: <math> r = {\log_{g}}(x) </math>. Consider the [[abelian group]] <math> \mathbb{Z}_{p} \times \mathbb{Z}_{p} </math>, where each factor corresponds to modular addition of values. Now, consider the function

:<math>
f \colon \mathbb{Z}_{p} \times \mathbb{Z}_{p} \to G \;;\; f(a,b) = g^{a} x^{- b} .
</math>

This gives us an abelian [[hidden subgroup problem]], where <math> f </math> corresponds to a [[group homomorphism]]. The [[Kernel (algebra)|kernel]] corresponds to the multiples of <math> (r,1) </math>. So, if we can find the kernel, we can find <math> r </math>. 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 <math> f </math> as a quantum transform, followed finally by a quantum Fourier transform.<ref name=":0" /> 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.<ref name=":0">{{cite book |last1=Nielsen |first1=Michael A. |url=http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf |archive-url=https://web.archive.org/web/20190711070716/http://mmrc.amss.cas.cn/tlb/201702/W020170224608149940643.pdf |archive-date=2019-07-11 |url-status=live |title=Quantum Computation and Quantum Information |last2=Chuang |first2=Isaac L. |date=9 December 2010 |publisher=Cambridge University Press |isbn=978-1-107-00217-3 |edition=7th |access-date=24 April 2022}}</ref> To see this, consider the group of integers under addition, and for a given <math> a\in\mathbb{Z}</math> such that: <math> a^{r}=1</math>, the function
:<math>
f \colon \mathbb{Z}\to \mathbb{Z} \;;\; f(x) = a^{x},\; f(x+r) = f(x) .
</math>
For any finite abelian group <math>G</math>, a quantum algorithm exists for solving the hidden subgroup for <math>G</math> in polynomial time.<ref name=":0" />

== See also ==
* [[Lenstra elliptic-curve factorization#Quantum version (GEECM)|GEECM]], a factorization algorithm said to be "often much faster than Shor's"<ref>{{cite book |doi=10.1007/978-3-319-59879-6_18 |chapter=Post-quantum RSA |title=Post-Quantum Cryptography |series=Lecture Notes in Computer Science |date=2017 |last1=Bernstein |first1=Daniel J. |last2=Heninger |first2=Nadia |last3=Lou |first3=Paul |last4=Valenta |first4=Luke |volume=10346 |pages=311–329 |isbn=978-3-319-59878-9 }}</ref>
* [[Grover's algorithm]]

== References ==
{{reflist}}

== Further reading ==
* {{cite book |last1=Nielsen |first1=Michael A. |last2=Chuang |first2=Isaac L. |title=Quantum Computation and Quantum Information: 10th Anniversary Edition |date=2010 |publisher=Cambridge University Press |isbn=978-1-107-00217-3 }}
* {{cite book |doi=10.1093/oso/9780198570004.001.0001 |title=An Introduction to Quantum Computing |date=2006 |last1=Kaye |first1=Phillip |last2=Laflamme |first2=Raymond |last3=Mosca |first3=Michele |isbn=978-0-19-857000-4 }}
* [http://scottaaronson.com/blog/?p=208 "Explanation for the man in the street"] by [[Scott Aaronson]], "[http://scottaaronson.com/blog/?p=208#comment-9958 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 [http://www.scottaaronson.com/blog/?p=208#comment-5187 one of the comments]. Scott Aaronson suggests the following 12 references as further reading (out of "the 10<sup>10<sup>5000</sup></sup> quantum algorithm tutorials that are already on the web."):
* {{Citation |last=Shor |first=Peter W. |year=1997 |title=Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer |journal=SIAM J. Comput. |volume=26 |issue=5 |pages=1484–1509 |doi=10.1137/S0036144598347011 |arxiv=quant-ph/9508027v2|bibcode = 1999SIAMR..41..303S }}. 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").
* [https://quantum-algorithms.herokuapp.com/299/paper/index.html Quantum Computing and Shor's Algorithm], Matthew Hayward's [https://quantum-algorithms.herokuapp.com/ Quantum Algorithms Page], 2005-02-17, imsa.edu, LaTeX2HTML version of the original [https://quantum-algorithms.herokuapp.com/299/paper.tex LaTeX document], also available as [https://quantum-algorithms.herokuapp.com/299/paper.pdf PDF] or [https://quantum-algorithms.herokuapp.com/299/paper.ps postscript] document.
* [http://homepages.cwi.nl/~rdewolf/publ/qc/survey.ps Quantum Computation and Shor's Factoring Algorithm], Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.
* [http://www.cs.berkeley.edu/~vazirani/f04quantum/notes/lec9.ps Shor's Factoring Algorithm], Notes from Lecture 9 of Berkeley CS 294–2, dated 4 Oct 2004, 7 page postscript document.
* [http://www.theory.caltech.edu/people/preskill/ph229/notes/chap6.ps Chapter 6 Quantum Computation] {{Webarchive|url=https://web.archive.org/web/20200430110523/http://www.theory.caltech.edu/people/preskill/ph229/notes/chap6.ps |date=2020-04-30 }}, 91 page postscript document, Caltech, Preskill, PH229.
* [http://www-users.cs.york.ac.uk/~schmuel/comp/comp.html Quantum computation: a tutorial] by [http://www.cs.york.ac.uk/~schmuel/ Samuel L. Braunstein].
* [http://www.cs.ucr.edu/~neal/1996/cosc185-S96/shor/high-level.html The Quantum States of Shor's Algorithm], by Neal Young, Last modified: Tue May 21 11:47:38 1996.
* [https://web.archive.org/web/20121115112940/http://people.ccmr.cornell.edu/~mermin/qcomp/chap3.pdf 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.
* {{Cite arXiv|eprint=quant-ph/0303175|last1= Lavor|first1= C.|title= Shor's Algorithm for Factoring Large Integers|last2=  Manssur|first2= L. R. U.|last3=  Portugal|first3= R.|year= 2003}}
* {{Cite arXiv|eprint=quant-ph/0010034|last1=Lomonaco|first1=Jr|title=Shor's Quantum Factoring Algorithm|year=2000}}  This paper is a written version of a one-hour lecture given on Peter Shor's quantum factoring algorithm. 22 pages.
* [http://www.cs.princeton.edu/theory/complexity/quantumchap.pdf 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}}
* [http://blogs.discovermagazine.com/80beats/2011/01/19/a-step-towards-quantum-computing-entangling-10-billion-particles/ A Step Toward Quantum Computing: Entangling 10 Billion Particles] {{Webarchive|url=https://web.archive.org/web/20110120103006/http://blogs.discovermagazine.com/80beats/2011/01/19/a-step-towards-quantum-computing-entangling-10-billion-particles/ |date=2011-01-20 }}, from "Discover Magazine", Dated January 19, 2011.
* [http://www.fi.muni.cz/usr/gruska/survey1.ps Josef Gruska - ''Quantum Computing Challenges''] also in [https://www.amazon.com/Mathematics-Unlimited-Bj%C3%B6rn-Engquist/dp/3540669132 Mathematics unlimited: 2001 and beyond], Editors Björn Engquist, Wilfried Schmid, Springer, 2001, {{isbn|978-3-540-66913-5}}

==External links==
* Version 1.0.0 of [http://www.libquantum.de/ 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 Digital Studios|PBS Infinite Series]] created two videos explaining the math behind Shor's algorithm, "[http://www.pbs.org/video/how-to-break-cryptography-ahby1s/ How to Break Cryptography]" and "[http://www.pbs.org/video/hacking-at-quantum-speed-with-shors-algorithm-8jrjkq/ Hacking at Quantum Speed with Shor's Algorithm]".
* [https://short.classiq.io/shor Complete implementation of Shor's algorithm with Classiq]

{{Quantum computing}}

{{number theoretic algorithms}}

{{DEFAULTSORT:Shor's Algorithm}}
[[Category:Quantum algorithms]]
[[Category:Integer factorization algorithms]]
[[Category:Post-quantum cryptography]]
[[Category:Eponymous algorithms]]