In this last article we attempted to motivate the use of the Quantum Fourier Transform (QFT) in a quantum circuit by looking at what happens when we assume:

Then we could then factor the unitary operator as

\displaystyle U^{2^n}|\psi\rangle = e^{2\pi i 2^n \theta}|\psi\rangle

We then extended the unitary operator in to a controlled unitary and noticed that it has the exact same form as the controlled phase gate R which essentially maps |1\rangle to e^{i\theta}|1\rangle.

With the Hadamard gate H and the controlled phase gates R we could then apply a sequence of them to build the following quantum state:

\displaystyle \frac{1}{\sqrt{2^n}} \underbrace{ \left( |0\rangle + e^{2\pi i 2^{n-1}\theta}|1\rangle\right)}_{\textup{first qubit}} \otimes \cdots \otimes \underbrace{\left(|0\rangle + e^{2\pi i 2^{1}\theta}|1\rangle\right)}_{(n-1)^{\textup{st}}\textup{ qubit}} \otimes \underbrace{\left(|0\rangle + e^{2\pi i 2^{0}\theta}\right)}_{n^{\textup{th}}\textup{ qubit}}

which is nothing but:

\displaystyle \frac{1}{\sqrt{2^n}} \sum_{k=0}^{2^n - 1} e^{2\pi i \theta k}|k\rangle

which is the mathematical represention of the Fourier transform!

Then, in this article, we derived the actual matrix representation of the QFT. Here is what it looks like for a resgister of 4 qubits:

\displaystyle \textbf{QFT}_4 := \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & i & -1 & -i \\ 1 & -1 & 1 & -1 \\ 1 & -i & -1 & i \end{pmatrix}

How do we use this?

Let’s say we have two quantum registers that differ only in their relative positions:

\displaystyle |\Theta\rangle := \begin{pmatrix} \alpha_0 \\ \alpha_1 \\ \alpha_2 \\ \alpha_3 \end{pmatrix} \quad\quad\quad\quad |\Psi\rangle := \begin{pmatrix} \alpha_1 \\ \alpha_2 \\ \alpha_3 \\ \alpha_0 \end{pmatrix}

Then look what happens when we apply the QFT to them:

\displaystyle |\widehat{\Theta}\rangle = \textbf{QFT}_4|\Theta\rangle = \frac{1}{2} \begin{pmatrix} \alpha_0 + \alpha_1 + \alpha_2 + \alpha_3 \\ \alpha_0 + i\alpha_1 - \alpha_2 - i\alpha_3 \\ \alpha_0 - \alpha_1 + \alpha_2 - \alpha_3 \\ \alpha_0 - i\alpha_1 - \alpha_2 + i\alpha_3 \end{pmatrix} =: \begin{pmatrix} \beta_0 \\ \beta_1 \\ \beta_2 \\ \beta_3 \end{pmatrix}

and

\displaystyle |\widehat{\Psi}\rangle = \textbf{QFT}_4|\Psi\rangle = \frac{1}{2} \begin{pmatrix} \alpha_0 + \alpha_1 + \alpha_2 + \alpha_3 \\ -i\alpha_0 + \alpha_1 - i\alpha_2 - i\alpha_3 \\ -\alpha_0 + \alpha_1 - \alpha_2 + \alpha_3 \\ i\alpha_0 + \alpha_1 - i\alpha_2 - \alpha_3 \end{pmatrix} =: \begin{pmatrix} \beta_0 \\ -i\beta_1 \\ -\beta_2 \\ i\beta_3 \end{pmatrix}

which, crucially, only differs by a relative phase shift (see the ordering of the \beta‘s is (0,1,2,3) in both cases), which makes absolutely no impact on the measurement of the register.

The phase of the state does not effect the probability of measuring that state.

As another illustrative example, imagine that we have the following two physically identical states:

\displaystyle |\Theta\rangle := \begin{pmatrix} 1 \\ 1 \\ 1 \\ 1 \end{pmatrix} \quad\quad\quad\quad |\Psi\rangle := \begin{pmatrix} 1 \\ i\cdot 1 \\ (-1)\cdot 1 \\ -i\cdot 1 \end{pmatrix}

