Shor's Algorithm - Procedure

Procedure

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

Moreover, for the algorithm to work, we need not to be the power of a prime. This can be tested by taking square, cubic, ..., -roots of, for, and checking that none of these is an integer. (This actually excludes that for some integer and .)

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

In turn, finding such a is reduced to finding an element 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, as order-finding 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.