Application of QFT to Order-finding

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|yrangle = |xypmod Nrangletag1 $$

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 $expfrac{2pi 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 $|vrangle$ is an eigenvector of $U$ associated with eigenvalue $lambda$ then

$$ U^k|vrangle = lambda^k|vrangle. $$

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

$$ U^k|yrangle = |x^k ypmod Nrangle $$

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

$$ lambda^r|vrangle = U^r|vrangle = |vrangle $$

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 = expfrac{2pi 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^0pmod Nrangle,dots|x^{r-1}pmod Nrangle$. Consequently, the uniform superposition

$$ |v_0rangle = frac{1}{sqrt{r}}sum_{k=0}^{r-1}|x^kpmod Nrangletag3 $$

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^kpmod Nrangletag4 $$

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

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_arangle = frac{1}{sqrt{r}}sum_{k=0}^{r-1}a^k|x^kpmod Nrangle. $$

Let us try it

$$ begin{align} U|v_arangle &= frac{1}{sqrt{r}}sum_{k=0}^{r-1}a^k|x^{k+1}pmod Nrangle &= a^{-1}frac{1}{sqrt{r}}sum_{k=0}^{r-1}a^{k+1}|x^{k+1}pmod Nrangle end{align} $$

so if $a^r=1$ then

$$ begin{align} U|v_arangle &= a^{-1}frac{1}{sqrt{r}}sum_{k=0}^{r-1}a^{k+1}|x^{k+1}pmod Nrangle &= a^{-1}frac{1}{sqrt{r}}sum_{k=0}^{r-1}a^k|x^kpmod Nrangle &= a^{-1} |v_arangle end{align} $$

and $|v_arangle$ 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 = expleft(-frac{2pi i s}{r}right)$. Putting it all together, we see that

$$ |u_srangle = |v_{e^{-2pi is/r}}rangle = sum_{k=0}^{r-1}expleft(-frac{2pi isk}{r}right)|x^k pmod Nrangle $$

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