quant-phNov 16, 2026

Quantum-Classical Separation in Probability Distribution Transport via Nonlocal Games

Authors: Fangjun Hu, Xun Gao

Organizations: QuEra Computing Inc., 1380 Soldiers Field Road, Boston, MA 02135, USA · JILA and Department of Physics, University of Colorado Boulder, Boulder, CO 80309, USA

Abstract

In many-body physics and generative artificial intelligence, locality provides a natural notion of phase equivalence: two quantum states or classical probability distributions are regarded as in the same phase when local dynamics can reversibly transform one into the other. This raises a fundamental question: can local quantum dynamics transport classical probability distributions in ways that local classical dynamics cannot? We establish a quantum-classical separation in distribution transport: two classical distributions can be connected exactly and reversibly by a constant-depth local quantum circuit, whereas classical stochastic transport requires a substantially larger spatial range. We demonstrate this separation explicitly on a one-dimensional chain and develop a general construction principle on graphs, based on nonlocal games. Moreover, the source distribution can itself be generated by a simple local classical process, establishing a quantum advantage in distribution generation as well. Our results reveal a fundamental distinction between classical and quantum local reversibility, even when both the initial and final states are entirely classical.

Figures & tables

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

Aug 5, 2026

Representational separation between unitary and channel quantum generative models via shared classical randomness at shallow depth

Near-term quantum hardware limits circuit depth and often imposes geometrically local connectivity for quantum generative models, restricting the output distributions accessible to shallow unitary Born models. Introducing stochasticity into a unitary quantum Born model can improve the empirical generative performance of the resulting channel model and, for a restricted small-scale architecture, has been proven to represent a strictly larger family of distributions than its unitary counterpart. However, whether such randomness provides a provable separation at fixed shallow depth for arbitrarily large systems has remained open. Here, we show that shared classical randomness, a comparatively weak resource from entanglement theory, is sufficient to establish such a strict scalable representational separation over the corresponding shallow unitary Born model. More specifically, we augment bounded-connectivity shallow unitary circuits, followed by computational-basis measurements, with spatially separated local Pauli operations, whose joint application is controlled by a single classically sampled random bit. The resulting shallow-depth channel model generates long-range correlations in the classical output distribution that no purely unitary shallow-depth model with bounded connectivity can reproduce. For one-dimensional nearest-neighbour architectures, reproducing such distributions with a purely unitary model can require depth Ω(N)Ω(N) in the worst case. We further show that measurement-based quantum computation (MBQC) provides a natural implementation of the required shared classical randomness through suitable adaptation of the random measurement outcomes. Numerical experiments on MBQC-based generative models support the analytical results.
Aug 25, 2026

Provable Quantum-Classical Separation for Continuous Gibbs Sampling

We prove the first quantum-classical separation for a sampling problem over a continuous domain. For a class of Gibbs states p∝e−βEp\propto e^{-βE} on the torus Td\mathbb{T}^d with smooth (ss-Gevrey) potential and barrier amplitude α=eβΔα=e^{βΔ}, where Δ=max⁡E−min⁡EΔ= \max E-\min E, every classical algorithm querying the value, gradient, or any higher-order derivatives of the log-density requires Ω(α)Ω(α) queries to sample at constant accuracy in total variation distance, while a quantum algorithm based on quantum singular value thresholding and temperature annealing samples with O~(α)\tilde{O}\left(\sqrtα\right) queries to an oracle for the gradient. The advantage is quadratic in the barrier amplitude, which becomes exponential in the dimension, eΩ(d)e^{Ω(d)}, at low temperature. The classical bound is information-theoretic, holding for every classical algorithm with query access to the Gibbs potential and its derivatives at any order.
Aug 12, 2026

A Quantum/Classical Example Oracle Separation for Making Things Up

Consider two PAC learning algorithms, both having access to quantum computation, but differing in the types of examples they obtain: one is provided with classical samples, while the other is given quantum samples. Are there any learning tasks that can be efficiently performed by the latter, but not by the former? This question, the focus of our work, is surprisingly still open. Our main result is to show that relative to an oracle, there are distributions that can be efficiently generated by a quantum learner with access to quantum samples, but not by a quantum learner with access to only classical samples, making progress to answering this question in the affirmative.