= Solution
All steps through the transformed state are the same as in part (c), but the second measurement now gives $y=8$. The classical fraction is
$$
\frac8{16}=\frac12,
$$
so reduction or the <continued-fraction algorithm> proposes denominator $2$. This is not a period, since for example
$$
f(0)=2\ne3=f(2).
$$
Equivalently, 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.
Back to article page
