Researchers Adam Bene Watts at the Institute for Quantum Computing, University of Waterloo, and Natalie Parham of Columbia University and Perimeter Institute for Theoretical Physics have demonstrated a clear advantage for quantum circuits when sampling from specific probability distributions. This establishes a logarithmic difference in computational depth, even when classical circuits utilize a limited number of input bits; specifically, k times n plus n to the power of delta i.i.d.

Bernoulli random variables with entropy 1/k. This work directly addresses a challenge posed by Bravyi, Gosset, and Koenig, confirming quantum advantage extends to input-independent sampling tasks. The researchers published their findings in Quantum, volume 10, page 2188, with DOI 10.22331/q-2026-.

Distribution D_n Defines Quantum Sampling Task

A quantum circuit can approximate a specific probability distribution using fewer resources than its classical counterpart, clarifying the potential for near-term quantum advantage. This work establishes a concrete resource gap, revealing that any classical circuit attempting to approximate distribution D_n to a useful degree requires a minimum of “k times n plus n to the power of delta i.i.d. The core of this advantage lies in the computational depth required to achieve equivalent results.

The team’s quantum circuit can sample from D_n while classical circuits demand a depth of to accomplish the same task, even when those classical circuits are designed with bounded fan-in gates. This logarithmic difference in computational depth is a key indicator of quantum speedup, suggesting that certain sampling problems are inherently better suited to quantum computation.

The distribution D_n itself was inspired by earlier work from Viola, who identified a related distribution that also resists efficient approximation by constant-depth classical circuits. However, the current research provides a more rigorous and unconditional proof of quantum advantage, meaning it doesn’t rely on any unproven assumptions about the limits of classical computation. This is achieved through the construction of a specific quantum circuit architecture tailored to efficiently sample from D_n, while simultaneously establishing a lower bound on the resources required for classical circuits to achieve comparable performance.

This research shows that constant-depth quantum circuits can sample from certain probability distributions that comparable constant-depth classical circuits cannot reproduce, even approximately. Here, constant depth means that the number of computational steps remains fixed, even as the size of the system grows.

Earlier work by Bravyi, Gosset, and Koenig showed that constant-depth quantum circuits outperform constant-depth classical circuits on a task with an externally supplied input. They asked whether a quantum advantage could also exist for a task with no external input, where the goal is simply to generate samples from a specified distribution. We answer this question affirmatively, with a restriction on the amount of randomness available to the classical circuit.

Achieving a computational advantage with shallow circuits is a significant step towards realizing quantum technologies that can outperform classical computers in the near term. The researchers also demonstrated a separation between constant-depth quantum circuits with advice and classical circuits, even when the classical circuits have access to an unbounded number of random inputs. This work also connects to broader efforts in quantum machine learning.

Efficiently sampling from complex probability distributions is fundamental to many machine learning algorithms, and the demonstrated quantum advantage could potentially lead to new and improved learning techniques. The team’s findings are detailed in their paper, which includes a discussion of related work.

The researchers emphasize that their results provide an “unconditional proof that constant-depth quantum circuits can sample from distributions that can’t be reproduced by constant-depth bounded fan-in classical circuits, even up to additive error”. This finding, they argue, solidifies the potential for quantum computers to tackle problems that are intractable for even the most powerful classical machines.

Bravyi-Gosset-Koenig Work Inspires Shallow Circuit Proof

Recent advances in quantum computing demonstrate a clear advantage for shallow circuits in specific computational tasks, building upon foundational questions first raised by Bravyi, Gosset, and Koenig. Their earlier work highlighted quantum speedups in search problems achievable with circuits of limited depth; this new research extends that concept to the realm of input-independent sampling, confirming a quantum advantage even without externally supplied input. The team’s work centers on demonstrating that a quantum computer can efficiently sample from distribution D_n, while any classical circuit attempting the same task requires a significantly greater computational depth.

Specifically, the researchers proved that any classical circuit needing to approximate D_n with a total variation distance error must process at least k times n plus n to the power of delta i.i.d. Bernoulli random variables with entropy 1/k, and even then will require a depth of Ω(log log n).

This logarithmic difference in depth is a key finding, indicating a substantial resource gap between quantum and classical approaches for this particular sampling problem. The researchers emphasize that this separation holds true even when classical circuits are allowed to utilize a bounded fan-in, a common constraint in circuit design. The distribution D_n used in the study was carefully chosen to highlight the differences between quantum and classical computation.

It is designed such that while it can be efficiently sampled by the quantum circuit, classical circuits require increasingly complex operations to achieve the same level of accuracy. This work also builds on previous research demonstrating quantum advantage in areas like quantum supremacy and shallow circuit complexity, including studies by Håstad and Razborov on lower bounds for circuit size and depth.

The researchers published their findings in Quantum, volume 10, page 2188, detailing the construction of the quantum circuit and the mathematical proof of the separation between quantum and classical performance. The implications of this work extend beyond theoretical computer science, potentially influencing the development of new quantum algorithms and applications. While the current research focuses on a specific distribution, the underlying principles could be applied to other problems where efficient sampling is critical.

Unconditional Quantum Advantage Achieved for Sampling

“We prove this separation unconditionally, without relying on unproven assumptions about the power of classical computation,” explained the authors in their published paper. This means the advantage isn’t contingent on any future breakthroughs in classical algorithms, but is inherent in the fundamental differences between the two computational paradigms.

The distribution D_n is not merely a theoretical construct; it serves as a benchmark for assessing the power of quantum circuits and identifying the specific conditions under which they outperform their classical counterparts. Further research is planned to explore the limits of this quantum advantage and to investigate whether similar separations can be found for other distributions and computational tasks, and the team is also interested in developing new quantum algorithms that can leverage this advantage to solve real-world problems.

👉 More information
🗞 Unconditional Quantum Advantage for Sampling with Shallow Circuits
✍️ Adam Bene Watts and Natalie Parham
🧠 DOI: https://quantum-journal.org/papers/q-2026-08-12-2188/

More like this