The application of the QFT on each of these will result in different outputs even though the inputs are physically identical!

\displaystyle |\widehat{\Theta}\rangle = \textbf{QFT}_4|\Theta\rangle = \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix}

\displaystyle |\widehat{\Psi}\rangle = \textbf{QFT}_4|\Psi\rangle = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \end{pmatrix}

And this shows that one can have two physically identical states but physically different Fourier transformed states. While also having two physically different states but physically identical Fourier transformed states. It appears that the QFT is sensitive to some characteristics of a register of qubits, while being completely indifferent to others.

We will exploit this behaviour of the QFT in what follows.

The Algorithm

So how can an algorithm find prime factors?

Well, there are many classical algorithms which do the job just fine (although slowly) and they’ve been around for a long time. For example, the quadratic sieve or the general number field sieve (the fastest known classical algorithm), which uses a few simplifying assumptions (like N is composite and odd, the Euclidean algorithm, the fundamental theorem of arithmetic, and the Chinese remainder theorem, etc…) to speed things up. But they are all essentially implementing the greatest common divisor (GCD) function that spits out the list of prime factors as you choose different, randomly chosen starting points, denoted a.

These are all classical algorithms – and not the subject of this article. Suffice it to say: those algorithms are all very well known and work rather well. I would say that the only weakness in the classical algorithms is in the subroutine that attempts the find the period of the function f(x) := a^x \mod N, where a is the random choice that the algorithm makes in its first step that attempts to preclude it from potential divisors of N.

The faster the algorithm can preclude more and more a‘s the faster it can narrow down non-trivial factors of N, leaving just the best candidates for prime factors. But it still has to randomly choose a starting point a and decide if it satisfies as being a prime factor or not.

Thus, if the algorithm finds out that \gcd(a,N) \neq 1 then it knows that a results in a non-trivial factor and we can exclude it. However, if it finds that \gcd(a,N) = 1 (i.e. a trivial factor) then a only might be a prime factor and further testing must be done.

This further testing is when we need to figure out the period of

\displaystyle f(x) := a^x \mod N

If it turns out that the period is odd then the a chosen at random is no-good. However if it is even then there is a good chance it is good (just one more classical test is required).

It is in the figuring out the order of this periodic function where the quantum Fourier transform comes in.

Using the QFT to Find the Order of a Periodic Function

First, note that there are many ways to factor an integer besides reducing factoring to period-finding.

In the last section above we showed that we can easily find a factor of N given the order of some element. What remains is how do we determine the order? Because, if we know the order we can exclude the test if it is odd and move on to the next test.

Classical computers suffer badly when trying to figure out the order of a function because they have to check each candidate one after the other until a success is found. Quantum computers, on the other hand, c

Even and Odd Functions

OK, two things can happen when you try to compute f(x+r). Either f(x+r)=f(x), like, for example, when you add 360 degrees to the argument of a sine function: \sin(x+2\pi) = \sin(x)) and we say that it is periodic. Or, f(x+r) = a^{x+r}\mod N and we say that it is not periodic.

If f(x) = f(-x) then we call the function even and there will be symmetry about x=0. They are called even because the first such function discovered that display this property were f(x) = x^n where n is an even integer. However, not all even exponents result in an even function. For example, f(x):=(x+1)^2 is not even.

A function is odd if it changes sign when the argument is negative: -f(x) = f(-x) and there will again be symmetry about x=0.

Given these two definitions we can say that the cosine function is even while the sine function is odd.

Even and Odd do not cover all examples. There are a huge number of functions which are neither even nor odd. Yet, it is very easy to test if a function is even or odd: just substitute -x for x in the function argument and see what you get. If the negative sign works its way through and ends up out the front then you have an odd function. If it works its way through and cancels with itself leaving the original function as though you had put a positive argument in, then you have an even function. If you get some ugly mess, then you have neither.

