Sampling Advantage Claims: What Random Circuits and Boson Sampling Do and Do Not Prove
Why sampling?
Early on, theorists asked: what is the easiest task a quantum device could do that a classical computer plausibly cannot? The answer was not an answer at all, but a sample: produce random outputs drawn from the right probability distribution. Verifying one answer is easy for factoring, but sampling targets the device's raw behavior. A quantum chip can just run and listen. The price is that the outputs are random, so the result has no use, and checking correctness needs statistical tests. The big-picture debate is in supremacy and advantage. This page goes deeper on the logic.
Random circuit sampling (RCS)
RCS runs a random sequence of gates on many qubits and records the output bit strings. Google's 53-qubit Sycamore chip did this in about 200 seconds, and Google estimated 10,000 years for a classical supercomputer; the result appeared in Nature on October 23, 2019, per the reference. IBM countered that an optimized method on Summit could take about 2.5 days. Later, improved tensor-network methods were estimated to let Frontier handle the 53-qubit benchmark in about six seconds, per the same reference, which shows how fast classical bounds move. In China, the Zuchongzhi processor (October 2021) ran 56 qubits and was reported to raise classical cost by 2 to 3 orders of magnitude over Sycamore (more here).
On December 9, 2024, Google reported that its 105-qubit Willow chip completed an RCS benchmark in under five minutes, which it estimated would take Frontier about 10 septillion years, calling the estimate conservative. Remember the lesson of 2019: such estimates depend on the best known classical method at the time. In the same period Quantinuum researchers reported RCS on the H2 trapped-ion machine, up to 56 qubits with a 99.843 percent two-qubit gate fidelity, and noted that around 50 qubits is the scale where such experiments are mainly vulnerable to classical simulation (arXiv, June 2024; PRX 2025). See Willow and benchmarks.
Boson sampling
Boson sampling sends identical photons through a network of beam splitters and records where they land. Aaronson and Arkhipov proposed it in 2010 (published 2013). Output probabilities relate to matrix permanents, which are very hard to compute. Their abstract says that exact classical sampling would collapse the polynomial hierarchy to its third level, but the stronger, realistic result for approximate or noisy sampling rests on two unproven conjectures about the permanents of random Gaussian matrices. That is the shape of every sampling argument: strong evidence, built on conjectures.
USTC's Jiuzhang (December 2020, 76 photons, Gaussian boson sampling) was reported to be 2.5 billion years of classical work. Then came rebuttals: Oh, Fefferman and coauthors posted a classical tensor-network algorithm for simulating experimental Gaussian boson sampling whose cost drops under heavy photon loss. A conference abstract reports 10 million samples in about an hour on up to 288 GPUs, and the authors claim it outperforms the experiment, an author claim not independently settled. See Jiuzhang and Zuchongzhi.
What these experiments do prove
- Hardware reality. A programmable machine can create and control entangled states of many qubits or photons at a scale that stresses classical simulators.
- A hard-to-fake signature. Complexity-theory arguments say that efficient exact classical simulation of RCS would collapse the polynomial hierarchy, considered very unlikely (reference above).
What they do not prove
- Usefulness. RCS has no known practical use, and the reference notes it is a benchmark that "fails if just a single component of the computer is not good enough."
- Permanence. Claims are provisional, because classical algorithms and computers improve.
- Noise robustness at scale. Real, noisy devices differ from the ideal distributions in the theory, which is exactly where spoofing attacks work. Noisy approximate sampling is the weakest link in the hardness story.
- Fault-tolerant power. Beating a simulator at sampling says little about whether the same chip can run Shor's algorithm.
How to read the next claim
Ask: Is the task checkable? What classical methods were tried, and how recently? Is the claim about the ideal distribution or the noisy one? Is a useful task attached? Sampling milestones are healthy progress markers, not finish lines. The finish line for most people is error-corrected hardware, covered in the error correction state of play. Education only, not financial advice, and the QNT memecoin has no connection to Quantinuum Ltd.
Sources and further reading
- Wikipedia: quantum supremacy
- Wikipedia: boson sampling
- Aaronson and Arkhipov: The Computational Complexity of Linear Optics (arXiv)
- Oh et al.: Classical algorithm for simulating experimental Gaussian boson sampling (arXiv)
- Google: Meet Willow, our state-of-the-art quantum chip (Dec 9, 2024)
- DeCross et al.: The computational power of random quantum circuits in arbitrary geometries (arXiv, PRX 2025)
Reported as of 2026-10-09. Theory results are proven only under the stated assumptions, and experimental claims and classical rebuttals keep changing, so check the primary papers. Nothing here is financial advice and nothing here predicts the price of any asset. The QNT memecoin is independent of Quantinuum Ltd, the real company, and of every lab and researcher named on this page.
Frequently asked questions
What does random circuit sampling prove?
That a programmable device can complete a sampling task that is very costly to simulate with the best known classical methods. It does not prove usefulness and the classical cost estimates have dropped over time.
Was Google's 2019 claim refuted?
IBM argued a supercomputer could do it in about 2.5 days, and later tensor-network methods were estimated to be far faster. The experiment itself was not shown to be wrong, but the size of the gap was disputed.
Why is boson sampling hard to fake?
Its outputs relate to matrix permanents. The proof for approximate sampling relies on two unproven conjectures, and real experiments with photon loss have been targeted by classical algorithms.
Keep reading
- Quantum Supremacy vs Quantum Advantage Explained
What the terms quantum supremacy and quantum advantage mean, and why headline claims are often debated. - Zuchongzhi and Jiuzhang: China's Two Quantum Computer Families Explained
What USTC's superconducting Zuchongzhi chips and photonic Jiuzhang machines actually showed, and the honest caveats on the big speedup claims. - Google Quantum AI: Willow, Error Correction and Quantum Echoes
What Google's Willow chip and the Quantum Echoes result showed, why below-threshold error correction matters, and what is still unproven.
All Quantum computing guides | Back to top | Search the site
Main pages: Quantum computing explained | Quantum and crypto | Companies | Quantum news | Glossary