An Unbounded Separation of Almost-Quantum and Commuting-Operator Correlations in Zero-Error Communication

Abstract

Almost-quantum correlations form the $\mathtt{1+AB}$ level of the Navascués--Pironio--Acín hierarchy. They strictly contain the quantum set, are characterized by a single semidefinite program, arise in Sorkin's quantum measure theory, and satisfy several principles proposed to single out quantum theory. We show that they are nevertheless unboundedly stronger than quantum correlations in a zero-error communication task. Alice and Bob receive labels $s,t\in[N]$, $N\ge3$; after one bit from Alice, Bob must decide whether $s=t$, never erring but allowed to abstain. For every model of quantum correlations, from finite-dimensional tensor products to commuting operators, the optimal worst-case probability of a conclusive answer is exactly $1/N$, the value attained with shared randomness, so the bound does not depend on the resolution of Tsirelson's problem. An explicit family of almost-quantum correlations attains $1/19$ for every $N$. For certificates of equality from binary-outcome boxes, we solve the underlying semidefinite programs in closed form. The almost-quantum optimum equals $N^2/(17N^2-80N+64)$ for $N\ge8$ and tends to $1/17$. The first level of the hierarchy, which coincides with the set singled out by macroscopic locality, attains $N/[8(N-2)]$, which tends to $1/8$; its optimal boxes lie outside the almost-quantum set for every $N\ge5$. For longer messages, entanglement saves at most one bit over shared randomness, whereas almost-quantum correlations reduce the one-way zero-error cost of deciding equality of $n$-bit strings from $n$ bits to at most $13$. The quantum bound also yields a linear witness of post-quantumness on a face of the nonsignalling polytope.

The paper asks how much almost-quantum (AQ, NPA level $1+AB$) correlations can outperform quantum correlations in zero-error communication. Alice and Bob receive labels $s,t\in[N]$; after one classical bit from Alice, Bob must decide whether $s=t$, allowing abstention but no errors. Performance is the worst-case probability of a conclusive answer. For every $N\ge3$, the optimal efficiency is exactly $1/N$ with shared randomness, entanglement, or commuting-operator correlations. Explicit binary-output AQ boxes instead achieve efficiency $1/19$ for every $N$, giving an unbounded ratio of at least $N/19$. For the restricted problem of certifying equality through a single joint outcome of a binary-output box, the AQ optimum is $1/N$ for $N\le8$ and $N^2/(17N^2-80N+64)$ for $N\ge8$, approaching $1/17$. The corresponding NPA level-1 optimum is $N/[8(N-2)]$ for $N\ge4$, approaching $1/8$. For equality of $n$-bit strings with abstention probability at most $1/2$, one-way classical communication costs exactly $n$ bits with quantum resources, versus at most $13$ with AQ resources. The quantum bounds use sequential-measurement packing and zero-error support constraints, extended to commuting operators. AQ membership is established through explicit Gram-vector constructions; symmetry-reduced semidefinite programs have matching analytic primal and dual certificates. The unrestricted AQ one-bit optimum remains open, as do possible improvements from larger outcome alphabets or message-dependent settings. The separation relies on exact zeros: its associated linear post-quantumness witness applies only on a specified nonsignalling face and establishes neither noise tolerance nor quantitative distance from quantum correlations.