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<N \text{ and } \gcd(x,N)=1$$

(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$$


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?

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

1 Answer 1


$$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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.