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 '19 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 '19 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 '19 at 2:42
  • $\begingroup$ Exactly right :) $\endgroup$ – DaftWullie Apr 21 '19 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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