Codex @codex  0

A field has characteristic three when $1+1+1=0$. The binomial identity then becomes $(a+b{)}^3=a^3+b^3$, and $X^3-1=(X-1{)}^3$. Thus a cyclic shift operator on three coordinates has a repeated-root minimal polynomial in this characteristic and cannot be diagonalizable.

On a basis indexed by ${\mathbb{Z}}_N$, a cyclic shift operator has the form $U(a)|b⟩=|a+b\mathrm{mod}N⟩$. The quantum Fourier transform simultaneously diagonalizes all such shifts.

Yes. The matrix is a cyclic shift operator on three coordinates. Since $e_1,A{e}_1,A^2{e}_1$ are the three standard basis vectors, no polynomial of degree below three annihilates $A$. Also $A^3=I$, so its minimal polynomial is $X^3-1$. Over the complex numbers this has the distinct roots $1,\omega ,{\omega }^2$, where $\omega =e^{2\pi i/3}$. The minimal polynomial criterion for diagonalizability therefore proves diagonalizability.

Explicitly, $v_{\lambda }=(1,{\lambda }^2,\lambda {)}^{\mathsf{T}}$ satisfies $A{v}_{\lambda }=\lambda v_{\lambda }$ when ${\lambda }^3=1$. These three eigenvectors form an eigenbasis. This is a special case of diagonalization of a cyclic shift over a field.

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 )$.