Shor's algorithm

The Shor algorithm is an algorithm from the mathematical subfield of number theory, which uses means of quantum computing. It calculates a nontrivial divisor of a composite number on a quantum computer and thus belongs to the class of factorization methods.

For practically relevant tasks, Shor's algorithm is not yet applicable, since so far (as of 2020) no sufficiently large and error-free quantum computers are available. To solve a number with binary digits (i.e., $n<2^{N}$ ), a quantum computer requires a quantum register whose size grows at least linearly with the number of binary digits. Shor's original algorithm requires 3n qubits, the best known variant gets by with 2n+3 qubits. These numbers hold for an ideal (error-free) quantum computer. In practice, it is necessary to use quantum error correction techniques. Then more physical qubits are needed by a (large, but constant in n) factor M, where M depends very much on the error rate and the error correction code used. It is estimated that 10 to 100 million qubits are needed for a 2048-bit number (in the error-free case it would be only a few thousand). In 2001, for example, a research group at the US company IBM used a quantum computer with seven qubits to decompose the number 15 into the factors 5 and 3.

The Shor algorithm is very significant for cryptography because it finds a nontrivial divisor essentially faster than classical algorithms: While these require subexponential but much higher than polynomial running time, the Shor algorithm has only polynomial running time. This poses a threat, for example, to the RSA cryptosystems often used for encrypted data transmission, whose security is based precisely on the assumption that no factorization procedure with polynomial runtime exists.

The algorithm was published in 1994 by Peter Shor, who was then employed at AT&T Bell Laboratories. The paper is entitled Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. It also describes a second algorithm for computing the discrete logarithm, also called Shor's algorithm. In general, however, this designation is used for the factorization procedure.

Properties

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

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

Expiration

The basic idea is that one can factorize back to the determination of the order. This determination can be done effectively using the quantum Fourier transform. One therefore often divides the algorithm into a classical part to reduce the problem and a quantum part that efficiently solves the residual problem.

Classic part

Choose a number with $1<x<n$ .
Determine the $ggT$ $(x$ , $n)$ (for example, using the Euclidean algorithm). If the result is not equal to 1, return this as the solution and terminate. Otherwise, proceed to the next step.
Using the quantum part (see below), determine the order of in the prime residue class group $({\mathbb Z}/n{\mathbb Z})^{\times }$ (the smallest $r\in {\mathbb {N}}$ , such that $x^{r}\equiv 1({\textrm {mod}}\;n)$ ). Step 2 ensured that such an exists.
Start over at 1 if:

is odd, or
$x^{{r/2}}\equiv -1({\textrm {mod}}\;n)$ .

Return ${\textrm {ggT}}(x^{{r/2}}-1,n)$ as the solution.

Solution in the last step

Consider the product ( $x^{{r/2}}-1$ ) - ( $x^{{r/2}}+1$ ) = $x^{r}-1$ . We know after step 3 that holds: $x^{r}-1\equiv 0\mod n$ , that it does not hold: $x^{r/2}+1\equiv \ 0\mod n$ (Step 4) and that does not hold: $x^{r/2}-1\equiv \ 0\mod n$ (step 3, since is the smallest number with $x^{r}-1\equiv \ 0\mod n$ and {r/2}<r holds), from which it follows that contains $x^{{r/2}}-1$ nontrivial divisors of ; the Euclidean algorithm for computing the $ggT$ yields these divisors in polynomial time.

Number of iterations for the partial invention

The probability of obtaining a divisor given a random choice of is at least $1-1/2^{{k-1}}$ , where the number of distinct prime factors of (not equal to 2). For example, if is composed of only two prime factors, one solution is obtained with probability 1/2 per pass, so the probability of failure after steps is only $2^{{-t}}$ .

Quantum Part

Determine as a power of 2 with $n^{2}\leq q<2n^{2}$ .
Initialize the first quantum register (input register) with the superposition (see qubit) of all states $a{\bmod {q}}$ ( is a number less than ). This leads to the state:
${\frac {1}{q^{{1/2}}}}\sum _{{a=0}}^{{q-1}}|a\rangle \ |0\rangle$ .
Initialize the second register (output register) with the superposition of the states $x^{a}{\bmod {n}}$ . The result is the state:
${\frac {1}{q^{1/2}}}\sum _{a=0}^{q-1}|a\rangle \ |x^{a}{\bmod {n}}\rangle$ .
On the first register, perform the quantum Fourier transform where:
$QFT\left(|a\rangle \right)={\frac {1}{q^{{1/2}}}}\sum _{{c=0}}^{{q-1}}e^{{2\pi iac/q}}\ |c\rangle$
such that results in:
${\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$ .
Perform a measurement (take the contents of the registers). The probability for the state $\left|c,x^{k}{\bmod {n}}\right\rangle$ with is given by:
$\left|{\frac {1}{q}}\ \sum _{{a:x^{a}\equiv x^{k}}}e^{{2\pi iac/q}}\right|_{{}}^{2}$ . Here, the relation $a\equiv k\mod r$ or $a=br+k$ , so that we can write:
$\left|{\frac {1}{q}}\ \sum _{{b}}e^{{2\pi i\left(br+k\right)c/q}}\right|_{{}}^{2}$ By amplification, this discrete function has characteristic maxima for values of a variable $d\in {\mathbb {Z}}$ , which is the relation
$\left|{\frac {c}{q}}-{\frac {d}{r}}\right|\leq {\frac {1}{2q}}$ . It can be shown that for the given relations of $q,r$ and there is at most one such value at fixed Thus, computed if and are divisor-irrelevant. (The probability for this case is at least ϕ ${\frac {\phi (r)}{3r}}$ or Ω $\Omega \!\left({\frac {1}{\log \log r}}\right)$ , that is, we get with high probability after $O(\log \log r)$ repetitions).
Return the computed value $r^{\prime }$ if it is indeed the order of , otherwise repeat the experiment.