Primitive Roots of Unity

The last tool we need in our toolbox is the concept of a primitive root of unity. Recall that with the complex numbers there always exists n solutions to the simple equation

\displaystyle z^n = 1

For example, if n=2, the complex number z would be +1 or -1. If n=4, then z = \{1, i, -1, -i\}.

But wait a second. So far, each of these solutions (i.e. \{1, i, -1, -i\}) are also all solutions to this equation:

\displaystyle\omega = e^{2\pi i / n}

As such, it is much easier to write the solutions for n=4 as simply \omega^n where n runs from 1 through to 4, in this example. So we don’t need to actually calculate the solutions to z^n = 1, we simply use the \omega function (the so-called primitive root of unity) at each n to find the full set of solutions.

In this language, when n=5, then the solutions are simply \{\omega^1, \omega^2, \omega^3, \omega^4, \omega^5\} and we are done.

If you want to know specifically what, say, \omega^5 is, then we evaluate it as

\displaystyle \omega^5 :=e^{2\pi i / n} = e^{2\pi i /5}

Graphically, these solutions all lie on the unit circle (hence the name):

PrimitiveRootsOfUnity5

The Discrete Fourier Transform

We’ve already seen in past articles that the QFT can be written in matrix form.

DiscreteQFTInMatrixForm

The 2-dimensional QFT (i.e. with M = 2) becomes

\displaystyle \mathbf{QFT}_2 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & \omega \end{pmatrix}

But since \omega := e^{2\pi i / n} = e^{2\pi i / 1} = e^{2 \pi i} = 1, we have that

\displaystyle \mathbf{QFT}_2 = \frac{1}{\sqrt{2}}\begin{pmatrix} 1 & 1 \\ 1 & \omega \end{pmatrix} = H^{\otimes 2}

is just the 2-dimensional Hadamard gate!

Indeed, the QFT is a generalisation of the Hadamard gate.

The QFT is unitary because its columns are all orthonormal. This also means that whenever you perform the QFT and then its adjoint, you get the identity operator:

\displaystyle \mathbf{QFT}_M \mathbf{QFT}^{\dagger} = I

Period Finding

What is period finding?

Well, suppose you have a periodic function (e.g. \sin(x)), that is, some function which repeats itself for larger and larger input values. The sine of x is periodic because when x = \pi, \sin(x) = 0 which is that same value as when x = 0. In other words, \sin(0) = \sin(\pi) = \sin(2\pi) = \cdots for all integer multiples of \pi.

But what if I said that \pi = 2\pi?

It does, in modulo \pi, it does.

In fact, all of those x‘s that render the sine function zero are all equal to each other…in module \pi.

Periodic functions and arguments equalling one another in some modulo are equivalent statements:

A periodic function has the property that f(x)=f(y) if and only if x \equiv y \mod r

In our case, the remainder r was just \pi. But in general, we don’t know that f(x) is periodic…until we find r, the so-called period.

We can classicaly find the period r by checking precisely every single value that it could be…that’s r checks.

Very slow.

In fact, as the dimensionality n increases, the number of checks is r = 2^n, and so we say that finding the period classically is a problem in exponential time. One of the slowest, if not, the slowest types of problems.

With quantum computers though, we can place 2^n functions in superposition and query the values in just n checks. A so-called exponential speedup.

If we take our register of N+1 = 2^n +1 qubits, initialised in the zero state, we can place the first n in superposition, with

\displaystyle |0\rangle^{\otimes N}|0\rangle \xrightarrow[]{\mathbf{QFT}_N} \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle|0\rangle

Now, we transform our ancilliary zero-state according to some unitary operator U_f which essentially performs the evaluation of the function f(x):

\displaystyle |0\rangle^{\otimes N}|0\rangle \xrightarrow[]{U_f} \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} |x\rangle|f(x) \rangle

If we then decide to measure the ancilliary state |f(x)\rangle , it must collapse in to some measureable value f(x_0). Furthermore, since measuring |f(x) \rangle reveals some information about x, the QFT state |x\rangle must also collapse in to the pre-image of f(x_0).

