Shor's algorithm

Shor's algorithm is a quantum computer algorithm for finding the prime factors of an integer. It was developed in 1994 by the American mathematician Peter Shor.[1]

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.[2] Specifically, it takes quantum gates of order using fast multiplication,[3] or even utilizing the asymptotically fastest multiplication algorithm currently known due to Harvey and Van Der Hoven,[4] 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 almost exponentially faster than the most efficient known classical factoring algorithm, the general number field sieve, which works in sub-exponential time: .[5] The efficiency of Shor's algorithm is due to the efficiency of the quantum Fourier transform, and modular exponentiation by repeated squarings.[6]

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[7]

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.

In 2001, Shor's algorithm was demonstrated by a group at IBM, who factored into , using an NMR implementation of a quantum computer with qubits.[8] 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.[9][10] In 2012, the factorization of was performed with solid-state qubits.[11] Also, in 2012, the factorization of was achieved, setting the record for the largest integer factored with Shor's algorithm.[12] 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.[13] Though larger numbers have been factored by quantum computers using other algorithms,[14] 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.[15]

ProcedureEdit

The problem that we are trying to solve is, given a composite number  , to find a non-trivial divisor of   (a divisor strictly between   and  ). Before attempting to find such a divisor, if there's any doubt whether   is composite or prime, one can use relatively quick primality-testing algorithms to verify that   is indeed composite, although this is not a part of Shor's algorithm.

Shor's algorithm consists of two parts:

  1. A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.
  2. A quantum algorithm to solve the order-finding problem.

The aim of the algorithm is to find a non-trivial square root   of   modulo   that is different from   and  , because then

 

for a non-zero integer   that gives us two distinct non-trivial divisors   and   of  . This idea is similar to other factoring algorithms, such as the quadratic sieve, and a more detailed explanation can be found in the Explanation section below. Before starting the algorithm, it is imperative to check   to be odd (otherwise   is a divisor) and not to be any power of an integer (otherwise that integer is a divisor), so as to guarantee the existence of a non-trivial square root   of   modulo  .

In turn, finding such a   is reduced to finding an element   as a parameter in an integer function, such that the function has an even period with a certain additional property (as explained below, it is required that the condition of Step 6 of the classical part does not hold). The quantum algorithm is used for finding the period of randomly chosen elements  , as this is a difficult problem on a classical computer.

Classical partEdit

  1. Pick a random number  .
  2. Compute  , the greatest common divisor of   and  . This may be done using the Euclidean algorithm.
  3. If  , then   is a nontrivial factor of  , so we are done.
  4. Otherwise, use the quantum period-finding subroutine (below) to find  , which denotes the period of the following function:
     
    Equivalently,   is the smallest positive integer that satisfies  .
  5. If   is odd, then go back to step 1.
  6. If  , then go back to step 1.
  7. Otherwise, both   or   are nontrivial factors of  , so we are done.

For example: Given  ,  , and  , we have  , where   and  . For   that is a product of two distinct primes,   and  ,  , which for   is  , and   divides  .

Quantum part: period-finding subroutineEdit

 
Quantum subroutine in Shor's algorithm

The quantum circuits used for this algorithm are custom designed for each choice of   and each choice of the random   used in  . Given  , find   such that  , which implies that  . The input and output qubit registers need to hold superpositions of values from   to  , and so have   qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least   different values of   that produce the same  , even as the period   approaches  .

