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?

The short answer

$\newcommand{\modN}[1]{#1\,\operatorname{mod}\,N}\newcommand{\on}[1]{\operatorname{#1}}$Quantum Computers are able to run subroutines of an algorithm for factoring, exponentially faster than any known classical counterpart. This doesn't mean classical computers CAN'T do it fast too, we just don't know as of today a way for classical algorithms to run as efficient as quantum algorithms

The long answer

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.

• I tried to keep this short and not filled with too much rigor that may bore a reader. If you want to open something up, ask questions, get more detail, request a proof, or additional sources, feel free to drop in comments – frogeyedpeas Mar 28 '18 at 19:13
• Also PLEASE comment, if you encounter a word that you don't understand, that'll help other readers at the same level as you figure out what is going on – frogeyedpeas Mar 28 '18 at 19:16
• Good lord, I think I understood all of that. If I am correct in my understanding, in essence an array of Qubits ability to perform a (Quantum) Fourier transform over a very large set of data is what makes the process so efficient. – Paul Turner Mar 28 '18 at 19:56
• Yes, or to be very precise: a Quantum Computers ability to perform Fourier Transforms on Qubits which represent massive data sets, is what makes the process efficient. – frogeyedpeas Mar 28 '18 at 19:58
• @frogeyedpeas note that you can use markdown to add links to words, like this one, using the syntax [text](https://en.wikipedia.org/wiki/Integer_factorization). It may improve the readability of the answer – glS Mar 29 '18 at 17:26

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!

There are two main algorithms available for quantum computing, and they solve different problems. Grover's algorithm is good at sorting phone books and other sort related math problems. (Traveling Salesman, Wedding Seat planner, NP-complete problems, etc.) Shor's algorithm uses a different property of physics, and solves NP-incomplete problems such as factoring and discrete logarithms, which is the foundation of current public-private cryptography. Knowing these are two different problem sets that can be solved by two different kinds of hardware is important.

Quantum Computing often discusses quantum state, entanglement and superposition, and other tricks to function. These things are necessary components to the engineering of quantum computers, but the core realization in my mind is understanding what is different between traditional silicon computing and quantum computing.

Silicon computing has only two instructions: addition and comparison of two numbers. Subtraction is performed by taking a two's complement, followed by addition. Quantum computing is fundamentally different, because physics itself solves the question loaded into the machine. There are caveats: the entire question must be loaded into the machine, the question needs to be encoded, solved and read before heat interferes with the entanglement, the reading of the resulting quantum state is error prone and difficult, the answer could be randomly incorrect. Instead of addition and comparison, quantum computers uses physics to auto-magically solve the math question. I refer to it as the "magic 8 ball" of computing because it is random, error prone, and something of a black box for calculation.

The actual math problem involved for factoring numbers and solving discrete logs is the "Quantum Fourier Transform" one of many quantum algorithms.

• This answer is incorrect and highly misleading. Shor's algorithm is not believed to be able to solve any NP-complete problems. Neither factoring nor discrete logarithms is believed to be NP-complete. This is a persistent misconception in popular accounts. – tparker Mar 28 '18 at 17:10
• Could you comment on: jstage.jst.go.jp/article/iis/19/2/19_IIS190202/_pdf and arxiv.org/pdf/quant-ph/0212002.pdf since this sort of question is beyond most wikipedia articles? – Ian Smith Mar 28 '18 at 17:46
• tparker, I am very interested in your review of the papers I cited that support my claim of NP-completeness. If the papers are incorrect or I am misinterpreting them completely, then it changes my opinion on what the next 20 years of computing looks like. – Ian Smith Mar 29 '18 at 22:31
• You are misinterpreting them completely. Neither of these papers claims that factoring or discrete log are NP-complete. The first one specifically says that the possibility that "either [discrete log] or [factoring] is complete for NP ... is believed to be an unlikely event." It says that they reduce to an NP-complete set, which is a completely different statement and true by definition for any problem in NP. I don't see anything in the second paper that you could have possibly construed as a claim that factoring or discrete log are NP-complete. – tparker Mar 30 '18 at 1:27
• I thought the QFT was NP-complete, but apparently not. The classification of NP-intermediate wasn't well documented last time I looked into this at length. The second paper described more efficient quantum circuits which can be used to solve NP-complete problems. If there exists an NP-incomplete algorithm (QFT) which is able to solve NP-complete problems, doesn't that make all NP-complete problems no longer NP-hard? If NP-complete is not "as hard as expected" that would change the QFT subset of NP-incomplete to be "NP-complete, by reducing NP-complete to QFT." – Ian Smith Apr 3 '18 at 18:07