But that’s not so bad, because we know that f is periodic.

Which means the pre-image must contain some set of \frac{N}{r}-1 periodic values:

\displaystyle f(x_0) \in \left\{ x_0, x_0 + r, x_0 + 2r, \dots, x_0 + \left(\frac{N}{r} - 1\right)r\right\}

So, our measurement makes this change:

\displaystyle \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}|x\rangle|f(x)\rangle \xrightarrow[]{\textup{measure}} \frac{1}{\sqrt{N}} \sum_{x=0}^{N-1} \left|\left( x_0 + \left(\frac{N}{r} - 1\right)r\right)\right\rangle|f(x_0) \rangle

\displaystyle = \frac{1}{\sqrt{\frac{N}{r}}} \sum_{j=0}^{\frac{N}{r}-1} \left|\left(x_0 +jr\right)\right\rangle|f(x_0) \rangle

The astute reader will notice that the summation has narrowed, and we will be just ignoring the last n bits, essentially they have been fixed by the measurement.

Now our register is in a periodic superposition where its period is equal to the period of the function f.

But we can’t measure it just yet! This is because when we run this algorithm up to this point we might measure a different value of |f\rangle , thus obtaining a periodic superposition that’s linearly shifted, and this random shift relays back useless information.

The QFT again comes to our rescue.

Recall that if a function f is periodic with period r such that N/k = r, then the Fourier transform \hat{f} will also be periodic but with a period k.

Further, recall that when this happens, any constant linear shift inherent in the function is transformed in to the phase of \hat{f}.

The Quantum Fourier Transform not only transforms periods of the form N/k to k, but also transforms constant shifts in to the phase.

Therefore, if we take the QFT of the first register, we will be left with only the states that are multiples of N/r. This is all in Section 5.3 of [2].

Applying the QFT to the first \frac{N}{r}-1 bits we get (as in [5]):

\displaystyle \sqrt{\frac{r}{N}}\sum_{j=0}^{\frac{N}{r}-1} |x_0 + jr \rangle \xrightarrow[]{\mathbf{QFT}} \frac{1}{\sqrt{r}} \sum_{j=0}^{r-1} \omega^j \left| i \frac{N}{r} \right\rangle

where \omega^j is just some, unimportant phase associated with each term due to the linear shift. Sometimes it is denoted by \omega^j := \omega^{(x_0 + jr)s}=e^{2\pi i j \frac{N}{r}}.

We can now measure and retrieve k\frac{N}{r} for some integer k.

We repeat this algorithm and measure to retrieve several multiples of N/r. Once we have enough values we can computer their GCD (thanks to Euclid’s Algorithm) to retrieve N/r. And since N is known, r is easy to deduce.

This algorithm can be summed up by the following circuit:

PeriodFindingCircuit

Example

Suppose we define a periodic function f(x) to be equal to f(x) := x\mod 2. In this case, we know beforehand that the period is 2. But let’s see if we can find the same value using the above quantum algorithm.

Let’s use a 3-qubit system, so that N = 2^n = 2^3 = 8. We could use any size, but for the convenience of the math, let’s keep to it N=8.

First, let’s apply the QFT:

\displaystyle |0\rangle^{\otimes 3}|0\rangle \xrightarrow[]{\mathbf{QFT}_8} \frac{1}{\sqrt{8}}\sum_{x=0}^7 |x\rangle|0\rangle

Now we apply our function:

\displaystyle \frac{1}{\sqrt{8}}\sum_{x=0}^7 |x\rangle|0\rangle \xrightarrow[]{U_f} \frac{1}{\sqrt{8}}\sum_{x=0}^7 |x\rangle|f(x) \rangle

We (can) measure (just to see what’s happening in this mid-step):

\displaystyle \frac{1}{\sqrt{8}}\sum_{x=0}^7 |x\rangle|f(x) \rangle \xrightarrow[]{\textup{measure }|f(x)\rangle } \frac{1}{2}(|1\rangle + |3\rangle + |5\rangle + |7\rangle)\otimes|1\rangle

