2
$\begingroup$

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

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?

$\endgroup$
  • 1
    $\begingroup$ What does it mean when we say that the order of x modulo N is r? $\endgroup$ – DaftWullie Apr 20 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 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 at 2:42
  • $\begingroup$ Exactly right :) $\endgroup$ – DaftWullie Apr 21 at 5:42
2
$\begingroup$

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

$\endgroup$

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.