Finite-size boundary of classical hardness for noisy random circuit sampling
In plain words
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 statement
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
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.