8
$\begingroup$

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?

$\endgroup$
8
  • 3
    $\begingroup$ 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 scottaaronson.com/blog/?p=5359, pointing to this twitter thread twitter.com/inf_0_/status/1367376526300172288 $\endgroup$
    – glS
    Mar 9, 2021 at 16:55
  • 4
    $\begingroup$ 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. $\endgroup$ Mar 9, 2021 at 18:23
  • 1
    $\begingroup$ @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). $\endgroup$ Mar 12, 2021 at 22:07
  • 1
    $\begingroup$ @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? $\endgroup$ Mar 12, 2021 at 22:08
  • 1
    $\begingroup$ @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). $\endgroup$ Mar 13, 2021 at 0:46

1 Answer 1

6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Is the quasiquadratic complexity valid for discrete log as well? $\endgroup$
    – Turbo
    Jul 23 at 22:47
  • $\begingroup$ I don't know what you're asking. $\endgroup$ Jul 24 at 3:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.