# 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?

• @Discretelizard If you have an answer, please post it in the 'answer' section below. And please remember that links sending uses elsewhere to find what they are searching for are not considered an "answer" in the context of this site. Users here will work hard to curate this collection of knowledge, so when someone finally finds this site through search, the last thing we want to do is send them elsewhere to find that information. Thank you. – Robert Cartaino Mar 28 '18 at 14:38
• @RobertCartaino So you claim that I both posted an answer and not an answer? Nevertheless, I was waiting for such a request, as I had doubts whether this is an answer. I will make an attempt to summarise the given source. – Discrete lizard Mar 28 '18 at 15:20
• @RobertCartaino Do you have a source on meta for your claim that "links sending uses elsewhere to find what they are searching for are not considered an 'answer' in the context of this site"? Personally, when I find this site through search, a good detailed blog post is exactly what I want, rather than an answer which has been artificially constrained to fit the SE requirements. – tparker Mar 28 '18 at 15:29
• @Discretelizard Yes, answering a question in comments is not permitted... with a forewarning not to repeat that particular style answer in your post (i.e. links are not considered an answer in the context of this site). – Robert Cartaino Mar 28 '18 at 15:31
• @tparker If I find a link, I will drop it here, but the proof is largely circular. We designed this system to be a final-destination curation of knowledge. It's not a Google-esque search engine nor a list of links — we’re a bit like Wikipedia in that respect. Folks often flag links as "not an answer" because links can break, but if I were to search Wikipedia (or any encyclopedic compilation) for information about the early life of “Ronald Regan” (for example), the system would not would not permit an entry like: “Go read his autobiography <link>.” It’s not a valid use case for that site. – Robert Cartaino Mar 28 '18 at 18:20


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