From the previous post, we have seen the theory on how the Quantum Fourier Transform is used to crack the RSA. In order to utilize the QFT, we need to implement a circuit for it. In other words, we need to program it.
In this blog post, we will start with the basic definition of the Quantum Fourier Transform and implement a circuit for a 2 qubit system. We will then show the generalization to multiple qubits and implement a circuit for a 4-qubit system which we will use later to implement Shor’s algorithm.
Definition
The Quantum Fourier Transform is defined on its action on the computational basis as
\[\mathbf{U}_\mathrm{FT} |x\rangle = \displaystyle \frac{1}{\sqrt{2^n}}\sum_{y=0}^{2^n-1}e^{2\pi i xy/2^n}|y\rangle\]2-Qubit Example
To see how this looks like for a 2-qubit system, let’s write out the terms:
\[\begin{array}{rl} \mathbf{U}_\mathrm{FT} |x_1x_0\rangle &= \displaystyle \frac{1}{\sqrt{2^2}}\sum_{y=0}^{2^2-1}e^{2\pi i xy/2^2}|y\rangle\\[10px] &= \displaystyle \frac{1}{2}\left( e^{\pi i x\cdot 0/2}|0\rangle + e^{\pi i x\cdot 1/2}|1\rangle + e^{\pi i x\cdot 2/2}|2\rangle + e^{\pi i x\cdot 3/2}|3\rangle\right )\\[10px] &= \displaystyle \frac{1}{2}\left( |00\rangle + e^{\pi i x\cdot 1/2}|01\rangle + e^{\pi i x\cdot 2/2}|10\rangle + e^{\pi i x\cdot 3/2}|11\rangle\right )\\[10px] \end{array}\]In the last line, we used the binary representation of the integer $y$.
The multiplication, like $x\cdot 3$ is done in the following manner:
\[(x_1\cdot 2^1 + x_0\cdot 2^0)(1\cdot 2^1 + 1\cdot 2^0) = 4x_1 + 2x_1 + 2x_0 + x_0\]For example,
\[\begin{array}{rl} \displaystyle e^{\pi i x\cdot 3/2} &= \displaystyle e^{\pi i \left( 4x_1 + 2x_1 + 2x_0 + x_0 \right)/2}\\[10px] &= \displaystyle \exp\left[\pi i \left( 2x_1 + x_1 + x_0 + \frac{x_0}{2} \right)\right]\\[10px] &= \displaystyle \exp\left[\pi i \left( x_1 + x_0 + \frac{x_0}{2} \right)\right]\\[10px] \end{array}\]The last line above results because for any integer $m$
\[\begin{array}{rl} \exp(2\pi i mx) &= \cos(2\pi mx) + i\sin(2\pi mx)\\ &= 1 \end{array}\]Going back to the Fourier Transform and expanding the multiplications, we get
\[\begin{array}{rl} \mathbf{U}_\mathrm{FT} |x_1x_0\rangle &=\displaystyle \frac{1}{2}\left(|00\rangle + \underbrace{\exp[\pi i(x_1 + \frac{x_0}{2})]}|01\rangle +\exp[\pi i(x_0)|10\rangle + \exp[\pi i(x_1+ \frac{x_0}{2} + x_0)|11\rangle\right) \end{array}\]We can group the 2nd and 4th terms and factor out the term in the underbrace:
\[\begin{array}{rl} \mathbf{U}_\mathrm{FT} |x_1x_0\rangle &= \displaystyle \frac{1}{2}\left[|00\rangle + \exp[\pi i(x_0)|10\rangle + \exp[\pi i(x_1 + \frac{x_0}{2})]|01\rangle + \exp[\pi i(x_1+ \frac{x_0}{2} + x_0)|11\rangle\right]\\[10px] &= \displaystyle \frac{1}{2}\left[\underbrace{\left(|0\rangle + \exp[\pi i(x_0)]|1\rangle\right)}\otimes|0\rangle + \underbrace{\left(|0\rangle + \exp[\pi i(x_0)]|1\rangle \right)}\otimes\exp[\pi i(x_1 + \frac{x_0}{2})]|1\rangle\right] \end{array}\]Factor out the term in the underbrace to get
\[\begin{array}{rl} \mathbf{U}_\mathrm{FT} |x\rangle &= \displaystyle \frac{1}{2}\left[\underbrace{\left(|0\rangle + \exp[\pi i(x_0)]|1\rangle\right)}|0\rangle + \underbrace{\left(|0\rangle + \exp[\pi i(x_0)]|1\rangle \right)}\exp[\pi i(x_1 + \frac{x_0}{2})]|1\rangle\right]\\[10px] &= \displaystyle \frac{1}{\sqrt{2}}\left[|0\rangle + \exp[\pi i(x_0)]|1\rangle\right)\otimes \frac{1}{\sqrt{2}}\left(|0\rangle + \exp[\pi i(x_1 + \frac{x_0}{2})]|1\rangle\right] \end{array}\]Some Gates We Need For the Circuit
The Hadamard Gate
The first factor from the left is just the Hadamard gate acting on the first qubit since
\[\begin{array}{rl} \displaystyle \frac{1}{\sqrt{2}}\left(|0\rangle + \exp[\pi i(x_0)]|1\rangle\right) &= \displaystyle \frac{|0\rangle + (-1)^{x_0} |1\rangle}{\sqrt{2}}\\[10px] &= \mathbf{H}|x_0\rangle \end{array}\]The Controlled-Phase Rotation
Let’s define the following operator acting on two qubits:
\[\begin{array}{rl} \mathbf{V}_{ij}|x_{n-1}\cdots x_j\cdots x_i\cdots 0\rangle &= e^{\pi i x_ix_j/2^{|i-j|}}|x_{n-1}\cdots x_j\cdots x_i\cdots 0\rangle \end{array}\]This is called the Controlled-Phase rotation operator. Notice that if either $x_i$ or $x_j$ is 0, the operator becomes the identity. Only when both are 1 will the operator multiply a phase $e^{\pi i/2^{ | i-j | }}$. |
Using these 2 operators, we can now write the gates for the Fourier Transformation.
Constructing the circuit for a 2-qubit System
Consider the following sequence of operations
\[\begin{array}{rl} \mathbf{H}_1\mathbf{V}_{01}\mathbf{H}_0 |x_0x_1\rangle &= \displaystyle \mathbf{H}_1\mathbf{V}_{01}|x_0\rangle\frac{1}{\sqrt{2}}(|0\rangle + \exp(\pi ix_1)|1\rangle)\\ &= \displaystyle \mathbf{H}_1 |x_0\rangle\frac{1}{\sqrt{2}}(|0\rangle + \exp(\pi i(x_1 + \frac{x_0}{2})|1\rangle)\\ &= \displaystyle \frac{1}{\sqrt{2}}(|0\rangle + \exp(\pi ix_0)|1\rangle\frac{1}{\sqrt{2}}\otimes(|0\rangle + \exp(\pi i(x_1 + \frac{x_0}{2})|1\rangle)\\ \end{array}\]If you compare this with the $\mathbf{U}_\mathrm{FT}\vert x_1x_0\rangle$, they are similar except for the order of the bits. Therefore, if you measure
\[\mathbf{H}_1\mathbf{V}_{01}\mathbf{H}_0 \vert x_0x_1\rangle\]and get a value $y$, you just need to reverse the bits of the binary representation of $y$ to get the corresponding state in $\mathbf{U}_\mathrm{FT}\vert x_1x_0\rangle$.
Visualizing the Circuit
This is the QISKit code to visualize the circuit
And here is the result
General Fourier Transform Circuit
The Fourier Transform of an n-qubit system is generalized by its action on the computational basis
\[\displaystyle \frac{1}{\sqrt{2^n}} (|0\rangle + e^{2\pi i0.x_0}|1\rangle)\otimes(|0\rangle + e^{2\pi i0.x_1x_0}|1\rangle)\otimes\cdots\] \[\displaystyle \otimes(|0\rangle + e^{2\pi i 0.x_m\ldots x_2x_0}|1\rangle)\]where
\[0.x_{m-1}x_{m-2}\ldots x_1x_0 = \displaystyle \frac{x_{m-1}}{2^1}+\frac{x_{m-2}}{2^2}+\cdots + \frac{x0}{2^m}\]Constructing the circuit for a 4-qubit System
Using this formula, the Fourier Transform of a 4-qubit system is
\[\begin{array}{rl} \mathbf{U}_\mathrm{FT} |x_3x_2x_1x_0\rangle &= (|0\rangle + e^{2\pi i0.x_0}|1\rangle)\otimes(|0\rangle + e^{2\pi i0.x_1x_0}|1\rangle)\otimes\\ & (|0\rangle + e^{2\pi i0.x_2x_1x_0}|1\rangle)\otimes(|0\rangle + e^{2\pi i0.x_3x_2x_1x_0}|1\rangle) \end{array}\]Consider the following series of transformations:
\[\mathbf{H}_3\mathbf{V}_{23}\mathbf{H}_2\mathbf{V}_{13}\mathbf{V}_{12}\mathbf{H}_1\mathbf{V}_{03}\mathbf{V}_{02}\mathbf{V}_{01}\mathbf{H}_0|x_3x_2x_1x_0\rangle\]This will give you
\[(|0\rangle + e^{2\pi i0.x3}|1\rangle)\otimes(|0\rangle + e^{2\pi i0.x_2x_3}|1\rangle)\] \[\otimes(|0\rangle + e^{2\pi i0.x_1x_2x_3}|1\rangle)\otimes(|0\rangle + e^{2\pi i0.x_0x_1x_2x_3}|1\rangle)\]If you compare this with $\mathbf{U}_\mathrm{TF}\vert x_3x_2x_1x_0\rangle$, they look similar except for the order of the bits. If you define the mapping
\[\begin{array}{rl} x_3 &\rightarrow x_0\\ x_2 &\rightarrow x_1\\ x_1 &\rightarrow x_2\\ x_0 &\rightarrow x_3 \end{array}\]and apply it to the transformation above, you’ll get the $\mathbf{U}_\mathrm{FT}\vert x_3x_2x_1x_0\rangle$.
Therefore, whatever $y$ you measure using
\[\mathbf{H}_3\mathbf{V}_{23}\mathbf{H}_2\mathbf{V}_{13}\mathbf{V}_{12}\mathbf{H}_1\mathbf{V}_{03}\mathbf{V}_{02}\mathbf{V}_{01}\mathbf{H}_0\]just reverse the bits to get the corresponding result using $\mathbf{U}_\mathrm{FT}\vert x_3x_2x_1x_0\rangle$.
Implementing the 4-Qubit Fourier Transform
The following code in QISKit implements the circuit
\[\mathbf{H}_3\mathbf{V}_{23}\mathbf{H}_2\mathbf{V}_{13}\mathbf{V}_{12}\mathbf{H}_1\mathbf{V}_{03}\mathbf{V}_{02}\mathbf{V}_{01}\mathbf{H}_0|x_3x_2x_1x_0\rangle\]Below is the circuit diagram
Now that we have a circuit for a 4-qubit Fourier Transform, let’s proceed to the next blog post and use it to crack the RSA!
Image Credit: “fourier” by fotodiagramas is marked with CC BY-NC 2.0. To view the terms, visit https://creativecommons.org/licenses/by-nc/2.0/?ref=openverse