Revision 1

Accepted · first revision · record

Title: Finite-size boundary of classical hardness for noisy random circuit sampling
Plain: At a fixed error rate per gate, very large random circuits become easy for classical computers, yet the experiments done so far are believed to be hard. Where the crossover lies, in qubit number, depth and noise rate, is not known.
Precise: 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}$).
Settled by: Classical algorithms and complexity bounds that place each published experiment on a quantified side of the boundary.
Kind: well-posed
Answer type: value
References: (empty)
Literature status: contested
Status note: 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.
Posed since: (empty)