Algorithm Sheet — QFT, Phase Estimation, Shor, Grover, Trotter, VQE (L08–L12)

Quantum Fourier Transform (L08)¶

$\text{QFT}|j\rangle = \frac{1}{\sqrt N}\sum_{k=0}^{N-1} e^{2\pi i jk/N}|k\rangle$, $N=2^n$.
Circuit: $H$ + controlled-$R_k$ ($R_k=\text{diag}(1,e^{2\pi i/2^k})$) + final swaps.
Cost: $\mathcal O(n^2)$ gates vs classical FFT $\mathcal O(n2^n)$.
Caveat: amplitudes, not data — you cannot read them all out. QFT pays off inside period-finding structures.

Quantum Phase Estimation (L09)¶

Given $U|u\rangle = e^{2\pi i\varphi}|u\rangle$: $t$ ancillas in $H^{\otimes t}$, controlled-$U^{2^j}$, inverse QFT, measure $\to$ $\varphi$ to $t$ bits.
Success $\ge 1-\epsilon$ with $t = n_{\text{prec}} + \lceil\log(2+\tfrac{1}{2\epsilon})\rceil$.
Materials use: $U=e^{-iH\tau}$ $\Rightarrow$ eigenphases give energies $E_k$ — the fault-tolerant route to spectra.

Shor / Order Finding (L09)¶

Factor $N$: pick $a$; find order $r$ of $a \bmod N$ via QPE on $U|y\rangle=|ay \bmod N\rangle$; if $r$ even and $a^{r/2}\ne-1$: $\gcd(a^{r/2}\pm1, N)$ gives factors.
Continued fractions recover $r$ from measured $\varphi \approx s/r$.
Cost: $\mathcal O((\log N)^3)$ vs. sub-exponential classical (GNFS).

Grover / Amplitude Amplification (L10)¶

Oracle $O_f|x\rangle = (-1)^{f(x)}|x\rangle$; diffusion $D = 2|s\rangle\langle s| - I$, $|s\rangle=H^{\otimes n}|0\rangle$.
Iterate $G=DO_f$ about $R \approx \frac\pi4\sqrt{N/M}$ times ($M$ marked of $N$).
Geometry: each $G$ rotates by $2\theta$, $\sin\theta=\sqrt{M/N}$.
Overshooting reduces success — Grover is not monotone.
Quadratic speedup is provably optimal for unstructured search.

Trotterization (L11)¶

$H=\sum_k h_kH_k$: $e^{-iHt}\approx\left(\prod_k e^{-ih_kH_kt/r}\right)^r$,
error $\mathcal O\!\big(\tfrac{t^2}{r}\sum_{j<k}\|[H_j,H_k]\|\big)$; 2nd-order symmetric: $\mathcal O(t^3/r^2)$.
Pauli-string evolution $e^{-i\theta P}$: basis rotations + CNOT ladder + $R_z(2\theta)$ + undo.
Jordan–Wigner: $a_j\mapsto \big(\prod_{k<j}Z_k\big)\tfrac{X_j+iY_j}{2}$.

VQE (L12)¶

$E(\boldsymbol{\theta})=\langle \psi(\boldsymbol{\theta})|H|\psi(\boldsymbol{\theta})\rangle\ge E_0$; hybrid loop: QPU measures Pauli groups, CPU optimizes.
Parameter-shift: $\partial_\theta E=\tfrac12[E(\theta{+}\tfrac\pi2)-E(\theta{-}\tfrac\pi2)]$.
Shots for precision $\varepsilon$: $\sim(\sum_k|h_k|)^2/\varepsilon^2$. Chemical accuracy: 1.6 mHa.
Watch for: barren plateaus (deep random ansätze), noise floor, local minima.

When to Use What¶

Complexity Snapshot¶

BQP $\supseteq$ BPP; believed BQP $\ne$ NP-complete-solving.
Speedups: exponential (structured: factoring, simulation), quadratic (unstructured search).
Exam habit: always report qubit count, circuit depth, and shot/repetition cost.