### 10.2 Computing the period of a sequence

Given the sequence* f(0), f(1), . . . , f(q-1)* where* q = 2 ^{n}*, find its period.

To start with, take two registers, the first of n-qubits to store the

*q*argument values of the function

*f*, and the second of k qubits, long enough to store the longest value of

*f(x)*. With an appropriately chosen

*U*, we get

_{f}A measurement on the second register now will collapse it to some value of f that corresponds to some

* x = x _{0}*. Given that

*f(x + kr) = f(x),*where r is the period of the function

*f*and

*k*is an integer, the first register will correspondingly attain a superposition of state vectors

*{…, x*. So, the state of the combined registers is

_{0}-r, x_{0}, x_{0}+r, x_{0}+2r,…}.For notational convenience, we now choose x_{0} to be the lowest* x∈{0,…, 2 ^{n}-1}* such that

*f(x) = f(x*Thus, the index j in the summation will take the values

_{0}).*0, 1,…, A-1.*We now apply the QFT to the first register

A measurement of the first register will yield a* |y〉* with probability

since

When r divides *2 ^{n}* exactly

*, A = 2*and

^{n}/r*A/ 2*, the probability becomes

^{n}= 1/rIf* y = A, 2A,* etc., then

because* jy/A* is an integer and hence

But if* y* is incommensurate (irrational) with A, then we will hit a range of points around the circle, eventually filling the whole circle so the resulting interference will be totally destructive, and we will have *p(y) = 0*. Therefore, in effect, the measurement will return a *y ∈{A, 2A,…, rA}.* From this we can easily find A, and knowing the range* 2 ^{n} *we can find

*r = 2*.

^{n}/AIn general,* r* will not divide *2 ^{n}* exactly, so measurements will return y scattered around integer multiples of

*1/r*, such that the constructive interferences produce narrow peaks at multiples of

*1/r.*Thus, we will obtain only a random multiple of the inverse period. To extract the period itself we will need to repeat this quantum computation roughly log

*log r/n*times in order to have a high probability for at least one of the multiples to be relatively prime

^{19}to the period r, thereby uniquely determining the period. This algorithm yields only a probabilistic answer but the probability can be made as high as we like. The actual determination of

*r*can be made by using the continued fractions algorithm.

This is a method for determining for an arbitrary real number, x, an expansion of the form^{20}

Consider, for example, 31/13. This is successively split into its integer and fractional parts,

A truncated continued fraction is called a convergent. The *k-th* convergent is written* [a _{0},…, a_{k}].* The decomposition terminates when the fraction has a numerator or a denominator of 1. The method terminates after a finite number of ‘split and invert’ steps for any rational number, since successive numerators are strictly decreasing.

One can show that if *φ= s/r* is a rational number and s and r are *L* bit integers, then the continued fraction expansion for φ can be computed using *O(L ^{3})* operations—

*O(L)*‘split and invert steps’ and

*O(L*gates for elementary arithmetic. There is also a useful theorem about continued fractions.

^{2})**Theorem 1.** If* s/r* is any rational number satisfying *|s/r- φ| ≤ 1/(2r ^{2})* then

*s/r*is a convergent of the continued fraction for

*φ*. Moreover the convergent is such that

*gcd(s, r) = 1.*

We can use this theorem to find the closest rationals to the terms s/r and hence find the period r. Furthermore, given

*φ*the continued fractions algorithm efficiently produces numbers s’ and r’ with no common factor, such that

*s’/r’ = s/r*. Euclid’s Algorithm for finding the greatest common divisor of two numbers is intimately related to continued fractions

^{21}.

To find the period, r, measure the state of the first register. This effectively samples from the discrete Fourier transform, and returns some number y’ that is some multiple s of *q/r*; that is *y’ /q ≈ s/r* for some positive integer s. To determine the period* r* we need to estimate s. This is accomplished by computing the continued fraction expansion for* y’/q*. By repeating the quantum computation several times (roughly *log log r/n* times) we create a set of samples of the discrete Fourier transform in the first register. This gives samples of multiples of* 1/r as s _{1}/r, s_{2}/r*,

*s*,… for various integers

_{3}/r*s*Once sufficient samples have been obtained from the first register, we can use the continued fraction technique to compute as to what the s

_{i}._{i}could be and hence to guess r.

Computing the period of a sequence lies at the heart of efficiently factoring numbers, which we discuss below.

### 10.3 Shor’s factoring algorithm

The problem of distinguishing prime numbers from composites, and of resolving composite numbers into their prime factors, is one of the most important and useful in all of arithmetic. […] The dignity of science seems to demand that every aid to the solution of such an elegant and celebrated problem be zealously cultivated. – Carl Friedrich Gauss

In 1994, Peter Shor surprised the world by describing a polynomial time quantum algorithm for factoring integers^{22}. It was declared a killer application and received huge publicity because the widely used* RSA*^{23}, a public key crypto-system, used in securing electronic bank accounts suddenly became utterly vulnerable. It relies on the difficulty of finding prime factors of large numbers. Shor’s algorithm was a shot in the arm to the quantum computing community.

Shor’s factoring algorithm has two parts: a quantum procedure within the algorithm and a classical algorithm that calls the quantum procedure. The algorithm uses a number theory result that relates the period of a particular periodic function to the factors of an integer. The crux of the algorithm is the quantum method for computing the period r of the function *f(a) = x ^{a}* mod N for

*a = 0, 1,*… that is exponentially more efficient than any known classical method. Thus, given an integer N (the number to be factored), construct

*f(a) = x*mod

^{a}*N*where

*x < N i*s a randomly chosen number which is coprime

^{24}to N. It can be shown that f(a) thus constructed is periodic, that is,

Here r is the first non-trivial power where* x ^{r} ≡ 1* mod

*N*, and that

*f(a)*is periodic with period

*r, i.e., f(a) = f(a+r) = f(a+2r) =*… Obviously, different values of

*x*may produce different periodicities. The periodicity of

*f(a)*can be determined by using the quantum algorithm described in Section 10.2. For a given N and a chosen x if the period r is an even number, we can write

19 Two integers are relatively prime if they do not share common positive factors (divisors) except 1.

20 For applications in quantum computing, it is convenient to allow a0 = 0 as well.

21 For a good description of continued fractions and an online calculator, see Knott ().

22 Shor (1994). An expanded version of the paper is available in Shor (1997).

23 The RSA system was invented by Ronald Rivest, Adi Shamir, and Leonard Adleman in 1978. It rules e-commerce and pops up in countless security applications. They received the Turing Award (2002) for their contributions to public key cryptography.

24 Coprime: Two integers a and b are coprime (or relatively prime) if the greatest common divisor of a and b is 1. For example, 55555 and 7811 are coprime even though neither number is itself a prime. One may use Euclid’s algorithm to determine if x and N are coprime.