Quantum Fourier Transform (QFT)

The classical Fourier Transform is used in signal processing, data compression, and complexity theory. The quantum computing implementation, known as the Quantum Fourier Transform (QFT), applies Fourier transformations to wave function amplitudes. The QFT is used in Shor’s Factoring Algorithm (Quantum Phase Estimation).

Since IBM Q Experience has a 3-qubit implementation of the Quantum Fourier Transform in both Qiskit and OpenQASM, I decided to experiment with a 4-qubit variation.

OPENQASM 2.0;
include "qelib1.inc";
qreg q[4];
creg c[4];

// set input states
h q[0];
u1(-pi) q[0];
h q[1];
u1(-pi/2) q[1];
h q[2];
u1(-pi/4) q[2];
h q[3];
u1(-pi/8) q[3];

// perform Quantum Fourier Transform (QFT)
h q[0];
cu1(pi/2) q[1], q[0];
cu1(pi/4) q[2], q[0];
cu1(pi/8) q[3], q[0];
barrier q;
h q[1];
cu1(pi/2) q[2], q[1];
cu1(pi/4) q[3], q[1];
barrier q;
h q[2];
cu1(pi/2) q[3], q[2];
barrier q;
h q[3];

measure q[0] -> c[0];
measure q[1] -> c[1];
measure q[2] -> c[2];
measure q[3] -> c[3];

The input states are set up specifically to cause a result of 0001 when the QFT is applied.

The QFT is certainly elegant. The key gates are the orange rotation gates (set the input states) and the purple controlled-rotation gates (with the blue Hadamard gates, perform the transformation). Adding qubits extends the pattern you see here.

It is worth noting that the Python Qiskit implementation is far more efficient when using larger and larger numbers of qubits because you can use FOR loops. It’s not a big deal when using only 3 qubits, but even at only 4 qubits there are noticeable redundancies in non-looping code.

On a simulator, the result is perfect. Next up: real hardware.

On real hardware, the histogram gets messy. Errors on real hardware result from imperfect measurements and residual heat.

I experimented with different input states. Moving the 1, for example to 0010, causes the result to have a probability near-but-less-than 100% even on a simulator. Setting more than one 1, for example 1010, decreases accuracy substantially. I’m not sure why, but it is something I am going to look deeper into.

I’m thinking about trying Quantum Fourier Teleportation, combining Quantum Fourier Transformation with Quantum Teleportation. I haven’t seen that anywhere, but it seems like a logical next step. I’ll set the input states to 001, for initial simplicity, teleport the input states, and then perform the QFT to confirm successful teleportation. We’ll see what happens….