In the Nielsen & Chuang book, section 5.3.1 page 226, there is a statement which goes like this:- (statement-1)

The quantum algorithm for order-finding is just the phase estimation algorithm applied to the unitary operator $U|y\rangle ≡ |xy(mod N)\rangle$

Well, this statement is not a trivial one. And then one more, (statement-2) (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$$

Now, there are two questions:

  1. How do we know statement-1? How do we know that the unitary operator which we have defined here, would give us the solution to the order finding problem?

  2. How do we arrive at statement-2? Eigenstates of $U$ are just the eigenvectors of $U$, so somebody might have calculated them, right? (For example, by solving $U-\lambda I= 0$). However, I don't see how one would arrive at something so elegant. Or is it just some of those "define" statements?

I would be glad if I get an answer to any of these questions.

  • $\begingroup$ Can you elaborate on what you mean by "this" in "How do we know this? and "that" in "How do we arrive at that?" in your questions? $\endgroup$
    – Condo
    Jan 12, 2021 at 18:24
  • $\begingroup$ The calculation which proves that the states $|u_s\rangle$ defined by $(5.37)$ are the eigenvectors of $U$ is given in $(5.38)$ and $(5.39)$ on the same page. Is the step from $(5.38)$ to $(5.39)$ unclear or is there some other question here? $\endgroup$ Jan 12, 2021 at 18:39
  • $\begingroup$ @Condo I am sorry that I posed in such a way. Let me rephrase it. $\endgroup$
    – user27286
    Jan 13, 2021 at 3:32
  • $\begingroup$ @AdamZalcman.: No that part is clear, but let's suppose I tell you "how do you know that the state would be what is shown here?" What is the answer for that? $\endgroup$
    – user27286
    Jan 13, 2021 at 3:37
  • 1
    $\begingroup$ @user27286 Well firstly things aren't discovered the way they are laid out in a textbook. Shor's original paper on polynomial-time factoring actually used a slightly different method to order finding on a quantum computer, the method mentioned in N&C is due to Kitaev... I don't think there is an easy answer to your question but perhaps you can start here arxiv.org/pdf/quant-ph/9903071.pdf $\endgroup$
    – Condo
    Jan 13, 2021 at 20:20

1 Answer 1


Answer to question 1

There are many ways the first quantum algorithm for order finding could have been conceived and I don't know how it really happened. However, here is a plausible though entirely fictional account of how one might have arrived at it:

Alice: Hey, I was imagining doing arithmetic on a quantum computer and made a unitary that computes multiplication modulo a given integer $N$.
Bob: Hey, that's cool! What is it?
Alice: Well, it really just permutes the computational basis states like this $$ U|y\rangle = |xy\pmod N\rangle\tag1 $$

when $x$ and $y$ are coprime to $N$ and acts as identity otherwise.
Bob: Right. I wonder what $U$'s eigenvalues are...

See the answer to question 2 below for details of what occurs here. Some time later:

Alice: So the eigenvalues are $\exp\frac{2\pi i s}{r}$ for $s=0,\dots,r-1$ where $r$ is the order of $x$ modulo $N$.
Bob: Interesting... Wait, what?!... We can use the Quantum Phase Estimation algorithm to compute eigenvalues of any unitary. This means we could use QPE to find $r$!
Alice: You're right! Wasn't finding $r$ supposed to be computationally hard?
Bob: On a classical computer? As far as we know, yeah.
Alice: Looks like it's computationally easy on a quantum computer!

Answer to question 2

As in question 1, there are many ways one can arrive at the result. The following elementary approach is loosely inspired by the power iteration algorithm for finding eigenvectors and eigenvalues. Note that if $|v\rangle$ is an eigenvector of $U$ associated with eigenvalue $\lambda$ then

$$ U^k|v\rangle = \lambda^k|v\rangle. $$

However, from the definition of $U$ in $(1)$ we know that

$$ U^k|y\rangle = |x^k y\pmod N\rangle $$

for a computational basis state $|y\rangle$ encoding a $y$ coprime to $N$. Now, let $r$ be the order of $x$ modulo $N$, i.e. $x^r = 1\pmod N$. Then,

$$ \lambda^r|v\rangle = U^r|v\rangle = |v\rangle $$

and we see that $\lambda$ is a number such that

$$ \lambda^r = 1. $$

In other words, the eigenvalues are the $r$th roots of unity

$$ \lambda = \exp\frac{2\pi i s}{r}\tag2 $$

for $s = 0,\dots,r-1$.

Having found the eigenvalues, we now want to find the corresponding eigenvectors. We begin with the observation that $U$ permutes the states $|x^0\pmod N\rangle,\dots|x^{r-1}\pmod N\rangle$. Consequently, the uniform superposition

$$ |v_0\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}|x^k\pmod N\rangle\tag3 $$

is an eigenvector associated with eigenvalue $1$. Hoping that $(3)$ might be a special case of a more general pattern, we next try

$$ |v_{a_0,\dots,a_{r-1}}\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a_k|x^k\pmod N\rangle\tag4 $$

for some complex numbers $a_0,\dots,a_{r-1}$. If we apply $U$ to both sides of $(4)$, we get

$$ U|v_{a_0,\dots,a_{r-1}}\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a_k|x^{k+1}\pmod N\rangle $$

which shifts the kets by one position cyclically relative to the coefficients $a_k$. However, by definition of eigenvector, we need this reshuffling to allow us to pull a constant out in front of the sum, so we see that we need $a_k = a^k$ for some constant $a$, i.e.

$$ |v_a\rangle = \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^k|x^k\pmod N\rangle. $$

Let us try it

$$ \begin{align} U|v_a\rangle &= \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^k|x^{k+1}\pmod N\rangle \\ &= a^{-1}\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^{k+1}|x^{k+1}\pmod N\rangle \end{align} $$

so if $a^r=1$ then

$$ \begin{align} U|v_a\rangle &= a^{-1}\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^{k+1}|x^{k+1}\pmod N\rangle \\ &= a^{-1}\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}a^k|x^k\pmod N\rangle \\ &= a^{-1} |v_a\rangle \end{align} $$

and $|v_a\rangle$ is an eigenvector associated with eigenvalue $\lambda = a^{-1}$. This is reassuring, because it means that our assumption that $a^r=1$ is satisfied. It also means that $a = \exp\left(-\frac{2\pi i s}{r}\right)$. Putting it all together, we see that

$$ |u_s\rangle = |v_{e^{-2\pi is/r}}\rangle = \sum_{k=0}^{r-1}\exp\left(-\frac{2\pi isk}{r}\right)|x^k \pmod N\rangle $$

is an eigenvector of $U$ associated with eigenvalue $\exp\left(\frac{2\pi i s}{r}\right)$ in agreement with $(5.37)$ on p.227 in Nielsen & Chuang.

  • $\begingroup$ Thanks. It helps. $\endgroup$
    – user27286
    Jan 15, 2021 at 23:02

Your Answer

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