## Wednesday, 11 September 2013

### The Quantum Fourier Transform Circuit

The quantum Fourier transform $QFT$ was defined to map an arbitrary  computational basis state $\left|j\right>\in\mathcal{H}^{2^n}$ to the state
$\left|\psi\right>=QFT\left|j\right>=\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{k=0}^{2^n-1}e^{\frac{i2\pi jk}{2^n}}\left|k\right>.$
In this section, it will be shown that this state $\left|\psi\right>$ can be expressed as the tensor product of $n$ qubits $\left|\psi_i\right>$ so that
$\left|\psi\right>=\left|\psi_1\right>\otimes\left|\psi_2\right>\otimes\dots\otimes\left|\psi_n\right>.$
Such a construction will provide insight on how an explicit circuit can be constructed that implements the $QFT$.

Before beginning, recall the equivalent means of representing the computational basis states of $\bigotimes_{i=1}^{n}\mathcal{H}^2$ in the binary representation as $\left|b_1b_2\dots b_n\right>$, for $b_i\in\{0,1\}$, and  the decimal representation as $\left|j\right>$, for an integer $j\in{0,1,\dots,2^n-1}$, given by the map
$\displaystyle\sum\limits_{i=1}^{n}b_i2^{n-i}=b_12^{n-1}+b_{2}2^{n-2}+...+b_{n-1}2+b_n=j.$
For some fraction $\omega\in[0,1)\subset\mathbb{R}$, a binary representation can be defined for this decimal as $\omega=0.x_1x_2\dots x_n$ for some $n$ as the map
$\omega=\displaystyle\sum\limits_{i=1}^{n}x_i2^{-i}=x_12^{-1}+x_22^{-2}+\dots+x_n2^{-n}.$ Instead the decimal $\omega$ may be given by bitstrings that begin labelled with a higher index such as $\omega=x_lx_{l+1}\dots x_n$ for some $l>1$. In this case
$\omega=\displaystyle\sum\limits_{i=l}^{n}x_i2^{-i+l-1}=x_l2^{-1}+x_{l+2}2^{-2}+...+x_n2^{-n+l-1}.$
If $\omega$ is a rational number, then its decimal representation is of finite length and the number of binary digits $n$ of $\omega=0.x_1x_2\dots x_n$ is determined by the number of bits needed to completely specify $\omega$. Such a $\omega$ always corresponds to the fraction $\omega=x/2^n$ for some integer $x\in\{0,1,2,\dots, 2^{n}-1\}$. On the other hand, if $\omega$ is an irrational number then the binary representation $\omega=0.x_1x_2x_3\dots$ will contain infinitely many bits $x_i$ in the expansion. However, irrational numbers $\omega= 0.x_1x_2x_3\dots$ can be approximated by a rational number $\tilde{\omega}=0.x_1x_2\dots x_k$ for some $k$, meaning the $x_i$ of $\tilde{\omega}$ coincide with the $x_i$ of $\omega$ up to the first $k$ bits. In this context, $\tilde{\omega}$ is called a rational approximation of $\omega$ to $k$ bits of accuracy.

Let $k$ be some integer and consider the product of $2^k$ with $\omega=0.x_1x_2\dots x_n$
$2^k\omega=2^k\displaystyle\sum\limits_{i=1}^{n}x_i2^{-i}=x_12^{k-1}+x_{2}2^{k-2}+...+x_n2^{k-n}.$
Suppose now that $k$ is some positive integer such that $1\leq k<n$. Then this summation can be regarded as two different sums, one over non-negative powers of $2$ and the other over negative powers of $2$:
$\begin{array}{r l} 2^k\omega=2^k\displaystyle\sum\limits_{i=1}^{n}x_i2^{-i}= & \displaystyle\sum\limits_{i=1}^{k}x_i2^{k-i}+\displaystyle\sum\limits_{i=k+1}^{n}x_i2^{k-i} \\ = & \left(x_12^{k-1}+x_{2}2^{k-2}+...+x_k2^{0}\right)+\left(x_{k+1}2^{-1}+x_{k+2}2^{-2}+...+x_n2^{-n}\right) \\ \equiv & x_1x_2\dots x_{k} + 0.x_{k+1}x_{k+2}\dots x_{n} \\ = & x_1x_2\dots x_{k}.x_{k+1}x_{k+2}\dots x_{n}. \end{array}$
Here, $x_1x_2\dots x_{k}$ can be thought of as the integer part of the number $2^k\omega$, and $0.x_{k+1}x_{k+2}\dots x_{n}$ can be thought of as the fractional part of $2^k\omega$.

