= Solution
The two registers start in $|0\rangle|0\rangle$. A <quantum Fourier transform> on the first and evaluation of $f$ give
$$
|0\rangle|0\rangle
\longmapsto
\frac14\sum_{x=0}^{15}|x\rangle|0\rangle
\longmapsto
\frac14\sum_{x=0}^{15}|x\rangle|f(x)\rangle.
$$
The first <quantum measurement in the computational basis>[measurement], on the function register, returns $1$. The compatible inputs are $1,5,9,13$, so the normalized state becomes
$$
\frac12\bigl(|1\rangle+|5\rangle+|9\rangle+|13\rangle\bigr)|1\rangle.
$$
Apply $\operatorname{QFT}_{16}$ to the first register and put $\omega=e^{2\pi i/16}$. Its state is
$$
\frac18\sum_{y=0}^{15}
\omega^y\left(1+\omega^{4y}+\omega^{8y}+\omega^{12y}\right)|y\rangle.
$$
The geometric sum vanishes unless $4\mid y$. Thus this is
$$
\frac12\left(
|0\rangle+i|4\rangle-|8\rangle-i|12\rangle
\right),
$$
up 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,
$$
\frac{12}{16}=\frac34.
$$
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
$$
\boxed{r=4}.
$$
Back to article page