Proceed as follows:

  1. Initialize the registers to
     

    where   denotes the tensor product.

    This initial state is a superposition of   states, and is easily obtained by generating   independent qubits, each a superposition of   and   states. We can accomplish this by initializing the qubits to the zero-position, and then applying the Hadamard gate in parallel to each of the   qubits, where  .
  2. Construct   as a quantum function and apply it to the above state, to obtain
     
     
    This is still a superposition of   states. However, the   qubits, i.e, the   input qubits and   ( ) output qubits, are now entangled or not separable, as the state cannot be written as a tensor product of states of individual qubits. Importantly, the value containing the   we are looking for is now stored in the phase of the input qubits   as a result of "phase kickback", where using qubits as control inputs to unitary gates alters the relative phase of the control qubits.[16]
  3. Apply the inverse quantum Fourier transform to the input register. This transform (operating on a superposition of   states) uses a  -th root of unity such as   to distribute the amplitude of any given   state equally among all   of the   states, and to do so in a different way for each different  . We thus obtain
     
    This leads to the final state
     
    Now, we reorder this sum as
     
    This is a superposition of many more than   states, but many fewer than   states, as there are fewer than   distinct values of  . Let
    •   be a  -th root of unity,
    •   be the period of  ,
    •   be the smallest of the   for which   (we have  ), and
    • write  
    •   indexes these  , running from   to  , so that  .
    Then   is a unit vector in the complex plane (  is a root of unity, and   and   are integers), and the coefficient of   in the final state is
     
    Each term in this sum represents a different path to the same result, and quantum interference occurs — constructive when the unit vectors   point in nearly the same direction in the complex plane, which requires that   point along the positive real axis.
  4. Perform a measurement. We obtain some outcome   in the input register and some outcome   in the output register. As   is periodic, the probability of measuring some state   is given by
     
     
    Analysis now shows that this probability is higher the closer the unit vector   is to the positive real axis, or the closer   is to an integer. Unless   is a power of  , it will not be a factor of  .
  5. Since   is close to some integer  , the known value   is close to the unknown value  . Performing [classical] continued fraction expansion on   allows us to find approximations   of it that satisfy two conditions:
    1.  .
    2.  .
    Given these multiple conditions (and assuming   is irreducible),   is very likely to be the appropriate period  , or at least a factor of it.
  6. Check (classically) if  . If so, then we are done.
  7. Otherwise, (classically) obtain more candidates for   by using multiples of  , or by using other   with   near  . If any candidate works, then we are done.
  8. Otherwise, try again starting from step 1 of this subroutine.

Explanation of the algorithmEdit

The algorithm is composed of two parts. The first part of the algorithm turns the factoring problem into the problem of finding the period of a function and may be implemented classically. The second part finds the period using the quantum Fourier transform and is responsible for the quantum speedup.

Non-trivial square root of 1Edit

Shor's algorithm hinges on finding a non-trivial square root of   modulo  ; That is, a solution to

 

where  .

If such   exists, we claim that   is a proper factor of  , i.e.,  . In fact, if  , then   divides  , so that  , which goes against the construction of  . If, on the other hand,  , then by Bézout's identity, there are integers   such that

 

Multiplying both sides by  , we obtain

 

As   divides  , we find that   divides  , so that  , again contradicting the construction of  .

Therefore,   is the required proper factor of  . Similarly, it can be proven that   is also a proper factor of  .

For such a non-trivial square root of   modulo   to exist, notice that  , and for any power of an odd prime  , there is no non-trivial square root of   modulo  : For any   either   or   has to be a multiple of  .

Therefore, for Shor's algorithm to work, we need   to be odd (otherwise   is a divisor) and not to be any power of an odd prime (otherwise that prime is a divisor). We can check that there are no integer roots   for  , and if   is not a power of any integer, it is not a power of any odd prime. Here, the upper bound for the integer   that we need to check is determined by  , since for   to be odd,   cannot be  . This check, however, cannot rule out that   may be an odd prime itself, which can only be ruled out by primality-testing algorithms.

Given that   is odd and not any power of an odd prime, based on the fundamental theorem of arithmetic, we may assume that   is the product of two coprime integers greater than   (  and  ). From the four combinations of choosing plus sign and minus sign in the integer equations  , based on the Chinese remainder theorem and  , there are at least four distinct square roots of   modulo  , and therefore at least two distinct non-trivial square roots exist. In fact, they are the solutions to   and  .

Obtaining factors from periodEdit

The integers less than   and coprime with   form the multiplicative group of integers modulo  , which is a finite abelian group  . The size of this group is given by  . By the end of step 3, we have an integer   in this group. As the group is finite,   must have a finite order  , which is the smallest positive integer such that

 

This is the order   of the finite cyclic subgroupa⟩ of the group  , which is the smallest positive integer   for which  . Since   and   are coprime, by Euler's totient theorem,   must exist, and divides  , where   denotes Euler's totient function.

Therefore,   divides   (also written  ). Suppose that we are able to obtain   and that it is even. (If   is odd, then by step 5, we have to restart the algorithm with a different random number  ) Now   is a square root of   modulo   that is different from  . This is because   is the order of   modulo  , so  , or else the order of   in this group would be  . If  , then by step 6, we have to restart the algorithm with a different random number  .

Eventually, we must hit an   of order   in   such that  . This is because such a   is a square root of   modulo   other than   and  , whose existence is guaranteed by the Chinese remainder theorem, as the odd number   is not a prime power.

