= Modular multiplication eigenstates
{title2=$|u_s\rangle=r^{-1/2}\sum_{j=0}^{r-1}e^{-2\pi isj/r}|x^j\bmod n\rangle$}
For $\gcd(x,n)=1$ and order $r$, multiplication by $x$ modulo $n$ is a <unitary operator>. On the orbit of one it cyclically permutes $r$ basis states. The displayed orthonormal <eigenstates> have <eigenvalues> $e^{2\pi is/r}$, and $|1\rangle=r^{-1/2}\sum_s|u_s\rangle$. Thus <quantum phase estimation> on this efficiently prepared state samples a uniform $s$ without knowing $r$. Controlled powers are implemented by <quantum modular exponentiation>. Sufficient phase resolution allows <continued-fraction recovery in quantum order finding>; the reduced denominator equals $r$ only when $s$ is coprime to $r$.
Back to article page
