Shor algorithm

The Shor algorithm is an algorithm from the mathematical branch of number theory that uses quantum computer science . It calculates a nontrivial divisor of a composite number on a quantum computer and thus belongs to the class of factorization methods .

The Shor algorithm cannot yet be used for practically relevant tasks, since up to now (as of 2020) there are no sufficiently large and low-error quantum computers available. A number of binary digits (i. E., ) To factor, a quantum computer requires a quantum register , the size of at least grows linearly with the number of binary digits. Shor's original algorithm requires 3n qubits , the best known variant manages with 2n + 3 qubits. These numbers apply to an ideal (error-free) quantum computer. In practice it is necessary to use quantum error correction methods. Then by a (large, but constant in n ) factor M more physical qubits are required, where M depends very strongly on the error rate and the error correction code used. It is estimated that 10 to 100 million qubits are required for a 2048-bit number (in the absence of errors it would only be a few thousand). For example, a research group at the US company IBM used a quantum computer with seven qubits in 2001 to break down the number 15 into the factors 5 and 3. ${\displaystyle N}$ ${\displaystyle n}$ ${\displaystyle N<2^{n}}$

The Shor algorithm is very important for cryptography because it finds a nontrivial divisor essentially faster than classical algorithms : While these require subexponential, but significantly higher than polynomial runtime , the Shor algorithm only has polynomial runtime . This represents a danger, for example, for the RSA cryptosystems that are often used for encrypted data transmission , the security of which is based precisely on the assumption that there is no factoring method with a polynomial runtime.

The algorithm was published in 1994 by Peter Shor , who was then employed by AT&T Bell Laboratories . The work is entitled Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer . This also describes a second algorithm for calculating the discrete logarithm , which is also referred to as the Shor algorithm. In general, however, this term is used for the factorization procedure.

properties

The Shor algorithm is a probabilistic algorithm . In some cases, depending on the number of repetitions, it leads to no result; the algorithm thus belongs to the class of Monte Carlo algorithms .

• Input: A composite number . ${\displaystyle n}$
• Output: A non-trivial factor of . ${\displaystyle n}$
• Runtime: gate operations. ${\displaystyle O\left((\log \,n)^{3}\right)}$

procedure

The basic idea is that factorization can be reduced to determining the order . This determination can be carried out effectively with the aid of the quantum Fourier transform . The algorithm is therefore often divided into a classic part to reduce the problem and a quantum part that efficiently solves the remaining problem .

Classic part

1. Pick a number with . ${\displaystyle x}$ ${\displaystyle 1<x<n}$
2. Find the , (e.g. using the Euclidean algorithm ). If the result is not 1, return this as the solution and terminate. Otherwise go to the next step. ${\displaystyle ggT}$ ${\displaystyle (x}$ ${\displaystyle n)}$
3. Determine with the help of the quantum part (see below) the order of in the prime residue class group (the smallest such that ). Step 2 made sure that one exists. ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle r\in \mathbb {N} }$ ${\displaystyle x^{r}\equiv 1({\textrm {mod}}\;n)}$ ${\displaystyle r}$
4. Start again at 1 if:
   1. ${\displaystyle r}$ is odd, or
   2. ${\displaystyle x^{r/2}\equiv -1({\textrm {mod}}\;n)}$.
5. Give back as a solution. ${\displaystyle {\textrm {ggT}}(x^{r/2}-1,n)}$

Solution in the last step

Consider the product ( ) * ( ) = . After step 3 we know that: that does not apply: (step 4) and that does not apply: (step 3, since the smallest number with is and applies), from which it follows that contains nontrivial factors of ; the Euclidean algorithm for calculating the supplies these divisors in polynomial time. ${\displaystyle x^{r/2}-1}$ ${\displaystyle x^{r/2}+1}$ ${\displaystyle x^{r}-1}$ ${\displaystyle x^{r}-1\equiv 0\mod n}$ ${\displaystyle x^{r/2}+1\equiv \ 0\mod n}$ ${\displaystyle x^{r/2}-1\equiv \ 0\mod n}$ ${\displaystyle r}$ ${\displaystyle x^{r}-1\equiv \ 0\mod n}$ ${\displaystyle {r/2}<r}$ ${\displaystyle x^{r/2}-1}$ ${\displaystyle n}$ ${\displaystyle ggT}$

Number of iterations for the part invention

The probability of obtaining a factor by randomly choosing is at least , where the number of mutually different prime factors is (not equal to 2). If, for example, is composed of only two prime factors, one gets a solution with a probability of 1/2 per run, so the probability of failure after steps is only . ${\displaystyle x}$ ${\displaystyle 1-1/2^{k-1}}$ ${\displaystyle k}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle t}$ ${\displaystyle 2^{-t}}$

Quantum part

