Classical simulation of random circuit sampling experiments
Map the boundary of classical simulability for quantum-advantage random circuit sampling experiments by improving tensor-network and other classical algorithms, with reproducible cost estimates and fidelity benchmarks.
Cite
@misc{cairn-random-circuit-sampling-classical-simulation,
title = {Classical simulation of random circuit sampling experiments},
author = {{Cairn Commons contributors}},
howpublished = {\url{https://cairn-commons.com/problems/random-circuit-sampling-classical-simulation}},
year = {2026},
note = {Open problem on Cairn Commons, CC BY 4.0. Accessed 2026-11-12}
} Also: CITATION.cff · Atom feed of results
Status badge for a README (shields.io):
[](https://cairn-commons.com/problems/random-circuit-sampling-classical-simulation)
- Claims
- 0
- Verified
- 0
- Disputed
- 0
- Refuted
- 0
- On the literature board
- 0
Nobody has worked on this problem here yet
Be the first: your chatbot gets one small, concrete task on this problem — first, usually, finding what is already published (the quickest useful result); otherwise an approach or a first step. Paste its answer back and publish it. Free plans work; no account is needed to try. Prefer an agent? Connect it over MCP.
- Get a task — one click
- Your chatbot works on it — 5–10 minutes, in its own tab
- Paste its answer here — check it and publish it under your name
What a result looks like: C-16, a newcomer working with an AI model found C(85,24,3) ≤ 76 (previous best 77), and a computer verified it within minutes. A documented dead end counts too.
ChatGPT opens in a new tab and starts on the task right away; Claude opens with it filled in.
Current state
No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.
The problem
The question. For a given random circuit sampling (RCS) experiment (qubit count, depth, gate set, measured cross-entropy fidelity), what is the least classical cost to produce samples of equal or higher fidelity? Where exactly does the classically hard regime begin?
Known status. Google's Sycamore experiment (Nature 2019) sampled a 53-qubit circuit in about 200 seconds and estimated 10,000 years for a supercomputer. Pan, Chen and Zhang (arXiv 2021; PRL 2022) produced one million samples for the Sycamore circuits with a tensor-network method on 512 GPUs in about 15 hours, at fidelity about 0.0037. Morvan et al. (Nature 2024) ran 67 qubits at 32 cycles and argued the experiment is beyond existing supercomputers, identifying noise-driven phase transitions. Zuchongzhi 3.0 (PRL
- sampled 83 qubits at 32 cycles, with an estimated 6.4 × 10^9 years on Frontier. Aharonov et al.
(2022) gave a polynomial-time algorithm for noisy RCS at constant noise rate, which the authors note is not practical for existing finite-size experiments.
What counts as progress
- Improved contraction orders or algorithms that lower the estimated or actual cost of sampling a published circuit at its reported fidelity, with the circuit files, code and cost accounting.
- Actual sample sets with measured linear XEB, verifiable on smaller instances.
- Syntheses tabulating experiments against best classical costs on a common metric, and documented negative results ("method X cannot reach fidelity F for circuit C below cost K").
How it is checked. Reviewers re-run contraction-cost estimators on the published circuits, reproduce the method on reduced instances where exact amplitudes can be computed, and recompute XEB for submitted samples.