🔢 mathematics

Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling

This paper challenges the premise of quantum advantage in random circuit sampling by proposing an efficient classical "frozen-tree" algorithm that generates statistically indistinguishable samples in linear time, arguing that the true computational hardness lies in identifying a specific circuit realization rather than sampling from the underlying Dirichlet distribution.

Original authors: Sangchul Oh

Published 2026-07-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Sangchul Oh

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: The "Quantum Magic" Challenge

Imagine a high-stakes game of "Guess the Pattern." Scientists have claimed that quantum computers can do something impossible for regular computers: they can generate a specific type of random string of 0s and 1s (like a digital coin flip sequence) so complex that no classical computer could ever predict or copy it. This task is called Random Circuit Sampling (RCS), and it has been used as the main proof that quantum computers are superior to classical ones.

The author of this paper, Sangchul Oh, says: "Wait a minute. You don't need a quantum computer to do this. I can do it on a regular laptop, and I can do it faster."

The Core Idea: The "Frozen Tree"

To understand how the author does this, let's use an analogy of a giant, magical tree.

The Quantum Claim: When a quantum computer runs a random circuit, it creates a "forest" of possibilities. Every time you ask it for an answer, it picks a path through this forest. The claim is that this forest is so chaotic and tangled that a classical computer (like your laptop) cannot figure out the rules of the forest to pick the same paths.
The Author's Discovery: The author found that this "chaotic forest" actually has a hidden, perfect structure. It looks like a binary tree (a tree where every branch splits into two).
- At the top (the root), the tree splits.
- At the next level, those branches split again.
- This continues until you reach the bottom leaves, which represent the final 0s and 1s.

The secret sauce is a rule called "Conditional Scale Invariance." In plain English, this means the tree is self-similar. The way the tree splits at the very top looks statistically identical to how it splits halfway down, and how it splits right before the leaves. It's like a fractal: the whole pattern is repeated in every small piece.

The "Frozen" Trick

Here is the clever part. The author realized that to simulate this quantum tree, you don't need to calculate the whole thing at once. You just need to build it as you walk through it.

The Walk: Imagine you are walking from the top of the tree to a leaf. At every fork in the road, you have to decide: "Do I go left (0) or right (1)?"
The "Frozen" Moment: In a real quantum experiment, these decisions are made by the quantum machine. In the author's classical method, when you arrive at a fork for the first time, you flip a special coin to decide the split ratio (how likely you are to go left vs. right).
- Crucially: Once you flip that coin and decide the ratio for that specific fork, you "freeze" it. You write it down.
- If you (or anyone else) ever visit that same fork again, you use the exact same frozen ratio. You don't flip the coin again.

Because the tree is "frozen" in this way, the author can generate these random strings incredibly fast. The paper claims this takes O(n) time, which means if you double the number of bits, you only double the work. It's linear and efficient.

The "Statistical Twin" Argument

The paper makes a very strong claim about the results:

The Quantum Result: A quantum computer produces a list of numbers based on a specific random circuit.
The Classical Result: The "Frozen-Tree" algorithm produces a list of numbers based on the tree structure.

The author proves mathematically that both lists come from the exact same statistical family (called a Dirichlet distribution).

Think of it like two different bakers making chocolate chip cookies.

Baker A (Quantum) uses a secret, chaotic oven.
Baker B (Classical) uses a precise, frozen mold.

The paper argues that if you hand a blindfolded judge a cookie from Baker A and a cookie from Baker B, they cannot tell the difference. The cookies (the data) are statistically identical.

Why This Matters (According to the Paper)

Currently, scientists say, "Look! The quantum computer produced these weird, complex patterns that a classical computer couldn't make. Therefore, the quantum computer is winning."

The author says: "That's not true. We just showed that a classical computer can produce those exact same patterns instantly using the Frozen-Tree method."

