Hsin-Yuan Huang, Soonwon Choi, Jarrod McClean, and John Preskill proposed five properties that define an ideal quantum advantage in a perspective article that Physical Review X published on July 9, 2026. By quantum advantage, the authors meant capabilities “fundamentally beyond what is possible with classical technology.” The four researchers named the properties predictability, typicality, robustness, verifiability, and usefulness, and called them keystones.
The authors wrote that Shor’s algorithm “exemplifies genuine computational quantum advantage” and that it satisfies their “keystone criteria.” Shor’s algorithm factors large numbers and computes discrete logarithms, the problems on which the security of RSA and elliptic-curve cryptography depends. The authors also wrote that finding a new quantum advantage that achieves all five properties simultaneously “remains a grand challenge for the field.”
Huang is at the California Institute of Technology (Caltech) and Google Quantum AI, Choi at the Massachusetts Institute of Technology, McClean at Google Quantum AI, and Preskill at Caltech and the AWS Center for Quantum Computing. On August 7, 2025, the authors posted the manuscript as an arXiv preprint, a version released publicly before journal publication. Physical Review X received it that day and a revised version on March 19, 2026.
The five keystones
In the authors’ definitions, a quantum advantage is predictable if there is sufficient evidence that the necessary quantum technology would provide capabilities beyond those of classical technology. It exhibits typicality if it applies to “a substantial fraction of practically relevant problem instances” and is not confined to particular instances that classical computers find hard. An advantage has robustness if it persists “despite deviations from idealized theoretical assumptions,” such as imperfect hardware, limited resources, or flawed input data.
An advantage is verifiable if “it can be checked efficiently that the quantum technology is producing the correct output.” It is useful if it “provides practical value to a user who seeks an effective method for a significant application,” the authors wrote. The user in question “does not care whether the underlying technology is classical or quantum,” they added.
The authors sorted known advantages into four groups: computational, learning and sensing, space, and a combined group for cryptography, communication, and strategic games. Space advantages concern memory, where quantum algorithms “can sometimes achieve exponential space savings,” the authors wrote.
Shor’s algorithm and random circuit sampling
“As of now, most superpolynomial quantum advantages are not known to be typical,” the authors wrote. Superpolynomial advantages are speedups that grow faster than any polynomial function of the problem size.
In one example, the authors described Google’s Willow processor performing random circuit sampling in a few minutes, a task they wrote a classical computer would need “much longer than the age of the Universe” to complete. In random circuit sampling, a quantum processor repeatedly runs a randomly chosen circuit, a sequence of quantum logic operations, and records the string of bits it reads out each time.
The authors concluded from published results that the advantages of random circuit sampling are typical. The resulting bit strings, however, “are not known to be of much use,” they wrote.
“Even decades after its discovery, no efficient classical algorithm has emerged to challenge its speedup,” the authors wrote of Shor’s algorithm. They noted that its output can be checked efficiently with classical multiplication. In their discussion of typicality, they described it as an advantage “for breaking cryptographic protocols, where one can reinstate security by using postquantum cryptography.”
The authors defined predictability as a forecast conditional on the necessary quantum technology. Separately, Craig Gidney of Google Quantum AI estimated in a May 2025 preprint that a quantum computer with fewer than a million noisy physical qubits could factor a 2048-bit RSA integer in less than a week if each logic operation failed 0.1% of the time and each round of error checks took 1 microsecond.
Advantages classical computers cannot predict
The authors proved that some quantum advantages cannot be predicted using classical resources alone, in a result they labeled Theorem 1. In it, they considered predicting whether a quantum computer running a given circuit has a computational advantage over Pauli propagation. Pauli propagation is a classical technique that, the authors wrote, can efficiently estimate measured averages for most quantum circuits, a narrower task than reproducing a circuit’s full output.
BPP and BQP are the classes of problems that classical and quantum computers, respectively, can solve efficiently. If BPP ≠ BQP, meaning the two classes differ, quantum computers can quickly solve some problems that classical computers cannot. Under that assumption, the authors wrote, only a quantum computer can solve the prediction problem efficiently.
Pseudoadvantages and noise
“A pseudoadvantage arises when a quantum protocol appears to outperform all classical approaches, only to be matched by a clever classical strategy that was previously overlooked,” the authors wrote. Among their examples are quantum recommendation systems, for which, they wrote, “classical algorithms could achieve comparable performance.”
For sensing, the authors noted that entangled sensors can in principle reduce their measurement error in proportion to 1/(NT), where N is the number of particles and T the total sensing time, compared with 1/(√N T) for unentangled sensors. For many sensing tasks, “even small amounts of noise can completely destroy the asymptotic quantum advantage,” the authors wrote, citing recent no-go theorems, proofs that rule out a capability under stated conditions. In that case, they wrote, the errors of entangled and unentangled sensors both fall in proportion to 1/√(NT).
For computation, the authors pointed to the threshold theorem, a result from the theory of quantum error correction. Quantum error correction spreads information across many physical qubits to catch and fix errors. Under the theorem, hardware with errors below a certain threshold can run “arbitrarily long quantum computations at reasonable overhead.”