This representation will be useful in the analysis to come, because of the consequences this has when considering the number $e^{i2\pi(2^k\omega)}$ with $\omega=0.x_1x_2\dots x_n\in[0,1)$ and $k\geq 1$. Since $e^{i2\pi z}=1$ for any integer $z$, it follows that
$\begin{array}{r l} e^{i2\pi(2^k\omega)}=&e^{i2\pi( x_1x_2\dots x_{k}.x_{k+1}x_{k+2}\dots x_{n})} \\ &=e^{i2\pi(x_1x_2\dots x_{k}) }e^{i2\pi(0.x_{k+1}x_{k+2}\dots x_{n})} \\ &=e^{i2\pi z}e^{i2\pi(0.x_{k+1}x_{k+2}\dots x_{n})} \\ &=e^{i2\pi(0.x_{k+1}x_{k+2}\dots x_{n})}, \end{array}$where $z=x_1x_2\dots x_{k}$ is just some integer.

With these results in mind, the following identity will be proved which expresses the action of the $QFT$ on a basis state $\left|j\right>\in\mathcal{H}^{2^n}$ as the tensor product state of $n$ qubits, where $\left|j\right>=\left|j_1j_2\dots j_n\right>$ when represented in the binary representation. That is, if $\left|\psi\right>=QFT\left|j\right>$, it will be shown that $\left|\psi\right>=\left|\psi_1\right>\otimes\left|\psi_2\right>\otimes\dots\otimes\left|\psi_n\right>$ for some states $\left|\psi_i\right>\in\mathcal{H}^2$.
In this tensor decomposition the state of each qubit is in some superposition and has a relative phase factor in terms of the bit string $j_1j_2\dots j_n$. Showing this will ultimately be an  algebraic exercise in translating between the decimal and binary representation of basis states. Proceed as follows:
$\begin{array}{r l} \left|\psi\right>=QFT\left|j\right>=&\displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{k=0}^{2^n-1}e^{\frac{i2\pi jk}{2^n}}\left|k\right> \\ =& \displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{k_1=0}^{1}\cdots \displaystyle\sum\limits_{k_n=0}^{1}e^{i2\pi j(\sum_{l=1}^nk_l2^{-l})}\left|k_1k_2\dots k_n\right> \\ =& \displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\sum\limits_{k_1=0}^{1}\cdots \displaystyle\sum\limits_{k_n=0}^{1}\displaystyle\bigotimes\limits_{l=1}^{n}e^{i2\pi j k_l2^{-l}}\left|k_l\right> \\ =& \displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\bigotimes\limits_{l=1}^{n}\left[\displaystyle\sum\limits_{k_l=0}^{1}e^{i2\pi j k_l2^{-l}}\left|k_l\right>\right] \\ =& \displaystyle\frac{1}{\sqrt{2^n}}\displaystyle\bigotimes\limits_{l=1}^{n}\left[\left|0\right>+e^{i2\pi j 2^{-l}}\left|k_l\right>\right] \\ =& \left( \displaystyle\frac{\left|0\right>+e^{i2\pi j2^{-1}}\left|1\right>}{\sqrt{2}}\right)\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi j2^{-2}}\left|1\right>}{\sqrt{2}}\right)\otimes\dots\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi j2^{-n}}\left|1\right>}{\sqrt{2}}\right) \\ =& \left( \displaystyle\frac{\left|0\right>+e^{i2\pi0.j_n}\left|1\right>}{\sqrt{2}}\right)\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi0.j_{n-1}j_n}\left|1\right>}{\sqrt{2}}\right)\otimes\dots\otimes\left( \displaystyle\frac{\left|0\right>+e^{i2\pi0.j_1j_2\dots j_n}\left|1\right>}{\sqrt{2}}\right). \end{array}$

This decomposition of $\left|\psi\right>= \bigotimes_{i=1}^n\left|\psi_i\right>$ into the tensor product of the states $\left|\psi_i\right>$ is useful because it shows that if its possible to construct a unitary operators $U_i$ on the state space such that $U_i\left|j_1j_2\dots j_n\right>=\left|j_1\right>\dots\left|j_{i-1}\right>\left|\psi_i\right>\left|j_{i+1}\right>\dots\left|j_n\right>$ for each $i\in\{1,2,\dots n\}$, then the composition $U_nU_{n-1}\dots U_1$ must be the unitary operator that performs the quantum Fourier transform $QFT$:
$QFT\left|j_1j_2\dots j_n\right>=U_{n}U_{n-1}\dots U_1\left|j_1j_2\dots j_n\right>.$
If a circuit can be explicitly constructed that implements each $U_i$ in terms  of elementary gates, then the composition of these circuits can be used to construct a circuit for the quantum Fourier transform.

