9

In the article Fast Factoring Integers by SVP Algorithms the author claims that he discovered classical algorithm for factoring integers in polynomial time. The Quantum Report mentioned here that it has similar performance to Shor algorithm which is often considered to ignite interest in quantum computers.

Of course, the new classical algorithm has to be examined closely before it is confirmed that it is really so fast as claimed.

However, I would like to know if there are other quantum algorithms besides Shor and quantum binary optimization based.

Has it been proven that Shor algorithm is optimal or could there be another even faster quantum algorithms for integers factoring?

Martin Vesely
  • 15,244
  • 4
  • 32
  • 75

1 Answers1

6

Shor's algorithm is often quoted as having a cost of $\mathcal{O}(\log^3 n)$ quantum operations, though it's actually a bit smaller than that: $\mathcal{O}\left((\log n)^{2} (\log \log n) (\log \log \log n) \right)$, but since $\log \log n < \log n$ we know that the "verbose" cost is less than the often quoted cost of $\mathcal{O}(\log^3 n)$.

There's no proof that $\mathcal{O}\left((\log n)^{2} (\log \log n) (\log \log \log n) \right)$ is optimal, and I wouldn't be surprised if someone came up with a version that costs only $\mathcal{O}\left((\log n)^{2} (\log \log n) (\log \log \log n \log n) \right)$ (there's one extra $\log n$).

However I find myself reminded right now of Shalev Ben-David's talk at the Aspen conference for which I was the session chair, in 2016 when he was still a PhD student of Scott Aaronson. He had a slide that said "real computer scientists only care about exponential speed-ups" (with emphasis on "real" in the original version too). That might be a bit of an exaggeration, but a slightly less strong version of that statement will lead you to my main point here, which is that no one has yet been able to reduce the power from $\mathcal{O}(\log^3 n)$ to $\mathcal{O}(\log^{\color{red}{2}} n)$. In that sense, Shor's algorithm is still the most "efficient" in terms of the power of $\log n$ appearing in the number of quantum gates required.

There's plenty of work that's been done on reducing the exact number of gates (here the constant under the "Big Oh" now matters), and also plenty of work done on reducing the number of total qubits needed.

One somewhat recent paper title that comes to my mind is Craig Gidney's "Factoring with $n+2$ clean qubits and $n-1$ dirty qubits" and "How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits" (also by Craig Gidney).