# Application of QFT to Order-finding

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.

• 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? – Condo Jan 12 at 18:24
• 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? – Adam Zalcman Jan 12 at 18:39
• @Condo I am sorry that I posed in such a way. Let me rephrase it. – user27286 Jan 13 at 3:32
• @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? – user27286 Jan 13 at 3:37
• @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 – Condo Jan 13 at 20:20

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!

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.

• Thanks. It helps. – user27286 Jan 15 at 23:02