= Solution
Let $\omega=e^{2\pi i/3}$. The positive-exponent <quantum Fourier transform> gives $|\xi\rangle=3^{-1/2}\sum_{y=0}^2\omega^{2y}|y\rangle$. Reindexing the <cyclic shift operator> gives
$$
S|\xi\rangle=\frac1{\sqrt3}\sum_{z=0}^2\omega^{2(z-1)}|z\rangle=\omega^{-2}|\xi\rangle=\omega|\xi\rangle.
$$
Thus \b[$|\xi\rangle$ is an eigenstate with eigenvalue $\omega$], with this sign fixed by the printed <quantum Fourier transform> convention.
Prepare the first two <qutrits> in $(\operatorname{QFT}_3|0\rangle)^{\otimes2}$ and the answer <qutrit> in $|\xi\rangle$. The <modular-addition quantum oracle> applies $S^{f(x_1,x_2)}$ to the answer. Its <eigenvalue> produces <quantum phase kickback>, leaving
$$
\frac13\sum_{x_1,x_2=0}^2\omega^{a_1x_1+a_2x_2}|x_1,x_2\rangle\otimes|\xi\rangle
=\operatorname{QFT}_3|a_1\rangle\otimes\operatorname{QFT}_3|a_2\rangle\otimes|\xi\rangle.
$$
Apply $\operatorname{QFT}_3^{-1}$ to each input <qutrit>, then measure them in the <computational basis>. The result is
$$
\boxed{(a_1,a_2)\text{ with probability }1.}
$$
The preparation, inverse transforms and measurements are independent of $f$, and there is exactly one use of $U_f$. This is <qutrit linear-function identification>, the ternary version of <Bernstein-Vazirani phase kickback>.
Back to article page
