Let us now design a general circuit that performs the $n$-qubit QFT. From analyzing how it acts on the basis states, we can conclude that: 1. For a single qubit, the QFT is performed just using the Hadamard gate. 2. For $n \gt 1$ qubits, we may need to apply a Hadamard gate to produce a superposition, along with some kind of rotations to account for the added phases $\omega^{x \cdot y}$ . To understand how to create the circuit, it is beneficial to analyze what is happening to the qubits at an individual level. It turns out that it is possible to write the QFT in a way that is tensor-factorized. This representation, $$ U_{QFT}\vert x_1 x_2 \cdots x_n \rangle = \frac{1}{\sqrt N}\left[ \left(\vert 0 \rangle + e^{2 \pi i 0.x_n} \vert 1 \rangle \right) \left(\vert 0 \rangle + e^{2 \pi i 0.x_{n-1}x_n} \vert 1 \rangle\rangle \right) \cdots \left( \vert 0 \rangle + e^{2 \pi i 0.x_1x_2\cdots x_n} \vert 1 \rangle \right) \right], $$ looks very similar to the result of applying a Hadamard transform, except for the difference in phase between the $\vert 0 \rangle$ and $\vert 1 \rangle$ states on each qubit. Note that we've also introduced some new notation here in the exponents, called fractional binary, which we will soon discuss. In what follows, we will go through the steps to derive this factorized expression. We will first prove the following: $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N}\bigotimes_{k=1}^{n} \left[ \vert 0 \rangle + e^{\frac{2 \pi i}{2^k}x} \vert 1 \rangle \right]. \end{align} $$ The proof can be quite lengthy, therefore, we shall do it in two parts. --- ***Exercise F.3.2.*** (a) First, write down $y$ in its binary representation and derive an intermediate representation for the QFT $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N} \sum_{y=0}^{N-1} \omega^{x\cdot y} \vert y \rangle = \frac{1}{\sqrt N} \sum_{y=0}^{N-1} \prod_{k=1}^{n} e^{2 \pi i x \frac{y_k}{2^k} } \vert y \rangle. \\ \end{align} $$

Hint.

Summations can be taken out of an exponent and can be expressed as a product.

Solution.

We begin with the expression for applying the QFT to a computational basis state: $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N} \sum_{y=0}^{N-1} \omega^{x\cdot y} \vert y \rangle \\ &= \frac{1}{\sqrt N} \sum_{y=0}^{N-1} e^{\frac{2 \pi i}{N} x\cdot y} \vert y \rangle . \end{align} $$ Let's write down $y$ as a summation of its individual bits i.e., $$ y = \sum_{k=1}^{n} y_k 2^{n-k}. $$ Therefore, $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N} \sum_{y=0}^{N-1} e^{\frac{2 \pi i}{N} x\cdot \sum_{k=1}^{n} y_k 2^{n-k}} \vert y \rangle \\ &= \frac{1}{\sqrt N} \sum_{y=0}^{N-1} e^{\frac{2 \pi i}{2^n} x\cdot \sum_{k=1}^{n} y_k 2^n 2^{-k}} \vert y\rangle \\ &= \frac{1}{\sqrt N} \sum_{y=0}^{N-1} e^{2 \pi i x\cdot \sum_{k=1}^{n} \frac{y_k}{2^k} } \vert y \rangle.\\ \end{align} $$ The summation in the exponent can be expressed as a product of each term $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N} \sum_{y=0}^{N-1} \prod_{k=1}^{n} e^{2 \pi i x \frac{y_k}{2^k} } \vert y \rangle. \\ \end{align} $$

▢

(b) Continue from the intermediate representation and prove $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N}\bigotimes_{k=1}^{n} \left[ \vert 0 \rangle + e^{\frac{2 \pi i}{2^k}x} \vert 1 \rangle \right] . \end{align} $$

Hint.

It should be easier to separate each qubit in $y$ if the outer summation can be broken down in the following way: $$ \sum_{y=0}^{2^n-1} = \sum_{y_1=0}^{1} \sum_{y_2=0}^{1} \cdots \sum_{y_n=0}^{1}. $$

Solution.

