Quantum Fourier Transform and Eigenvalue Estimation

This repository contains a LaTeX report as part of a course in Quantum Information and Computation.
The document provides a complete theoretical and mathematical treatment of the Quantum Fourier Transform (QFT) and its application to eigenvalue estimation — one of the most important primitives in quantum computing.

---

Contents

1. Introduction

• Explains the motivation and intuition behind the Fourier Transform.
• Discusses how the Quantum Fourier Transform generalizes the classical Discrete Fourier Transform (DFT) to quantum systems.
• Compares computational complexity between classical and quantum implementations.

2. Derivation and Explanation of the QFT

• Step-by-step derivation of the QFT from its matrix definition.
• Shows factorization of the transformation into single-qubit rotations and controlled phase gates.
• Presents the circuit representation of the QFT using Hadamard and controlled-$R_k$ gates.
• Includes a full 3-qubit example and analysis of gate counts and complexity.

3. Eigenvalue Estimation Using the QFT

• Defines the eigenvalue (phase) estimation problem for a unitary operator ( U \ket{u} = e^{2\pi i \varphi}\ket{u} ).
• Derives the quantum algorithm for eigenvalue estimation, including all algebraic steps.
• Shows how the inverse QFT extracts the binary representation of the eigenphase.
• Discusses precision, probability of success, and algorithmic efficiency.
• Explains the broader implications for quantum algorithms such as:
  • Quantum Phase Estimation (QPE)
  • Hamiltonian eigenenergy estimation
  • Shor’s factoring and order-finding algorithms

---

Key Concepts Covered

• Quantum state representation and basis decomposition
• Controlled powers of unitaries ( U^{2^k} )
• Phase encoding and binary fraction interpretation
• Inverse Quantum Fourier Transform as a phase decoder
• Probabilistic precision and scaling with qubit count
• Role of QFT in eigenvalue extraction and quantum advantage

---

Technical Details

• Written entirely in LaTeX using the quantikz package for circuit diagrams.
• Document class: article (A4, 11pt).
• Compilation: tested with pdflatex and latexmk.
• Dependencies: amsmath, physics, quantikz, booktabs, hyperref, cleveref.