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

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)$.