Shor's Algorithm Procedure Classical Part Quantum Part Period

Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer. A message encrypted with RSA can be deciphered by factoring the public key N, which is the product of two prime numbers. Known classical algorithms cannot do this in time O((log N)^k) for any k, so they quickly become infeasible as N is increased. By contrast, Shor's algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.

Like all quantum computer algorithms, Shor's algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.

Shor's algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.

1 Procedure

The problem we are trying to solve is that, given an integer N, we try to find another integer p between 1 and N that divides N.

1.1 Classical part

1.2 Quantum part: Period-finding subroutine:

2 Explanation of the algorithm

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.

2.1 I. Obtaining factors from period

The integers less than N and coprimeIn mathematics, the integers a and b are said to be coprime or relatively prime iff they have no common factor other than 1 and -1, or equivalently, if their greatest common divisor is 1. For example, 6 and 35 are coprime, but 6 and 27 are not because the with N form a finite groupIn mathematics, a group is a set, together with a binary operation satisfying certain axioms, detailed below. The branch of mathematics which studies groups is called group theory. The historical origin of group theory goes back to the works of Evariste G under multiplication moduloModular arithmetic Group theory In mathematics, modular arithmetic is a system of arithmetic for certain equivalence classes of integers, called congruence classes . In modular arithmetic, numbers 'wrap around' after they reach a certain value (the modulu N, which is typically denoted (Z/NZ)^×. By the end of step 3, we have an integer a in this group. Since the group is finite, a must have a finite order r, the smallest positive integer such that

Therefore, N | (a ^r - 1). Suppose we are able to obtain r, and it is even. Then

r is the smallest positive integer such that a ^r ≡ 1, so N cannot divide (a ^{r / 2} - 1). If N also does not divide (a ^{r / 2} + 1), then N must have a nontrivial common factor with each of (a ^{r / 2} - 1) and (a ^{r / 2} + 1).

Proof: For simplicity, denote (a ^{r / 2} - 1) and (a ^{r / 2} + 1) by u and v respectively. N | uv, so kN = uv for some integer k. Suppose gcd(u, N) = 1; then mu + nN = 1 for some integers m and n (this is a property of the greatest common divisor.) Multiplying both sides by v, we find that mkN + nvN = v, so N | v. By contradiction, gcd(u, N) ≠ 1. By a similar argument, gcd(v, N) ≠ 1.

This supplies us with a factorization of N. If N is the product of two primes, this is the only possible factorization.

2.2 II. Finding the period

Shor's period-finding algorithm relies heavily on the ability of a quantum computer to be in many states simultaneously. Physicists call this behaviour a " superpositionQuantum superposition is the application of superposition principle to quantum mechanics. It occurs when an object simultaneously "possesses" two or more values for an observable quantity (e. the position or energy of a particle). More specifically, in qu" of states. To compute the period of a function f, we evaluate the function at all points simultaneously.

Quantum physics does not allow us to access all this information directly, though. A measurement will yield only one of all possible values, destroying all others. Therefore we have to carefully transform the superposition to another state that will return the correct answer with high probablity. 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 .

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).
Implement the function f as a quantum transform. To achieve this, Shor used repeated squaring for his modular exponentiation transformation.
Perform a quantum Fourier transform. By using controlled NOT gates and single qubit rotation gates Shor designed a circuit for the quantum Fourier transform that uses just gates.

After all these transformations a measurement will yield an approximation to the period r. For simplicity assume that there is a y such that yr/N is an integer. Then the probability to measure y is 1. To see that we notice that then

for all integers b. Therefore the sum that gives us the probability to measure y will be N/r since b takes roughly N/r values and thus the probability is 1/r. There are r y such that yr/N is an integer, so the probabilities sum to 1.

Note: another way to explain Shor's algorithm is by noting that it is just the quantum phase estimation algorithm in disguise. Quantum algorithms

3 References

Preprint of the original paper by Peter Shor:

Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, Peter W. Shor

A general textbook on quantum computing:

Quantum Computation and Quantum Information, Michael A. Nielsen, Isaac L. Chuang, Cambridge University Press, 2000

<Hide>

Home > Shor's algorithm