A Quick Post on Factoring

Edit: \( \LaTeX \) is now working

Note. I was going to make a proper blog post on this (I still may at some point. Also, my blog is not ready, for instance, LaTeX is not working).

Recently, I was visiting IIT-Kanpur and I was surprised by them not taking Shor’s factoring algorithm as a sign of quantum advantage (I swore to never use the term “quantum supremacy”). With this post I hope to convey some insight into the arguments of both sides.

Me: Factoring is hard for classical computers and since there exists an efficient quantum algorithm for factoring, quantum computers can solve more problems!

The audience at IIT-K: Well, there is no proof of that! (There isn’t!) Moreover, an efficient factoring algorithm for quantum computers increases the likelihood of an efficient classical algorithm for factoring (I believe that it does!).

Adding to the pain, an unpublished result of Mosca says that there exists an exact quantum algorithm for factoring! And under the assumption that \( \textrm{EQP} \neq \textrm{BQP} \) (I will explain this in a another post but for now take my word that this is very different from the widely held conjuncture that \( \textrm{P} = \textrm{BPP} \)), Factoring is one of the easier problems a quantum computer can solve!

So, why do I think factoring is hard?
Because in the black box setting, PeriodFinding is provably hard for classical computers but easy for quantum computers (Shor’s actual result!). What does this have to do with factoring? And what is a black box? (Is it anything like the orange boxes?)

But, first, PeriodFinding is the problem of finding the period of a function that is promised to be periodic (duh!). By a simple number-theoretic reduction you can use an efficient algorithm for period finding to solve factoring (see any one of the \( 10^{10^{10}} \) articles on Shor’s algorithm online).

So does this implication go the other way (ie does an efficient algorithm for factoring imply an efficient algorithm for period finding)? We do not know. But I trust black boxes (and orange boxes!).

Actually, I believe that quantum computers are strictly more powerful than classical computers?
Why? you ask. We need to go all the way back to the dark days of 1993 when Quantum Computing was solely done by physicists and papers on the topic had phrases like “quantum parallelism”, when a sage and his grad student did the first complexity theoretic study of quantum computing. Bernstein and Vazirani showed that quantum computers were better than classical probabilistic computers in the black box setting by giving an efficient quantum algorithm for RecursiveFourierSampling (which btw until recently was one of the top candidates for showing \( \textrm{BQP} \not\subseteq \textrm{PH} \) (Which is still an open problem, if anyone is interested.) which is not efficiently computable classically. Simon then using similar (but not too similar!) techniques proved that a quantum computer can also efficiently solve Simon’s problem (invariance under an XOR mask, or PeriodFinding but in \( \mathbb{Z}/2\mathbb{Z} \)). Shor then extended that to \( \mathbb{Z}/n\mathbb{Z} \) to get an efficient quantum algorithm for PeriodFinding and hence Factoring. In the same paper, Shor also gave an efficient quantum algorithm for DiscreteLogarithm which is another problem which is conjectured to be hard for classical computer and on whose presumed hardness many cryptosystems are proven safe!

Also, the guys at IIT-K are not crazy. Recently (I mean in 2002, it is still more than a decade “recent” than quantum computing!) a group of three mathematicians (Agrawal, Kayal and Saxena; two of them were undergrads at the time!! #goals) at IIT-K showed that Primality was in \( \textrm{P} \) ie there exists a deterministic polynomial time algorithm for checking if a number is prime. So, that’s the dream. But the case with Primality is very different from that with Factoring. For instance, we do not yet have a \( \textrm{BPP} \) algorithm for Factoring but we did for Primality. But again, that was not trivial and required a lot of number theory, but one could argue that a proportional amount of effort has also been invested into doing that for Factoring. Trivially, if you assume some far-reaching extension of the Riemann hypothesis (like uniformity of primes) you can get an efficient bounded-error algorithm for factoring but at that point you might as well appeal to the Anthropic principle and say that if an efficient primality-testing algorithm existed then we would have already found it! So, yeah this research program is prolly going to take a while. And for the computational number theorists reading this, I believe in you!

Regardless, I do not have too much interest in this debate. An efficient classical algorithm for Factoring would merely almost all of current cryptography but theoretically it is still a very easy problem, it is in \( \textrm{UP} \cap \textrm{coUP} \) (the proof without AKS’s primality algorithm is very hard, but with it, is just four words: FUNDAMENTAL THEOREM OF ARITHMETIC!) On a side note, cryptographic assumptions are usually significantly stronger than what we assume in complexity (and people say we are too artificial!), for instance, \( \textrm{P} \neq \textrm{NP} \) cannot give you a public key cryptosystem.

If you cared, (as I wrote on the board during my talk,) my other beliefs are as follows:
\( \mathrm{BPP} = \mathrm{P} \) (See Nisan-Widgerson generator)
\( {\rm NP} \neq {\rm P} \) (See anything Aaronson ever wrote)
\( {\rm BQP} \neq {\rm BPP} \) (If it were untrue then Quantum Mechanics is very wrong)

A fun read regarding some material here is Scott Aaronson’s The Prime Facts: From Euclid to AKS.