= Solution
One classical query at any chosen $x_0$ returns only $v=sx_0+t$. Every possible slope $s\in\mathbb Z_3$ is compatible with that answer by choosing $t=v-sx_0$, so no one-query classical algorithm can determine $s$ with certainty.
For the quantum algorithm, let $\omega=e^{2\pi i/3}$ and prepare
$$
|\xi_0\rangle|\xi_{-1}\rangle
=\frac1{\sqrt3}\sum_{x\in\mathbb Z_3}|x\rangle|\xi_2\rangle.
$$
Part (b) shows that the single query applies <quantum phase kickback>:
$$
U_f|\xi_0\rangle|\xi_{-1}\rangle
=\frac1{\sqrt3}\sum_x\omega^{f(x)}|x\rangle|\xi_{-1}\rangle
=\omega^t|\xi_s\rangle|\xi_{-1}\rangle.
$$
The unknown intercept contributes only a <global phase>. Applying $\operatorname{QFT}_3^{-1}$ to the first register produces $|s\rangle$, whose computational-basis measurement determines $s$ with certainty after one query.
Back to article page
