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.

68 Responses to “Cargo Cult Quantum Factoring”

  1. Jud Says:

    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:

    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:

    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:

    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:

    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:

    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:

    Ashley #6: Thanks; I hadn’t seen that! Just added a link to the post.

  8. fred Says:

    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:

    So I think what you are really saying in a nutshell is that this paper is a Schnorr?

  10. Scott Says:

    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:

    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:

    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:

    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:

    Shor’s algorithm and Schnorr’s algorithm? What is this, Borscht Belt comedy?

  15. Tu Says:

    Thanks, Scott. I saw a headline, came straight here, and appreciate the time you saved me!

    Enjoy your time with the kids.

  16. Sigmund Waite Says:

    Scott!

    Ah, quantum mechanics!!

    Quantum computing sounds like an interesting subject, and I’ve tried to investigate but have encountered two problems:

    (1) The descriptions of how quantum computing would work, to me, make no sense.

    (2) Before trying to understand quantum computing, I want to understand just the basics of quantum mechanics, but the descriptions I’ve been able to find for quantum mechanics make little to no sense.

    Here the lack of sense is (A) the math and (B) the applications of the math to the physics and the physics itself.

    For (A) the math:

    (i) For the wave function, it is not clear just what the range and domain of the functions are.

    (ii) There is a claim that the wave functions form a Hilbert space, but the definition of Hilbert space I got from W. Rudin’s Real and Complex Analysis is a complete inner product space where complete means that every Cauchy convergent sequence converges. But the wave functions are also said to be differentiable, and easily enough can have a Cauchy convergent sequence converge to a function that is not differentiable or even continuous. To me, the claim that the wave functions form a Hilbert space needs a proof.

    (iii) The wave functions are said to be differentiable, but in the physics treatments I can’t find a clear and appropriate definition of differentiable function of several variables they are using. Merely that partial derivatives along three spacial coordinates and one time coordinate is not sufficient for a useful definition of differentiability but is about all I get from physics books.

    (iv) In the physics, it is not clear just what integral is being used, Riemann on a compact set, Riemann on an unbounded set, Lebesgue, Schwartz distributions.

    (vi) I’d like to see a very careful argument that momentum is the Fourier transform of the wave function — very careful.

    (vii) Okay, the absolute value of the wave function is real valued, non-negative, and differentiable. So, suppose it has a finite Lebesgue integral. Then divide by the value of this integral and get a function that can be a probability density. Physics claims that the particle of the wave function has this probability density — I want to see a justification or at least a confirmation of that.

    For the (B) the physics:

    (i) For the treatments of and claims about entanglement, in a few words, I don’t believe what is written.

    (ii) For “generalized coordinates” as used in some Lagrangian math, I’m still looking for a clear and meaningful definition.

    And I have other concerns.

    I want to take quantum seriously, with the work done carefully, even if the whole physics community doesn’t.

    Question: Can you recommend some books on quantum mechanics that have high quality treatments of both the math and the physics?

    For getting vaccines approved, for the mRMA vaccines there were Phase III trials, randomized, placebo controlled, double blind, published in the New England Journal of Medicine on February 4, 2021 with efficacy 94.1% and no side effects with a PDF at

    https://www.nejm.org/doi/full/10.1056/nejmoa2035389

    That seems to be fast work that justifies approval.

    To me, being a college professor looked, in two words, financially irresponsible leaving me unable to support a wife and children responsibly.

    I had a good career going in applied math and computing, got a pure/applied math Ph.D. to improve my qualifications, but was sorry to discover that I had, thus, ruined my career and ability to support a wife and family. Bummer.

    The best to you wife and kids.

  17. Scott Says:

    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.

  18. Encryption: RSA destroyed? experts doubt - DigLogs Says:

    […] 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 […]

  19. Verschlüsselung: RSA zerstört? Experten zweifeln – FragMichMa Says:

    […] ob dies neue Verfahren tatsächlich RSA bezwingen kann. Viel strenger ins Justizgebäude geht Scott Aaronson, Handwerksmeister in Sachen Quantencomputer: Dasjenige Paper sei eins jener irreführendsten, die er je gesehen hat und würde Behauptungen […]

  20. asdf Says:

    Best wishes to Dana for speedy and complete recovery, and to Scott for dealing with the kids.

    Klaus Schnorr has done lots of work in cryptography over the years and that’s the name he was born with, so we can’t blame him for any confusion with Peter Shor. However, the Shor/Schnorr separator was helpful.

  21. USTC Quantum Says:

    My first impression: too good to be true. The second impression: isn’t this bullshit already refuted long ago, for instance, in Scott’s blog? Then I looked at the last author’s Google Scholar and his “famous” Secure Direct Quantum Communication papers and the number of trash citations, and I was shocked.

  22. Gui-Lu Long Says:

    This is Gui-Lu Long, one corresponding author of the Factoring paper. What we did is clearly described in our paper:

    1. One algorithm is designed for factoring integer. The hard part of Schnorr’s classical algorithm is done quantum mechanically using QAOA.

    2. We demonstrated the algorithm by factoring a 48-bit integer on a 10-qubit real superconducting device. The largest ever factored in a quantum device.

    3. We estimated that RSA-2048 can be “challenged” using the method using a quantum device with 372 qubits a circuit depths of thousands. It is close to hardware in the near future. (qubits number has reached, and the depths of circuit is one or two orders away from known results).

    4. The time complexity of QAOA is unkown, as we said in our paper “It should be pointed out that the quantum speedup of the algorithm is unclear due to the ambiguous convergence of QAOA.”. Is this meant Cargo Cult?

  23. Gui-Lu Long Says:

    A researcher sent me an article published in Financial Times, I quote some from it:

    “As far as I can tell, the paper isn’t wrong,” said Peter Shor, the Massachusetts
    Institute of Technology scientist whose 1994 algorithm proving that a quantum
    machine could defeat online encryption helped to trigger a research boom in quantum
    computing. Shor’s method requires machines with many hundreds of thousands, or
    even millions, of qubits, something that many experts believe is a decade or more
    away.

    Shor added, however, that the Chinese researchers had “failed to address how fast the
    algorithm will run”, and said that it was possible it “will still take millions of years”.
    He said: “In the absence of any analysis showing that it will be faster, I suspect that
    the most likely scenario is that it’s not much of an improvement.”

  24. jemand Says:

    @asdf(#19): Schnorr’s first name is Claus-Peter.

  25. Scott Says:

    Gui-Lu Long #22: Thanks for the comment. I guess my questions for you are:

    (1) Is there any reason to believe that QAOA will provide any speedup whatsoever over classical—even a small improvement—for the hard part of Schnorr’s algorithm? Is there is, then why didn’t the paper say so? Is there isn’t, then what was the point of writing the paper?

    (2) Did you understand, when writing the paper, that people outside quantum computing would interpret it as claiming a potential major advance on breaking RSA with a near-term QC? If so, was it your intention that they should understand you as making such a claim?

    (3) Why not clarify right in the abstract that there’s no claim of a speedup, and in fact it’s unclear if there’s any speedup? Why bury that crucial information in a single sentence of the Conclusion section?

  26. Martin Mertens Says:

    Even Max Tegmark was fooled. From Facebook:

    Looks like #QuantumComputing may torpedo today’s computer security sooner than we thought, requiring only 372 physical qubits to break RSA-2048:

  27. DOT Says:

    I apologize if I’m asking a redundant question: What’s the opinion on the Basso et al paper, arXiv:2110.14206? It’s already out for more than a year… Can any TCS person comment who has read the MaxCut part thoroughly?

    Basso, Farhi, Marwaha, Villalonga, Zhou, “The QAOA at high depth for MaxCut on large-girth regular graphs etc.”

  28. Craig Gidney Says:

    Gui-Lu Long #22:

    1. You claim you factored a number using a 10 qubit circuit. How many samples did you take from this circuit, as part of the factoring process? In particular, was it more than \(2^{10}\)?

    2. Assuming a quantum computer with no noise, please select your best guess of how many circuit samples your method would perform as part of factoring a 2048 bit number: (a) less than \(10^{12}\) samples, (b) between \(10^{12}\) and \(10^{24}\) samples, (c) more than \(10^{24}\) samples.

    3. Please give your personal estimate of the odds that the method from your paper will be used to successfully factor a 2048 bit number in the next ten years. 90%? 10%? 1%? Less?

  29. Are quantum computers about to break online privacy? – Consumers Advisory Says:

    […] told, this is one of the most misleading quantum computing papers I’ve seen in 25 years,” blogged quantum computing theorist Scott Aaronson at the University of Texas at […]

  30. Ted Says:

    Scott, do you think that any quantum factoring algorithm could possibly provide a meaningful quantum speedup using a number of qubits that scales sublinearly in the length of the number to be factored?

    I know that in general you can do lots of stuff with classical pre- and post-processing, so you don’t necessarily have to either (a) directly upload the original problem instance into the quantum processor or (b) directly read out the factors (either of which would require a linear number of qubits). But heuristically, I would guess that in order to preserve enough information about the original problem instance for the quantum processor to provide a meaningful speedup, you’d need to input an (asymptotically) similar amount of data. Do you agree?

  31. asdf Says:

    Jemand #24, Oops! I guess I need quantum error correction. Thanks for the fix.

  32. fred Says:

    Well, that’s one way for China to take advantage of its 1.4 billion population – throw as many papers as possible at the wall (24 authors on this one)… and even if none stick, that should at least slow down progress in America by wasting everyone’s time trying to keep up with all the BS! LOL

  33. Scott Says:

    Ted #30: Yeah, that’s an extremely interesting question, even if this paper takes us no further toward answering it!

    There are surely some marginal improvements from, e.g., using Grover to speed up various inner loops of classical factoring algorithms, as discussed in the “post-quantum RSA” paper. Even there, though, it’s far from obvious if any such improvements would actually help in practice (i.e., once you account for the immense overheads of fault-tolerance).

    I can’t rule out something new being discovered that gives a clear advantage for factoring with sublinear qubits. Right now, though, if you want to factor with a QC, Shor seems like the way to go to me, both in theory and in practice.

  34. Craig Gidney Says:

    Ted #30:

    One sign that there could exist algorithms with sublinear qubits is that period finding is “compression robust” ( https://arxiv.org/abs/1905.10074 ). There are single-bit predicates P where measuring P(g^x mod N), instead of the entirety of g^x mod N, still succeeds at finding the period of f(x) = g^x mod N.

    So, a reasonable avenue of attack would be find a predicate P with this period-preservation property, and also the property that P(g^x mod N) could be computed without first computing the entirety of g^x mod N. For example, I would bet P(x) = x mod 2 has this property, but I don’t know any way to compute (g^x mod N) mod 2 using less space than computing g^x mod N.

  35. Scott Says:

    fred #32: Sorry, but any future comments that put the blame for this on “China” as a monolithic entity, rather than the individual authors, will be left in moderation.

  36. No, RSA Encryption Isn’t Obsolete | American Enterprise Institute - AEI Says:

    […] in the study. Specifically, the research team has no clue how much quantum computing actually speeds up the algorithm compared to regular computers. In other words, running the algorithm may have taken just as long on […]

  37. Craig Gidney Says:

    Addendum to my comment about sub-linear via compression robustness: computing the predicate also has to be compatible with the qubit recycling trick used to measure the Fourier transform of the function’s input without ever having all of the qubits of the input in memory at the same time.

    So, not only do you need a predicate that somehow tracks g^x using less workspace than directly instantiating g^x, it has to do so with single-pass serial access to the bits of x instead of random access to the bits of x.

  38. fred Says:

    Scott #35

    Right, right, and of course anything linked to breaking RSA or *pretending* to break RSA would never be closely tied/sponsored/watched to/by some of our favorite top government agencies (NSA, etc), and even less so when we’re talking about ruthless dictatorships (which shall stay unnamed as to not break the rules of this blog)!
    :_D

  39. Rahul Sarkar Says:

    Scott, I suspected that this paper in question was overselling the claims, coz I did not hear any whispers in the pure Math community either, so your comments are reassuring. However, I’m still hopeful that one day we would wake up to a news that the factoring problem has been solved. There is a Peter Sarnak talk somewhere on the internet, where he jokes about the same.

    However, I have a separate comment about QAOA. The 100s of papers on QAOA you mention, many of them seem to get highly cited. For young researchers, this creates a conundrum: work on empirical things that can generate citations and are also low-risk, or work on actual math problems which take longer to resolve, much higher risk of not getting anything at all in the end, and typically also end up with lower citation counts. The academic environment we are in creates a pretty strong incentive to do the former – not just my opinion, but also seems to be justified by the sheer volume of papers on QAOA, parameterized quantum circuits (e.g. VQA) etc. that one can find over the last 5-7 years, that a large number of academics seem to be writing.

    Is your skepticism about QAOA coming from the fact that at the end of the day, one has to find (globally minimizing?) solutions to non-convex optimization problems, and there is just no theoretical guarantees (except may be in very specific cases) where one can do that?

    Same issue seems to be plaguing the VQA community also, but in a different way with the issue of barren plateaus. There I think even if one can find some problem dependent ansatz where barren-plateau phenomenon is lessened, one still has to deal with the issue of finding global minima to non-convex optimization problems.

  40. Scott Says:

    Rahul Sarkar #39: There are actually plenty of topics in quantum computing and information where one can pick low-hanging fruit, publish papers, and also prove theorems and otherwise advance genuine understanding. The problem, in my experience, is that people also want to claim, whether for attention, funding, or both, that they’re discovering practical applications of QC, and ideally even of near-term QC. And as soon as you pile on that third requirement, the pickings become vastly slimmer. You can spin your wheels for years on quantum algorithms that would break lattice-based crypto or achieve super-Grover speedups on important NP-complete problems or whatever without making progress. So, the temptation must become irresistible to join some bandwagon where it’s been socially agreed to call something progress even if it isn’t—and a large fraction of the literature on QAOA and other NISQ heuristics fits that description, unfortunately.

  41. Raoul Ohio Says:

    As soon as I get around to it, I will revolutionize quantum matrix theory by upgrading the Schur complement to the Shnurr complement

  42. Are quantum computers about to break online privacy? – Nature.com - Shortlinker Says:

    […] told, this is one of the most misleading quantum computing papers I’ve seen in 25 years,” blogged quantum computing theorist Scott Aaronson at the University of Texas at Austin.In the email, Long […]

  43. Chinese researchers' claimed quantum encryption crack looks unlikely • The Register - Futurist Journal Says:

    […] Late that day, on January 4, Scott Aaronson, chair of computer science at The University of Texas at Austin, and director of its Quantum Information Center, offered a rebuttal with a succinct three word review of the paper: “No. Just No.“ […]

  44. Henning Says:

    Thanks for taking the time to fact check this paper! Hope you’ll get to enjoy some of the parenting chores amidst the screams, and that your wife will make a full recovery.

  45. Chaoyang Lu Says:

    After some interactions regarding this issue on Twitter with Solano, I come to the conclusion that, while Scott was kind enough to alert people not to waste time going to a dead end, you can never wake up people who pretend to be asleep, probably because of their quantum start-up VC…

  46. Anonymous Says:

    USTC Quantum #21: I’m very interested in your comments on the “famous” Secure Direct Quantum Communication papers and the number of trash citations. What exactly is the problem with ‘Secure Direct Quantum Communication’?

  47. USTC Quantum Says:

    Anonymous Comment #46 Dare not to say. Long is powerful. He is the vice president of the Chinese Physical Society, President of AAPPS, APS fellow, Vice-chair of C13 IUPAP, Professor of Physics at Tsinghua University, and Vice President of the Beijing Academy of Quantum Information Science. I am very junior…

  48. DecoyQcryptography Says:

    Anonymous Comment #46 I am a theoretical expert in QKD. Let me say something. In short, from Wiesner quantum money to BB84 QKD, Ekert91, to Wang-Lo Decoy-state, to Lo-MDI, to TF-QKD, these are scientific advances. From BB84 to Long-SDQC, is exactly the wrong direction, making simple science unnecessary complicated and ugly, making practicality useless. Check with BB, Ekert, Lo… or any QKD experimentist for their professional opinion. But this is not the worst part. The worst part is that Long’s SDQC, while no mainstream scientists took it seriously (c.f. RMP 92, 025002), has been manipulated to be cited by thousands of junk papers published in garbage journals, because of Long’s high position. This sets one of the worst examples for the young generations and is humiliating to the whole Chinese science community.

  49. SUSTECH Quantum Says:

    DecoyQcryptography #48 What is the problem with Prof. Long? He is a nice guy. I am now a postdoc in SUSTECH. I have heard President Long’s talk five times at various conferences. His slide has been always the same, the classic, talking about his lifetime achievement, from secure direction quantum communication 20 years ago, to the Grover-Long algorithm, to the NMR quantum computing cloud with Bei Zeng. He teaches us an easy way to be academically successful. Now finally he has new materials: Shor-Long!

  50. T Says:

    I think QAOA takes some inspiration from quantum adiabatic evolution (AQC).

    Has AQC demonstrated any speed ups that you know of?

    I’m asking because I just started reading the original papers on about AQC and QAOA…..

  51. YaoX-College-ZCZ Says:

    The algorithm won’t work even if they have 100% gate fidelity. The probability to get a correct output is still exponentially small. That is what’s called a “dead end”. Comparing the number factorized is meaningless at worst and bad taste at the best. The abstract is terrible.

  52. UniverseFlyPhysics Says:

    SUSTECH Quantum 49# Shor-Long is nearly as rubbish as Grover-Long, but SDQC-Long is unbeatably the most rubbish.

  53. fred Says:

    interesting new article (with quotes from Scott)

    https://www.quantamagazine.org/new-algorithm-closes-quantum-supremacy-window-20230109/

  54. Shanghaiguy Says:

    As an expert of quantum cryptography (I hope I am qualified to say so), I want to make some comments on Long’s SDQC (or QSDC) here:

    1. Long’s SDQC (or QSDC) appeared in around 2002. It is scientifically meaningless, because it is nothing but a lower-efficient version of QKD proposed by BB, Bennett and Brassard, in 1984 (the entangled-based QKD was proposed by Ekert in 1991) and hence there is no application room for Long’s SDQC (or QSDC).
    2. The name QSDC, “Quantum secure direct communication” is rather confusing and cheating. Actually, compared with QKD invented by BB in 1984, the so called QSDC runs in a way much more slower and inefficiently, much more expensive. It’s major “idea“ is to trivially (and meaninglessly) abuse the expensive quantum communication in those steps when classical communication works perfectly. In another viewpoint, Long’s QSDC needs to encode the secret message itself to quantum states, while QKD does not need so.
    3.There are revised versions of the so called QSDC in the recent years. It is not surprising that the efficiency of revised QSDC is improved somehow because as a trivial and lower-efficient variant of QKD, the revised QSDC is now more like QKD or QKD based communication. I have no doubt that one can continue to “revise” the QSDC to further improve its efficiency, to the same level of QKD, if he just takes (steals) the contents of existing QKD protocols (with trivial and unnecessary modifications) and then claims it as his own “QSDC protocol”. By my experiance, such type of story can happen in the future. It had patially happened in the past.
    4. Actually, in BB’s earlier unpublished manuscript written before 1984, it did have a step to encode message itself to quantum states. This makes the protocol inefficient. Later, BB revised this inefficient step of encoding message itself to quantum states and changed it into sharing secret key by transmitting quantum states. This great change made the revolutionary idea of quantum key distribution and BB84 protocol. In 1990s, scientists from Australia and also Poland “invented” again the idea to encode message itself to quantum states. These authors have not continued their study on that (because there is no need to continue that.) Say, Long is not the first one who re-discovered the trash idea of QSDC. Of course this is not the central point of my comment.
    5. Early literatures have shown clearly that the revolutionary idea of QKD by BB was to enhance the communication security using flying photons. And, QKD based communication proposed there is the most efficient way to make so. If one is clear of the history of quantum communication, one should not have “invented” the strange things like QSDC which is neither new nor useful. Also, claiming a trivial modification of QKD protocol as one’s own invention under the name of QSDC or SDQC was inappropriate.
    6. I can understand that some people were unaware of the history of quantum key distribution in the old days. However, now there have been 20 years passed after the “invention” of Long’s QSDC, one should have been clear of everything. Unfortunately, some people still pretend to “work” on QSDC as if it were a scientific research. They go ahead to announce meaningless things even though they have known clearly that they are meaningless. I can’t agree with Scott more on words like “actively misleading” in the comment on Cargo Cult Quantum Factoring.

  55. Ted Says:

    T #50: I assuming that by “AQC” you mean “adiabatic quantum computation”. AQC is known to be computationally equivalent to standard gate-based quantum computation, in the sense that either architecture can simulate the other one with only polynomial overhead: https://arxiv.org/abs/quant-ph/0405098. This means that in principle, an ideal adiabatic quantum computer would be capable of efficient factoring (by simulating Shor’s algorithm) and all of that other stuff.

    Importantly, this construction only applies to ideal AQC at zero temperature and slowly changing Hamiltonians, in which case the system always stays completely in its ground state. The construction does not apply to quantum annealing (like D-Wave does), which includes the possibility of thermal fluctuations, fast changes in the Hamiltonian, and other diabatic effects that can take the system out of its ground state. Quantum annealing is much harder than AQC to investigate theoretically, but there is currently no evidence (either theoretical or experimental) that it can efficiently simulate universal gate-based quantum computing, like AQC can.

  56. Raoul Ohio Says:

    Although “Cargo Cult” is an excellent descriptive adjective for results where there is actually nothing there, it does lack that certain “Latin sound” traditional in scholarly words. I propose “Polyfusion” as the word to throw cold water on bad ideas. This honors of two great exemplars, Poly Water (late 1960’s) and Cold Fusion (1989).

  57. MarkH Says:

    @Raoul Ohio:

    “Cargo Cult” goes beyond mere non-existence. It carries the nuance of steadfast faith that by summoning the wished-for phenomenon via magical construction, and endless persistence, it will somehow appear.

    Scott, thank you (and thanks to several informative commenters!) for clarifying the nature of this … shall I say, sensational paper.

  58. jerome Says:

    Even though they didn’t claim quantum speedup, the findings can be quantum speedupped by using the circuit in https://quantumfrontiers.com/2017/07/14/the-world-of-hackers-and-secrets/, which is theoretically faster than the MATLAB code.

  59. manorba Says:

    Raoul Ohio #56:

    “Although “Cargo Cult” is an excellent descriptive adjective for results where there is actually nothing there, it does lack that certain “Latin sound” traditional in scholarly words”

    Well both cargo and cult are words that come from latin tbh… cargo is from “carricare” (italian “caricare”,to carry, first person “io carico”, with the same spelling but as a noun “carico”= payload). Cultus is also a latin word 😉

    It seems to me that it is a widely accepted expression in science, given its origin 🙂

  60. Alex Meiburg Says:

    While “cargo cult factoring” is a great name, it occurred to me that there is an opposite effect as well, as discussed in [Szegedy’s recent comment](https://scirate.com/arxiv/2212.12572) on the PUWES [“quantum advantage for combinatorial optimization problems”](https://scirate.com/arxiv/2212.08678) paper. Instead of expecting numbers to be factored in a combinatorial problem by virtue of the solver being quantum (as above), this is the suggestion that quantum computers are useful for general combinatorial problems because they can do factoring.

    That is, I take a factoring problem P1 and write it as a combinatorial optimization problem P2 (say, 3-coloring). I then can certainly solve P2 much faster with a quantum computer, by first extracting the underlying factoring problem P1, applying Shor’s algorithm, and putting the answer back into P2-form. There is an implication that, since my quantum computer can solve all of these P2 problems, I’ve demonstrated that quantum computers are super-polynomially better at 3-coloring than classical computers.

    The authors do not quite make such a claim, but they come very close:
    > we prove that fault-tolerant quantum computers feature a super-polynomial advantage over classical computers in approximating solutions to combinatorial optimization problems.

    Is this cargo cult combinatorial optimization? Or something else?

  61. Scott Says:

    Alex Meiburg #60: While I don’t know what to call it, my understanding of that paper was enormously enhanced by Mario Szegedy’s subsequent commentary, which answered the “but why couldn’t you just…” that I asked at the time on Facebook with a simple “you can.”

  62. Manuel Says:

    Dear Mr. Aaronson,

    Would you mind giving me a minimum idea of the prerequisites for your book on Quantum Computing since Democritus? I was rather keen on giving it a go this year – New Year’s Resolutions.

    As to my background, I am a square Humanities person who’s discovered a love of math in the last year, but am still catching up. Right now, I have self-taught myself all high school math and starting with some of the undergraduate stuff (some basic set theory, logic and very elementary abstract algebra and number systems).

    Best greetings,

    M.

  63. Carey Underwood Says:

    Manuel #62: In my opinion, you’ll be fine with that background.

  64. manorba Says:

    Manuel #62:

    “I am a square Humanities person who’s discovered a love of math in the last year”

    Looks like I caught the same disease some years ago, and if you’re interested these are some of the resources that helped me a lot:

    https://webspace.science.uu.nl/~hooft101/theorist.html
    https://theoreticalminimum.com/
    https://www.feynmanlectures.caltech.edu/

  65. Pascal Says:

    What about this paper on quantum energy teleportation: https://arxiv.org/pdf/2301.02666.pdf.
    Is this something that one can be genuinely excited about, for a change? (I mean, excited in a positive way!)

  66. John Says:

    A new paper today was published Jan. 27 that shows improvements over QAOA for factoring with Schnorr’s algorithm. https://arxiv.org/pdf/2301.11005.pdf

    This alternative is called “Digitized-counterdiabatic quantum factorization” DCQF. Although using trapped-ions appears to currently reach limits for factoring around 128 bit numbers, they suggest current neutral atom systems have promise for DCQF and larger numbers.

    Sure, we still are not seeing a quantum speedup of Schnorr’s compared to running Schnorr’s on a PC. But, the point is understanding if benefits from DCQF can scale as NISQ systems grow. The authors, based on their understanding, seem convinced on the potential.

  67. Scott Says:

    Manuel #62: I keep hearing from people who tell me they only understood 10% of QCSD, but loved that 10%. Make of that whatever you will! 🙂

  68. Scott Says:

    John #66: Sorry, but I just read it, and it strikes me as yet another “cargo cult quantum factoring” paper.

    To say it one more time: no evidence has been offered, here or elsewhere, that QAOA should give any speedup compared to just running Schnorr’s algorithm on a classical computer. This is the actual core of the matter. No number of irrelevant experiments and papers—not 2, not 100, not a million—let the hypesters “win by attrition” without answering it!

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.