I’ve been wanting to write an article on Shor’s Algorithm but every time I start I find that I need to devote a large chunk of writing to explaining the Quantum Fourier Transform component, which ends up just taking up way too much of the article.

So instead, I thought I’d write this article to explain, at a high level, why a quantum algorithm would need a QFT in it in the first place; and then tackle Shor’s algorithm in a later article once the groundwork is laid.

Understanding why a QFT is useful in an quantum circuit can lead to a better understanding of the circuit design in general, and this understanding can scale to many other algorithms too.

So we are going to try to get to the point that when you see a “QFT” block in a quantum circuit diagram you won’t have to ask: “why is that there?”.

## Introduction

When a register of qubits is entangled and in a superposition, they can contain a huge amount of information, exponentially more than classical bits. The problem is: measuring the register results in the exact same amount of information as would measuring a classical register, i.e. one, single result.

But qubits can potentially contain an infinity of possible results – after all, they are essentially probability distributions. So who is to say the one we measured is correct?

Enter the mighty quantum Fourier transform.

If a problem is framed correctly (and we’ll talk more about that later), then a register of qubits can be transformed in to a new state whereby the measurement of that new state has had all the information focused in to one point with an infinite amplitude.

We also want to keep in the back of our mind the number one application of this process: Shor’s Algorithm.

Briefly, Shor’s Algorithm finds an integer’s prime factors. For example, the integer $N = 34866$ can be written as $34866 = 2 \times 3 \times 3 \times 13 \times 149$ where each $\left\{2,3,13,149\right\}$ are prime. More precisely, SA finds the order of an element $a$ modulo $N$. And so, the problem of finding a non-trivial (e.g. prime) factor of an integer is reduced to finding the order of a non-trivial (e.g. prime) element of the multiplicative quotient group $(\mathbb{Z}/n\mathbb{Z})^{\times}$.

If that’s too high-brow for you, don’t worry, we’ll get to this in the next article. First, we need to know what QFT can do for us and only then will we start to realise how it can be useful in the problem of finding prime factors.

## The General Idea Behind Using QFTs in Quantum Algorithms

In general, you will use a QFT in a quantum algorithm when you have already used superposition and entanglement to encode a problem on to an array of qubits, and you now what to measure those qubits to obtain an answer to the problem.

The problem with measuring a register of entangled qubits in superposition is that you will only ever get one single result (destroying the others) with only some probability that it is the correct one.

Instead, if you could somehow transform the register of entangled qubits in to another state altogether that, not only singles-out the correct result but also gives the associated probability of the singled-out result being correct (including the constraint that the sum of all probabilities equal one), then that would be marvelous!

But does such a transformation exist?

Yes, and it has a name: quantum phase estimation, and the trick is to express the problem as a unitary operator $U$ that acts on the register of qubits such that

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

where $0 \leq \theta < 1$ is knows as the phase. Also assume that the number of qubits is some power of two, i.e. $N = 2^n$. Then, if we make these assumptions about $U$, and they are quite strong assumptions, then two very interesting things happen that allows us to single-out correct results:

### First Interesting Thing

You can split additions in the exponent in to multiplications:

$U^{2^n}=U^{2^n + 0 } = U^{2^n+(1-1)}= U^{2^n-1}U=U^{2^n-1}e^{2\pi i \theta}$

Let’s initiate the pattern again…

$\displaystyle U^{2^n} = \cdots = U^{2^n-1}e^{2 \pi i \theta} = U^{2^n-1+0}e^{2 \pi i \theta} = U^{2^n - 1 + (1-1)}e^{2 \pi i \theta} = U^{2^n - 2}e^{2(2 \pi i \theta)}$

Doing this $n-1$ more times:

$\displaystyle U^{2^n} = \cdots = U^{2^n - 2^n}e^{2^n(2\pi i \theta)} = U^0e^{2\pi i 2^n \theta} = e^{2\pi i 2^n \theta}$

and we have the main result:

$\displaystyle U^{2^n} = e^{2\pi i 2^n \theta}$

What does this mean?

It means that anywhere we see $U^{2^n}|\psi\rangle$ we can replace it with $e^{2\pi i 2^n \theta}|\psi\rangle$, something which we will be doing in the following calculation.

