Quantum Fourier Transform and Eigenvalue Estimation

This repository contains a comprehensive LaTeX report prepared as part of a course in Quantum Information and Computation.
The report presents a rigorous theoretical and mathematical exploration of the Quantum Fourier Transform and its application to eigenvalue (phase) estimation, a core component of many quantum algorithms.

---

📘 Overview

The Quantum Fourier Transform (QFT) is the quantum analogue of the classical Discrete Fourier Transform (DFT) and is a fundamental subroutine in numerous quantum algorithms, including Shor’s factoring algorithm and Quantum Phase Estimation (QPE).
This project provides a detailed derivation, circuit construction, and analysis of the QFT, followed by its use in eigenvalue estimation for unitary operators.

---

🧠 Contents

1. Introduction

• Motivation and intuition behind the Fourier Transform
• Extension from classical DFT to quantum systems
• Comparison of computational complexity between classical and quantum implementations

2. Derivation and Structure of the QFT

• Step-by-step derivation from the matrix definition
• Factorization into single-qubit rotations and controlled phase gates
• Quantum circuit representation using Hadamard and controlled-(R_k) gates
• Detailed 3-qubit example with gate count and asymptotic complexity analysis

3. Eigenvalue (Phase) Estimation via the QFT

• Definition of the eigenvalue estimation problem for a unitary ( U \ket{u} = e^{2\pi i \varphi}\ket{u} )
• Full derivation of the Quantum Phase Estimation (QPE) algorithm
• Explanation of how the inverse QFT decodes the binary representation of the phase
• Analysis of precision, success probability, and scaling
• Discussion of applications in:
  • Quantum Phase Estimation (QPE)
  • Hamiltonian eigenenergy estimation
  • Shor’s algorithm and order-finding problems

---

🔑 Key Concepts

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

---

⚙️ Technical Details

• Language: LaTeX
• Document class: article (A4, 11pt)
• Circuit diagrams: quantikz package
• Compilation tested with: pdflatex, latexmk