# What makes quantum computers so good at computing prime factors?

One of the common claims about quantum computers is their ability to "break" conventional cryptography. This is because conventional cryptography is based on prime factors, something which is computationally expensive for conventional computers to calculate, but which is a supposedly trivial problem for a quantum computer.

What property of quantum computers makes them so capable of this task where conventional computers fail and how are qubits applied to the problem of calculating prime factors?


Quantum Computers are good at Discrete Fourier Transforms. There's a lot at play here that isn't captured by just "it's parallel" or "it's quick", so let's get into the blood of the beast.

The factoring problem is the following: Given a number $N = pq$ where $p,q$ are primes, how do you recover $p$ and $q$? One approach is to note the following:

If I look at a number $\modN{x}$, then either $x$ shares a common factor with $N$, or it doesn't.

If $x$ shares a common factor, and isn't a multiple of $N$ itself, then we can easily ask for what the common factors of $x$ and $N$ are (through the Euclidean algorithm for greatest common factors).

Now a not so obvious fact: the set of all $x$ that don't share a common factor with $N$ forms a multiplicative group $\on{mod} N$. What does that mean? You can look at the definition of a group in Wikipedia here. Let the group operation be multiplication to fill in the details, but all we really care about here is the following consequence of that theory which is: the sequence

$$\modN{x^0}, \quad\modN{x^1}, \quad\modN{x^2}, ...$$

is periodic, when $x,N$ don't share common factors (try $x = 2$, $N = 5$) to see it first hand as:

$$\newcommand{\mod}[1]{#1\,\operatorname{mod}\,5} \mod1 = 1,\quad \mod4 = 4,\quad \mod8 = 3,\quad \mod{16} = 1.$$

Now how many natural numbers $x$ less than $N$ don't share any common factors with $N$? That is answered by Euler's totient function, it's $(p-1)(q-1)$.

Lastly, tapping on the subject of group theory, the length of the repeating chains

$$\modN{x^0}, \quad\modN{x^1}, \quad\modN{x^2}, ...$$

divides that number $(p-1)(q-1)$. So if you know the period of sequences of powers of $x \mod N$ then you can start to put together a guess for what $(p-1)(q-1)$ is. Moreover, If you know what $(p-1)(q-1)$ is, and what $pq$ is (that's N don't forget!), then you have 2 equations with 2 unknowns, which can be solved through elementary algebra to separate $p,q$.

Where do quantum computers come in? The period finding. There's an operation called a Fourier transform, which takes a function $g$ written as a sum of periodic functions $a_1 e_1 + a_2 e_2 ...$ where $a_i$ are numbers, $e_i$ are periodic functions with period $p_i$ and maps it to a new function $\hat{f}$ such that $\hat{f}(p_i) = a_i$.

Computing the Fourier transform is usually introduced as an integral, but when you want to just apply it to an array of data (the Ith element of the array is $f(I)$) you can use this tool called a Discrete Fourier Transform which amounts to multiplying your "array" as if it were a vector, by a very big unitary matrix.

Emphasis on the word unitary: it's a really arbitrary property described here. But the key takeaway is the following:

In the world of physics, all operators obey the same general mathematical principle: unitarity.

So that means it's not unreasonable to replicate that DFT matrix operation as a quantum operator.

Now here is where it gets deep an $n$ Qubit Array can represent $2^n$ possible array elements (consult anywhere online for an explanation of that or drop a comment).

And similarly an $n$ Qubit quantum operator can act on that entire $2^n$ quantum space, and produce an answer that we can interpret.

See this Wikipedia article for more detail.

If we can do this Fourier transform on an exponentially large data set, using only $n$ Qubits, then we can find the period very quickly.

If we can find the period very quickly we can rapidly assemble an estimate for $(p-1)(q-1)$

If we can do that fast then given our knowledge of $N=pq$ we can take a stab at checking $p,q$.

That's whats going on here, at a very high level.

What makes quantum computers good at factoring large numbers is their ability to solve the period finding problem (and a mathematical fact that relates finding prime factors to period finding). That's basically Shor's algorithm in a nutshell. Yet it only begs the question what makes quantum computers good at period finding.

At the core of period finding is the ability to calculate a function's value over its entire domain (that is, for every conceivable input). This is called quantum parallelism. This in itself is not good enough, but together with interference (the ability to combine results from quantum parallelism in a certain way), it is.

I suppose this answer might be a bit of a cliff hanger: How does one use these abilities to actually factor? Find the answer to that at wikipedia on Shor's algorithm.

First of all, factoring can be done on a quantum computer (with usage of 'unitary' quantum gates) by means of Shor's algorithm.

An explanation that doesn't require advanced mathematics nor any advanced knowledge of physics is this blog post by Scott Aaronson, titled "Shor, I'll do it."

A brief summary of his ideas is the following:

First, we represent our quantum gates/qubits with clocks (using the 'complex numbers as arrows (i.e. elements of $\mathbb{R}^2$ with weird multiplication), representation')

Then, we note that a CS researcher has very irregular sleeping periods. To find this strange period, we use the clocks. Then, we note that this period finding can be used to factor integers (using a similar construction as in the randomized Pollard -$\rho$ algorithm)

Hence, our strange quantum clocks can help us factor efficiently!