Quantum Phase Estimation

Quantum Phase Estimation

Quantum Phase Estimation (QPE) is the central subroutine of Shor's factoring algorithm, quantum chemistry solvers, and HHL for linear systems. Given a unitary U and its eigenstate $|u⟩$, QPE extracts the phase $\varphi$ where $U|u⟩=e^{2\pi i\varphi }|u⟩$.

The Problem

If $|u⟩$ is an eigenstate of U with eigenvalue $e^{2\pi i\varphi }$, we want to find $\varphi$. Classically, this requires $O(1/{\epsilon }^2)$ queries to U for $\epsilon$-precision. QPE achieves $\epsilon$-precision with $O(1/\epsilon )$ queries: a quadratic improvement.

Circuit Structure

Why Does It Work?

This is exactly a QFT of |φ⟩ in binary. The inverse QFT undoes this transform, concentrating amplitude at the value of φ. Measuring gives the n-bit binary representation of φ with high probability.

Precision: With n ancilla qubits, φ is estimated to 2⁻ⁿ. For φ = 1/8 = 0.001₂, three ancilla qubits suffice.

Controlled-Phase Operation

For our unitary $U=P(2\pi /8)$: $U|1⟩=e^{i\cdot 2\pi /8}|1⟩=e^{i\pi /4}|1⟩$ (eigenvalue with phase $\pi /4=2\pi \cdot (1/8)$, so $\varphi =1/8$).

The controlled-$U^{2^k}$ applies U $2^k$ times when the control is $|1⟩$. Since U is a phase rotation: $U^{2^k}|1⟩=e^{i\cdot 2^k\cdot 2\pi /8}|1⟩=e^{i\cdot 2^k\cdot \pi /4}|1⟩$. This is equivalent to a controlled phase gate $CP(2^k\cdot 2\pi /8)$.