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

Let the spectral decomposition of the Hermitian matrix beThe HHL algorithm proceeds as follows.

Efficiently prepare the normalized amplitude encoding $|b⟩$.
Apply quantum phase estimation to the simulated evolution $e^{iAt}$, producing an approximation of each eigenvalue: Add one ancilla and perform an eigenvalue-controlled rotationwhere $0<C\le {\min }_j|{\lambda }_j|$.
Uncompute the eigenvalue register. Conditional on measuring the ancilla as $1$, the system register isThe postselection probability can be increased with amplitude amplification.

The ingredients used here are efficient sparse Hamiltonian simulation of $e^{iAt}$ and quantum phase estimation, which converts an eigenphase of that evolution into a binary approximation of ${\lambda }_j$. For sparsity $s$, condition number $\kappa$, and error $ϵ$, the cost is polynomial in $s$, $\kappa$, $1/ϵ$, and $\log N$ under the stated access assumptions.

Finally estimate $⟨x|M|x⟩$ by repeated measurement of an efficient observable decomposition of $M$, or by a Hadamard test when $M$ is unitary. A general efficiently block-encoded Hermitian $M$ can similarly be measured through its block encoding. Repetition and a concentration inequality give additive sampling error $O(1/\sqrt{R})$ after $R$ independent preparations.

The essential requirement is an efficient quantum state preparation circuit $B$ satisfyingA standard sufficient promise is that $b$ has only $\mathrm{poly}(\log N)$ nonzero components, with their positions and values classically computable to the required precision in $\mathrm{poly}(\log N)$ time, and with efficiently computable normalization. More structured dense vectors are also allowed whenever cumulative weights or an equivalent data-access oracle permit amplitude encoding in polylogarithmic time. Without such a promise, merely loading $N$ arbitrary classical entries already costs $\Omega (N)$ and removes the claimed exponential dependence on dimension.

Use reversible quantum arithmetic on an ancillary work register. On each computational-basis branch, computewhereBecause the classical algorithms for $A_i$ and $B_i$ are efficient, they can be made reversible with polynomial overhead. Reversible division, square root, and inverse cosine to the retained binary precision likewise use $\mathrm{poly}(\log N)$ gates under the question's precision convention. Uncompute the $A_i$ and $B_i$ work registers, leaving

Suppose the angle register stores a fixed-point expansion ${\theta }_i={\sum }_{r=1}^q{\theta }_{ir}{2}^{-r}{\theta }_{\max }$. Append a target qubit in $|0⟩$. For each angle bit $het{a}_{ir}$, apply to the target a controlled $R_y(2^{1-r}{\theta }_{\max })$. Rotations about the same axis commute, so their product is $R_y(2{\theta }_i)$ andWith $q=O(\mathrm{poly}\log N)$ retained bits, each controlled rotation decomposes into one- and two-qubit gates and the complete quantum variable rotation has polylogarithmic size. Thus the required branchwise map is implemented coherently for every $i$.

The ratio $f_i=A_i/B_i$ is the conditional probability that $X$ lies in the left half of interval $i$. After the controlled rotation and uncomputation of $|{\theta }_i⟩$, append the rotation qubit to the interval label. The amplitudes becomeButConsequently one refinement step mapsStarting from $|{\psi }_1⟩$ and repeating this hierarchical probability-distribution state preparation for $m=1,\dots ,n-1$ givesThere are $n-1=O(\log N)$ refinement levels, each of polylogarithmic size by assumption.