1. Determine as a power of 2 with . ${\displaystyle q}$ ${\displaystyle n^{2}\leq q<2n^{2}}$
2. Initialize the first quantum register (input register) with the superposition (see qubit ) of all states ( is a number smaller than ). This results in the state: . ${\displaystyle a{\bmod {q}}}$ ${\displaystyle a}$ ${\displaystyle q}$
   ${\displaystyle {\frac {1}{q^{1/2}}}\sum _{a=0}^{q-1}|a\rangle \ |0\rangle }$
3. Initialize the second register (output register) with the superposition of the states . The result is the state: . ${\displaystyle x^{a}{\bmod {n}}}$
   ${\displaystyle {\frac {1}{q^{1/2}}}\sum _{a=0}^{q-1}|a\rangle \ |x^{a}{\bmod {n}}\rangle }$
4. Leads to the first register the quantum Fourier transformation through, wherein: so that we have: .
   ${\displaystyle QFT\left(|a\rangle \right)={\frac {1}{q^{1/2}}}\sum _{c=0}^{q-1}e^{2\pi iac/q}\ |c\rangle }$
   
   ${\displaystyle {\frac {1}{q}}\ \sum _{a=0}^{q-1}\ \sum _{c=0}^{q-1}e^{2\pi iac/q}\ |c\rangle \ |x^{a}{\bmod {n}}\rangle }$
5. Take a measurement (read the contents of the registers). The probability of the state with given by: . For this the relationship or applies , so that we can write: This discrete function has characteristic maxima for values ​​of a variable that satisfy the relationship through amplification . It can be shown that for the given relationships of and there is at most one such value for fixed . This can be used to calculate if and are relatively prime. (The probability for this case is at least or , that is, we get with a high probability after repetitions.) ${\displaystyle \left|c,x^{k}{\bmod {n}}\right\rangle }$ ${\displaystyle 0<k<r}$
   ${\displaystyle \left|{\frac {1}{q}}\ \sum _{a:x^{a}\equiv x^{k}}e^{2\pi iac/q}\right|_{}^{2}}$ ${\displaystyle a\equiv k\mod r}$ ${\displaystyle a=br+k}$
   ${\displaystyle \left|{\frac {1}{q}}\ \sum _{b}e^{2\pi i\left(br+k\right)c/q}\right|_{}^{2}}$ ${\displaystyle d\in \mathbb {Z} }$
   ${\displaystyle \left|{\frac {c}{q}}-{\frac {d}{r}}\right|\leq {\frac {1}{2q}}}$ ${\displaystyle q,r}$ ${\displaystyle n}$ ${\displaystyle c}$ ${\displaystyle r}$ ${\displaystyle d}$ ${\displaystyle r}$ ${\displaystyle {\frac {\phi (r)}{3r}}}$ ${\displaystyle \Omega \!\left({\frac {1}{\log \log r}}\right)}$ ${\displaystyle r}$ ${\displaystyle O(\log \log r)}$
6. Return the calculated value if it is actually the order of , otherwise repeat the experiment. ${\displaystyle r^{\prime }}$ ${\displaystyle x}$

literature

• M. Homeister: Understanding Quantum Computing . 5th edition. Springer Vieweg, Wiesbaden 2018, ISBN 978-3-658-22883-5 , p. 223 ff.
• B. Lenze: Mathematics and Quantum Computing . Logos Verlag, Berlin 2020, second edition, ISBN 978-3-832-54716-5 , pp. 89ff.
• RJ Lipton, KW Regan: Quantum Algorithms via Linear Algebra: A Primer . MIT Press, Cambridge MA 2014, ISBN 978-0-262-02839-4 , pp. 97 ff.
• MA Nielsen, IL Chuang: Quantum Computation and Quantum Information . Cambridge University Press, Cambridge MA 2010, ISBN 978-1-107-00217-3 , p. 234 ff.
• W. Scherer: Mathematics of quantum informatics . Springer-Verlag, Berlin / Heidelberg 2016, ISBN 978-3-662-49079-2 , p. 206 ff.
• CP Williams: Explorations in Quantum Computing . Springer-Verlag, London 2011, second edition, ISBN 978-1-846-28886-9 , pp. 272 ​​ff.
• IBM's Test Tube Quantum Computer Makes History; First Demonstration Of Shor's Historic Factoring Algorithm - ScienceDaily, December 20, 2001

Individual evidence

1. ↑ ^{a b} Craig Gidney, Martin Ekerå: How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits . May 23, 2019, Tables 1 and 2 , arxiv : 1905.09749 (English).
2. ↑ Lieven MK Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood and Isaac L. Chuang: Experimental realization of an order-finding algorithm with an NMR quantum computer. In: Nature , 414/2001, pp. 883-887, doi: 10.1038 / 414883a
3. ↑ Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In: SIAM Journal on Computing , 26/1997, pp. 1484–1509, arxiv : quant-ph / 9508027