Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 324 / 2

For the HHL algorithm to have runtime polynomial in $\log N$, the Hermitian matrix $A$ must be invertible, have a condition number $\kappa$ bounded by $\mathrm{poly}(\log N)$, and be a sparse matrix with its nonzero entries efficiently accessible by an oracle. The normalized state $|b⟩$ must also be preparable in $\mathrm{poly}(\log N)$ time. With precision costs suppressed, these assumptions let HHL prepare, with high probability,

Normalization gives $p^2+q^2=1$. Write $p=\sin \theta$, $q=\cos \theta$ with $0<\theta <\pi /2$, and set $|u⟩=U|b⟩$. Define the two Householder reflectionsThe amplitude amplification iterate $G=R_u{R}_{\xi }$ preserves $\mathrm{span}\{|\xi ⟩,|\varphi ⟩\}$ and rotates that plane through $2\theta$. ConsequentlyIn particular, $O(1/p)$ iterations raise the success probability to a constant close to one.

Choose an integer $k$ large enough thatPrepare an ancillary qubit in $\sqrt{1-c^2}|0⟩+c|1⟩$ and declare only $|\xi ⟩|1⟩$ to be good. The initial good amplitude ofis $pc=\sin {\theta }^{\prime }$. Applying $k$ amplitude amplification iterations gives good amplitudeThe final state is therefore $|\xi ⟩|1⟩$ up to a global phase. Discarding the ancilla prepares $|\xi ⟩$ exactly; this is exact amplitude amplification.

Let $t=e^{iz}$ and $|u⟩=U|b⟩=p|\xi ⟩+q|\varphi ⟩$. The first factor in $G$ isSince $R(\xi ,z)|u⟩=pt|\xi ⟩+q|\varphi ⟩$, the coefficient of $|\varphi ⟩$ in $G|u⟩$ isIt vanishes whenor, using $p^2+q^2=1$,A unit-modulus solution $t=e^{iz}$ exists exactly when the right-hand side lies in $[-2,2]$. The upper bound is automatic, while the lower bound isThus exact preparation by one application of $G$ is possible precisely whenOne may choose $z$ so that $\cos z=(p^2-q^2)/(2p^2)$. Then $G|u⟩$ has no $|\varphi ⟩$ component and, by unitarity, equals $|\xi ⟩$ up to phase. This is a phase-matched amplitude amplification step.