💼 Case: consider the order-finding problem, given $x,N \in \N$ with $\gcd (x,N)=1$ the order $x \mod N$ is the smaller positive integer $r$ such that
$$ x^r\equiv 1 \; (\mod N) $$
🗒️ Note: since $x$ and $N$ are coprime, an $r$ always exists
⚽ Goal: find $r$ efficiently
🗒️ Note: there are no known classical polynomial time algorithms in $L$ to solve this problem where $L=\operatorname{ceil} (\log (N))$ so that $N\le 2^L$
✨ Proposition: the greatest common divisor of two integers $a$ and $b$ is the least positive integer which can be written in the form $ar+bs$ where $r$ and $s$ are integers
🧚♂️ Proof: Assume $u=ar+bs$ is the least positive integer, since $\gcd(a,b)$ divides both $a$ and $b$ it therefore divides $u$ and hence $\gcd(a,b) \le u$ . in a similar fation we can also show that $\rm gcd(a,b) \ge u$ meaning the only available solution is $\gcd(a,b)=u$
🔁 Corollary: An integer $c$ divides both $a$ and $b$ if $c$ divides $\gcd(a,b)$
🗒️ Note: we say $x$ and $n$ are coprime if $\gcd (x,n)=1$
🔃 Corollary: An integer $x$ has an inverse modulo $n>1$ if $x$ and $n$ are co-prime
lets now actually complete our goal using the same case
We apply the phase estimation algorithm to the operation $U$ defined by
$$ U \ket{y}= \left \{ \begin{matrix} \ket{xy(\mod N)} & \text{for} & 0 \le y \le N \\ \ket{y} & \text{for} & N \le y \le 2^L -1 \end{matrix}\right . $$
For $0\le s \le r-1$ let
$$ \ket{u_s} = \frac{1}{\sqrt{r}} \sum ^{r-1}_{k=0} \exp \left ( \frac{-2\pi isk}{r} \right )\ket{x^k ( \mod N )} $$
which we can simplify using $x^r=1 \; (\mod N)$
$$ \begin{aligned} U\ket{u_s} & = \frac{1}{\sqrt{r}} \sum ^{r-1}_{k=0} \exp \left ( \frac{-2\pi isk}{r}\right )\ket{x^{k+1} (\mod N)} \\ &=\exp \left ( \frac{2\pi is}{r} \right )\ket{us}
\end{aligned} $$
💎 Conclusion: $\ket{u_s}$ is an eigenvector of $U$ with eigenvalue $\exp \left ( \frac{2\pi is}{r} \right )$ for $0\le s \le r-1$
Our approach will be to compute the phase $s/r$ which we can use to find $r$
Since $\ket{u_s}$ depends on $r$ we instead note that
$$ \frac{1}{\sqrt{r}} \sum ^{r-1}{s=0} \ket{u_s} = \sum ^{r-1}{k=0} \left ( \frac{1}{r} \sum ^{r-1}_{s=0} e^{\frac{-2\pi isk}{r}} \right )\ket{x^k (\mod N)}=\ket{1} $$
since $\ket{x^k (\mod N)}=\ket{1}$ when $k=0$ and $\ket{0}$ otherwise
We therefore use $\ket{1}$ in the second register(linear combination of eigenvectors of $U$)
From there we need to find how the $U^{2^k}$ gates are applied and how to approximate $\phi_s$
The state of the first register after the Hadamard gate is
$$ \frac{1}{\sqrt{2^t}} \sum ^{2^-1}_{k=0} \ket{k} $$
💼 Case: consider the state $\ket k= \ket{k_t k_{t-1}\cdots k_1}$ of the first register (up) and the state $\ket{u}$ of the second register (down)
The sequence of Controlled $U^{2^k}$ gives
$$ \begin{aligned}|k\rangle |u\rangle &\mapsto |k\rangle U^{k_t 2^{t-1}} U^{k_{t-1} 2^{t-2}} \cdots U^{k_1 2^0} |u\rangle \\&= |k\rangle |x^{k_t 2^{t-1}} x^{k_{t-1} 2^{t-2}} \cdots x^{k_1 2^0} u \bmod N\rangle \\&= |k\rangle |x^{k_t 2^{t-1} + k_{t-1} 2^{t-2} + \cdots + k_1 2^0} u \bmod N\rangle \\&= |k\rangle |x^k u \bmod N\rangle\end{aligned} $$
💎 Conclusion: equivalent to $\times$ mod N the second register with $x\hat \;$ of the content of the first register