Movatterモバイル変換

Shor's algorithm

From Wikipedia, the free encyclopedia

Quantum algorithm for integer factorization

Shor's algorithm is aquantum algorithm for finding theprime factors of an integer. It was developed in 1994 by the American mathematicianPeter Shor.^[1]^[2] 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.^[3] However, beating classical computers will require millions of qubits due to the overhead caused byquantum error correction.^[4]

Shor proposed multiple similar algorithms for solving thefactoring problem, thediscrete 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 thehidden subgroup problem.

On a quantum computer, to factor an integer $N {\displaystyle N}$ , Shor's algorithm runs inpolynomial time, meaning the time taken is polynomial in $\log N$ .^[5] It takesquantum gates of order $O\!\left((\log N)^{2}(\log \log N)(\log \log \log N)\right)$ using fast multiplication,^[6] or even $O\!\left((\log N)^{2}(\log \log N)\right)$ utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey andvan der Hoeven,^[7] thus demonstrating that theinteger factorization problem can be is consequently in thecomplexity classBQP. This is significantly faster than the most efficient known classical factoring algorithm, thegeneral number field sieve, which works insub-exponential time: $O\!\left(e^{1.9(\log N)^{1/3}(\log \log N)^{2/3}}\right)$ .^[8]

Feasibility and impact

[edit]

Assuming a quantum computer with a sufficient number ofqubits could operate without succumbing toquantum noise and otherquantum-decoherence phenomena, then Shor's algorithm could be used to breakpublic-key cryptography schemes, such as

TheRSA scheme
The finite-fieldDiffie–Hellman key exchange
Theelliptic-curve Diffie–Hellman key exchange^[9]

RSA can be broken if factoring large integers is computationally feasible. As far as is known, this is not possible using classical (non-quantum) computers; no classical algorithm is known that can factor integers in polynomial time. However, Shor's algorithm shows that factoring integers can be done with a polynomial complexity circult on an ideal quantum computer. Thus, it might be feasible to defeat RSA by constructing a large enough quantum computer. This was 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 calledpost-quantum cryptography (PQC).

Physical implementation

[edit]

As of 2025, the high error rates of quantum computers and limited number of physical qubits available forquantum error correction, laboratory demonstrations of Shor's algorithm obtain correct results in only in a fraction of attempts, and have used succeeded with smallsemiprimes.

In 2001, Shor's algorithm was demonstrated by a group atIBM, who factored $15 {\displaystyle 15}$ into $3\times 5$ , using anNMR implementation of a quantum computer with seven qubits.^[10] After IBM's implementation, two independent groups implemented Shor's algorithm usingphotonic qubits, emphasizing that multi-qubitentanglement was observed when running the Shor's algorithm circuits.^[11]^[12] In 2012, the factorization of $15 {\displaystyle 15}$ was performed with solid-state qubits.^[13] Later, in 2012, the factorization of $21 {\displaystyle 21}$ was achieved.^[14] In 2016, the factorization of $15 {\displaystyle 15}$ was performed again using trapped-ion qubits.^[15] However, none of these demonstrations fulfill the requirements of Shor’s algorithm: they compile the circuit using prior knowledge of the solution, and some have even oversimplified the algorithm in a way that makes it equivalent to coin flipping.^[16]

Algorithm

[edit]

The problem that we are trying to solve is:given an oddcomposite number $N {\displaystyle N}$ , find itsinteger factors.

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

A classical reduction of the factoring problem to the problem oforder-finding. This reduction is similar to that used for otherfactoring algorithms, such as thequadratic 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 $N {\displaystyle N}$ into just two integers $p {\displaystyle p}$ and $q {\displaystyle q}$ greater than 1, since if either $p {\displaystyle p}$ or $q {\displaystyle q}$ are not prime, then the factoring algorithm can in turn be run on those until only primes remain.

A basic observation is that, usingEuclid's algorithm, we can always compute theGCD between two integers efficiently. In particular, this means we can check efficiently whether $N {\displaystyle N}$ is even, in which case 2 is trivially a factor. Let us thus assume that $N {\displaystyle N}$ is odd for the remainder of this discussion. Afterwards, we can use efficient classical algorithms to check whether $N {\displaystyle N}$ is aprime power.^[17] For prime powers, efficient classical factorization algorithms exist,^[18] hence the rest of the quantum algorithm may assume that $N {\displaystyle N}$ is not a prime power.

