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:
- the detailed exploration of irrelevancies (mostly, optimization of the number of qubits, while ignoring the number of gates), and
- 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.
Follow
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!
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?)).
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 🙂
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.
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.
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 🙂
Comment #7 January 5th, 2023 at 9:06 am
Ashley #6: Thanks; I hadn’t seen that! Just added a link to the post.
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.
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?
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!
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.)
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?
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!
Comment #14 January 5th, 2023 at 12:37 pm
Shor’s algorithm and Schnorr’s algorithm? What is this, Borscht Belt comedy?
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.
Comment #16 January 5th, 2023 at 1:40 pm
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.
Comment #17 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.
Comment #18 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 […]
Comment #19 January 5th, 2023 at 6:19 pm
[…] 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 […]
Comment #20 January 5th, 2023 at 6:56 pm
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.
Comment #21 January 5th, 2023 at 9:38 pm
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.
Comment #22 January 5th, 2023 at 10:18 pm
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?
Comment #23 January 5th, 2023 at 10:21 pm
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.”
Comment #24 January 6th, 2023 at 5:29 am
@asdf(#19): Schnorr’s first name is Claus-Peter.
Comment #25 January 6th, 2023 at 8:02 am
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?
Comment #26 January 6th, 2023 at 9:56 am
Even Max Tegmark was fooled. From Facebook:
Comment #27 January 6th, 2023 at 10:19 am
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.”
Comment #28 January 6th, 2023 at 11:17 am
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?
Comment #29 January 6th, 2023 at 12:22 pm
[…] 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 […]
Comment #30 January 6th, 2023 at 12:55 pm
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?
Comment #31 January 6th, 2023 at 1:33 pm
Jemand #24, Oops! I guess I need quantum error correction. Thanks for the fix.
Comment #32 January 6th, 2023 at 1:38 pm
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
Comment #33 January 6th, 2023 at 1:42 pm
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.
Comment #34 January 6th, 2023 at 1:55 pm
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.
Comment #35 January 6th, 2023 at 2:13 pm
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.
Comment #36 January 6th, 2023 at 2:24 pm
[…] 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 […]
Comment #37 January 6th, 2023 at 2:25 pm
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.
Comment #38 January 6th, 2023 at 2:57 pm
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
Comment #39 January 6th, 2023 at 3:07 pm
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.
Comment #40 January 6th, 2023 at 4:17 pm
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.
Comment #41 January 6th, 2023 at 5:38 pm
As soon as I get around to it, I will revolutionize quantum matrix theory by upgrading the Schur complement to the Shnurr complement
Comment #42 January 6th, 2023 at 11:19 pm
[…] 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 […]
Comment #43 January 7th, 2023 at 8:27 am
[…] 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.“ […]
Comment #44 January 7th, 2023 at 4:07 pm
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.
Comment #45 January 7th, 2023 at 8:29 pm
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…
Comment #46 January 7th, 2023 at 8:52 pm
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’?
Comment #47 January 8th, 2023 at 7:04 am
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…
Comment #48 January 8th, 2023 at 5:05 pm
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.
Comment #49 January 8th, 2023 at 5:50 pm
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!
Comment #50 January 8th, 2023 at 7:31 pm
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…..
Comment #51 January 8th, 2023 at 8:40 pm
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.
Comment #52 January 8th, 2023 at 8:57 pm
SUSTECH Quantum 49# Shor-Long is nearly as rubbish as Grover-Long, but SDQC-Long is unbeatably the most rubbish.
Comment #53 January 9th, 2023 at 9:48 am
interesting new article (with quotes from Scott)
https://www.quantamagazine.org/new-algorithm-closes-quantum-supremacy-window-20230109/
Comment #54 January 9th, 2023 at 11:55 am
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.
Comment #55 January 9th, 2023 at 12:46 pm
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.
Comment #56 January 9th, 2023 at 6:13 pm
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).
Comment #57 January 10th, 2023 at 12:53 am
@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.
Comment #58 January 10th, 2023 at 6:14 am
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.
Comment #59 January 10th, 2023 at 6:49 am
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 🙂
Comment #60 January 10th, 2023 at 7:25 pm
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?
Comment #61 January 10th, 2023 at 9:55 pm
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.”
Comment #62 January 14th, 2023 at 9:06 am
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.
Comment #63 January 14th, 2023 at 1:56 pm
Manuel #62: In my opinion, you’ll be fine with that background.
Comment #64 January 15th, 2023 at 4:21 am
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/
Comment #65 January 17th, 2023 at 3:01 pm
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!)
Comment #66 January 27th, 2023 at 12:41 am
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.
Comment #67 January 27th, 2023 at 11:16 am
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! 🙂
Comment #68 January 27th, 2023 at 11:21 am
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!
Comment #69 January 28th, 2023 at 5:32 am
Hi Scott. Big fan of yours. Thanks for reading our report. But it seems like you misunderstood our work. Even though we show enhancement over QAOA, our algorithm has no similarities with QAOA. Please have another look.
The previous claim tells that RSA-2048 can be tackled by finding the ground state of an Ising spin glass Hamiltonian with ~370 qubits, which triggered our attention. As physicists, we are more interested in a special case, here N=370. We are not interested in a general case where N is arbitrary and large. We use the tools developed for studying quantum many-body ground state and apply it here. We are not interested in the standard digital quantum computer either. There are various other ways to encode the problem more natively on different hardware platforms.
If your argument is that no quantum algorithm will tackle this Ising spin glass Hamiltonian with 370 qubits on any quantum hardware platforms in the near term, I highly doubt your argument. Look forward to your reply.
Comment #70 January 28th, 2023 at 5:20 pm
Narendra #69: Can we please try to stay focused on the central question here? Namely: what is the evidence that any of these approaches to factoring—none of which encode any of the insights of Shor’s algorithm—will get any advantage compared to just factoring using a classical computer? And if there’s no such evidence, then why are you writing papers giving people the impression that there is?
Comment #71 January 29th, 2023 at 1:27 am
Thanks for the reply. Are you saying that adiabatic quantum computation (AQC) has no quantum advantage/speed up for tackling the Ising spin glass Hamiltonian? Our algorithm is based on AQC. The counterdiabatic protocol helps to mimic the quasi-adiabatic evolution. Here, we are not competing against Shor’s algorithm in terms of quantum speed up. We make it clear that it’s very unlikely to have any polynomial-time quantum algorithm for the Ising spin glass Hamiltonian. However, you can’t rule out the fact that there might be some polynomial quantum speed-up. And the system size of ~370 seems tractable on near-term devices. It’s interesting to explore such a possibility and write a paper.
Comment #72 January 29th, 2023 at 11:08 pm
Narendra #71: My point was that, so far, I haven’t seen a case for why there should even be a polynomial speedup over classical for factoring integers using adiabatic optimization! Do you know such a case? If so, what is it?
Now of course there’s the Grover speedup, which can sometimes be achieved adiabatically. But the Grover speedup is completely swamped by the Number Field Sieve, and other classical methods that exploit the special nature of factoring (as Grover’s algorithm doesn’t). You know that, don’t you?
And of course there’s the celebrated 2003 theorem that AQC is universal—but all that tells us is that ultimately, you could run Shor’s algorithm itself adiabatically, by engineering a Hamiltonian whose unique ground state was the Feynman-Kitaev history state for Shor’s algorithm! It gives no hope whatsoever that naïve adiabatic optimization, which doesn’t know anything about number theory or periodicity or FFTs, is going to just “magically see” the structure in factoring that enables a quantum speedup for it. That would seem like a miracle, wouldn’t it?
Surely, then, any honest paper about using AQC to factor would make these points very clearly, so as not to mislead the reader, wouldn’t it?
Comment #73 January 30th, 2023 at 8:51 am
You might know the difficulty in estimating the time complexity of adiabatic quantum optimization (AQO). People have been exploring for many years to directly test it on hardware and look for quantum speed up. However, such studies mainly consider finite-time quantum annealing running on incoherent quantum hardware to study stoquastic Hamiltonians. Even though there are experimental results showing quantum speed up, so far, no polynomial quantum speed has been observed. Here we are talking about a different problem (even though the final Hamiltonian of interest is stoquastic). By construction, the CD terms are non-stoquastic for optimization problems. And no classical algorithms are known to simulate their dynamics efficiently. And even the quantum annealers can’t implement the CD protocols due to non-stoquastic terms. In our previous studies, we provided numerical evidence showing a polynomial scaling enhancement even with the simplest approximate CD protocol compared to the naive finite time AQO (similar results are observed by Innsbruck group). We have clearly mentioned these points on the first page of our report.
Exploring the possibility of polynomial quantum speed for an optimization task with the CD protocol is an interesting research problem. And telling not to write a paper on that seems like an unjustified statement.
Comment #74 January 30th, 2023 at 8:03 pm
Narendra #73: I never suggested that people shouldn’t write papers about these things! What I want is for the papers to do one of two things: either
(1) give something resembling a positive case to believe that there might be an actual speedup this way over the best known classical algorithms for the same problems, or else
(2) clearly, explicitly, prominently acknowledge that there’s no such case, to head off the by-now-100%-predictable flood of hypesters, confuseniks, and misunderstandinistas claiming that there is.
Unless you can respond directly to what I’m asking for above, by e.g. explaining why you didn’t provide it, rather than changing the subject, this exchange is unfortunately at an end.
Comment #75 January 31st, 2023 at 1:26 pm
It is mystifying to me why two of the authors of the paper in question have now been directly confronted with the central objection to what it seems to claim and have entirely failed to respond on point, *unless* they simply don’t understand what you’re asking.
Comment #76 January 31st, 2023 at 10:52 pm
@Jud:
Commenter Long (comments #22 and #23) presented himself as an author of the controversial paper this post is about (“Factoring integers with sublinear resources on a superconducting quantum processor”). Both Scott and another commenter responded here with several pointed questions, to which I have seen no answer as yet.
Commenter Narendra (#69, #71, #73) presented himself as an author of a different paper (“Digitized-counterdiabatic quantum factorization”) cited by John (#66). It seems that Narendra also has not directly answered Scott’s pointed question.
Although the techniques of the second paper are very different, its abstract also claims potential to factor 2048-bit semiprimes (specifically, challenge number RSA-2048). Unless it’s faster than classical algorithms, it can never factor such numbers … Scott requested the argument for why the paper’s approach can be expected to be faster. The (very brief) paper itself didn’t make the case satisfactorily, and so far author Narendra hasn’t done so in this comment thread.
Carl Sagan was fond of saying that extraordinary claims require extraordinary evidence. If anyone publishes factors of RSA-2048, that would convince me!
Arguing (for example) that “nobody knows yet” or “it hasn’t been proved impossible” is not enough.
Comment #77 February 5th, 2023 at 1:19 am
Before factors are provided for RSA-2048, it would be helpful to see evidence of speed up over classical algorithms. Regarding the use of Schnorr’s algorithm with either QAOA or DCQF, they should show the lines for 200 or 400 bit numbers drop meaningfully below the baseline of the Quadratic Sieve (QS) shown in slide 20 of here: https://projects.cwi.nl/crypto/risc_materials/2021_05_20_ducas_slides.pdf
Wikipedia notes QS is fastest up to about 100 decimal digit numbers (~320 bits). IF that could be shown, the next place to look is evidence that the speed up continues scaling as numbers to factor grow even larger and also meaningfully faster than GNFS.
Comment #78 February 11th, 2023 at 1:19 pm
Let me say that Clauss Schnorr is an excellent mathematician, and was occupying the same general name-space as I do well before I came onto the scene. It’s not actually the same name — my name is derived from Hebrew, and is in fact the same name as Schorr (my great-grandfather’s name before it got mangled at Ellis Island), Shore, Schur, and Chor when written in its proper alphabet: שׁוֹר. But there’s no “n” in the Hebrew. It’s not a case of ““Diz-Nee Land, Not Affiliated With Disneyland”.
And as far as I can tell, there’s nothing really wrong with the classical version of Schnorr’s algorithm; it’s a good idea, it just doesn’t happen to run as fast as the Quadratic Sieve and the Number Field Sieve in practice.
Comment #79 February 13th, 2023 at 2:55 pm
Peter Shor #78: While my commenters and I proved unable to resist a bit of lowbrow humor based on the similarity between your and Claus-Peter Schnorr’s names, indeed I have no doubt that Schnorr is an excellent mathematician and I’d feel bad if anyone got any other idea from this post.
Comment #80 February 20th, 2023 at 7:33 am
Hello everybody. Thank you a lot for this hot and lively thread (:-))
Very interesting recent preprint:
Computing 256-bit Elliptic Curve Logarithm in 9 Hours with 126133 Cat Qubits
https://arxiv.org/abs/2302.06639
Especially the end of the main part of this long preprint (39 pages):
extrapolation of their method for RSA-2048:
(…) we estimated that the implementation of Shor’s algorithm for the factorization of
2048-RSA integers would take 349 133 cat qubits and 4 days.
(…)
Thanks in advance for your impression on their specific implementation of Shor’s algorithm.
Best regards.
Comment #81 March 9th, 2023 at 12:33 am
Here is an update. This preprint from March 9 is not finding speed up using QAOA with Schnorr, when reproducing the original work from December 2022.
https://arxiv.org/pdf/2303.04656.pdf
Comment #82 March 9th, 2023 at 1:28 am
Hello, another piece for this topic:
Pitfalls of the sublinear QAOA-based factorization algorithm
https://arxiv.org/abs/2303.04656
Preprint, Wed, 8 Mar 2023 15:23:50 UTC
Several in-depth aspects including Schnorr’s algorithm.
Best regards
Comment #83 March 14th, 2023 at 5:27 am
[…] is author of “Quantum Computing Since Democritus”) summed up the Chinese report in his blog “Cargo Cult Quantum Factoring” with a concise three-word review: “No. Just […]
Comment #84 March 18th, 2023 at 4:54 am
[…] is author of “Quantum Computing Since Democritus”) summed up the Chinese report in his blog “Cargo Cult Quantum Factoring” with a concise three-word review: “No. Just […]
Comment #85 May 16th, 2023 at 10:51 am
Here is another update. The preprint for reproducing the Dec. 2022 factoring algorithm with Schnorr+QAOA has been updated: https://arxiv.org/pdf/2303.04656.pdf. The original attempt to reproduce was in March and linked above in comments 81 and 82.
The conclusion is essentially the same. But, this update (compared to the March version), has reproduced more of the Dec. 2022 Schnorr+QAOA individual steps. The updated version says, “In this way, given that the QAOA provides a number of bottom eigen values of Hˆc, we verified and sr-pairs indeed can be obtained.” The March version suggested performance was closer to a random walk.
Figure 1c shows at least one very clear outlier run for ” Convergence of mean energy E to the minimal energy Emin” for use of 14 qubits to factor the 15 decimal digit number. It’s interesting there is no specific comment on that run, because IF true, that would suggest something potentially significant.
Comment #86 July 5th, 2023 at 12:36 am
[…] leveraged DeepMind’s own version of the tensor simulation of quantum circuits to create a cargo cult factoring algorithm. Offenbach R.M.C. first breaks into Aberdeen’s systems and commandeers thousands of military […]