If a classical computer can mimic the quantum output perfectly, then the "Quantum Advantage" (the idea that the quantum computer is doing something the classical one can't) disappears for this specific test.

The "Noise" Factor

Real quantum computers are messy; they make mistakes (noise). The paper also shows that the Frozen-Tree method can easily mimic these mistakes. Whether the quantum computer has "depolarizing noise" (random static), "amplitude damping" (energy loss), or "readout errors" (misreading the result), the classical Frozen-Tree can simulate those errors perfectly.

The paper concludes that no test based solely on the final list of numbers (the samples) can prove a quantum computer is doing something special. The "hardness" isn't in the randomness itself; it's just in figuring out which specific tree the quantum computer built. But since the statistical results are the same, the benchmark fails.

Summary in One Sentence

The paper claims that the "magic" of random quantum circuits is actually just a hidden, self-similar tree structure that a classical computer can replicate perfectly and instantly by "freezing" its decisions as it walks down the tree, meaning the current tests for quantum advantage are flawed.

Technical Summary: Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling

Problem Statement
Random Circuit Sampling (RCS) is currently regarded as a primary benchmark for demonstrating quantum advantage, where a quantum computer samples bitstrings from a Haar-random quantum state generated by a random circuit. The prevailing assumption is that this task is classically intractable because random quantum states are highly entangled and lack exploitable patterns, exhibiting statistical properties such as exponential output distributions, linear cross-entropy benchmark (XEB) scores, heavy output generation, and anti-concentration. The paper challenges the premise that these statistical properties constitute evidence of quantum advantage, arguing that the hardness of RCS is often conflated with the difficulty of identifying a specific circuit realization rather than the difficulty of sampling from the underlying probability distribution.

Methodology: The Frozen-Tree Sampler
The authors propose a classical algorithm, the frozen-tree sampler, which exploits the exact conditional scale invariance of Haar-random quantum states. The core theoretical insight is that the probability $p(x) = |\langle x|\psi\rangle|^2$ of finding a bitstring $x$ in a random $n$ -qubit state can be represented as a binary tree walk.

Tree Representation: The joint probability is decomposed via the chain rule into a product of conditional probabilities:
$p(x) = \prod_{k=1}^n R_{x_{<k}}^{1-x_k} (1 - R_{x_{<k}})^{x_k}$
where $x_{<k}$ is the prefix of the first $k-1$ bits. The "branch ratios" $R_u$ at each node $u$ are independent random variables drawn from a Beta distribution:
$R_u \sim \text{Beta}(K, K), \quad \text{where } K = 2^{n-|u|-1}.$
This structure arises from the aggregation property of the Dirichlet distribution and the conditional scale invariance of random states.
Sampling Algorithm: The sampler performs a random walk from the root to a leaf ( $n$ steps).
- Lazy Generation: Instead of pre-computing all $2^n - 1$ branch ratios, the algorithm generates them on demand. When a node $u$ is visited for the first time, a ratio $R_u$ is drawn from $\text{Beta}(K, K)$ and "frozen" (stored or deterministically regenerated via a pseudo-random function keyed by the node identity).
- Efficiency: The algorithm draws one bitstring in $O(n)$ time. For $M$ samples, the total runtime is $O(Mn)$.
- Noise Modeling: The framework naturally incorporates noise channels (global depolarizing, amplitude damping, readout error) by applying affine transformations or confusion matrices to the tree structure or the final bitstring, maintaining the $O(n)$ cost.

Key Results

Statistical Identity: The authors prove that the output probability $p_F(x)$ of the frozen-tree sampler and the output probability $p_C(x)$ of a random quantum circuit are independent realizations of the same flat Dirichlet distribution on the $(N-1)$ -simplex ( $N=2^n$ ). Consequently, $p_F(x) \stackrel{d}{=} p_C(x)$ .
Indistinguishability: Because the distributions are statistically identical, no statistical test acting solely on the sampled bitstrings (such as XEB, heavy output generation, or anti-concentration tests) can distinguish the classical frozen-tree sampler from a quantum random circuit.
Performance: The sampler generates $10^7$ samples for $n=1000$ qubits in seconds on a standard GPU. This contrasts with the Google Sycamore processor, which required ~200 seconds to collect $\sim 10^6$ samples at $n=53$ .
Noise Reproduction: The frozen-tree sampler exactly reproduces the statistical distortions caused by noise (e.g., the suppression of the exponential peak and tail behavior under amplitude damping) observed in experimental data, without requiring empirical estimation from finite samples.

Significance and Claims
The paper claims that the quantum advantage of RCS does not withstand scrutiny when the task is defined as sampling from the Dirichlet distribution of a random state.

The "hardness" of RCS lies not in the sampling process itself—which is classically efficient at $O(n)$ per sample—but in the specific mapping from a circuit to its amplitudes.
Since the frozen-tree sampler reproduces all standard verification metrics (exponential distribution, XEB, etc.) classically and efficiently, these metrics cannot serve as standalone evidence of quantum advantage.
The authors conclude that RCS, as currently verified, is not a sound stand-alone benchmark for quantum advantage. They note that any residual advantage must reside in the circuit-specific realization, a topic addressed in their companion work regarding a "Hurwitz–frozen-tree circuit" that admits an efficient classical sampler.