Now let’s make this a controlled unitary operation on qubits. All this means is that you apply $U$ on $|\psi_i\rangle$ in the target register only if $U|i\rangle = |1\rangle$ in the control register.

This means we need two registers, denoted $|0\rangle^{\otimes n}|\psi\rangle$, consisting of $n$ qubits each.

We also apply the Hadamard gate to the first register to get them all in to a superposition, so we have:

$\displaystyle \frac{1}{\sqrt{2^n}}\left( |0\rangle + |1\rangle \right)^{\otimes n}|\psi\rangle$

If we apply the unitary operator $U$ on the first qubit $|0\rangle$ we get

as (To be Completed)

### Second Interesting Thing

After applying $n$ controlled $U$ operations to each of the $n$ qubits in the target register $|\psi\rangle$ (controlled by states of the control register $|0\rangle$), the combined state of the control register (remember, after the Hadamard gate has been applied to each qubit) is:

$\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}}$

This is nothing but:

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

where $|k\rangle$ is the binary representation of $k$, i.e. it is the $k^{\textup{th}}$ computational basis (see the previous article here with a more in-depth explanation) But notice that since all the change is in the global phase part of the summation, the target register is essentially (physically) left completely unchanged!

### Applying the Inverse Quantum Fourier Transform

The form of the target qubit register above inspires us to apply the inverse quantum Fourier transform, which yields

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

which equals

$\displaystyle \frac{1}{2^n} \sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} \exp\left( -\frac{2\pi i k}{2^n}(x-2^n\theta) \right) |x\rangle$

Now, we would like to perform a measurement on this second register (as it contains our answers!). However, by definition, quantum measurements must yield real results and therefore are modelled by performing inner products with the measurement state. Probabilities associated with measurement are then found by taking the absolute value squared, in the usual way:

$\displaystyle \mathbb{P}[a] := \left| \langle a | \psi | x \rangle \right|^2$

Our problem here is that we have no value of $a$ in our expression, we only have $n$, $k$, $\theta$, and $x$. Uh oh!

How can we get one in there?

### Phase Approximation Representation

This is where the phase approximation part comes in!

Take that little exponent $-\frac{2\pi i k}{2^n}(x-2^n\theta)$. We know that $\theta \in [0,1]$, thus $\mathbb{R} \ni 2^n\theta \in [0,2^n]\,\forall n \in \mathbb{Z}$. Thus, $2^n\theta$ is a real number, not an integer. We can always split real numbers out in to integers plus an difference, i.e. we always have $\textup{Real Number } \approx \textup{ Integer } + d$, where $d$ is always less than or equal to one-half, so long as $\textup{Integer}$ is the nearest integer to $2^n$.

We don’t need that $2^n\theta$ bit in the exponent. So we approximate it as

$\displaystyle 2^n \theta \approx a + 2^n d$

for all $n$, where $a$ is the nearest integer to $2^n \theta$, and the difference (which scales with $n$) satisfies the bounds

$\displaystyle 0 \leq |2^n d | \leq \frac{1}{2}$

Now we have an expression, with a discretised, approximated phase that includes an $a$ in it:

$\displaystyle \frac{1}{2^n} \sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} \exp\left( -\frac{2\pi i k}{2^n}(x-2^n\theta)\right)$
$\displaystyle = \frac{1}{2^n} \sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} \exp\left( -\frac{2\pi i k}{2^n}\left(x-(a+2^n d \right)\right)$
$\displaystyle = \frac{1}{2^n} \sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} \exp\left( -\frac{2\pi i kx}{2^n}+\frac{2\pi i k a}{2^n} - \frac{2\pi i k 2^n d}{2^n} \right)$
$\displaystyle = \frac{1}{2^n} \sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} \exp\left( -\frac{2\pi i k}{2^n}(x-a)\right)e^{2\pi i d k }$

Performing measurement in the computational basis on the first, control, register yields the result $a$ with probability:

$\displaystyle \mathbb{P}[a] = \left| \left\langle a \Bigg| \frac{1}{2^n} \sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1} \exp\left( -\frac{2\pi i k}{2^n}(x-a)\right)e^{2\pi i \delta k }\Bigg| x\right\rangle \right|^2$

Evaluating the left-hand side of the inner product first we see that we get $(a-a)=0$ in the exponent, so that part reduces to 1. We can also pull out the $\frac{1}{2^n}$ outside of the absolute value squared to get $\frac{1}{2^{2n}}$. Lastly, since the $(a-a)=0$ cancellation leaves us with no terms with $x$ in them, the $x$-summation disappears as well, and we are left with:

$\displaystyle \mathbb{P}[a] = \frac{1}{2^{2n}} \left| \sum_{k=0}^{2^n - 1} e^{2\pi i \delta k } \right|^2$

When $d = 0$, which implies that $2^n \theta$ is precisely an integer and no approximation is necessary, then (remember, going from zero to $2^n - 1$ is, in fact, $2^n$ terms!):

$\displaystyle \mathbb{P}[a] = \frac{1}{2^{2n}} \left| \sum_{k=0}^{2^n - 1} e^{2\pi i \delta k } \right|^2 = \frac{1}{2^{2n}} \left| \sum_{k=0}^{2^n - 1} e^0 \right|^2 = \frac{1}{2^{2n}} \left| 2^n \right|^2 = \frac{1}{2^{2n}}(2^n)^2 = \frac{2^{2n}}{2^{2n}} = 1$

In other words, the qubit register, when measured, yields the correct result $a$ with probability 100%.

Wow!

If $d \neq 0$, i.e. $2^n\theta$ is not an integer, then the qubit register, when measured, yields the correct result with probability bounded below by 40.5%. Which is a pretty good lower bound, and, in fact, can be increased to practically 100% by including more and more qubits in the register[1].

## Summary

So what have we done so far?

Well, we have assumed that our mathematical problem can be expressed as a unitary operator on the input register of $2^n$ qubits. Using the properties of the unitary operator and the fact that we have exactly $2^n$ number of qubits we found that we could express the unitary operator as an exponential with phase equal to some factor of $2^n$, in other words, the size of the register becomes part of the phase of the mathematical problem. Then we found that the exponential could be factored in to a product of $n$ factors, where those factors themselves were motivated by the potential to implement each one as a Hadamard and Rotation gate in a quantum circuit. But then we noticed that the expanded, factored expression is precisely that of the quantum Fourier transform that we found in the previous article here.

Thus, assuming unitarity, power of two sizes of qubit registers, and the factors being Hadamard and Rotation gates, we find that the exponentiated factorisation has precisely the same form as if we had just applied a quantum Fourier transform!

The beauty of this result looking like the quantum Fourier transform is that all the transforming going on is only occurring with the global phases of the qubits, and not with their actual physical components. Thus, if we had encoded a mathematical problem in to a register of qubits, then our assumptions of unitarity, size, and factoring in to H and R-style gates, does not alter the state of the qubit – only their phases. One could say that all the information of the problem is now encoded in to the global phase of the register – which is essentially something we can do as much as we like without destroying the structure of the problem.

To get an actual result, however, we have to transform the information held in the global phase back in to a target register of qubits $|x\rangle$. To do this we applied the inverse quantum Fourier transform and found that if the phase (which is a real number with modulus) was exactly an integer then the global phase transforms back in to one single result with 100% probability! This is because the inverse QFT maps the exponentiated factored input register back in to a state that has focused all the amplitudes.

Which is utterly amazing in my opinion.

However, the likelihood that the global phase is exactly an integer is minuscule. But the neat thing about this setup is: when the phase is not a integer the global phase transforms back in to one single result with a non-zero probability – not a zero probability as if it were, say, a uniform probability distribution (which is what it is in the beginning). In fact, the probability is dependent on the size of the input qubit register, and repeated measurements will only serve to increase the probability of obtaining a correct answer, theoretically to 100% in the infinite limit.

While we have enforced quite a number of assumptions in this setup, it is still truly remarkable, yet completely mathematically logical, that performing, essentially what is a discrete quantum Fourier transform and then applying the inverse quantum Fourier transform gathers together the amplitudes and focuses them in to a delta-like function right at the point that we need it to. The algorithm knows to do this because that point where all the amplitudes are focused is an eigenvalue of the unitary operator.

Therefore, the quantum phase estimation algorithm utilises the power of linear algebra to manipulate the global phases of a register of entangles qubits in superposition such that the inverse quantum Fourier transform provides the answer that we are looking for with an infinite amplitude, a.k.a. 100% surety.

## Coming Up

In the next article we will be discussing Shor’s algorithm and how it used the sorcery of quantum phase estimation to find prime factors.

## 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).