If those easy cases do not produce a nontrivial factor of $N {\displaystyle N}$ , the algorithm proceeds to handle the remaining case. We pick a random integer $2\leq a<N{.}$ A possible nontrivial divisor of $N {\displaystyle N}$ can be found by computing $\gcd(a,N)$ , which can be done classically and efficiently using theEuclidean algorithm. If this produces a nontrivial factor (meaning $\gcd(a,N)\neq 1$ ), the algorithm is finished, and the other nontrivial factor is $N/\gcd(a,N)$ . If a nontrivial factor was not identified, then this means that $N {\displaystyle N}$ and the choice of $a {\displaystyle a}$ arecoprime, so $a {\displaystyle a}$ is contained in themultiplicative group of integers modulo $N {\displaystyle N}$ , having amultiplicative inverse modulo $N {\displaystyle N}$ . Thus, $a {\displaystyle a}$ has amultiplicative order $r {\displaystyle r}$ modulo $N {\displaystyle N}$ , meaning

a^{r}\equiv 1{\bmod {N}},

and $r {\displaystyle r}$ is the smallest positive integer satisfying this congruence.

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

The algorithm restated shortly follows: let $N {\displaystyle N}$ be odd, and not a prime power. We want to output two nontrivial factors of $N {\displaystyle N}$ .

Pick a random number $1<a<N$ .
Compute $K=\gcd(a,N)$ , thegreatest common divisor of $a {\displaystyle a}$ and $N {\displaystyle N}$ .
If $K\neq 1$ , then $K {\displaystyle K}$ is anontrivial factor of $N {\displaystyle N}$ , with the other factor being $N/K$ , and we are done.
Otherwise, use the quantum subroutine to find the order $r {\displaystyle r}$ of $a {\displaystyle a}$ .
If $r {\displaystyle r}$ is odd, then go back to step 1.
Compute $g=\gcd(N,a^{r/2}+1)$ . If $g {\displaystyle g}$ is nontrivial, the other factor is $N/g$ , 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.^[2] In practice, a single call to the quantum order-finding subroutine is enough to completely factor $N {\displaystyle N}$ with very high probability of success if one uses a more advanced reduction.^[19]

Quantum order-finding subroutine

[edit]

The goal of the quantum subroutine of Shor's algorithm is, givencoprime integers $N {\displaystyle N}$ and $1<a<N$ , to find theorder $r {\displaystyle r}$ of $a {\displaystyle a}$ modulo $N {\displaystyle N}$ , which is the smallest positive integer such that $a^{r}\equiv 1{\pmod {N}}$ . To achieve this, Shor's algorithm uses a quantum circuit involving two registers. The second register uses $n {\displaystyle n}$ qubits, where $n {\displaystyle n}$ is the smallest integer such that $N\leq 2^{n}$ , i.e., $n=\left\lceil {\log _{2}N}\right\rceil$ . The size of the first register determines how accurate of an approximation the circuit produces. It can be shown that using $2n$ qubits gives sufficient accuracy to find $r {\displaystyle r}$ . The exact quantum circuit depends on the parameters $a {\displaystyle a}$ and $N {\displaystyle N}$ , which define the problem. The following description of the algorithm usesbra–ket notation to denote quantum states, and $\otimes$ to denote thetensor product, rather thanlogical AND.

The algorithm consists of two main steps:

Usequantum phase estimation with unitary $U {\displaystyle U}$ representing the operation of multiplying by $a {\displaystyle a}$ (modulo $N {\displaystyle N}$ ), and input state $|0\rangle ^{\otimes 2n}\otimes |1\rangle$ (where the second register is $|1\rangle$ made from $n {\displaystyle n}$ qubits). The eigenvalues of this $U {\displaystyle U}$ encode information about the period, and $|1\rangle$ 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 ${\frac {j}{r}}2^{2n}$ for random $j=0,1,...,r-1$ .
Use thecontinued fractions algorithm to extract the period $r {\displaystyle r}$ 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,^[2] but was later proposed by Kitaev.^[20]

Quantum phase estimation

[edit]

In general thequantum phase estimation algorithm, for any unitary $U {\displaystyle U}$ and eigenstate $|\psi \rangle$ such that $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$ , sends input states $|0\rangle |\psi \rangle$ to output states close to $|\phi \rangle |\psi \rangle$ , where $\phi$ is a superposition of integers close to $2^{2n}\theta$ . In other words, it sends each eigenstate $|\psi _{j}\rangle$ of $U {\displaystyle U}$ to a state containing information close to the associated eigenvalue. For the purposes of quantum order-finding, we employ this strategy using the unitary defined by the action $U|k\rangle ={\begin{cases}|ak{\pmod {N}}\rangle &0\leq k<N,\\|k\rangle &N\leq k<2^{n}.\end{cases}}$ The action of $U {\displaystyle U}$ on states $|k\rangle$ with $N\leq k<2^{n}$ is not crucial to the functioning of the algorithm, but needs to be included to ensure that the overall transformation is a well-defined quantum gate. Implementing the circuit for quantum phase estimation with $U {\displaystyle U}$ requires being able to efficiently implement the gates $U^{2^{j}}$ . This can be accomplished viamodular exponentiation, which is the slowest part of the algorithm.

