Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 3 / 15D / c / Solution

One classical query at any chosen $x_0$ returns only $v=s{x}_0+t$. Every possible slope $s\in {\mathbb{Z}}_3$ is compatible with that answer by choosing $t=v-s{x}_0$, so no one-query classical algorithm can determine $s$ with certainty.

For the quantum algorithm, let $\omega =e^{2\pi i/3}$ and preparePart (b) shows that the single query applies quantum phase kickback:The unknown intercept contributes only a global phase. Applying ${\mathrm{QFT}}_3^{-1}$ to the first register produces $|s⟩$, whose computational-basis measurement determines $s$ with certainty after one query.