Recall that our starting point is $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N} \sum_{y=0}^{N-1} \prod_{k=1}^{n} e^{2 \pi i x \frac{y_k}{2^k} } \vert y \rangle. \\ \end{align} $$ The term $\sum_{y=0}^{N-1}$ can be broken down for each qubit in the system with $$ \sum_{y=0}^{2^n-1} = \sum_{y_1=0}^{1} \sum_{y_2=0}^{1} \cdots \sum_{y_n=0}^{1} $$ and $$ \vert y \rangle = \vert y_1y_2 \cdots y_n \rangle. $$ Here, each of the $y_k$ terms in the exponent corresponds to one of the bits of $y$, $$ \begin{align} U_{QFT} \left\lvert x \right\rangle =\frac{1}{\sqrt{N}}\sum_{y_1=0}^1\sum_{y_2=0}^1\cdots \sum_{y_n=0}^1 \left(\prod_{k=1}^n e^{2\pi i x \frac{y_k}{2^k}}\right)\left\lvert y_1 \cdots y_n\right\rangle. \end{align} $$ Let us now see the action of this qubit-by-qubit. $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt{N}}\sum_{y_1=0}^1 e^{2\pi i x\frac{y_1}{2^1}}\left\lvert y_1\right\rangle \otimes \sum_{y_2=0}^1 e^{2\pi ix\frac{y_2}{2^2}}\left\lvert y_2\right\rangle\otimes\cdots\otimes \sum_{y_n=0}^1 e^{2\pi i x\frac{y_n}{2^n}}\left\lvert y_n\right\rangle \end{align} $$ Expanding the summation on the first qubit, we get $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt{N}}\left [e^{2 \pi i x \frac{0}{2^1} } \vert 0 \rangle + e^{2 \pi i x \frac{1}{2^1} } \vert 1 \rangle \right] \otimes \sum_{y_2=0}^1 e^{2\pi ix\frac{y_2}{2^2}}\left\lvert y_2\right\rangle\otimes\cdots\otimes \sum_{y_n=0}^1 e^{2\pi i x\frac{y_n}{2^n}}\left\lvert y_n\right\rangle \\ & = \frac{1}{\sqrt{N}}\left [\vert 0 \rangle + e^{ \frac{2 \pi i }{2^1}x } \vert 1 \rangle \right] \otimes \sum_{y_2=0}^1 e^{2\pi ix\frac{y_2}{2^2}}\left\lvert y_2\right\rangle\otimes\cdots\otimes \sum_{y_n=0}^1 e^{2\pi ix\frac{y_n}{2^n}}\left\lvert y_n\right\rangle. \end{align} $$ Similarly, by expanding the summation on each of the qubits, we obtain $$ \begin{align} U_{QFT} \vert x \rangle & = \frac{1}{\sqrt{N}}\left [\vert 0 \rangle + e^{ \frac{2 \pi i }{2^1}x } \vert 1 \rangle \right] \otimes \left [\vert 0 \rangle + e^{ \frac{2 \pi i }{2^2}x } \vert 1 \rangle \right]\otimes\cdots\otimes \left [\vert 0 \rangle + e^{ \frac{2 \pi i }{2^n}x } \vert 1 \rangle \right] \\ &= \frac{1}{\sqrt N}\bigotimes_{k=1}^{n} \left[ \vert 0 \rangle + e^{\frac{2 \pi i}{2^k}x} \vert 1 \rangle \right]. \end{align} $$

▢

