3 ms·

This paper is claiming to make quantum factoring thousands of times cheaper than previously estimated (maybe even hundreds of thousands of times, depending on i

This paper is claiming to make quantum factoring thousands of times cheaper than previously estimated (maybe even hundreds of thousands of times, depending on if error correction is needed). I think it's wrong, but if it was correct it would have major implications for how fast quantum-safe cryptosystems had to be rolled out. Like, "a machine capable of running this could conceivably exist next year, instead of next decade" level of change in expectation. It would hit pretty damn hard.

i_am_jl 4y ago
I didn't intend to downplay the impact of such a development, only to highlight my skepticism regarding their claims (and the title provided in the post). Bruce Schneier sums it up better than I could: "One of the issues with the algorithm is that it relies on a recent factoring paper by Claus Schnorr. It’s a controversial paper; and despite the “this destroys the RSA cryptosystem” claim in the abstract, it does nothing of the sort. Schnorr’s algorithm works well with smaller moduli—around the same order as ones the Chinese group has tested—but falls apart at larger sizes. At this point, nobody understands why. The Chinese paper claims that their quantum techniques get around this limitation (I think that’s what’s behind Grimes’s comment) but don’t give any details—and they haven’t tested it with larger moduli." Scott Aaronson says "All told, this is one of the most actively misleading quantum computing papers I’ve seen in 25 years, and I’ve seen … many." https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html https://www.schneier.com/blog/archives/2023/01/breaking-rsa-... https://scottaaronson.blog/?p=6957 https://scottaaronson.blog/?p=6957