what is Quantum Fourier Transform (QFT) in quantum computing. explain with examples

 The Quantum Fourier Transform (QFT) is the quantum equivalent of the classical Discrete Fourier Transform (DFT).¹ While the classical version finds the frequency components of a signal, the QFT transforms a quantum state from the computational basis (zeros and ones) to the Fourier basis (relative phases).²

It is a critical "building block" for many of the most famous quantum algorithms because it can find patterns and periodicities in data exponentially faster than classical computers.³

---

1. The Core Concept

Think of a standard qubit state like a clock hand. In the computational basis, the hand is either at the 12 o'clock position ($|0\rangle$) or the 6 o'clock position ($|1\rangle$).

The QFT takes these states and rotates them around the equator of the sphere (the XY-plane).⁴ Instead of just being "up" or "down," the information is now encoded in the angle (phase) of the clock hand.

2. How it Works (Mathematical Intuition)

The QFT maps a state $|j\rangle$ to a new state according to this formula:

$$\text{QFT} |j\rangle = \frac{1}{\sqrt{N}} \sum_{k=0}^{N-1} e^{2\pi i j k / N} |k\rangle$$

Where:

• $N = 2^n$ (for $n$ qubits).

• $e^{2\pi i j k / N}$ is the phase factor that "encodes" the frequency.

The Efficiency Jump:

• Classical (FFT): Takes ⁵$O(N \log N)$ steps.⁶

• Quantum (QFT): Takes 7$O((\log N)^2)$ steps.8

  Because $N$ is $2^n$, this is the difference between a calculation taking billions of years (classical) vs. a few seconds (quantum) for very large numbers.

---

3. Example: 1-Qubit QFT

The simplest example is a single qubit.⁹ For ¹⁰$n=1$, the QFT is actually identical to the Hadamard (H) gate.¹¹

• Input $|0\rangle$: Becomes $\frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$, which is the $|+\rangle$ state.

• Input $|1\rangle$: Becomes $\frac{1}{\sqrt{2}}(|0\rangle - |1\rangle)$, which is the $|-\rangle$ state.

In this case, the "phase" is either $0^\circ$ (for $|+\rangle$) or $180^\circ$ (for $|-\rangle$).

---

4. Example: 3-Qubit QFT

In a 3-qubit system ($N=8$), the QFT spreads the information across all 8 possible states ($|000\rangle$ through $|111\rangle$), each with a specific phase rotation.

The circuit consists of:

1. Hadamard Gates: To put qubits into superposition.¹²

2. Controlled Phase Gates (¹³$R_k$): To apply precise rotations based on the state of other qubits.¹⁴

3. SWAP Gates: At the end, to reverse the order of the qubits (since the QFT math naturally outputs them in reverse).¹⁵

---

5. Why do we need it?

You can't "read" the phases directly (measuring collapses them), so we use QFT as a step inside other algorithms to make the right answer "interfere" constructively:

• Shor's Algorithm: Uses QFT to find the period of a function, which is the secret to breaking RSA encryption.¹⁶

• Quantum Phase Estimation: Uses QFT to calculate the energy levels (eigenvalues) of molecules for chemistry simulations.¹⁷