https://scottaaronson.blog/?p=6957 Shtetl-Optimized The Blog of Scott Aaronson If you take nothing else from this blog: quantum computers won't solve hard problems instantly by just trying all solutions in parallel. Also, next pandemic, let's approve the vaccines faster! --------------------------------------------------------------------- << Happy 40th Birthday Dana! Cargo Cult Quantum Factoring Just days after we celebrated my wife's 40th birthday, she came down with COVID, meaning she's been isolating and I've been spending almost all my time dealing with our kids. But if experience has taught me anything, it's that the quantum hype train never slows down. In the past 24 hours, at least four people have emailed to ask me about a new paper entitled "Factoring integers with sublinear resources on a superconducting quantum processor." Even the security expert Bruce Schneier, while skeptical, took the paper surprisingly seriously. The paper claims ... well, it's hard to pin down what it claims, but it's certainly given many people the impression that there's been a decisive advance on how to factor huge integers, and thereby break the RSA cryptosystem, using a near-term quantum computer. Not by using Shor's Algorithm, mind you, but by using the deceptively similarly named Schnorr's Algorithm. The latter is a classical algorithm based on lattices, which the authors then "enhance" using the heuristic quantum optimization method called QAOA. For those who don't care to read further, here is my 3-word review: No. Just No. And here's my slightly longer review: Schnorr [?] Shor. Yes, even when Schnorr's algorithm is dubiously "enhanced" using QAOA--a quantum algorithm that, incredibly, for all the hundreds of papers written about it, has not yet been convincingly argued to yield any speedup for any problem whatsoever (besides, as it were, the problem of reproducing its own pattern of errors) (one possible recent exception from Sami Boulebnane and Ashley Montanaro). In the new paper, the authors spend page after page saying-without-saying that it might soon become possible to break RSA-2048, using a NISQ (i.e., non-fault-tolerant) quantum computer. They do so via two time-tested strategems: 1. the detailed exploration of irrelevancies (mostly, optimization of the number of qubits, while ignoring the number of gates), and 2. complete silence about the one crucial point. Then, finally, they come clean about the one crucial point in a single sentence of the Conclusion section: It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA. "Unclear" is an understatement here. It seems to me that a miracle would be required for the approach here to yield any benefit at all, compared to just running the classical Schnorr's algorithm on your laptop. And if the latter were able to break RSA, it would've already done so. All told, this is one of the most actively misleading quantum computing papers I've seen in 25 years, and I've seen ... many. Having said that, this actually isn't the first time I've encountered the strange idea that the exponential quantum speedup for factoring integers, which we know about from Shor's algorithm, should somehow "rub off" onto quantum optimization heuristics that embody none of the actual insights of Shor's algorithm, as if by sympathetic magic. Since this idea needs a name, I'd hereby like to propose Cargo Cult Quantum Factoring. And with that, I feel I've adequately discharged my duties here to sanity and truth. If I'm slow to answer comments, it'll be because I'm dealing with two screaming kids. Email, RSSEmail, RSS Follow This entry was posted on Wednesday, January 4th, 2023 at 11:06 pm and is filed under Complexity, Quantum, Rage Against Doofosity, Speaking Truth to Parallelism. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site. 17 Responses to "Cargo Cult Quantum Factoring" 1. Jud Says: Comment #1 January 4th, 2023 at 11:23 pm As one of the four who inquired, grateful thanks (especially when dealing with screaming children!). I am not surprised that there is, well, no surprise. Quantum computing potentially breaking RSA seems to be one of those scientific subjects about which people tend to lose their skepticism prematurely. A belated Happy Birthday to your wife, and may her recovery experience a quantum speedup! 2. Curious Says: Comment #2 January 4th, 2023 at 11:44 pm I looked at the paper. Schnorr's algorithm seems to be about sieving and using Babai's algorithm for CVP. I remember Shor is still attempting to make progress on CVP and SVP using quantum algorithms (for example the retracted claim in https://arxiv.org/ abs/1611.06999). If there is a way using Quantum methods without QFFT it is hard to believe. Having said that, people are trying to make progress on CVP and SVP (for example https:// eprint.iacr.org/2022/233.pdf). Progress on CVP alone would be an important progress in itself. Is there anything new in the new paper https://arxiv.org/pdf/2212.12372.pdf for CVP and SVP improving Babai before looking at factoring itself? If there is nothing new to CVP and SVP then using plain vanilla Babai to lower resources might have been already seen by the community. If not the authors are indeed lucky if the algorithm works out (being probably the first to have looked at Schnorr's algorithm from a quantum angle (is there any such related study before this on a quantum Schnorr algorithm?)). 3. Aspect Says: Comment #3 January 5th, 2023 at 2:16 am Was expecting you to also bring up the paper by Pirnay et al. on quantum advantage for combinatorial optimization problems since factoring is also involved in that one. I'm guessing others have already asked you to comment on it (sorry if I'm annoying in that case!). Mario Szegedy already published a criticism on Arxiv but I was curious if you have anything to add to the discussion 4. Shaun Griffith Says: Comment #4 January 5th, 2023 at 4:24 am Follow is broken for me? I think it's important to have these "breakthrough" announcements thoroughly critiqued and analyzed, lest someone with much enthusiasm, but without the necessary background, set off to waste our time and other resources for naught. 5. Olivier Ezratty Says: Comment #5 January 5th, 2023 at 7:15 am Nice points Scott. QAOA doesn't scale. Case closed. Found some other clue that may be relevant or not. Hardware resources wise, the paper mentions a need to execute 1139 to 1490 gate cycles, without indeed detailing the number of gates and gate types. That would require qubit fidelities in the 5-nines range minimum, thus mandating some QEC with physical qubits having 99.9% fidelities, then qubit # overhead >x100 with some fancy surface code. Thus, invalidating their 372 qubits sizing. And IBM Osprey doesn't yet have publicized qubit fidelities, but we can expect these to be way below 99% (1Q, 2Q, readout). So, forget NISQ to factorize large integers! Looks like the paper is designed to generate some FUD and leverage Brandolini's law. 6. Ashley Montanaro Says: Comment #6 January 5th, 2023 at 8:37 am Hi Scott, No argument from me about the issue with applying QAOA to factoring, but regarding your point that QAOA "has not yet been convincingly argued to yield any speedup for any problem whatsoever" - you might find my recent paper https://arxiv.org/ abs/2208.06909 with Sami Boulebnane (one of the hundreds!) of interest. We consider applying QAOA to random k-SAT and develop theoretical and numerical arguments that the scaling of QAOA will outperform leading classical algorithms. Whether these arguments are convincing is of course up to the reader 7. Scott Says: Comment #7 January 5th, 2023 at 9:06 am Ashley #6: Thanks; I hadn't seen that! Just added a link to the post. 8. fred Says: Comment #8 January 5th, 2023 at 11:04 am Without reading any paper, the principle of minimization of hilarious coincidences tells us it's indeed very unlikely that something called Schnorr would beat something called Shor. 9. Nova Spivack Says: Comment #9 January 5th, 2023 at 11:06 am So I think what you are really saying in a nutshell is that this paper is a Schnorr? 10. Scott Says: Comment #10 January 5th, 2023 at 11:15 am fred #8, Nova #9: You know the Simpsons episode where Homer and Marge take the kids to "Diz-Nee Land, Not Affiliated With Disneyland"? This is Schnorr's Algorithm, not affiliated with Shor's Algorithm! 11. JimV Says: Comment #11 January 5th, 2023 at 11:17 am Sounds like the kids need an uncle, to play boards games with, give them horsey-back rides (not piggy-back! I'm not a piggy!), take them to the park, throw a frisbee, et cetera. I'm a bit too old to volunteer at this point, though. I've been watching the sports and news personalities deal with the Damar Hamlin injury for a couple days now, and I haven't heard anyone say this: it's time for safe helmets. Take the cushioning head gear that sparring boxers wear, paint it with the the team colors and logo, and add a facemask. Then Tua Tagovailoa won't get a concussion when the back of his head hits the turf, and running backs who run into safeties head-first won't injure them. (No need to take this out of moderation, but I had to say it somewhere.) 12. OC Says: Comment #12 January 5th, 2023 at 11:18 am I'm sorry, but I'm having trouble believing there's something called "Schnorr's Algorithm". Does it involve begging an oracle to give the answer? 13. Itan Barmes Says: Comment #13 January 5th, 2023 at 11:20 am I am really curious where they sent the manuscript. When I was in academia I've had the "privilege" to review this type of articles. It is amazing to me how much flawed logic you can have in one paper. The funniest part of the paper is the very last sentence (page 32!) which states: "However, the touch-size is an ideal basic situation, the QAOA usually works more than one layer and deeper circuit required. Besides, the quantum speedup is unknown, it is still a long way to break RSA quantumly". They basically trash their own work! 14. Pooty Says: Comment #14 January 5th, 2023 at 12:37 pm Shor's algorithm and Schnorr's algorithm? What is this, Borscht Belt comedy? 15. Tu Says: Comment #15 January 5th, 2023 at 1:39 pm Thanks, Scott. I saw a headline, came straight here, and appreciate the time you saved me! Enjoy your time with the kids. 16. Scott Says: Comment #16 January 5th, 2023 at 1:51 pm Itan Barmes #13: While I can't reveal my sources, I have it on good authority that the paper was submitted to a journal, and already received the following review from a reviewer who shall remain anonymous. This paper claims a major advance on factoring integers using near-term, non-error-corrected quantum computers. It does so NOT using the famous Shor's algorithm, but instead using the superficially similar-sounding Schnorr's algorithm -- a known classical algorithm based on lattices. The central idea is to speed up Schnorr's algorithm using QAOA, a known quantum heuristic optimization algorithm. The fundamental, and in my opinion fatal, problem with the paper, is that no evidence or argument is ever provided that the use of QAOA provides any benefit whatsoever in speeding up Schnorr's algorithm -- either now or in the future. Instead, the paper spends pages on optimizing the number of *qubits,* something that's manifestly irrelevant unless one can also factor using a reasonable number of *gates.* The lack of any evidence for a quantum speedup -- i.e., the issue that seems to kill the entire approach -- is only acknowledged obliquely in a single sentence in the Conclusion section. Even if the paper doesn't contain a single false sentence (which is possible, although I didn't check!), I view the way it's written as actively misleading. The paper seems designed to create the public impression that Schnorr+QAOA has been shown to be a viable approach to breaking RSA with near-term quantum computers, when nothing of the kind is true, and when the authors themselves seem to be aware of the lack of any QAOA-powered speedup for this sort of problem. For these reasons, I recommend summary rejection. If I'm right about the intent to mislead, then I can't imagine any revision of the paper that would cause me to support its acceptance in any journal ever. 17. Encryption: RSA destroyed? experts doubt - DigLogs Says: Comment #17 January 5th, 2023 at 3:13 pm [...] Bruce Schneier doubts whether the new method can actually defeat RSA. Much more severe in the court Scott Aaronson, expert on quantum computing: The paper is one of the most misleading he has ever seen and makes claims that it can by no means [...] Leave a Reply You can use rich HTML in comments! You can also use basic TeX, by enclosing it within $$ $$ for displayed equations or \( \) for inline equations. Comment Policies: 1. All comments are placed in moderation and reviewed prior to appearing. 2. You'll also be sent a verification email to the email address you provided. YOU MUST CLICK THE LINK IN YOUR VERIFICATION EMAIL BEFORE YOUR COMMENT CAN APPEAR. WHY IS THIS BOLD, UNDERLINED, ALL-CAPS, AND IN RED? BECAUSE PEOPLE ARE STILL FORGETTING TO DO IT. 3. This comment section is not a free speech zone. It's my, Scott Aaronson's, virtual living room. Commenters are expected not to say anything they wouldn't say in my actual living room. This means: No trolling. No ad-hominems against me or others. No presumptuous requests (e.g. to respond to a long paper or article). No conspiracy theories. No patronizing me. Comments violating these policies may be left in moderation with no explanation or apology. 4. Whenever I'm in doubt, I'll forward comments to Shtetl-Optimized Committee of Guardians, and respect SOCG's judgments on whether those comments should appear. 5. I sometimes accidentally miss perfectly reasonable comments in the moderation queue, or they get caught in the spam filter. If you feel this may have been the case with your comment, shoot me an email. [ ] Name (required) [ ] Mail (will not be published) (required) [ ] Website [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [Submit Comment] [ ] [ ] [ ] [ ] [ ] [ ] [ ] D[ ] --------------------------------------------------------------------- Shtetl-Optimized is proudly powered by WordPress Entries (RSS) and Comments (RSS).