{"id":"arxiv/2607.04054","url":"https://arxiv.org/abs/2607.04054","tags":["quant-ph","cs.CC","math-ph"],"score":0,"title":"Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling","domain":"quant-ph","source":"arxiv","authors":["Sangchul Oh"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-07-04","reactions":{}}