Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling

Random circuit sampling of bitstrings from a Haar-random quantum state is widely believed to be classically intractable, and has therefore been implemented as a primary benchmark for demonstrating quantum advantage.

Here, we challenge this premise by proposing an efficient classical frozen-tree sampling algorithm that exploits the conditional scale invariance of Haar-random quantum states [Oh, arXiv:2602.19448].

The frozen-tree sampler draws bitstrings of $n$ qubits in $O(n)$ time per sample.

Moreover, its output probability $p_F(x)$ is statistically identical to the probability $p_C(x)$ of a random quantum circuit, since both are independent instances of the same Dirichlet distribution.

Consequently, no statistical test acting on samples alone can distinguish the classical frozen-tree sampler from a quantum random circuit.

The claimed quantum advantage of random circuit sampling therefore does not withstand scrutiny: its hardness lies not in sampling from the Dirichlet distribution, which is classically efficient, but in identifying a specific circuit realization.