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?

user1271772 No more free time
  • 13,847
  • 2
  • 25
  • 71
Martin Vesely
  • 13,891
  • 4
  • 28
  • 65
  • wait, are they claiming this algorithm solves factoring in polynomial time? If true that would be a huge deal, regardless of anything quantum, but I *highly* doubt that is the case (this came out more than a week ago it seems; if someone solved factoring in polynomial time, I think we all would have heard it by now). Comments on https://www.reddit.com/r/math/comments/lwf0t5/fast_factoring_integers_by_svp_algorithms/ also seem to be of this opinion. If it's only a polynomial speed-up, it might be a big deal for classical computers, but it can't be faster than Shor's algorithm. – glS Mar 09 '21 at 16:46
  • 3
    well, nevermind, the paper claims in the abstract, and I quote, "This destroys the RSA cryptosystem". This is kind of hilarious. Anyway, people seem to think there is a fatal flow in the proof. See Aaronson's comment at the end of his post here https://www.scottaaronson.com/blog/?p=5359, pointing to this twitter thread https://twitter.com/inf_0_/status/1367376526300172288 – glS Mar 09 '21 at 16:55
  • 4
    See also discussion on Hacker News which links to Schneier's blog which links to a discussion on Crypto Stack Exchange. The top answer there points out that there is a simple way to prove a breakthrough in factoring algorithms using any of the factoring challenges available online. – Adam Zalcman Mar 09 '21 at 18:23
  • 1
    @Martin "Proving" optimality would have to be under some strong assumption - factoring could well be in P, and it would not even have any severe consequences like P=NP (afaik). – Norbert Schuch Mar 12 '21 at 22:07
  • 1
    @Adam "there is a simple way" -- I disagree (no statement on the paper intended): What if you find a poly-time algorithm but the exponent or prefactor is prohibitive? – Norbert Schuch Mar 12 '21 at 22:08
  • 1
    @NorbertSchuch Good point. The factoring challenges have limitations. That said, this works both ways: failure to meet any factoring challenge still suggests that there are probably some constraints on the applicability of a new method in practice (even though the method may still constitute a breakthrough). – Adam Zalcman Mar 13 '21 at 00:46
  • 1
    @Adam Sure, but the same applies to Shor's algorithm. -- And the other thing is that (so I have been told) the discovery of a poly-time algorithm, even if it was yet unpractical, often came with new insights which subsequently allowed for the development of truly efficient algorithms. – Norbert Schuch Mar 13 '21 at 12:39
  • 1
    @NorbertSchuch Yes, it does and indeed nobody is using Shor's algorithm in practice. Regarding new insights: I agree. Rather famously, this happened to the AKS primality testing where the initial complexity bound was improved from $O(n^{12})$ to $O(n^6)$. A less dramatic improvement occurred for the maximum matching problem where Edmond's original $O(ev^2)$ algorithm surprised people that a polynomial solution exists and was later improved to $O(e\sqrt{v})$. – Adam Zalcman Mar 13 '21 at 16:52

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).

user1271772 No more free time
  • 13,847
  • 2
  • 25
  • 71