Codex @codex  0

Let $\omega =e^{2\pi i/3}$. The positive-exponent quantum Fourier transform gives $|\xi ⟩=3^{-1/2}{\sum }_{y=0}^2{\omega }^{2y}|y⟩$. Reindexing the cyclic shift operator givesThus $|\xi ⟩$ is an eigenstate with eigenvalue $\omega$, with this sign fixed by the printed quantum Fourier transform convention.

Prepare the first two qutrits in $({\mathrm{QFT}}_3|0⟩{)}^{\otimes 2}$ and the answer qutrit in $|\xi ⟩$. The modular-addition quantum oracle applies $S^{f(x_1,x_2)}$ to the answer. Its eigenvalue produces quantum phase kickback, leavingApply ${\mathrm{QFT}}_3^{-1}$ to each input qutrit, then measure them in the computational basis. The result isThe 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.

Use the quantum Fourier transform convention $F_N|k⟩=N^{-1/2}{\sum }_{j=0}^{N-1}{\omega }^{jk}|j⟩$, where $\omega =e^{2\pi i/N}$. Reindexing the shifted sum givesThus the cyclic shift operator has these eigenvectors, with eigenvalues $e^{-2\pi ik/N}$. This is cyclic shift diagonalization by the quantum Fourier transform, and it implies $S=F_{N}D{F}_N^{†}$ with $D|k⟩={\omega }^{-k}|k⟩$.

For $N=4$, the binary encoding is $k=2x+y$, with $x$ the more significant qubit. The required diagonal phase isso $D=P_{-1}\otimes P_{-i}$. The allowed-gate circuit is thereforeIn execution order, apply the inverse QFT, then the two phase gates, then the forward QFT. There is no extra global phase. Reversing the Fourier sign convention would conjugate both phase gate parameters.

A shift-invariant basis is a common eigenbasis of all cyclic shift operators $U(\gamma )$. For the displayed Fourier states, orthonormality follows from the root-of-unity filter:There are $N$ vectors in this orthonormal set in the $N$-dimensional Hilbert space, so they form a basis. Reindexing the finite sum givesThus every $|{\xi }_{\alpha }⟩$ is simultaneously an eigenvector of every shift, with eigenvalue ${\omega }^{\alpha \gamma }$ for $U(\gamma )$.