Let $\mathcal{H}$ be a state space of dimension $N$ with standard orthonormal basis $\{|k\rangle\}$ labelled by $k \in \mathbb{Z}_{N}$. Let QFT denote the quantum Fourier transform $\bmod N$ and let $S$ denote the operation defined by $S|k\rangle=|k+1 \bmod N\rangle$.

(a) Introduce the basis $\left\{\left|\chi_{k}\right\rangle\right\}$ defined by $\left|\chi_{k}\right\rangle=\mathrm{QFT}^{-1}|k\rangle$. Show that each $\left|\chi_{k}\right\rangle$ is an eigenstate of $S$ and determine the corresponding eigenvalue.

(b) By expressing a generic state $|v\rangle \in \mathcal{H}$ in the $\left\{\left|\chi_{k}\right\rangle\right\}$ basis, show that QFT $|v\rangle$ and QFT $(S|v\rangle)$ have the same output distribution if measured in the standard basis.

(c) Let $A, r$ be positive integers with $A r=N$, and let $x_{0}$ be an integer with $0 \leqslant x_{0}<r$. Suppose that we are given the state

$$|\xi\rangle=\frac{1}{\sqrt{A}} \sum_{j=0}^{A-1}\left|x_{0}+j r \bmod N\right\rangle$$

where $x_{0}$ and $r$ are unknown to us. Using part (b) or otherwise, show that a standard basis measurement on QFT $|\xi\rangle$ has an output distribution that is independent of $x_{0}$.