order finding

Given \(x\) find the minimum integer \(r\) such that \(x^r \equiv 1 \pmod{N}\). That is, find the order of \(x\)

Consider the matrix \(U_x\) such that for \(0\leq y \leq N\), \(U_x\ket{y} = \ket{yx\mod N}\)

Then, we see that there are \(r\) eigenstates of \(U_x\): \[ \ket{u_s} \equiv \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-\frac{2\pi sk}{r}}\ket{x^k\mod N} \] for \(0\leq s \leq r-1\) because \[ U_x\ket{u_s} = e^{\frac{2\pi sk}{r}} \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-\frac{2\pi sk}{r}}\ket{x^k\mod N} \] Why? In the first equation, imagine each one of the terms \(\ket{x^k\mod N}\) being placed on a clock (the unit circle) according to their position. Starting from 1 and working counter clockwise, the terms can be placed. Multiplying each one of the terms by \(U_x\) shifts all the terms clockwise once. So the eigenvalue is \(e^{\frac{2\pi sk}{r}}\), which corresponds with one shift clockwise.

Then, using phase estimation, we can find \(\phi\) where the eigenvalue is \(e^{2\pi i \phi}\). In this case, \(\phi=s/r\), then \(r\) can be recovered.

But \(\phi\) is a decimal number. How do we recover the fraction \(s/r\)? We can do this using the continued fraction.

But \(\phi\) may not be exactly correct. It's an approximation (as returned by the phase estimation algorithm). That's ok, as long as \(\phi\) can be guaranteed to be within some distance of \(s/r\), then \(s/r\) will be a convergent (think of a partial sum) of the continued fraction.

Finally, we won't know the eigenstate \(\ket{u_s}\) a priori. But it turns out that \[ \ket{1} = \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1} \ket{u_s} \] so we see that \(\ket{1}\) is a superposition of all the eigenvectors we care about. Why is the above fact true? Look at a coefficient for \(\ket{x^k\mod N}\), which is \(\sum_{s=0}^{r-1} e^{2\pi i sk/r}\). If \(k=0\), then these terms are all 1. Otherwise, these terms occupy positions on the clock that, when added together, cancel each other out.