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

## 2-Qubit Example

To see how this looks like for a 2-qubit system, let’s write out the terms:

In the last line, we used the binary representation of the integer .

The multiplication, like is done in the following manner:

For example,

The last line above results because for any integer

Going back to the Fourier Transform and expanding the multiplications, we get

We can group the 2nd and 4th terms and factor out the term in the underbrace:

Factor out the term in the underbrace to get

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

### The Controlled-Phase Rotation

Let’s define the following operator acting on two qubits:

This is called the Controlled-Phase rotation operator. Notice that if either or is 0, the operator becomes the identity. Only when both are 1 will the operator multiply a phase .

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

If you compare this with the , they are similar except for the order of the bits. Therefore, if you measure and get a value , you just need to reverse the bits of the binary representation of to get the corresponding state in .

## Visualizing the Circuit

This is the QISKit code to visualize the circuit

# 2-qubit circuit from qiskit import Aer import math from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute from qiskit.tools.visualization import circuit_drawer, plot_histogram from qiskit import BasicAer, execute input_register = QuantumRegister(2,name="qin") c = ClassicalRegister(4) qc = QuantumCircuit(input_register) qc.h(input_register[0]) qc.cu1(math.pi/float(2),input_register[0],input_register[1]) qc.h(input_register[1]) qc.draw(output='mpl')

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

where

## Constructing the circuit for a 4-qubit System

Using this formula, the Fourier Transform of a 4-qubit system is

Consider the following series of transformations:

This will give you

If you compare this with , they look similar except for the order of the bits. If you define the mapping

and apply it to the transformation above, you’ll get the . Therefore, whatever you measure using , just reverse the bits to get the corresponding result using .

## Implementing the 4-Qubit Fourier Transform

The following code in QISKit implements the circuit

# Fourier Transform from qiskit import Aer from qiskit import QuantumCircuit, ClassicalRegister, QuantumRegister, execute from qiskit.tools.visualization import circuit_drawer, plot_histogram from qiskit import BasicAer, execute import math input_register = QuantumRegister(4,name="qin") c = ClassicalRegister(4) qc = QuantumCircuit(input_register) qc.h(input_register[0]) qc.cu1(math.pi/float(2),input_register[0],input_register[1]) qc.cu1(math.pi/float(2**2),input_register[0],input_register[2]) qc.cu1(math.pi/float(2**3),input_register[0],input_register[3]) qc.barrier() qc.h(input_register[1]) qc.cu1(math.pi/float(2),input_register[1],input_register[2]) qc.cu1(math.pi/float(2**2),input_register[1],input_register[3]) qc.barrier() qc.h(input_register[2]) qc.cu1(math.pi/float(2),input_register[2],input_register[3]) qc.h(input_register[3]) qc.barrier() qc.draw(output='mpl')

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!