Up to this point we have seen the basic idea of factoring prime numbers from **nontrivial square roots**. On the other hand we have seen how to obtain the period of a state with respect to an operator $U$ with a quantum computer using the **period finding** algorithm. In this lesson we will bring the two concepts together and see how to finally implement Shor's algorithm. Recall that given a number $N$, a nontrivial square root is an integer $x$ such that $x^2 \equiv 1 \pmod N$. Actually, it would be sufficient to find a number $x$ such that $x^r \equiv 1 \pmod N$ where $r$ is an even number since in this case, assuming $r = 2r'$, we would have that $x^r = x^{2r'} \equiv (x^{r'})^2 \equiv 1$ and therefore $x^{r'}$ would be our nontrivial square root. Let's go a step further and define the following function: $$f_{N,a}(m) = a^m \pmod N.$$ We would like to know which $m$ satisfies $f_{N,a}(m) = 1$, that is, $a^m \equiv 1 \pmod N$, because if it were even we would have already found the nontrivial square root. Mathematically, it can be checked that $f_{N,a}$ is a periodic function and the minimum $m$ such that $f_{N,a}(m) = 1$ is just the period. --- ***Exercise S.4.1.*** Let $f_{N,a}(m) = a^m \pmod N$ and $r$ be the minimum integer (not equal to 0) such that $f_{N,a}(r) = 1$. Prove that this is a periodic function and $r$ is the period.

Hint.

We say $f$ is a periodic function if $f(r + m) = f(m)$ for all $m$.

Solution.

By definition a function is periodic with period $r$ if $f(r + m) = f(m)$ for all $m$. Let's check it: $$f_{N,a}(r+m) = a^{r+m} \pmod N \equiv a^ra^m \pmod N.$$ Making use of the fact that $r$ is the period we get that: $$a^ra^m \pmod N \equiv 1 \cdot a^m \pmod N = f_{N,a}(m),$$ as we wanted to demonstrate. ▢

--- Shor's algorithm proposes to define an operator $U_{N,a}$ such that $U_{N,a}^m \vert 1\rangle = \vert f_{N,a}(m)\rangle$. In this situation, finding an $r$ such that $f_{N,a}(r) = 1$ would be equivalent to finding the minimum $r$ such that $U_{N,a}^r \vert 1\rangle \equiv \vert 1\rangle $. This is what we will calculate by applying the **period finding** algorithm. Moreover, a fundamental theorem in Shor's algorithm guarantees that the whole procedure is closed: **Theorem**: Given a random number $a$ between 2 and $N-2$, it follows that the probability that the period of $f_{N,a}$ is even is greater than 50%. Therefore, the strategy will be to take a random element $a$. Then, with the help of period finding, take a candidate for $r$ (the period of $U_{N,a} \vert 1\rangle$) and repeat until $r$ is even to obtain the nontrivial square root. --- ***Exercise S.4.2.*** Suppose the probability of getting an even period is $60\%$. What is the probability of getting at least one even period if we run the circuit 3 times?

Solution.

The probability of getting an odd-period number is $40\%$, so the probability of this event occurring three times in a row is $0.4^3 = 0.064$ or 6.4\%. As we are asked for the probability of success, we calculate the complementary: $100\% - 6.4\% = 93.6\%$.

--- The operator $U_{N,a}$ we are looking for can be defined as follows: $$U_{N,a}|y\rangle = |ay \pmod N\rangle.$$ Seen in this way, we can verify that: $$U^2_{N,a}|y\rangle = |a (a y) \pmod N\rangle = |a^2 y \pmod N\rangle.$$ Generalizing the idea and applying it to $y = 1$ we arrive at: $$U^m_{N,a}|1\rangle = |a^m \pmod N\rangle,$$ which is exactly the expression we wanted to obtain.

Codercise S.4.1 - Period finding and square roots

Codercise S.4.2 - Shor's algorithm

Period finding and nontrivial square roots

The full algorithm