Shor's Algorithm - RPIQuantumComputing/QuantumCircuits GitHub Wiki

Shor's Algorithm Shor's Algorithm was made famous for its ability to crack RSA encryption and quickly became the poster child of Quantum Computing. Shor's Algorithm boils down to a period-finding algorithm based on a variety of long-established theorems, and as a side effect can also factor large multiples of primes. The majority of the algorithm can be realized using a classical computer.

Background: Suppose two people, Bob and Alice, want to have a conversation. A third person, Charlie, wants to listen in on their conversation. Bob and Alice don't want Charlie knowing what they're talking about, so we want to encrypt the data sent by Bob to Alice and vice versa such that both Bob and Alice can easy decrypt the data but Charlie cannot. This gets into public keys, private keys, and math covered in networking courses, so we won't go over all of that here. The gist of it is that you can multiply two large primes together to encrypt your data, and if you don't know at least one factor of the multiple of primes then it will take a very, very long time to brute force the factors out and thus decrypt the data.

The Solution: Note that quantum computation can utilize a quantum superposition to calculate many answers to a problem all at once for a single given input. You will only get one of the answers out at the end, randomly, with different probabilities for each outcome. The key to this is to calculate all the possible answers at once while also cleverly arranging them such that all the wrong answers destructively interfere with each other, leading to the answer you get out likely being the correct one.

Let $N = s * t$, where $N$ is the large multiple of primes, and $s$ and $t$ are prime factors of that multiple. We know $N$, but we do not know $s$ or $t$. We need only to find $s$ in order to also have $t$, since $t = \frac{N}{s}$.

For any pair of numbers $A$, $B$ that don't share any common factors, if you multiply $A*A*A*A*...$ enough times, you will eventually arrive at $m*B + 1$, which is a whole number multiple of $B$, plus $1$. i.e. eventually $A^p = m*B + 1$ for some $p$. So we have that $g^p = m*N + 1$. We can manipulate this to get $(g^{p/2} + 1)(g^{p/2} - 1) = m*N$.

Shor's Algorithm is the process of taking any guess $g$ of what $s$ could be and transforming it into a $g^{p/2} \pm 1$ that probably shares factors with $N$, where $p$ is some integer. So we make a quantum circuit that takes a number | $x$ > as input and computes $g^x$. It then sets another qubit to $g^x$ to give you | $x$ , $g^x$ >. We then create another quantum circuit that takes | $x$ , $g^x$ > and calculates how much larger than $m*N$ $g^x$ is, where $m$ is some integer, i.e. | $x$ , $+r$ >, where $+r = g^x mod(m*N)$.

However, we run into a problem. We can't just measure this superposition to find the answer, as it would give you a random one. If you tried to do this to find the factors of the big multiple of primes then you would be no better off in terms of time complexity than randomly guessing factors with a classical computer. So we need to make all the non- $p$ answers destructively interfere with each other such that the most likely output is | $p$ , $+1$ >.

This is possible due to another mathematical observation which is arguably the most important part of the algorithm. If we knew what $p$ was, we could get a $g^p = m * N + 1$. If instead we feed it a random number for $p$, it's probably going to give you $m_1 * N + b$, where $b$ isn't $1$. However, if you take $g^{a+p}$ for some integer $a$, that will return $m_2 * N + b$, where $b$ is the same value as the previous $b$. If you take $g^{a+2p}$, that will return $m_3 * N + b$, where $b$ is again the same $b$. Only the $m$ values here are different between iterations. This pattern holds for any power of $g$. Thus we know that $p$ has a repeating property. A cyclical one. Periodic, even. We can now take advantage of this to find $p$.

If we take our superposition of | $x$ , $+r$ > and only measure the remainder, we will get one of those $+r$ values out at random. What exactly it returns doesn't matter, but the important part is that we are left with a superposition of just $g^{a+np}$ values that will give you the same remainder. This is because quantum computers will take any non-injective function that you superpose and measure (i.e. a function where an element of the range has multiple elements from the domain that map to it) and leave your superposition as a superposition of all the two-qubit pairs of numbers and that $+r$ value.

We can leverage this fact to get a superposition of all the powers of $g$ that are $p$ apart from each other. These numbers have a frequency of $\frac{1}{p}$, so all we have to do now is find that.

Note that generally speaking, Fourier Transforms are the best tool to find the frequency of a function. Thus all we have to do to find $\frac{1}{p}$ is define a new type of Fourier Transform that's compatible with Quantum Computers and superpositions, the Quantum Fourier Transform (QFT).

Given a vector $(x_0, x_1, ... x_{N-1}) \in {\mathbb{C}}^N$, the Quantum Fourier Transform maps that vector to another vector $(y_0, y_1, ... y_{N-1}) \in {\mathbb{C}}^N$ according to the following formula: $${\Large y_k = \frac{1}{\sqrt{N}} \displaystyle \sum_{n=0}^{N-1} x_n e^{\frac{-2 \pi i n k}{N}} }$$ where $k = 0, 1, 2, ... N-1$.

If you input a single number into the QFT, e.g. | $1$ >, it will return a superposition of all the number numbers in your universal set of choice where each number is weighted by different scaling coefficients, and the weights look roughly like the values of a sine wave that has the frequency of the number we input. When you input a superposition of numbers, you get a superposition of superpositions and their sine waves, which either add together or cancel out. So if you put in a superposition of numbers that are all separated by $p$, all the sine waves destructively interfere such that you get out the single quantum state representing | $\frac{1}{p}$ >. Now all you have to do is invert that, and you have your answer.

If $p$ is an even integer, then we have $g^{p/2} \pm 1$, which are fairly good guesses for the factors of $N$. However, we could run into some pitfalls here:

1. If one of $g^{p/2} \pm 1$ is an exact multiple of $N$, then the other will be some factor of $m$. This is useless information, since we are left exactly where we started.
2. If $p$ is odd, then $\frac{p}{2}$ will not return an integer, and $g^{p/2}$ won't be an integer either, rendering the entire result useless, since prime numbers cannot be non-integers.

If either of these cases takes place, then we simply start the entire algorithm from scratch with a different guess. If we do manage to get a valid value out of this process (which happens 37.5% of the time, giving you a 99% chance to reach this point in fewer than 10 guesses), then we are guaranteed that the value shares at least one factor with $N$. If we somehow manage to get out $s$ exactly, then we can easily find $t$. Alternatively, if we instead get some number that shares one or more factors with $N$ but is not itself a factor of $N$, then we can use Euclid's Algorithm to find $s$ and $t$.

To apply Euclid's Algorithm, we take $N mod(s') = r_1$, where $s'$ is the number we found above. Then we take $s' mod(r_1) = r_2$. Then we take $r_1 mod(r_2) = r_3$, and we repeat this process until $r_{n-2} mod(r_{n-1}) = r_n = 0$. The factor $s$ of $N$ is $r_{n-1}$.

Now that we have $s$, we can easily find $t$ by $t = \frac{N}{s}$, and our problem is solved. The entirety of Shor's Algorithm takes logarithmic time, since the number of computations necessary to find a factor of $N$ is logarithmic in relation to the size of $N$.