Quantum Fourier Transform (QFT)

Table of Contents

1. Introduction
2. Classical Fourier Transform Background
3. Motivation for Quantum Fourier Transform
4. Definition of QFT
5. Mathematical Formulation
6. Action on Quantum Basis States
7. Inverse Quantum Fourier Transform
8. Comparison to Classical FFT
9. Circuit Construction
10. Hadamard and Controlled Phase Gates
11. Step-by-Step Circuit Decomposition
12. QFT for 2 and 3 Qubits
13. QFT Matrix Representation
14. Inverse QFT Circuit
15. Measurement and Extraction
16. Efficiency and Complexity
17. Applications of QFT
18. QFT in Shor’s Algorithm
19. Phase Estimation and QFT
20. Precision and Error Analysis
21. Example: Applying QFT on Basis States
22. Geometric Interpretation
23. Tools for Simulating QFT
24. Limitations in Physical Implementation
25. Conclusion

1. Introduction

The Quantum Fourier Transform (QFT) is a quantum analog of the classical discrete Fourier transform (DFT). It plays a central role in many quantum algorithms, most notably Shor’s factoring algorithm and Quantum Phase Estimation.

2. Classical Fourier Transform Background

The classical discrete Fourier transform transforms a vector of complex numbers into its frequency representation:

This transformation reveals frequency components of data.

3. Motivation for Quantum Fourier Transform

The QFT allows a quantum computer to extract periodic structure from superpositions. It is exponentially faster than classical DFT, with \(\mathcal{O}(n^2)\) gate complexity for \( n \)-qubit inputs.

4. Definition of QFT

Let \( |x\rangle \) be a computational basis state of \( n \) qubits. The QFT maps this to:

\[
\text{QFT}|x\rangle = \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n – 1} e^{2\pi i x y / 2^n} |y\rangle
\]

5. Mathematical Formulation

Given:

• \( x = x_0 x_1 \dots x_{n-1} \)
• \( y = y_0 y_1 \dots y_{n-1} \)

QFT maps:

\[
|x\rangle \rightarrow \frac{1}{\sqrt{2^n}} \sum_{y=0}^{2^n – 1} e^{2\pi i x y / 2^n} |y\rangle
\]

Each amplitude encodes a phase dependent on \( x \cdot y \).

6. Action on Quantum Basis States

For example, for \( n = 2 \), and \( x = 01 \):

\[
\text{QFT}|01\rangle = \frac{1}{2} (|0\rangle + i|1\rangle – |2\rangle – i|3\rangle)
\]

7. Inverse Quantum Fourier Transform

The inverse QFT is defined by taking the complex conjugate of the exponent:

\[
\text{QFT}^{-1}|y\rangle = \frac{1}{\sqrt{2^n}} \sum_{x=0}^{2^n – 1} e^{-2\pi i x y / 2^n} |x\rangle
\]

8. Comparison to Classical FFT

• Classical FFT: \( \mathcal{O}(N \log N) \) operations
• QFT: \( \mathcal{O}(n^2) \) quantum gates, where \( N = 2^n \)

Exponential improvement for large inputs.

9. Circuit Construction

The QFT circuit uses:

• Hadamard gates
• Controlled phase gates (e.g., \( R_k \))

10. Hadamard and Controlled Phase Gates

For each qubit \( q_j \), apply:

1. Hadamard gate
2. Controlled \( R_k \) gates with \( k = 2, 3, …, n-j \)

Where:

\[
R_k = \begin{bmatrix}
1 & 0 \
0 & e^{2\pi i / 2^k}
\end{bmatrix}
\]

11. Step-by-Step Circuit Decomposition

For 3-qubit QFT:

• H on qubit 0
• \( R_2 \) between qubits 1 and 0
• \( R_3 \) between qubits 2 and 0
• H on qubit 1
• \( R_2 \) between qubits 2 and 1
• H on qubit 2
• Finally, swap qubits to reverse order

12. QFT for 2 and 3 Qubits

2-qubit QFT:

q0: ──H────■───────────X──
           │           │
q1: ───────R2────H─────X──

3-qubit QFT:

q0: ──H──■────■────────────X──────────
         │    │            │
q1: ─────R2───■────H───────┼──────X───
              │            │      │
q2: ──────────R3───R2──────H──────X───

13. QFT Matrix Representation

For \( n = 2 \), QFT matrix is:

\[
\frac{1}{2}
\begin{bmatrix}
1 & 1 & 1 & 1 \
1 & i & -1 & -i \
1 & -1 & 1 & -1 \
1 & -i & -1 & i
\end{bmatrix}
\]

14. Inverse QFT Circuit

Same as QFT but:

• Reverse the gate order
• Use complex conjugate of phase gates \( R_k^\dagger \)

15. Measurement and Extraction

The result after QFT encodes the frequency of periodic functions. Measuring yields values correlated to the period or eigenvalue of operators in phase estimation.

16. Efficiency and Complexity

Gate complexity: \( \mathcal{O}(n^2) \)
Can be approximated to \( \mathcal{O}(n \log n) \) by dropping small-angle gates for faster circuits.

17. Applications of QFT

• Shor’s Algorithm (period finding)
• Quantum Phase Estimation
• Quantum counting
• Hidden subgroup problems

18. QFT in Shor’s Algorithm

Used to extract the period \( r \) from \( e^{2\pi i k r / Q} \) via measurement of the QFT output.

19. Phase Estimation and QFT

The QFT is the core of phase estimation, allowing estimation of eigenvalues of unitary operators to exponential precision.

20. Precision and Error Analysis

The QFT spreads amplitude over many basis states. Precision depends on:

• Number of qubits
• Accuracy of \( R_k \) gates
• Noise and decoherence

21. Example: Applying QFT on Basis States

Let’s apply QFT to \( |01\rangle \):

\[
\text{QFT}|01\rangle = \frac{1}{2}(|0\rangle + i|1\rangle – |2\rangle – i|3\rangle)
\]

The result is a state encoding the relative phase of the binary index.

22. Geometric Interpretation

QFT rotates the quantum state into the Fourier basis, revealing periodicity encoded in phase relationships. The angles between basis vectors become structured after transformation.

23. Tools for Simulating QFT

• Qiskit: qiskit.circuit.library.QFT
• Cirq: custom gate construction
• Q#: built-in QFT
• Python simulation (NumPy, QuTiP) for visualization

24. Limitations in Physical Implementation

• Requires many controlled-phase gates
• Precision limited by gate fidelity
• Qubits need high coherence for deeper circuits

25. Conclusion

The Quantum Fourier Transform is a cornerstone of quantum computing. It enables powerful algorithms for factoring, phase estimation, and periodicity detection. Though challenging to implement physically, it exemplifies quantum computing’s strength in manipulating phase and interference.