Foundations of quantum mechanics · Theory (AI-assisted)
Quantum-Classical Separation in Probability Distribution Transport via Nonlocal Games
arXiv:2611.21840v1 ↗PDF ↗Submitted 16 November 2026
- Question
- Two probability distributions are often regarded as being in the same phase when a shallow circuit of local, locally reversible gates turns one into the other. Diffusion models in generative AI move between distributions in a similar way. If both endpoints are classical distributions, can local quantum dynamics connect them when no local classical stochastic dynamics can?
- Result
- Yes. On an open chain of \(n=4L+1\) bits with five evenly spaced question bits, the authors define distributions \(Q_n\) and \(P_n\) that a constant-depth, geometrically local quantum circuit maps exactly into each other in both directions. Any classical stochastic circuit whose input and output light cones have radius \(d\) with \(4(d+1)<L\), acting on any product distribution, produces an output at total-variation distance at least \(1/64\) from \(P_n\). Since \(Q_n\) itself has a radius-one classical sampler, the separation holds both for transporting \(Q_n\) to \(P_n\) and for generating \(P_n\). A general theorem turns any nonlocal game with a geometric all-versus-nothing obstruction into such a separation.
The paper in detail
In the theory of quantum phases, two states belong to the same phase when a constant-depth local circuit transforms one into the other. The same idea has been extended to mixed states and to classical probability distributions, with the extra requirement of local reversibility: every gate's action on the intermediate state can be undone by another local gate. Diffusion models in machine learning move between a simple distribution and a data distribution through roughly local denoising steps, and such transport can be run either by classical stochastic circuits or by quantum circuits acting on diagonal density matrices. The paper asks whether the two kinds of dynamics can disagree about which classical distributions are equivalent.
The construction lives on an open chain of bits \(y_0,\dots,y_{4L}\) with question bits \(q_0,\dots,q_4\) attached at sites \(0,L,2L,3L,4L\). The questions define the matrix \(M_q=A+\operatorname{diag}[x(q)]\) over \(\mathbb F_2\), where \(A\) is the path's adjacency matrix and \(x(q)\) places \(q_a\) at the marked sites. Its kernel has dimension at most one. When the kernel is spanned by \(u_q\), the source \(Q_q\) is uniform on strings with even parity \(u_q^{\mathsf T}y\), and the target \(P_q\) is uniform on strings whose parity equals a sign \(\lambda_q(u_q)\in\{0,1\}\); otherwise both are uniform. The source is easy to sample locally: draw random bits \(r\) and output \(z=M_qr\), whose \(j\)-th bit depends only on \(r_{j-1},r_j,r_{j+1}\).
The quantum circuit is a one-dimensional cluster-state measurement in disguise: Hadamards, a chain of CZ gates, an \(S^\dagger\) at each marked site controlled by its question bit, and Hadamards again. The questions choose whether a marked site is measured in the \(X\) or the \(Y\) basis, as in a nonlocal game. Conjugation maps each kernel parity \(Z^{u}\) to \((-1)^{\lambda_q(u)}Z^{u}\), so the diagonal state of \(Q_q\) becomes that of \(P_q\) exactly, and the inverse circuit undoes it. Classically, an output bit far from every marked site cannot depend on any question, and one near site \(p_a\) can depend only on \(q_a\). Six questions in Table 1 impose parity constraints that no such locally controlled assignment satisfies at once, which yields the \(1/64\) bound for any classical circuit with sublinear range.
Section V abstracts the recipe: start from any family of local unitaries \(C_q\) whose induced nonlocal game has a geometric all-versus-nothing obstruction, keep the Pauli-\(Z\) strings that \(C_q\) maps to diagonal operators, and define the source as uniform on the orthogonal complement and the target as uniform on the winning set. The source then has a local classical sampler, the transport is exact, and any \(d\)-local classical circuit is at total-variation distance at least \(p_*/2\), where \(p_*\) is the smallest probability of a hard question. The authors note that a target in the trivial quantum phase cannot give such a separation, because dephased local recovery maps would generate it classically.
Transferable methods
An all-versus-nothing parity contradiction for local responses
A classical circuit with light-cone radius \(d\) behaves like a team of players, one per output bit, each seeing at most one question bit. If the target distribution demands parity equations whose combined left-hand side cancels for every such strategy while the right-hand sides add up to 1, every strategy fails at least one hard question, and a coupling argument turns that into a fixed total-variation gap.
Call \(f:q\mapsto y\) locally controlled if \(y_j\) depends only on \(q_a\) when \(j\in N_a=B_{2d}(p_a)\) and on no question otherwise; for \(4d<L\) the neighbourhoods are disjoint. For each hard question \(q^{(\ell)}\), \(\ell=1,\dots,6\), every \(y\) in the support of \(P_{q^{(\ell)}}\) satisfies \[\bigoplus_ju^{(\ell)}_j\,y^{(\ell)}_j=\lambda^{(\ell)}.\] Table 1's kernels satisfy two cancellation rules: \(\bigoplus_\ell u^{(\ell)}_j=0\) at every site, and \(\bigoplus_{\ell:\,q^{(\ell)}_a=b}u^{(\ell)}_j=0\) for \(j\in N_a\) and either value \(b\).
XOR the six left-hand sides. A site outside every \(N_a\) has the same \(y_j\) for all six questions, so its contribution is \(y_j\bigoplus_\ell u^{(\ell)}_j=0\). A site in \(N_a\) has at most two values of \(y_j\), one for each value of \(q_a\), and grouping the questions by \(q_a\) makes each group vanish. Hence the XOR of the left-hand sides is 0 for every locally controlled \(f\), while \(\bigoplus_\ell\lambda^{(\ell)}=0\oplus1\oplus1\oplus1\oplus0\oplus0=1\), so at least one equation fails.
For a stochastic circuit on product randomness, a common seed \(\omega\) makes each map \(q\mapsto y(\omega,q)\) locally controlled while reproducing the conditional laws. If \(\eta_\ell\) is the failure probability at question \(\ell\), the pointwise statement gives \(\sum_\ell\eta_\ell\ge1\). Every failure lies outside the support of \(P_n\), and each question has probability at least \(1/32-\varepsilon\) under an output at distance \(\varepsilon\), so \[\varepsilon\ \ge\ \sum_\ell\mu(q^{(\ell)})\,\eta_\ell\ \ge\ \tfrac1{32}-\varepsilon,\] which gives \(\varepsilon\ge1/64\). Editorial check: recomputing the six kernels for \(L=3,5,7,9\) reproduces Table 1's signs and both cancellation rules.
How to reuse it
Mermin-type parity games embedded in a geometry give light-cone lower bounds for any task whose output must satisfy question-dependent parities. The same template underlies shallow-circuit separations for relation problems; here it bounds the total-variation error of local samplers.
Showing a circuit maps one diagonal state to another through its Pauli-Z expansion
A uniform distribution on a parity sector has a two-term Pauli expansion, \(2^{-n}(I+Z^u)\). To show that a unitary carries one such diagonal state to another, it suffices to track how the single string \(Z^u\) transforms, which for a Clifford circuit is a sign calculation.
Over \(\mathbb F_2\), \(M_qu=0\) reads \(u_{j-1}+x_ju_j+u_{j+1}=0\), so \(u_{j+1}=u_{j-1}+x_ju_j\) with \(u_{-1}=0\). The kernel vector is fixed by \(u_0\), and a nonzero solution exists exactly when the recurrence also satisfies the last equation. The sign is \[\lambda_q(u)=\sum_ju_ju_{j+1}+\tfrac12\sum_jx_ju_j\pmod 2,\] where the second sum is even on the kernel. Then \(\operatorname{diag}(Q_q)=2^{-n}(I+Z^{u_q})\) and \(\operatorname{diag}(P_q)=2^{-n}\bigl(I+(-1)^{\lambda_q(u_q)}Z^{u_q}\bigr)\).
Editorial sketch of the conjugation in \(C_q=H^{\otimes n}\,S^{\dagger x(q)}\,\prod_jCZ_{j,j+1}\,H^{\otimes n}\): the Hadamards turn \(Z^u\) into \(X^u\); the CZ chain attaches \(Z\) on the neighbours of each flipped site, giving \(X^uZ^{Au}\) up to sign; at each marked site with \(x_ju_j=1\), the phase gate turns \(X_j\) into \(\pm i\,X_jZ_j\), adding \(Z^{\operatorname{diag}(x)u}\). The \(Z\) part is \(Z^{M_qu}=I\) on the kernel, and the final Hadamards return \(X^u\) to \(Z^u\). The phase gates contribute a factor of modulus one built from \(i^{\sum_jx_ju_j}\), real because the sum is even on the kernel, and reordering neighbouring \(X\) and \(Z\) factors contributes further signs; the paper's Clifford calculation collects them into \((-1)^{\lambda_q(u)}\). Editorial check: a 13-qubit statevector simulation confirms the identity for all six questions.
The general construction keeps \(K_q=\{u:\ C_qZ^uC_q^\dagger\text{ is diagonal}\}\), a linear subspace. With \(Q_q\) uniform on \(K_q^\perp\), \[\operatorname{diag}(Q_q)=2^{-n}\sum_{u\in K_q}Z^u,\qquad C_q\operatorname{diag}(Q_q)C_q^\dagger=2^{-n}\sum_{u\in K_q}C_qZ^uC_q^\dagger=\operatorname{diag}(P_q),\] where \(P_q\) is uniform on the strings where every \(C_qZ^{u^{(\ell)}}C_q^\dagger\) has eigenvalue \(+1\). Controlling \(C_q\) by on-site question bits keeps the whole unitary \(\sum_q\ket{q}\bra{q}\otimes C_q\) geometrically local.
How to reuse it
Expanding diagonal states in Pauli-\(Z\) strings turns “does this circuit map distribution \(P\) to \(Q\)?” into stabilizer bookkeeping. The same move identifies which classical distributions a Clifford or near-Clifford circuit can transport exactly.
Context & limitations
Why it matters. Classical and quantum notions of “same phase” can differ even when every state involved is a classical distribution: the two distributions are one phase under local quantum dynamics but require classical range \(\Omega(n)\). The obstruction is the same parity contradiction behind Mermin's GHZ argument and the shallow-circuit separations of Bravyi, Gosset and König, now applied to the transport of distributions rather than to the solution of a computational task.
Limitations. Both distributions contain parity constraints spanning the whole system, so they have long-range conditional correlations and are not expected to form stable phases under generic local noise; whether a separation survives with finite correlation or Markov length is the stated open problem. The classical bound is a constant total-variation gap of \(1/64\), and the quantum transport is exact only with ideal gates. The classical model allows arbitrary product randomness but not correlated initial randomness. The authors state that part of the proof techniques were developed with GPT-5.6, GPT-6 Astra and Claude Opus 5.5, while the idea of building transport separations from nonlocal games was their own.