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

Measure the second register of $|f⟩$. If the result is $f(x_0)$, injectivity within one period collapses the first register to the periodic coset stateApply ${\mathrm{QFT}}_N$ and measure the first register. By the stated transform identity, the outcome isfor a uniformly random $l\in \{0,\dots ,r-1\}$.

Reduce the rational numberto lowest terms and call its denominator $q$. The exact period recovery from a Fourier sample givesThus $q=r$ exactly when $l$ is coprime to $r$.

The success can be certified with two classical function evaluations. Compute $f(0)$ and $f(q)$. Since $q\mid r$ and $0\le q\le r$, periodicity and injectivity within a period implyReport $q$ only when this equality holds; otherwise report failure. The success probability isusing the standard lower bound for the Euler totient function. This is heralded exact quantum period finding when the period divides the register size.

The powers of $3$ modulo $10$ areThey then repeat, and none of the first three positive exponents returns $1$. Hence the least period is $\boxed{r=4}$.

Each of the four valuesoccurs for three of the twelve inputs. The corresponding basis states in the first register are orthogonal, so the Born rule gives

The value $3$ occurs at $x=1,5,9$. Projecting onto that measurement outcome and normalizing leaves the periodic coset state

Here $N=12$, $r=4$, $A=N/r=3$, and $x_0=1$. The supplied quantum Fourier transform of a periodic coset state gives, with $\omega =e^{2\pi i/12}$,Consequently,