The gate thus defined satisfies $U^{r}=I$ , which immediately implies that its eigenvalues are the $r {\displaystyle r}$ -throots of unity $\omega _{r}^{k}=e^{2\pi ik/r}$ . Furthermore, each eigenvalue $\omega _{r}^{j}$ has an eigenvector of the form ${\textstyle |\psi _{j}\rangle =r^{-1/2}\sum _{k=0}^{r-1}\omega _{r}^{-kj}|a^{k}\rangle }$ , and these eigenvectors are such that ${\begin{aligned}{\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{aligned}}$ where the last identity follows from thegeometric series formula, which implies ${\textstyle \sum _{j=0}^{r-1}\omega _{r}^{jk}=0}$ .

Usingquantum phase estimation on an input state $|0\rangle ^{\otimes 2n}|\psi _{j}\rangle$ would then return the integer $2^{2n}j/r$ with high probability. More precisely, the quantum phase estimation circuit sends $|0\rangle ^{\otimes 2n}|\psi _{j}\rangle$ to $|\phi _{j}\rangle |\psi _{j}\rangle$ such that the resulting probability distribution $p_{k}\equiv |\langle k|\phi _{j}\rangle |^{2}$ is peaked around $k=2^{2n}j/r$ , with $p_{2^{2n}j/r}\geq 4/\pi ^{2}\approx 0.4053$ . This probability can be made arbitrarily close to 1 using extra qubits.

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

Continued-fraction algorithm to retrieve the period

[edit]

Then, we apply thecontinued-fraction algorithm to find integers $b {\displaystyle b}$ and $c {\displaystyle c}$ , where $b/c$ gives the best fraction approximation for the approximation measured from the circuit, for $b,c<N$ andcoprime $b {\displaystyle b}$ and $c {\displaystyle c}$ . The number of qubits in the first register, $2n$ , which determines the accuracy of the approximation, guarantees that ${\frac {b}{c}}={\frac {j}{r}},$ given the best approximation from the superposition of $|\phi _{j}\rangle$ was measured^[2] (which can be made arbitrarily likely by using extra bits and truncating the output). However, while $b {\displaystyle b}$ and $c {\displaystyle c}$ are coprime, it may be the case that $j {\displaystyle j}$ and $r {\displaystyle r}$ are not coprime. Because of that, $b {\displaystyle b}$ and $c {\displaystyle c}$ may have lost some factors that were in $j {\displaystyle j}$ and $r {\displaystyle r}$ . This can be remedied by rerunning the quantum order-finding subroutine an arbitrary number of times, to produce a list of fraction approximations ${\frac {b_{1}}{c_{1}}},{\frac {b_{2}}{c_{2}}},\ldots ,{\frac {b_{s}}{c_{s}}},$ where $s {\displaystyle s}$ is the number of times the subroutine was run. Each $c_{k}$ will have different factors taken out of it because the circuit will (likely) have measured multiple different possible values of $j {\displaystyle j}$ . To recover the actual $r {\displaystyle r}$ value, we can take theleast common multiple of each $c_{k}$ : $\operatorname {lcm} (c_{1},c_{2},\ldots ,c_{s}).$ The least common multiple will be the order $r {\displaystyle r}$ of the original integer $a {\displaystyle a}$ 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.^[21]

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, $2n$ qubits is sufficient to guarantee that the optimal bitstring measured from phase estimation (meaning the $|k\rangle$ where ${\textstyle k/2^{2n}}$ is the most accurate approximation of the phase from phase estimation) will allow the actual value of $r {\displaystyle r}$ to be recovered.

Each $|\phi _{j}\rangle$ before measurement in Shor's algorithm represents a superposition of integers approximating $2^{2n}j/r$ . Let $|k\rangle$ represent the most optimal integer in $|\phi _{j}\rangle$ . The following theorem guarantees that the continued fractions algorithm will recover $j/r$ from $k/2^{2{n}}$ :

Theorem—If $j {\displaystyle j}$ and $r {\displaystyle r}$ are $n {\displaystyle n}$ bit integers, and $\left\vert {\frac {j}{r}}-\phi \right\vert \leq {\frac {1}{2r^{2}}}$ then the continued fractions algorithm run on $\phi$ will recover both ${\textstyle {\frac {j}{\gcd(j,\;r)}}}$ and ${\textstyle {\frac {r}{\gcd(j,\;r)}}}$ .

^[3] As $k {\displaystyle k}$ is the optimal bitstring from phase estimation, $k/2^{2{n}}$ is accurate to $j/r$ by $2n$ bits. Thus, $\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}}}$ which implies that the continued fractions algorithm will recover $j {\displaystyle j}$ and $r {\displaystyle r}$ (or with their greatest common divisor taken out).

