Quantum Gate

QFT Overview

The Quantum Fourier Transform is a quantum operation that applies the Discrete Fourier Transform to a set of qubits.

The Discrete Fourier Transform converts a list of complex numbers into a list of frequency components. The Quantum Fourier Transform acts on amplitudes of a quantum state, revealing details about periodic signals that may be hidden in the amplitudes.

Like all quantum operations, QFT is reversable, as no information is lost during the operation.

Reversed QFT is useful in other algorithms like Quantum Phase Estimation and Shor's Algorithm.

Mathematical Definition

The unitary matrix defining the QFT operation applied to qubits is defined as follows:

Equivalently, QFT can be described by how it acts upon standard basis states:

Notice that QFT can be defined for any positive integer , where , but it is only useful for values of where .

Examples

One qubit QFT () is equivalent to the Hadamard gate:

Two qubit QFT ():

Circuit Implementation

The implementation of QFT is recursive, where makes use of in its implementation.

[Future: insert circuit for QFT32 here.]

The cost of implementing the QFT circuit is gates, where is the number of qubits that QFT operates on.

Resources

See the Qiskit documentation for the qft gate: https://quantum.cloud.ibm.com/docs/en/api/qiskit/qiskit.circuit.library.QFT

Lesson 7 in John Watrous' Understanding Quantum Information & Computation — Phase Estimation and Factoring.

A written paper is also available.