= Solution
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\leq j<r$ and $0\leq t<N/r$. Use the positive-exponent <quantum Fourier transform> convention already used in the concept article. The amplitude of first-register value $y$ is
$$
\frac1N\sum_{j=0}^{r-1}e^{2\pi ijy/N}|f(j)\rangle
\sum_{t=0}^{N/r-1}e^{2\pi itry/N}.
$$
By the <root-of-unity filter>, the inner sum vanishes unless $y=mN/r$. Define
$$
\boxed{M=\{mN/r:0\leq m<r\},\qquad
|e_{mN/r}\rangle=\frac1{\sqrt r}\sum_{j=0}^{r-1}e^{2\pi imj/r}|f(j)\rangle.}
$$
The distinct $f(j)$ give an <orthonormal basis> of the second register, and the transformed state is
$$
|\xi\rangle=\frac1{\sqrt r}\sum_{m=0}^{r-1}|mN/r\rangle|e_{mN/r}\rangle.
$$
Reindexing $j+l$ modulo $r$ shows
$$
\boxed{U_l|e_{mN/r}\rangle=e^{-2\pi iml/r}|e_{mN/r}\rangle.}
$$
Consequently 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)$.
Back to article page
