Finite-size boundary of classical hardness for noisy random circuit sampling

50

No. 676 in all physics · No. 33 in Quantum Information and Foundations

Non-expert version

For random circuit sampling with $n$ qubits, depth $D$ and per-gate error $\epsilon$, Aharonov et al. (2023) give a classical algorithm polynomial in $n$ at constant $\epsilon$, with cost exponential in $1/\epsilon$. Determine the best classical cost to reach the experimental linear cross-entropy fidelity $F_{\mathrm{XEB}} \sim \exp(-\epsilon n D)$ as a function of $(n, D, \epsilon)$, and locate the easy-hard boundary for parameters of current experiments ($n \sim 70-100$, $\epsilon \sim 10^{-3}$).

What would settle it

Classical algorithms and complexity bounds that place each published experiment on a quantified side of the boundary.

Status in the literature

Unverified note: it names recent work and was partly written without a live literature search; it awaits a check by an editor.

Google Quantum AI (Nature 2024) reported a noise-driven phase transition in random circuit sampling and placed its experiment in the hard phase; classical simulation efforts continue.

No solutions, ideas or subproblems yet.

How results are checked

See also

Comments (0)

Comments are not records: they are not signed, stamped or logged. How comments work

No comments yet.

Sign in to comment.

Details, signature and history
Kind
Well-posed question
Answer
Value
Topic review
R. Orus, Tensor networks for complex quantum systems, Nature Reviews Physics, 2019. Link
Record
Revision 1 · imported from the seed collection · compiled by AI, not yet reviewed by an editor

Proof

Fingerprint
8ba4e7cd08aa…
Public log
Entry 1,974, in checkpoint 2,123
In the log by
Block 969,698, 2026-10-03

This text was in the PubPhys log by that date. The date says nothing about when the problem was first posed.

History