In order to construct a circuit for each $U_i$ define the single qubit gate $R_k$ parameterized by an integer $k$ and  defined by mapping the basis states as $R_k\left|0\right>=\left|0\right>$ and $R_k\left|1\right>=e^{i2\pi/2^k}\left|1\right>$. The matrix for $R_k$ in the computational basis is given as
$R_k=\begin{pmatrix}1 & 0 \ 0 & e^{i2\pi/2^k} \end{pmatrix},$
and it can be seen as adding a relative phase factor to a qubit  in some superposition
$R_k\frac{1}{\sqrt{2}}\left(\left|0\right>+\left|1\right>\right)=\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi/2^k}\left|1\right>).$
Also, define a two qubit controlled$-R_k$ gate $c_r-R_k$ acting in an ambient $n$ qubit register, where the index $r$ signifies that the $r^{th}$ qubit in the register is to serve as the control qubit. The $c_r-R_k$ gate applies the $R_k$ gate to some qubit only if the qubit in the $r^{th}$ register is in the state $\left|1\right>$ and leaves the qubit unchanged if the control is in the state $\left|0\right>$.

Consider the first qubit $\left|j_1\right>$ in the $n$ qubit basis state $\left|j\right>=\bigotimes_{i=1}^{n}\left|j_i\right>$. Then applying the Hadamard gate to $\left|j_1\right>$ gives
$H\left|j_1\right>=\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi 0.j_1}\left|1\right>),$
since $e^{i2\pi 0.j_1}=1$ if $j_1=0$ and $e^{i2\pi 0.j_1}=-1$ if $j_1=1$. Now, if a $c_2-R_2$ gate is applied to $H\left|j_1\right>$ while using the state $\left|j_2\right>$ of the qubit in the $2^{nd}$ register as the control qubit, then
$\begin{array}{r l} c_2-R_kH\left|j_1\right>=&c_2-R_k\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi 0.j_1}\left|1\right>) \\ =&\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi /2^2}e^{i2\pi 0.j_1}\left|1\right>) \\ =&\frac{1}{\sqrt{2}}(\left|0\right>+e^{i2\pi (0.j_1+j_n2^{-2})}\left|1\right>) \\ =&\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_1j_2}\left|1\right>\right). \end{array}$
In a similar manner, if this time the gate $c_3-R_3$ is applied to this state while using the $3^{rd}$ qubit $\left|j_3\right>$ in the register as the control what results is the state
$c_3-R_3c_2-R_2H\left|j_1\right>=c_3-R_3\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_1j_2}\left|1\right>\right)=\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_1j_2j_3}\left|1\right>\right).$
Then continuing in this way by applying $c_r-R_r$ gates iteratively for $2\leq r \leq n$ yields
$c_n-R_nc_{n-1}-R_{n-1}\dots c_2-R_2H\left|j_1\right>=\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_1j_2\dots j_n}\left|1\right>\right)=\left|\psi_n\right>,$
which is the state $\left|\psi_n\right>$ of the $n^{th}$ qubit in the register of the tensor decomposition of the $QFT$ shown above.

A similar set of operations is applied to each qubit $\left|j_i\right>$ in the $n$ qubit register. For the first $n-1$ qubits $\left|j_i\right>$, with $1\leq i<n$,  apply the gates
$c_{n+1-i}-R_{n+1-i}c_{n-i}-R_{n-1}\dots c_2-R_2H\left|j_i\right>=\frac{1}{\sqrt{2}}\left(\left|0\right>+e^{i2\pi0.j_ij_{i+1}\dots j_n}\left|1\right>\right)=\left|\psi_{n+1-i}\right>.$

For the last qubit $\left|j_n\right>$ of the register only apply the Hadamard gate. Notice that these states also correspond accordingly to the states $\left|\psi_{n+1-i}\right>$ of the $QFT$ decomposition.
By letting $U'_i$ denote the unitary operator consisting of these gates that act on the state $\left|j_i\right>$ of the $i^{th}$  qubit in the $n$ qubit register, it follows that
$U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>=\left|\psi_n\right>\otimes\left|\psi_{n-1}\right>\otimes\dots\otimes\left|\psi_1\right>.$
This is almost exactly the state
$\left|\psi\right>=QFT\left|j_1j_2\dots j_n\right>=\left|\psi_1\right>\otimes\left|\psi_{2}\right>\otimes\dots\otimes\left|\psi_n\right>,$
except that order of the qubits in the registers is merely reversed when compared to $U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>$.

