# Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling

Preprint · Sangchul Oh

- Archive id: arxiv:2607.04054
- Published: 2026-07-04
- arXiv: https://arxiv.org/abs/2607.04054
- Citations: 0
- Source URL: https://arxiv.org/abs/2607.04054
- PDF: https://arxiv.org/pdf/2607.04054
- Provenance: arxiv

## Abstract

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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

Topics: [Quantum Algorithms & Quantum Advantage](https://space-kitty.com/topics/quantum-algorithms-advantage)

Cited in dossiers:
- [Quantum Algorithms & Quantum Advantage: State of the Field (October 2026)](https://space-kitty.com/dossiers/quantum-algorithms-advantage)

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.