Shor algorithm

from Wikipedia, the free encyclopedia

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.

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.


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 .
  • Output: A non-trivial factor of .
  • Runtime: gate operations.


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 .
  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.
  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.
  4. Start again at 1 if:
    1. is odd, or
    2. .
  5. Give back as a solution.

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.

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 .

Quantum part

  1. Determine as a power of 2 with .
  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: .
  3. Initialize the second register (output register) with the superposition of the states . The result is the state: .
  4. Leads to the first register the quantum Fourier transformation through, wherein: so that we have: .

  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.)

  6. Return the calculated value if it is actually the order of , otherwise repeat the experiment.


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