Finding the periodEdit

Shor's period-finding algorithm relies heavily on the ability of a quantum computer to be in many states simultaneously.

Physicists call this behavior a "superposition" of states. To compute the period of a function  , we evaluate the function at all points simultaneously.

Quantum physics does not allow us to access all this information directly, however. A measurement will yield only one of all possible values, destroying all others. If not for the no-cloning theorem, we could first measure   without measuring  , and then make a few copies of the resulting state (which is a superposition of states all having the same  ). Measuring   on these states would provide different   values which give the same  , leading to the period. Because we cannot make exact copies of a quantum state, this method does not work. Therefore, we have to carefully transform the superposition to another state that will return the correct answer with high probability. This is achieved by the quantum Fourier transform.

Shor thus had to solve three "implementation" problems. All of them had to be implemented "fast", which means that they can be implemented with a number of quantum gates that is polynomial in  .

  1. Create a superposition of states. This can be done by applying Hadamard gates to all qubits in the input register. Another approach would be to use the quantum Fourier transform (see below).
  2. Implement the function   as a quantum transform. To achieve this, Shor used repeated squaring for his modular exponentiation transformation. It is important to note that this step is more difficult to implement than the quantum Fourier transform, in that it requires ancillary qubits and substantially more gates to accomplish.
  3. Perform a quantum Fourier transform. By using controlled rotation gates and Hadamard gates, Shor designed a circuit for the quantum Fourier transform (with  ) that uses just   gates.[17]

After all these transformations, a measurement will yield an approximation to the period  . For simplicity assume that there is a   such that   is an integer. Then the probability to measure   is  . To see this, we notice that then

 

for all integers  . Therefore, the sum whose square gives us the probability to measure   will be  , as   takes roughly   values and thus the probability is  . There are   possible values of   such that   is an integer, and also   possibilities for  , so the probabilities sum to  .

The period-finding routine can be considered a variation of the more general quantum phase estimation algorithm to determine the eigenvalue of a unitary corresponding to an eigenvector. In the case of the period-finding routine used in Shor's Algorithm, the unitary in question is modular multiplication by the chosen base mod  . While the computational basis   is not an eigenvector of this unitary, it is a uniform superposition of its   eigenvectors and thus the measurement will give the eigenvalue's phase for one of the eigenvectors. Since not all such phases can be used to extract the period, the retries of the subroutine may be necessary. [18]

The bottleneckEdit

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.[19][20] 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.

Discrete logarithmsEdit

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, as   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.[18] 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.[18] To see this, consider the group of integers under addition, and for a given   such that:  , the function

 

For any finite abelian group G, a quantum algorithm exists for solving the hidden subgroup for G in polynomial time.[18]

See alsoEdit

ReferencesEdit

  1. ^ 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: 124–134. doi:10.1109/sfcs.1994.365700. ISBN 0818665807. S2CID 15291489.
  2. ^ See also pseudo-polynomial time.
  3. ^ 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.
  4. ^ Harvey, David; van Der Hoeven, Joris (2020). "Integer multiplication in time O(n log n)". Annals of Mathematics.
  5. ^ "Number Field Sieve". wolfram.com. Retrieved 23 October 2015.
  6. ^ Gidney, Craig. "Shor's Quantum Factoring Algorithm". Algorithmic Assertions. Retrieved 28 November 2020.
  7. ^ Roetteler; et al. (2017). "Quantum resource estimates for computing elliptic curve discrete logarithms". arXiv:1706.06752.
  8. ^ 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
  9. ^ 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
  10. ^ 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
  11. ^ 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.
  12. ^ 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.
  13. ^ 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.
  14. ^ 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.
  15. ^ "Quantum computing motte-and-baileys". Shtetl-Optimized. 2019-12-28. Retrieved 2021-11-15.
  16. ^ Qiskit authors. "Qiskit Textbook: Quantum Phase Estimation". IBM. Retrieved 7 November 2020.
  17. ^ Shor 1999, p. 14
  18. ^ a b c d 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. Retrieved 24 April 2022.
  19. ^ 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.
  20. ^ 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.
  21. ^ Bernstein, Daniel J.; Heninger, Nadia; Lou, Paul; Valenta, Luke (2017). "Post-quantum RSA" (PDF). International Workshop on Post-Quantum Cryptography. Lecture Notes in Computer Science. 10346: 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 readingEdit

External linksEdit