Table of Contents
July 9, 2026 — Physical Review X published a 29-page Perspective by four of the field’s most cited theorists that proposes a formal framework for telling genuine quantum advantages apart from illusions. In “Vast World of Quantum Advantage,” Hsin-Yuan Huang (Caltech and Google Quantum AI), Soonwon Choi (MIT), Jarrod McClean (Google Quantum AI), and John Preskill (Caltech and the AWS Center for Quantum Computing) define five properties an ideal quantum advantage must satisfy, sort the known advantages into four domains, and prove that some quantum advantages cannot be predicted using classical resources alone. The paper, first posted to arXiv in August 2025, attracted dozens of citations as a preprint before the journal version appeared.
The five properties, which the authors call keystones, are predictability (rigorous evidence that the advantage will materialize once the hardware exists), typicality (the advantage holds for the problem instances people actually encounter rather than contrived worst cases), robustness (the advantage persists under noise and deviations from idealized assumptions), verifiability (the output can be checked efficiently), and usefulness (the method delivers practical value to a user who does not care whether the machinery behind it is quantum or classical). The authors call finding a new advantage that satisfies all five simultaneously a grand challenge for the field, and in the body of the paper, one existing example is described as meeting their keystone criteria.
That example is Shor’s algorithm, which solves the integer-factoring problem behind RSA and the discrete-logarithm problem behind elliptic-curve cryptography once a large enough machine runs it. Shor’s is the worked example for predictability, typicality, the noise keystone, and verifiability alike. For readers in security, that is the sentence to forward upstairs: the one advantage the authors describe as clearing their own bar is the cryptanalytic one.
Huang and his co-authors sort quantum advantages into four domains: computation, learning and sensing, cryptography and communication (a category that stretches to strategic coordination, including one cited proposal for entangled stock exchanges), and space, meaning memory efficiency. The sorting carries a warning. Computational advantages rest on unproven conjectures such as BPP ≠ BQP, the standard assumption that quantum computers can efficiently solve at least one problem classical computers cannot. Advantages in sensing and cryptography rest on physical law instead: Bell’s theorem, the no-cloning theorem, Holevo’s bound. A Bell violation does not care what complexity theorists prove next year.
Between proof and hope, the authors also describe a middle methodology the field has developed recently: forecasting advantage instance by instance. For a few algorithm families, including the Google-led decoded quantum interferometry proposal, classical computation can predict how the quantum algorithm would perform on a specific problem even though only a quantum computer could run it. That lets researchers benchmark against the best classical solvers before the hardware exists.
The paper is equally a history of what the authors call pseudoadvantages: quantum protocols that appeared to beat every classical approach until someone found the classical method that matched them. The paper walks through the best-known case, and the backstory deserves the space. In 2018, Ewin Tang, then an 18-year-old undergraduate working under Scott Aaronson at the University of Texas at Austin, published a classical algorithm only polynomially slower than a flagship quantum recommendation-system method, which erased its claimed exponential speedup, and a wave of “dequantizations” followed that trimmed a decade of quantum machine-learning claims built on the 2009 Harrow-Hassidim-Lloyd linear-systems algorithm. HHL itself keeps its advantage; many of its descendants did not keep theirs.
Prediction itself gets the paper’s most arresting result. Theorem 1 proves that deciding whether a given quantum circuit gains a computational advantage over one specific, well-understood classical simulation method (a heuristic called low-weight Pauli propagation, with advantage defined as the heuristic missing badly on a large share of inputs) is a task a quantum computer can perform efficiently and a classical computer cannot, assuming BPP ≠ BQP. The corollary the authors draw is blunt: mapping the territory of quantum advantage will itself require quantum machines.
There is bad news for one celebrated advantage. In the noiseless ideal, an entangled probe of N sensor qubits running for time T can resolve a signal of size $$1/(NT)$$, the Heisenberg limit, where unentangled probes manage only $$1/(\sqrt{N}T)$$. Appendix B proves, in a clean model of dephasing noise, that any fixed noise level drags both down to $$1/\sqrt{NT}$$, a floor an entirely unentangled protocol already reaches; the broader no-go the authors invoke adds that quantum error correction cannot rescue the scaling whenever signal and noise overlap at the operator level. The authors contrast this with computation, where the fault-tolerance threshold theorem carries an advantage through noisy hardware so long as error rates sit below threshold.
The Perspective is open access under a CC BY 4.0 license, received August 7, 2025, revised March 19, 2026, and published July 9, 2026, as PRX 16, 030501. The authors write that “quantum theorists are like prophets attempting to foretell the future,” and the paper reads as an attempt to give prophecy an error bar.
My Analysis
I spend a good part of my working life arguing with two groups: people convinced quantum computers will upend the world by Thursday, and people convinced they will never work at all. Both camps run on the same fuel, which is the word advantage deployed without a definition. This paper takes the fuel away. To my thinking it is the most useful 29 pages a technology decision-maker will read about quantum computing this year, and I say that as someone who writes competing pages for a living.
A due-diligence rubric for a market built on one word
Every quantum vendor sells an advantage of some kind. The panic merchants I catalogued in Q-FUD: The Quantum Panic Industry convert those claims into urgency; the denialists convert the eventual retractions into vindication. Neither camp has had to face a test. Now there is one, and it maps directly onto procurement language. Predictability asks what evidence exists that the method beats the best classical approach, and who did the looking on the classical side. Typicality, whether the demonstration instances resemble the instances you own or were picked because classical methods stumble on them. The third test covers noise, demanding numbers from hardware and data as imperfect as yours will be. Verifiability covers how you would know the output is correct at all. And usefulness is the coldest of the five: if the same capability arrived in a classical box, would you still sign the purchase order?
The authors open with a party trick that doubles as a warning label. Two entangled particles measured along a single fixed axis produce correlations that a pair of socks in gift boxes reproduces exactly; only when the observers start switching between well-chosen measurement bases does Bell’s theorem forbid any classical imitation. The gap between a quantum miracle and a sock drawer can be one measurement setting wide. That is the whole problem with advantage claims in miniature, and the paper’s catalog of pseudoadvantages shows how it plays out at industrial scale.
The Tang episode carries the market lesson. Quanta ran the story under the headline “Major Quantum Computing Advance Made Obsolete by Teenager,” and the field absorbed the point: a claimed exponential speedup lasts exactly as long as the strongest classical algorithm nobody has written yet. The Perspective adds the fine print that spared HHL but doomed many of its descendants anyway. Loading large classical datasets into quantum states, the QRAM step that most quantum machine-learning pitches cover in a single slide, carries a fault-tolerant spacetime cost that grows about as fast as the data itself. A vendor deck quoting an exponential machine-learning speedup without stating its data-loading assumptions is quoting the 2017 state of the art. The classical baseline keeps moving.
Shor’s algorithm keeps passing the tests
Run the tally. Predictability: the advantage reduces to the classical hardness of factoring and discrete logarithms, problems that have absorbed decades of attack from the best-funded cryptanalytic community on earth precisely because trillions of dollars of commerce sit on top of them, and no classical break has surfaced. Typicality: the discrete logarithm problem is random self-reducible—a randomly chosen key is provably as hard as the hardest key—so within the relevant groups, no key is protected by having landed on a mathematically lucky instance. Robustness: the threshold theorem carries the speedup through noisy hardware. Verifiability: multiply the factors back together, or exponentiate to check a recovered discrete log. Four for four, with the paper supplying each example itself.
Does it pass the fifth test? Usefulness, in the authors’ definition, means value to a user who is indifferent to whether the machinery is quantum or classical. Signals-intelligence agencies meet that definition with room to spare, and so does anyone holding harvested ciphertext with a long shelf life. The least disputed quantum application on the books is the one aimed at your key material. I have made that argument for years, and it is strange and a little grim to watch it emerge, unforced, from a paper whose authors were mostly worried about scientific method.
Each camp will read this selectively, so hold both halves in view. Denialists now have to explain why the most careful treatment of quantum advantage its leading theorists have published keeps reaching for the cryptanalytic example. The panic industry has the opposite problem: the same 29 pages document a graveyard of advantage claims that better classical algorithms later matched, which is an awkward document to wave around while selling urgency. My position sits where it has sat since I started this site. The threat to RSA and ECC stands on firmer ground than any other application claim in quantum computing, and the rest should face the five tests before they earn a budget line.
None of this moves Q-Day or the arrival date of a cryptographically relevant quantum computer. The engineering distances I track in my CRQC Quantum Capability Framework—error correction, magic-state production, real-time decoding, continuous operation—are the same this week as last, and the resource estimates keep falling: Craig Gidney’s 2025 analysis put RSA-2048 within reach of under a million noisy qubits, and newer architectural proposals claim six figures, on machines nobody has built. What changed is who owes an explanation. When regulators, insurers, and clients set migration deadlines, they were accused of buying hype; the field’s leading theorists now treat the underlying advantage as about as far from hype as quantum computing gets. Harvested traffic does not expire.
You need a quantum computer to referee quantum advantage
The result I keep turning over is Theorem 1, which the authors state with a straight face: deciding whether a given quantum circuit beats one specific, fixed classical simulation heuristic is quantumly easy and classically intractable. The construction is elegant. They build circuits in which the question “does the classical method track this device?” secretly encodes an arbitrary quantum computation, so any classical referee able to always call the match would be a classical machine doing quantum work. And that is the situation against a single heuristic the authors chose themselves; certifying an advantage against every classical algorithm, including the ones nobody has invented, is harder still.
Seven years of supremacy fights look different in that light. Google claimed in 2019 that its Sycamore sampling task would cost a classical supercomputer 10,000 years; IBM answered within days with a counter-estimate of 2.5 days; tensor-network methods kept cutting from there, a history I walked through in my random circuit sampling explainer. USTC’s Zuchongzhi processors pressed the same frontier from China, and Google’s Willow chip reset the bar with its 2024 sampling record. For its sampling showcase, the Perspective picks Willow’s 103-qubit follow-up, a run better known as the Quantum Echoes experiment, and calls it beyond classical reach, for now. I used to read that back-and-forth as embarrassing for the claimants. The theorem reads it as the permanent condition of the frontier: every advantage verdict is provisional against tomorrow’s classical algorithm, and a definitive classical certification was never on offer in the first place.
Keep two different guarantees apart here. Urmila Mahadev’s 2018 protocol lets a purely classical client verify, under a standard cryptographic assumption, that a quantum server computed what it claims, and Quantum Echoes leaned the same direction by measuring an observable other quantum computers can cross-check instead of random bits that nothing directly verifies. Both address the keystone the paper calls verifiability. Certifying that no classical shortcut exists is the harder promise, and the theorem now puts even its narrowest version, one fixed and well-understood heuristic, beyond any efficient classical procedure that works for every circuit. The broad version, ruling out every classical algorithm including those not yet invented, was never available to anyone. Classical analysts can still audit individual experiments and prove results for structured circuit families; what they cannot do is referee the whole territory. Procurement acceptance tests, national benchmarking programs, and press releases announcing advantage all inherit the consequence: the scoreboard is live, the verdicts are provisional, and for this class of calls the referee needs a quantum computer.
What the sensing proof kills, and what it spares
The sensing appendix will read as an obituary in some pitch decks, so it pays to be precise about the deceased. The casualty is the asymptotic entanglement advantage under generic noise: the Heisenberg-limit scaling that GHZ-style probes reach on paper and that no amount of error correction restores once noise and signal blur together at the operator level. Quantum sensing as a business is a different patient entirely. LIGO’s squeezed-light upgrade is a real quantum enhancement running in production inside a meticulously engineered noise budget. Nitrogen-vacancy magnetometers and optical clocks win on the innate sensitivity of quantum systems, with no entanglement scaling required. And the authors make an observation the sensing industry should frame: in sensing, constant-factor improvements carry real commercial weight, because you cannot parallelize your way past physics when the probe has to sit at the target and the interferometer arms are already 4 kilometers long. When I assess quantum sensing companies, the sorting question is now whether the deck sells a measured improvement in a deployed regime or a scaling law the noise floor forbids. Constant factors pay the bills.
The part of the map nobody can read
The final third of the paper widens the lens from tests to futures, and it is the part I expect to age best. The authors expect adoption to turn on empirical metrics in the end: total cost, wall-clock time, and what they call concept-to-solution time, the distance between having a problem and having a working method. Their example is pointed. If writing the quantum program takes an hour, and a matching classical algorithm exists but takes a talented computer scientist a year to find, the quantum machine won by a year, minus the hour. Classical computing’s own history argues for humility here; its defining applications arrived unannounced, unproven, and unforecast.
Then there is the iceberg the authors draw: known advantages above the waterline, and below it the empirical, the conceptual, and the classically unpredictable in the theorem’s precise sense. The deepest reading of Theorem 1 is that parts of the map can only be surveyed with quantum instruments, and the authors proved the blind spot rather than gesturing at it. Denialists can no longer treat the absence of a classical forecast as evidence of absence. The panic industry gains nothing either, because an advantage nobody can foresee cannot be put on a product slide.
So the honest position after all 29 pages is the one this site has argued from the start, now with better citations. The cryptanalytic threat is the strongest practically consequential quantum advantage anyone has identified, the migration deadlines built on it just got easier to defend, and nearly everything else sold under the same word now has five tests to pass, published where every buyer can read them. Bell gave physicists a way to tell entangled particles from boxed socks. Huang, Choi, McClean, and Preskill have done the same for the sales deck. When the next advantage claim lands on your desk, run the tests. Check for socks.