Now we need to extract the period without that annoying linear shift. So we once again apply the QFT:

\displaystyle \frac{1}{2}(|1\rangle + |3\rangle + |5\rangle + |7\rangle) \xrightarrow[]{\mathbf{QFT}_8} \frac{1}{\sqrt{2}}(|0\rangle + |4\rangle)

Note: if instead of measuring |f\rangle = |1\rangle we had measured |f\rangle = |0\rangle, there would be a different linear shift. But the properties of the QFT dictatet that this only affects the phase of the Fourier transformed function. In other words:

\displaystyle \frac{1}{2}(|0\rangle + |2\rangle + |4\rangle + |6\rangle) \xrightarrow[]{\mathbf{QFT}_8} \frac{1}{\sqrt{2}}(|0\rangle + |4\rangle)

See how the answer is still \frac{1}{\sqrt{2}}(|0\rangle + |4\rangle) !?

Finally, if we take just a few measurements we will see varying amounts of |0\rangle and |4\rangle, and nothing else.

Taking the largest value, we can compute N/r = 4, and since we know that N=8 from our qubit register setup, it is clear that the period of f(x) is r = 2.

In this case, y = 4 was a multiple of N/r (i.e. a multiple of 8/2 = 4. When this is the case (and it definitely is not always the case – depending on the basis), then

\displaystyle \omega^{kry} = e^{2\pi i r y / N} = e^{n2\pi i} = 1

And so the coefficient was \alpha_y = \frac{\sqrt{r}}{N}frac{N}{r} = \frac{1}{\sqrt{2}}. It should be clear by now that we get this coeffcient due to the constructive interference in rotations around the unit circle. When y is not a multiple of N/r, we get destructive interference. This interference that we get is one reason why quantum computers are so well-equipped for period finding.

Additions in the phase of the qubit state create constructive and destructive interference, cancelling and enhancing the probabilities of observing the correct quantum state upon measurement after performing a quantum Fourier transform.

Summary

We saw how a QFT is sensitive to the phase-structure of a register of qubits. Just because a register of qubits is physically identical to another is not enough to ensure the QFT of those registers are identical. Small differences is the unobservable, unphysical global phases can wildly affect the outcome of the QFT.

We then found a way to programmatically turn a function in to a binary test, by determining whether or not it is an even or an odd function – a binary outcome.

Then we found a connection between the primitive roots of unity and the matrix elements that make up the unitary QFT. We saw that the simplest QFT is, in fact, just the Hadamard transform. Higher-dimensional QFTs are just unitary matrices of rotations in the complex plane, just as products of primitive roots of unity are.

We then came to the problem of period finding. By first placing a register of qubits in to a superposition (via a QFT as a generalised Hadamard), we then apply the periodic function whose period we seek as a unitary transformation on the superpositioned register of qubits. By the definition of periodic, if we make a measurement here, we know the qubit states must collapse in to one of the periodic values, but not necessarily the largest one that we seek. We can increase the probability of finding the right one by applying the QFT again (and in this case, not necessarily as a Hadamard but as a way to provide destructive and constructive interference in the global phases of the superpositioned qubits, so that the final measurement will have a higher likelihood of being the period that we seek.

References

[1] Cleve, Ekert, Macchiavello, Mosca – Quantum algorithms revisited, Proceedings of the Royal Society 454 (1998).

[2] Nielsen, N. & Chuang, I. L. – Quantum Computation and Quantum Information, Cambridge University Press, (2010).

[3] Kendon, V. M. & Munro, W. J. – Entanglement and its Role in Shor’s algorithm, arXiv:quant-ph/0412140 (2006).

[4] Jozsa, R. – Quantum factoring, discrete logarithms and the hidden subgroup problem, arXiv:quant-ph/0012084 (2001).

[5] Cleve, R., Ekert, A., Macchiavello, C., & Mosca, M., – Quantum Algorithms Revisited, (1997)