The bottleneck

[edit]

The runtime bottleneck of Shor's algorithm is quantummodular exponentiation, which is by far slower than thequantum 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 withreversible gates, starting withripple-carry adders. Knowing the base and the modulus of exponentiation facilitates further optimizations.^[22]^[23] Reversible circuits typically use on the order of $n^{3}$ gates for $n {\displaystyle n}$ qubits. Alternative techniques asymptotically improve gate counts by usingquantum 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 thediscrete log and the order finding problems are instances of an algorithm solving the period finding problem.^{[citation needed]} All three are instances of thehidden subgroup problem.

Shor's algorithm for discrete logarithms

[edit]

Given agroup $G {\displaystyle G}$ with order $p {\displaystyle p}$ andgenerator $g\in G$ , suppose we know that $x=g^{r}\in G$ , for some $r\in \mathbb {Z} _{p}$ , and we wish to compute $r {\displaystyle r}$ , which is thediscrete logarithm: $r={\log _{g}}(x)$ . Consider theabelian group $\mathbb {Z} _{p}\times \mathbb {Z} _{p}$ , where each factor corresponds to modular addition of values. Now, consider the function

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

This gives us an abelianhidden subgroup problem, where $f {\displaystyle f}$ corresponds to agroup homomorphism. Thekernel corresponds to the multiples of $(r,1)$ . So, if we can find the kernel, we can find $r {\displaystyle r}$ . 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 $f {\displaystyle f}$ as a quantum transform, followed finally by a quantum Fourier transform.^[3] 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.^[3] To see this, consider the group of integers under addition, and for a given $a\in \mathbb {Z}$ such that: $a^{r}=1$ , the function

f\colon \mathbb {Z} \to \mathbb {Z} \;;\;f(x)=a^{x},\;f(x+r)=f(x).

For any finite abelian group $G {\displaystyle G}$ , a quantum algorithm exists for solving the hidden subgroup for $G {\displaystyle G}$ in polynomial time.^[3]

References

[edit]

