Quantum Fourier Transform - Circuit Implementation

Circuit Implementation

The quantum Fourier transform can be approximately implemented for any N; however, the implementation for the case where N is a power of 2 is much simpler. Suppose N = 2n. We have the orthonormal basis consisting of the vectors

Each basis state index can be represented in binary form

where

Similarly, we also adopt the notation

.

For instance, and .

With this notation, the action of the quantum Fourier transform can be expressed as:

In other words, the discrete Fourier transform, an operation on n-qubits, can be factored into the tensor product of n single-qubit operations, suggesting it is easily represented as a quantum circuit. In fact, each of those single-qubit operations can be implemented efficiently using a Hadamard gate and controlled phase gates. The first term requires one Hadamard gate, the next one requires a Hadamard gate and a controlled phase gate, and each following term requires an additional controlled phase gate. Summing up the number of gates gives gates, which is polynomial in the number of qubits.