= Solution
Changing the summation variable from $y$ to $z=y+1$ gives
$$
S|\xi_x\rangle
=\frac1{\sqrt d}\sum_y\omega_d^{xy}|y+1\rangle
=\omega_d^{-x}\frac1{\sqrt d}\sum_z\omega_d^{xz}|z\rangle
=\boxed{\omega_d^{-x}|\xi_x\rangle}.
$$
Thus the <quantum Fourier transform> diagonalizes the cyclic shift.
For $f:\mathbb Z_m\to\mathbb Z_n$,
$$
U_f=\sum_{x\in\mathbb Z_m}|x\rangle\langle x|\otimes S^{f(x)}.
$$
Consequently the product states
$$
\boxed{|x\rangle|\xi_y\rangle,
\qquad x\in\mathbb Z_m,quad y\in\mathbb Z_n,}
$$
form an <eigenbasis>, with corresponding <eigenvalues>
$$
\boxed{\omega_n^{-y f(x)}.}
$$
Back to article page