(Part of the circuit used to implement the quantum Fourier transform QFT. Not shown in the circuit is the seqiences of $SWAP$ gates used to reverse the order of the $\left|\psi_i\right>$. This circuit begins with an $n$ qubit register is some computational basis state $\left|j_1j_2\dots j_n\right>$ and then applies the sequence of gates given by $U'_i$ to each $\left|j_i\right>$ consisting of a Hadamard gate followed by controlled$-R_k$ gates that use the states $\left|j_k\right>$, for $j>i$ in the register as control qubits.)

At this point, one might be satisfied as accepting the state produced by $U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>$  as being close enough to actually implementing the $QFT$. After all, simply relabeling the qubits in the registers seems to be a logical triviality. However, there does exist a unitary operator that effectively interchanges the states of two qubits in different registers given by the $SWAP$ gate presented in the section on quantum gates.

By appropriately interchanging the states of the qubits in the register of the state $\left|\psi_n\right>\otimes\left|\psi_{n-1}\right>\otimes\dots\otimes\left|\psi_1\right>$, this state can be transformed into the state $\left|\psi_1\right>\otimes\left|\psi_{2}\right>\otimes\dots\otimes\left|\psi_n\right>$. Only $\frac{n}{2}$ $SWAP$ operations performed on the appropriate registers are needed to reverse the order of the qubits. By performing this reversal of states after the operation $U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>$ is applied, the basis state $\left|j_1j_2\dots j_n\right>$ is finally transformed into the state given by $\left|\psi\right>=QFT\left|j_1j_2\dots j_n\right>$. The circuit produced by appending the appropriate $SWAP$ gates to the end of the circuit shown in the figure below implements the actual $QFT$, and can itself be represented by a quantum gate that signifies this circuit as shown.

(The gate representing the quantum Fourier transform $QFT$. The $QFT$ takes as input the state $\left|j\right>$ and transforms it to the state $\left|\psi\right>=\left|\psi_1\right>\otimes\left|\psi_2\right>\otimes\dots\otimes\left|\psi_n\right>$. This gate is equivalent to the circuit shown in the previous figure with the necessary $SWAP$ gates appended to the end of the circuit.)

A more careful analysis of the implementing the quantum Fourier transform is  worthwhile in order to determine its computational complexity. In terms of elementary gates, it can be seen that $n+1-i$ gates are needed to perform the operation $U'_i$. Then since each $U_i$ must be performed, for $1\leq 1\leq n$, the total number of gates to implement $U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>$ is
$n+(n-1)\dots+1=\displaystyle\sum\limits_{i=1}^{n}i= \frac{n(n+1)}{2}.$Therefore the  circuit size or time complexity of implementing $U'_n\cdots U'_2U'_1\left|j_1j_2\dots j_n\right>$ is in $O(n^2)$. In addition, the $\frac{n}{2}$ $SWAP$ operations must be accounted for in order to determine the true circuit size of implementing the $QFT$. Recall, that $3$ controlled$-NOT$ gates were able to simulate the effect of the $SWAP$ gate. Then the total number of elementary gates needed to perform the $\frac{n}{2}$ swap operations is just $\frac{3n}{2}$, which is in $O(n)$ but still bounded above by $O(n^2)$. Hence, the total number of gates needed to perform the quantum Fourier transform $QFT$ is $O(n^2)$.

It is important to keep in mind that the $QFT$ was defined in general on the state space $\mathcal{H}^{N}$ for an arbitrary positive integer $N$. The construction shown above is for the case when $N=2^n$ for some $n$. Although, this case will be the most relevant for quantum computing, the QFT can be defined for general $N$.\cite{coppersmith} Moreover, the family of circuits constructed for varying $N$ is also uniformly polynomial, which is a necessary property when considering the computational complexity of algorithms that make use of the $QFT$.

The quantum Fourier transform will prove to be a useful and essential tool in the quantum algorithms to follow. The $QFT$ allows special superpositions of states to be constructed and novel ways to encode information in the states involved and their relative phases, which can then be exploited to accomplish interesting tasks. An important property of the $QFT$ is that it can be efficiently implemented in polynomial time, whereas $\omega(n2^n)$ operations are needed to implement the classical discrete Fourier transform on $2^n$ complex numbers.\cite{winograd}

Hence, the quantum algorithm is exponentially faster than its classical counterpart. Therefore, if the $QFT$ is used in some algorithm it can be done so efficiently.