--- Now that we have our final state in the following representation $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N}\bigotimes_{k=1}^{n} \left[ \vert 0 \rangle + e^{\frac{2 \pi i}{2^k}x} \vert 1 \rangle \right]. \end{align} $$ we need to determine which gates will produce this state. Taking a hint from the result in the previous exercise, we'd like elements that are $\vert 0 \rangle$ to be unchanged and the elements that are $\vert 1 \rangle$ to get a phase $e^{2 \pi i \frac{x}{2^k}}$. It is straightforward to design a gate that does this! $$ R_k = \begin{bmatrix} 1 & 0 \\ 0 & e^{\frac{2 \pi i}{2^k}} \end{bmatrix} $$ This looks quite familiar: it is an $RZ$ gate, up to a global phase! Putting the pieces together, we seem to need a Hadamard and some $Z$ rotations. The only thing left to figure out is the $x$ part, which in its current state is the decimal representation. Can that be broken down into actions on the individual bits as well? To do this, we need the concept of a *fractional binary*. The number $$ \frac{x_l}{2} + \frac{x_{l+1}}{2^2} + \cdots + \frac{x_m}{2^{m-l + 1}}, $$ is denoted via $$ 0.x_lx_{l+1} \cdots x_m. $$ Using this representation we can rewrite the following expression for the QFT $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N}\bigotimes_{k=1}^{n} \left[ \vert 0 \rangle + e^{\frac{2 \pi i}{2^k}x} \vert 1 \rangle \right] \end{align} $$ as $$ U_{QFT}\vert x_1 x_2 \cdots x_n \rangle = \frac{1}{\sqrt N}\left[ \left(\vert 0 \rangle + e^{2 \pi i 0.x_n} \vert 1 \rangle \right) \left(\vert 0 \rangle + e^{2 \pi i 0.x_{n-1}x_n} \vert 1 \rangle\rangle \right) \cdots \left( \vert 0 \rangle + e^{2 \pi i 0.x_1x_2\cdots x_n} \vert 1 \rangle \right) \right]. $$ This turns out to be really useful as we will see below. We now have a *product representation* for the QFT which gives us more information about how to build the QFT circuit. --- ***Exercise F.3.3.*** Perform the QFT on the state $\vert x \rangle = \vert 110 \rangle$ using the *product representation* of QFT.

Solution.

We are given $$ \vert x \rangle = \vert 110 \rangle = 6, $$ where $x_1 = 1$, $x_2 = 1$, $x_3 = 0$, and $N = 2^3 = 8$. $$ \begin{align} U_{QFT}^{\otimes 3}\vert x_1 x_2 x_3 \rangle &= \frac{1}{\sqrt N}\left[ \left(\vert 0 \rangle + e^{2 \pi i 0.x_3} \vert 1 \rangle \right) \left(\vert 0 \rangle + e^{2 \pi i 0.x_2x_3} \vert 1 \rangle \right) \left( \vert 0 \rangle + e^{2 \pi i 0.x_1x_2x_3} \vert 1 \rangle \right) \right] \\ &= \frac{1}{\sqrt 8}\left[ \left(\vert 0 \rangle + e^{2 \pi i 0.0} \vert 1 \rangle \right) \left(\vert 0 \rangle + e^{2 \pi i 0.10} \vert 1 \rangle \right) \left( \vert 0 \rangle + e^{2 \pi i 0.110} \vert 1 \rangle \right) \right] \\ &= \frac{1}{2 \sqrt 2}\left[ \left(\vert 0 \rangle + e^{2 \pi i \frac{0}{2}} \vert 1 \rangle \right) \left(\vert 0 \rangle + e^{2 \pi i \left(\frac{1}{2} + \frac{0}{4}\right) } \vert 1 \rangle \right) \left( \vert 0 \rangle + e^{2 \pi i \left(\frac{1}{2} + \frac{1}{4}+ \frac{0}{8}\right)} \vert 1 \rangle \right) \right] \\ &= \frac{1}{2 \sqrt 2}\left[ \left(\vert 0 \rangle + \vert 1 \rangle \right) \left(\vert 0 \rangle + e^{i\pi} \vert 1 \rangle \right) \left( \vert 0 \rangle + e^{ \frac{3\pi i}{2}} \vert 1 \rangle \right) \right] \\ &= \frac{1}{2 \sqrt 2}\left[ \left(\vert 0 \rangle + \vert 1 \rangle \right) \left(\vert 0 \rangle - \vert 1 \rangle \right) \left( \vert 0 \rangle - i \vert 1 \rangle \right) \right] . \end{align} $$ Additionally, you can verify that your answer matches the solution from the following equation $$ \begin{align} U_{QFT} \vert x \rangle &= \frac{1}{\sqrt N}\bigotimes_{k=1}^{n} \left[ \vert 0 \rangle + e^{\frac{2 \pi i}{2^k}x} \vert 1 \rangle \right]. \end{align} $$

▢

Codercise F.3.1 - The 3-qubit QFT

Codercise F.3.2 - Swapping qubits

Codercise F.3.3 - Putting the QFT together

Codercise F.3.4 - A recursive solution

Codercise F.3.5 - The QFT in PennyLane

The QFT and the Hadamard transform

Designing the n-qubit QFT circuit

The n-qubit QFT circuit

Gate count and complexity