Quantum Fourier Analysis

As we mentioned before, the heart of the Shor algorithm is a quantum formulation of Fourier analysis that is much faster than the classical Fourier transform in finding the period of a periodic function. The quantum method is similar to the discrete Fourier transform for a classical signal.

We want to show how the quantum Fourier analysis allows us to find the smallest period $r$ of the function

$$f(x) = a^x \bmod N,$$

with $f(x) = f(x+r)$, excluding $r=0$, as mentioned previously. We have shown earlier that if we know the period, we can find the factors of $N$. We have used $x$ as the exponent to match what other authors have used and to link to the way we have previously labeled multi-qubit basis states. As usual, $a$, $x$, $r$, and $N$ are integers.

As we proceed through the algorithm, you should pay attention to where we use superposition states and measurements, which we have seen to be key features of other quantum algorithms.

The first ingredient we need is the quantum implementation of the function $f (x) = a^x \bmod N$ as a quantum function gate $U_f$. We won’t worry about the details of that implementation, but we note that it is usually based on binary modular exponentiation. As we have seen in other quantum algorithms, the function gate has two “registers” of input states: an upper register and a lower register, as shown in the figure below.

As usual, we start off with computational basis states. Both the upper and lower register states are $n$-qubit states with $n$ chosen so that $2^n = N$, the number we want to factor. The upper-register states are then acted on by Hadamard gates to produce a superposition state consisting of equal contributions of all the basis states labeled by the binary numbers $x$, where $x$ is in the range $[0, N − 1]$. We have seen this procedure in several of the other quantum algorithms. After the Hadamard gate acts on the upper-register states, the system state is

$$\vert\psi_1\rangle = H^{\otimes n} \vert\psi_0\rangle = \underbrace{\frac{1}{\sqrt{N}} \sum_{x=0}^{2^{n}-1} \vert x \rangle}_\text{upper register} \underbrace{\vert 0 \rangle_n.}_\text{lower register}$$

In analogy with some of the other quantum algorithms, the modular exponentiation function gate $U_f$ (not to be confused with the Fourier function $U_F$) then acts on the state in the equation above to produce the state

$$\vert\psi_2\rangle = U_f \vert\psi_1\rangle = \frac{1}{\sqrt{N}} \sum_{x=0}^{2^{n}-1} \underbrace{\vert x \rangle}_\text{upper register} \hspace{0.1cm} \underbrace{\vert f(x) \rangle.}_\text{lower register}$$