Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 15D / c / Solution

The two registers start in $|0⟩|0⟩$. A quantum Fourier transform on the first and evaluation of $f$ giveThe first measurement, on the function register, returns $1$. The compatible inputs are $1,5,9,13$, so the normalized state becomes

Apply ${\mathrm{QFT}}_{16}$ to the first register and put $\omega =e^{2\pi i/16}$. Its state isThe geometric sum vanishes unless $4\mid y$. Thus this isup to the unchanged second register. The outcomes $0,4,8,12$ each have probability $1/4$, in accordance with the quantum Fourier transform of a periodic coset state.

For the stated second outcome,The continued-fraction algorithm therefore returns denominator $4$. Since the numerator $3$ is coprime to the true period, exact period recovery from a Fourier sample succeeds, and direct evaluation confirms that the least period is