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

Use $m$ control qubits and exact quantum phase estimation. A controlled $U^{2^j}$ on the unknown eigenstate can be synthesized from the available uncontrolled operation and the known eigenstate $|{\xi }_0⟩$: conditionally swap $|\xi ⟩$ into an auxiliary register initialized to $|{\xi }_0⟩$, apply $U^{2^j}$ to that register, and swap back. The auxiliary state is restored, while the control-one branch acquires $e^{2\pi i{2}^j\varphi }$.

After Hadamard gates and these controlled powers, the control register isThe inverse quantum Fourier transform maps this state exactly to $|c⟩$, so measurement determines $c$ with certainty. There are $m$ controlled swaps of $O(n)$ qubits, each promised power costs $\mathrm{poly}(n,j)$, and the inverse transform uses $O(m^2)$ elementary gates. The total cost is therefore $\mathrm{poly}(n,m)$.

Expand $|b⟩={\sum }_i{b}_i|{\lambda }_i⟩$ in the nondegenerate eigenbasis of $A$. Apply quantum phase estimation to $U_{+}=e^{2\pi iA}$, using $U_{-}$ when inverse powers are needed, to coherently attach the eigenvalue:On an ancillary qubit perform the eigenvalue-controlled rotationUncompute the value register and measure the ancilla. Conditional on outcome one, the system is proportional toand normalization gives the desired $|\psi ⟩$.

The success probability isSince every ${\lambda }_i>0$,a positive lower bound independent of $|b⟩$. The promised precision assumptions permit the eigenvalue-controlled arithmetic and rotation.