Factoring

We now have as a primitive operation that the Fourier transform is a fast process on a quantum computer. Note that while the Fast Fourier transform on a conventional computer takes of order $N2^N$ steps, on a quantum computer the Fast Fourier transform of the state (note this is of the state, not of a collection of $2^N$ input numbers) takes only of order $N^2$ steps.

The first really significant result of Quantum Computing was Peter Shor's demonstration that factoring could be fast on a quantum computer. He accompished this by noticing that if one could find the period of a certain periodic function depending on the number in questin, one could factor that number. Finding that period made use of the quantum Fourier transform. In order to see how, we need to look at some number theory.

Let us assume that we have some integer $R$, which is the product of two prime factors $p$ and $q$. There are then a number of features of numbers which are important.

Definition: mod operation. Given two integers, $n$ and $m$, the term $n_{mod~m}$ means that integer, between $0$ and $m-1$ which is the remainder when you divide $n$ by $m$. I.e., $n=n_{mod~m} + k m$ for some integer $k$.

Now, for some number $x$ lying between 1 and $R-1$, which shares no common factors with $R$, consider $(x^r)_{mod~R}$. Eventually for some (smallest) value of $r$, this must be equal to $1$. ( since there are only $R-1$ possible numbers that this could be, eventually one power must equal some other power. I.e., $(x^s)_{mod~R}=(x^t)_{mod~R}$ which means that $R$ divides $(x^t(x^{s-t}-1)$. Since x has no common factors with $R$, neither does $x^t$, so $x^{s-t}-1$ must be a multiple of $R$ and $(x^{s-t})_{mod~R}=1$. Define $r$ as the smallest such power.

Then the function $(x^y)_{mod~R}$ is a periodic function in $y$ with period $r$. There are now three possibilities for that $r$ :

a)$r$ is odd;

If $r$ is even then we can write $(x^r-1)$, which is a multiple of $R$ as $(x^{r\over 2}-1)(x^{r\over 2}+1)$. Then, either

b) $R$ divides $x^{r\over 2}-1$, in which case our $r$ was not the smallest possible value of $r$,

c) $R$ divides $x^{r\over 2}+1$,

or

d) or one, but not both, of the factors of $R$ divides $x^{r\over 2}-1$ ( and thus also $(x^{r\over 2})_{mod~R}-1$.) I.e., $R$ and $(x^{r\over 2})_{mod~R}-1$ have a common factor.

If two numbers have a common factor, one can rapidly discover what that common factor is using Euclid's algorithm. If two numbers have a common factor, then the remainder when dividing the larger by the smaller also has the same common factor. Successively dividing in this way eventually leads to that unique greatest common factor in a time less than of order $ln(R)^2$.

Thus, if we can find the period of the function $(x^y)_{mod~r}$, we can test whether this $r$ falls into category d, and if it does, we have a factor of $R$. If it does not, (i.e., $r$ falls under classes a,b, or c), we try with another value of $x$. For randomly selected x, Shor claimed that there will be at least a 50% probability that the $r$ will fall into class d, and that we will have a solution. After testing a small number of randomly chosen $x$, the probability will become overwhelming that we will have found the factor. Note that the Shor algorithm is not a deterministic one. It is one in which the probability of not finding the right answer decreases at least exponentially with the number of trials.

The solution thus hinges on finding the period of the function, $(x^y)_{mod~R}$ for a given $x$. Finding periods is ideally suited to a Fourier Transform. To do this, first design a computer which takes a state $\vert y;0>$ and calculates $\vert y;x^y_{mod~R}>$. This need not even be a reversible computer as long as nothing in the environment becomes correlated with $y$. This can be done in a number of operations of order $ln(R)^\beta$ where $\beta$ is a number like 3. Then feed into this computer the state $\sum_{y=0}^{2^{2N}} {1\over 2^N}\vert y;0>$, where $N$ is the first integer larger than $ln_2(R)$-- i.e., $2^N>R$. The maximum value of $y$ is thus greater than $R^2$. This will produce the state ${1\over 2^N}\sum_y \vert y;(x^y)_{mod~R}>$. Measure the output state, (the bits which correspond to the output, $(x^y)_{mod~R}$ but not the input state. Assume that this measurement gave the value $C$ (it does not matter what this value actually is. It plays no role. This measurement need not even be carried out at this point, since those output bits will play no further role in the calculation and could also be measured a the end of the experiment). This will leave the system in the state

$$\sum_{y\vert(x^y)_{R}=C}{1\over \sqrt{M} } \vert y;C> = \sum_y {1\over \sqrt{M}} \alpha_y \vert y;C>$$ (15)

where $\alpha_y$ is 1 if $(x^y)_{mod~R}=C$ and is 0 otherwise. $M$ is the largest integer in ${2^{2N}\over r}$. These values of $y$ for which $\alpha_y$ is unity will be spaced $r$ apart, where $r$ is the required shortest period such that ($x^r_{mod~R}=1$).

We have a state in which the amplitudes are periodic and can do a Fourier transform of these amplitudes. The resultant state will be $\sum_k \tilde\alpha_k \vert k>$, where the $\tilde\alpha_k$ are the Fourier transform of the

$$\tilde\alpha_k = \sum_y {1\over 2^N} e^{i2\pi ky 2^{-2N}}{1\over \sqrt{M}} \alpha_y$$

$$= \sum_{n=0}^{M-1} {{1\over 2^N\sqrt{M}} e^{i 2\pi k(y_0+nr}2^{-2N}}$$

$$= {e^{i 2\pi k y_02^{-2N}}\over 2^N\sqrt{M}} \sum_{n=0}^{M-1} e^{i 2\pi knr 2^{-2N}}$$ (16)

This $\tilde\alpha_k$ will be non-zero only for those $k$ which lie close to some multiple of $2^{2N}/r$. Defining $k_s=\left[ s {2^{2N}\over r}\right]$, where $[]$ designate the "greatest integer in", and $z= s {2^{2N}\over r}-k_s$, we have for $k$ near $k_s$

$$\vert\tilde\alpha_k\vert^2\approx {M\over 2^{2N}}\vert\int_0... ...M\over 2^{2N}}{\vert\sin(\pi z)\vert^2\over[2\pi(k-k_s+z)]^2}$$ (17)

I.e., even in the worst case, where $z=1/2$, the width of the peak in $k$ space is only of order unity. It is easy to discover which value of $k$ within two or three of the measured position correspond to a possible value of $r$. The uncertainty in r from this uncertainty in $k$ is

$$\Delta r\approx \Delta k {r^2\over s2^{2N}} < \delta k \left({r\over R}\right)^2$$ (18)

which is typically much less than unity.

A measurement of $k$ will then give a us a number which is a multiple of $2^{2N}/r$. Unless $r$ and the multiple have a common factors (a rare situation), one can uniquely determine $r$ from the measured value of $k$. One can then use that $r$ to try to find the common factors of $(x^{r/2}-1$ and $R$. If one finds a common factor, one has a factor of $R$. If one does not, one tries again with a different value of $x$. The probability is thus very high that in only a few attempts one will have found a factors $R$.