^Shor, P.W. (1994). "Algorithms for quantum computation: Discrete logarithms and factoring".Proceedings 35th Annual Symposium on Foundations of Computer Science. pp. 124–134.doi:10.1109/sfcs.1994.365700.ISBN 978-0-8186-6580-6.
^^a ^b ^c ^dShor, 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.S2CID 2337707.
^^a ^b ^c ^d ^eNielsen, 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. Retrieved24 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.
^See alsopseudo-polynomial time.
^Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John (August 1996). "Efficient networks for quantum factoring".Physical Review A.54 (2):1034–1063.arXiv:quant-ph/9602016.Bibcode:1996PhRvA..54.1034B.doi:10.1103/physreva.54.1034.PMID 9913575.
^Harvey, David; van der Hoeven, Joris (March 2021)."Integer multiplication in time O (n log n)"(PDF).Annals of Mathematics.193 (2).doi:10.4007/annals.2021.193.2.4.
^"Number Field Sieve".wolfram.com. Retrieved23 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.ISBN 978-3-319-70696-2.
^Vandersypen, Lieven M. K.; Steffen, Matthias; Breyta, Gregory; Yannoni, Costantino S.; Sherwood, Mark H.; Chuang, Isaac L. (December 2001). "Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance".Nature.414 (6866):883–887.arXiv:quant-ph/0112176.Bibcode:2001Natur.414..883V.doi:10.1038/414883a.PMID 11780055.
^Lu, Chao-Yang; Browne, Daniel E.; Yang, Tao; Pan, Jian-Wei (19 December 2007). "Demonstration of a Compiled Version of Shor's Quantum Factoring Algorithm Using Photonic Qubits".Physical Review Letters.99 (25) 250504.arXiv:0705.1684.Bibcode:2007PhRvL..99y0504L.doi:10.1103/PhysRevLett.99.250504.PMID 18233508.
^Lanyon, B. P.; Weinhold, T. J.; Langford, N. K.; Barbieri, M.; James, D. F. V.; Gilchrist, A.; White, A. G. (19 December 2007). "Experimental Demonstration of a Compiled Version of Shor's Algorithm with Quantum Entanglement".Physical Review Letters.99 (25) 250505.arXiv:0705.1398.Bibcode:2007PhRvL..99y0505L.doi:10.1103/PhysRevLett.99.250505.PMID 18233509.
^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; 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.
^Monz, Thomas; Nigg, Daniel; Martinez, Esteban A.; Brandl, Matthias F.; Schindler, Philipp; Rines, Richard; Wang, Shannon X.; Chuang, Isaac L.; Blatt, Rainer (4 March 2016). "Realization of a scalable Shor algorithm".Science.351 (6277):1068–1070.arXiv:1507.08852.Bibcode:2016Sci...351.1068M.doi:10.1126/science.aad9480.PMID 26941315.S2CID 17426142.
^Smolin, John A.; Smith, Graeme; Vargo, Alexander (July 2013). "Oversimplifying quantum factoring".Nature.499 (7457):163–165.arXiv:1301.7007.Bibcode:2013Natur.499..163S.doi:10.1038/nature12290.PMID 23846653.
^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.
^For example, computing the first $\log _{2}(N)$ roots of $N {\displaystyle N}$ , e.g., with theNewton method and checking each integer result for primality (AKS primality test).
^Ekerå, Martin (June 2021)."On completely factoring any integer efficiently in a single run of an order-finding algorithm".Quantum Information Processing.20 (6) 205.arXiv:2007.10044.Bibcode:2021QuIP...20..205E.doi:10.1007/s11128-021-03069-1.
^Kitaev, A. Yu (1995). "Quantum measurements and the Abelian Stabilizer Problem".arXiv:quant-ph/9511026.
^Ekerå, Martin (May 2024)."On the Success Probability of Quantum Order Finding".ACM Transactions on Quantum Computing.5 (2):1–40.arXiv:2201.07791.doi:10.1145/3655026.
^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".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.

External links

[edit]

Version 1.0.0 oflibquantum: 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".
Complete implementation of Shor's algorithm with Classiq

Quantum information science

General

Theorems

Quantum
communication

Quantum cryptography	Post-quantum cryptography Quantum coin flipping Quantum money Quantum key distribution BB84 SARG04 other protocols Quantum secret sharing

Quantum algorithms

Quantum
complexity theory

Quantum
processor benchmarks

Quantum
computing models

Quantum
error correction

Physical
implementations

Quantum optics	Cavity QED Circuit QED Linear optical QC KLM protocol
Ultracold atoms	Neutral atom QC Trapped-ion QC
Spin-based	Kane QC Spin qubit QC NV center NMR QC
Superconducting	Charge qubit Flux qubit Phase qubit Transmon

Quantum
programming

v t e Number-theoretic algorithms
Primality tests	AKS APR Baillie–PSW Elliptic curve Pocklington Fermat Lucas Lucas–Lehmer Lucas–Lehmer–Riesel Proth's theorem Pépin's Quadratic Frobenius Solovay–Strassen Miller–Rabin
Prime-generating	Sieve of Atkin Sieve of Eratosthenes Sieve of Pritchard Sieve of Sundaram Wheel factorization
Integer factorization	Continued fraction (CFRAC) Dixon's Lenstra elliptic curve (ECM) Euler's Pollard's rho p − 1 p + 1 Quadratic sieve (QS) General number field sieve (GNFS) Special number field sieve (SNFS) Rational sieve Fermat's Shanks's square forms Trial division Shor's
Multiplication	Ancient Egyptian Long Karatsuba Toom–Cook Schönhage–Strassen Fürer's
Euclidean division	Binary Chunking Fourier Goldschmidt Newton-Raphson Long Short SRT
Discrete logarithm	Baby-step giant-step Pollard rho Pollard kangaroo Pohlig–Hellman Index calculus Function field sieve
Greatest common divisor	Binary Euclidean Extended Euclidean Lehmer's
Modular square root	Cipolla Pocklington's Tonelli–Shanks Berlekamp
Other algorithms	Chakravala Cornacchia Exponentiation by squaring Integer square root Integer relation (LLL;KZ) Modular exponentiation Montgomery reduction Schoof Trachtenberg system
Italics indicate that algorithm is for numbers of special forms