Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 4 / 10D (Quantum Information and Computation)

Writing $\omega =e^{2\pi i/N}$, $|{\chi }_k⟩=N^{-1/2}{\sum }_j{\omega }^{-jk}|j⟩$. Therefore $S|{\chi }_k⟩={\omega }^k|{\chi }_k⟩$.

If $|vangle={\sum }_k{c}_k|{\chi }_{k}angle$, then QFT measurement has probabilities $|c_k{|}^2$. Applying $S$ multiplies $c_k$ by the phase ${\omega }^k$, so the probabilities are unchanged.

The offset state is $S^{x_0}$ applied to the offset-zero periodic state. Part (b) therefore makes its QFT output distribution independent of $x_0$. Explicitly, only outcomes divisible by $A=N/r$ occur, each with probability $1/r$; $x_0$ contributes only a phase.