Shor's algorithm

Procedure

The problem we are trying to solve is: given an odd composite number N , find an integer d , strictly between 1 and N , that divides N . We are interested in odd values of N because any even value of N trivially has the number 2 as a prime factor. We can use a primality testing algorithm to make sure that N is indeed composite.

Moreover, for the algorithm to work, we need N not to be the power of a prime. This can be tested by checking that N k is not an integer, for all k ≤ log 2 ⁡ ( N ) .

Since N is not a power of a prime, it is the product of two coprime numbers greater than 1 . As a consequence of the Chinese remainder theorem, the number 1 has at least four distinct square roots modulo N , two of them being 1 and − 1 . The aim of the algorithm is to find a square root b that is different from 1 and − 1 ; such a b will lead to a factorization of N , as in other factoring algorithms like the quadratic sieve.

In turn, finding such a b is reduced to finding an element a of 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 a , as this is a hard problem on a classical computer.

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.

Classical part

For example: N = 15 , a = 7 , r = 4 , g c d ( 7 2 ± 1 , 15 ) = g c d ( 49 ± 1 , 15 ) , where g c d ( 48 , 15 ) = 3 , and g c d ( 50 , 15 ) = 5 .

Quantum part: Period-finding subroutine

The quantum circuits used for this algorithm are custom designed for each choice of N and each choice of the random a used in f(x) = a^x mod N. Given N, find Q = 2^q such that N 2 ≤ Q < 2 N 2 , which implies Q / r > N . The input and output qubit registers need to hold superpositions of values from 0 to Q − 1, and so have q qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least N different x which produce the same f(x), even as the period r approaches N/2.

Proceed as follows:

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.

Obtaining factors from period

The integers less than N and coprime with N form a finite abelian group G under multiplication modulo N. The size is given by Euler's totient function ϕ ( N ) . 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 divides a r − 1 (also written N ∣ a r − 1 ). Suppose we are able to obtain r, and it is even. (If r is odd, see step 5.) Now b ≡ a r / 2 ( mod N ) is a square root of 1 modulo N , different from 1. This is because r is the order of a modulo N , so a r / 2 ≢ 1 ( mod N ) , else the order of a in this group would be r / 2 . If a r / 2 ≡ − 1 ( mod N ) , by step 6 we have to restart the algorithm with a different random number a .

Eventually, we must hit an a , of order r in G , such that b ≡ a r / 2 ≢ 1 , − 1 ( mod N ) . This is because such a b is a square root of 1 modulo N , other than 1 and − 1 , whose existence is guaranteed by the Chinese remainder theorem, since N is not a prime power.

We claim that d = gcd ⁡ ( b − 1 , N ) is a proper factor of N , that is, d ≠ 1 , N . In fact if d = N , then N divides b − 1 , so that b ≡ 1 ( mod N ) , against the construction of b . If on the other hand d = gcd ⁡ ( b − 1 , N ) = 1 , then by Bézout's identity there are integers u , v such that

Multiplying both sides by b + 1 we obtain

Since N divides b 2 − 1 ≡ a r − 1 ( mod N ) , we obtain that N divides b + 1 , so that b ≡ − 1 ( mod N ) , again contradicting the construction of b .

Thus d is the required proper factor of N .

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 behavior a "superposition" 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. If not for the no cloning theorem, we could first measure f(x) without measuring x, and then make a few copies of the resulting state (which is a superposition of states all having the same f(x)). Measuring x on these states would provide different x values which give the same f(x), 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 log ⁡ N .

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 f 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 Q = 2^q) that uses just q ( q − 1 ) / 2 = O ( ( log ⁡ Q ) 2 ) 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/Q 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 whose square gives us the probability to measure y will be Q/r since b takes roughly Q/r values and thus the probability is 1 / r 2 . There are r y such that yr/Q is an integer and also r possibilities for f ( x 0 ) , 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.

The bottleneck

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. Reversible circuits typically use on the order of n 3 gates for n qubits. Alternative techniques asymptotically improve gate counts by using quantum Fourier transforms, but are not competitive with less than 600 qubits due to high constants.

Discrete logarithms

Given prime p with generator g where 1 < g < p − 1 , suppose we know that x = g r ( mod p ) , for some r, and we wish to compute r, which is the discrete logarithm: r = log g ⁡ x ( mod p − 1 ) . Consider the abelian group ( Z p ) × × ( Z p ) × where each factor corresponds to modular multiplication of nonzero values, assuming p is prime. Now, consider the function

This gives us an abelian hidden subgroup problem, as f corresponds to a group homomorphism. The kernel corresponds to modular multiples of (r,1). So, if we can find the kernel, we can find r.

In popular culture

On the television show Stargate Universe, the lead scientist, Dr. Nicholas Rush, hoped to use Shor's algorithm to crack Destiny's master code. He taught a quantum cryptography class at the University of California, Berkeley, in which Shor's algorithm was studied.

Shor's algorithm was a correct answer to a question in a Physics Bowl competition in the episode "The Bat Jar Conjecture" of the TV series The Big Bang Theory.

In the animated film "Summer Wars," the character Kenji Koiso reads an article titled "Shor's Factorization Algorithm" while riding on a train, foreshadowing his ability to understand and calculate complex equations.