Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 324 / 1 / b

The distinct values in one period imply that $r$ is the least positive period, $r\mid N$, and $|Y|=r$. Write $x=j+tr$, where $0\le j<r$ and $0\le t<N/r$. Use the positive-exponent quantum Fourier transform convention already used in the concept article. The amplitude of first-register value $y$ isBy the root-of-unity filter, the inner sum vanishes unless $y=mN/r$. DefineThe distinct $f(j)$ give an orthonormal basis of the second register, and the transformed state isReindexing $j+l$ modulo $r$ showsConsequently measurement in this common eigenbasis returns each $m$ with probability $1/r$; the corresponding eigenvalue of $U_1$ is a uniformly sampled $r$th root of unity. A single measured phase $-m/r$ reveals the denominator $r/\gcd (m,r)$, which need not be $r$. Repeated samples permit exact period recovery from a Fourier sample, for example by taking the least common multiple of their reduced denominators. The simultaneous eigenspaces and their probabilities depend on $r$, not on the particular labels $f(j)$.