# Quantum phase estimation
**Quantum phase estimation** (QPE) is a quantum algorithm that estimates the eigenvalue phase $\phi$ of a unitary operator $U$ given access to an eigenstate $\lvert u\rangle$ of $U$. It is one of the most important subroutines in quantum computing, used as a building block in [[shor|Shor's algorithm]], the [[hhl|HHL algorithm]], and quantum simulation.

If $U\lvert u\rangle = e^{2\pi i\phi}\lvert u\rangle$ with $\phi \in [0,1)$, then QPE estimates $\phi$ to $n$ bits of precision using $n$ ancilla qubits and $O(2^n)$ controlled-$U$ operations.

## Algorithm
Start with $n$ ancilla qubits in $\lvert 0\rangle^{\otimes n}$ and the system register in eigenstate $\lvert u\rangle$. Apply Hadamard gates to all $n$ ancilla qubits to create a uniform superposition. Then apply controlled-$U^{2^k}$ for $k = 0, 1, \ldots, n-1$, where qubit $k$ controls $U^{2^k}$. Finally, apply the inverse quantum Fourier transform to the ancilla register and measure it.

$$\lvert 0\rangle^{\otimes n}\lvert u\rangle \xrightarrow{H^{\otimes n}} \frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1}\lvert j\rangle\lvert u\rangle \xrightarrow{\text{ctrl-}U} \frac{1}{\sqrt{2^n}}\sum_{j=0}^{2^n-1} e^{2\pi i j\phi}\lvert j\rangle\lvert u\rangle \xrightarrow{\text{QFT}^{-1}} \lvert\tilde{\phi}\rangle\lvert u\rangle$$

## Precision and success probability
QPE estimates $\phi$ to $n$ bits of precision. If $2^n\phi$ is an integer, the algorithm is exact and succeeds with probability 1. Otherwise, it succeeds with probability at least $4/\pi^2 \approx 40\%$ for the closest $n$-bit estimate, and adding extra ancilla bits can boost this. To estimate $\phi$ to precision $\varepsilon$ with success probability $1 - \delta$, one needs $n = O(\log(1/\varepsilon) + \log(1/\delta))$ ancilla qubits.