# Eigenstate of unitary operator used for Order-Finding

In the "Quantum Computation and Quantum Information 10th Anniversary textbook by Nielsen and Chuang", chapter 5.3.1 introduces the concept of solving the Order-Finding Problem.

(Eqn 5.36) states the following:

$$U|y\rangle = |xy\text{ mod } N\rangle \text{ whereby } x

(Eqn 5.37) defines the eigenstates of the unitary operator $$U$$ as:

$$|u_s\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}\exp\left(\frac{-2\pi isk}{r}\right)\left|x^k\text{ mod } N\right\rangle \text{ for integer } 0 \leq s \leq r-1$$

Then when $$U$$ acts on $$|u_s\rangle$$, (Eqn 5.38 to 5.39) gives:

$$U|u_s\rangle = \frac{1}{\sqrt{r}} \sum_{k=0}^{r-1}\exp\left(\frac{-2\pi isk}{r}\right) |x^{k+1}\text{ mod } N\rangle = \exp\left(\frac{2\pi is}{r}\right)|u_s\rangle$$

I tried to work out Eqn 5.38 to 5.39 by substituting the index $$k$$ as dummy index $$v=k+1$$ which I get:

$$U|u_s\rangle = \exp\left(\frac{2{\pi}is}{r}\right) \frac{1}{\sqrt{r}}\sum_{v=1}^{r}\exp\left(\frac{-2\pi isv}{r}\right)|x^v\text{ mod }N\rangle$$

Question

Why is $$\frac{1}{\sqrt{r}}\sum_{v=1}^{r}\exp\left(\frac{-2\pi isv}{r}\right)|x^v\text{ mod }N\rangle = |u_s\rangle$$ when the summation limits are different? $$|x^0\text{ mod }N\rangle$$ and $$|x^r\text{ mod }N\rangle$$ are not the same right?

• What does it mean when we say that the order of x modulo N is r? Apr 20, 2019 at 17:51
• @DaftWullie It means r is the least integer that satisfies x^r = p*N + 1 for some integer p?
– C.C.
Apr 21, 2019 at 2:35
• @DaftWullie I see.. x^r mod N = 1 by definition of r, which is the same as x^0 mod N = 1
– C.C.
Apr 21, 2019 at 2:42
• Exactly right :) Apr 21, 2019 at 5:42

$$x^0 \bmod N = 1 \implies x^r \bmod N = 1$$ as by definition, $$r$$ is the order of $$x \bmod N$$ i.e. $$r$$ is the least integer that satisfies $$x^r=pN+1$$ for some integer $$p$$.