Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 2 / 15D (Quantum Information and Computation)

Writing ${\omega }_N=e^{2\pi i/N}$, the quantum Fourier transform acts on a computational-basis state as

Applying the transform twice givesThe root-of-unity filter makes the inner sum equal to $N$ exactly when $z\equiv -x(\mathrm{mod}N)$ and zero otherwise. HenceApplying modular negation twice givesTherefore ${\mathrm{QFT}}_N^2$ is an involution. Every one of its eigenvalues $\lambda$ satisfies ${\lambda }^2=1$, so its spectrum is contained in $\{1,-1\}$, as summarized by the square of the quantum Fourier transform.

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

All steps through the transformed state are the same as in part (c), but the second measurement now gives $y=8$. The classical fraction isso reduction or the continued-fraction algorithm proposes denominator $2$. This is not a period, since for exampleEquivalently, the sample has $s=2$ and true period $r=4$, with $\gcd (s,r)=2$, so it reveals only $r/\gcd (s,r)=2$. The algorithm does not succeed from this sample and must be repeated.