Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.41448

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

Rafiuddin Gazi, Biswadeep Chatterjee, Jayashree Karmakar, Ram Krishna Patra, Manik Banik, Anandamay Das Bhowmik

quant-phSubmitted Oct 30, 2026• Announced Nov 2, 2026• 1 citation
arXivHTMLPDF

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.

AI Summary

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.

Little sign of AI-generated textAI use disclosed
A large language model (Claude, Anthropic) was used to assist with editing the text, simplifying the analytic certificates in Sections~\ref{sec:aq} and~\ref{sec:vec}.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
35 pages, single column, 2 figures; comments are welcome

Related papers

A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations

Miguel Navascués, Stefano Pironio, Antonio Acín

We are interested in the problem of characterizing the correlations that arise when performing local measurements on separate quantum systems. In a previous work (Navascués et al 2007 Phys. Rev. Lett. 98 010401), we introduced an infinite hierarchy of conditions necessarily satisfied by any set of quantum correlations. Each of these conditions could be tested using semidefinite programming. We present here new results concerning this hierarchy. We prove in particular that it is complete, in the sense that any set of correlations satisfying every condition in the hierarchy has a quantum representation in terms of commuting measurements. Although our tests are conceived to rule out non-quantum correlations, and can in principle certify that a set of correlations is quantum only in the asymptotic limit where all tests are satisfied, we show that in some cases it is possible to conclude that a given set of correlations is quantum after performing only a finite number of tests. We provide a criterion to detect when such a situation arises, and we explain how to reconstruct the quantum states and measurement operators reproducing the given correlations. Finally, we present several applications of our approach. We use it in particular to bound the quantum violation of various Bell inequalities.

arXiv:0803.4290•New Journal of Physics•Jul 8, 2008•789 citations

Almost-Quantum Correlations Violate Information Causality

Anandamay Das Bhowmik, Manik Banik

Information causality (IC) posits that communicating m classical bits cannot give the receiver access to more than m bits of information about the sender's independent data. Although IC holds in quantum theory and excludes a broad class of supra-quantum correlations, its validity for the almost-quantum set has remained open. This semidefinite relaxation of the quantum set satisfies nontrivial communication complexity, no advantage for non-local computation, macroscopic locality, local orthogonality, and numerical evidence has suggested that it may also satisfy IC. Here we show that almost-quantum correlations violate IC, and do so without bound. Unlike earlier violations of IC, which rely on biased guesses, ours is driven by zero-error certificates: each is rare but never wrong, carries information linear in its probability, and vouches for many of the sender's bits at once. This establishes a sharp dichotomy: either IC is a valid physical principle that excludes these correlations, or any nonsignalling theory realizing them admits no mutual information obeying consistency, data processing and the chain rule. In the latter case, we discuss why the chain rule is the natural property to relinquish, and how this possibility relates to histories-based formulations and to locality defined relative to the state rather than presupposed in a fixed spacetime.

quant-pharXiv:2610.41444•Nov 2, 2026•1 citation

A Machine-Verified Separation of the Quantum and Almost-Quantum Sets in the 3322 Bell Scenario

Caleb Weiner

We give exact rational certificates for two results in the bipartite Bell scenario with three two-outcome measurements per party. First, the maximum of the $I_{3322}$ (Froissart) functional over the almost-quantum set -- the $1{+}AB$ level of the Navascues-Pironio-Acin (NPA) hierarchy -- is certified to lie between $0.2514708838$ and $0.2514709016$ (width $<2\times10^{-8}$), in the normalization with classical bound $0$ and quantum maximum $\approx0.2508754$; to our knowledge no value for this landmark had been published. Second, we exhibit a single exact rational behavior $T^{*}$ carrying certificates in both directions: a rational moment matrix proving $T^{*}$ almost-quantum, and a rational dual object proving that every NPA level-2 completion of $T^{*}$ requires slack at least $q=4.5934\times10^{-4}$, so that $T^{*}$ is not quantum. The strict inclusion $Q\subsetneq\tilde{Q}$ in the minimal three-setting scenario is thereby established end-to-end with no reliance on floating-point computation. Anatomically, the witness is locally quantum: all nine of its $2\times2$ correlator subtables pass the Tsirelson-Landau-Masanes criterion, so its non-quantumness is irreducibly a three-setting phenomenon, concentrated in ordering-dependent pseudo-moments coupling each party's third setting to the other's first two; the level-2 certificate is equivalently an exact sum-of-squares identity that any quantum state values nonnegatively and the witness is forced to value at $-q$. The certificates follow the rational rounding-projection-lifting programme recently developed for noncommutative optimization; for NPA moment matrices in canonical form the required projection reduces to a per-moment uniform shift, making certification essentially free at these sizes, and we work the programme in both the feasibility and infeasibility directions on one witness. Machine-checkable certificates and verifiers requiring only the Python standard library accompany the paper. Files in this record: the paper (PDF); exact rational certificates for both theorems (i3322_1AB_certificate.json, i3322_level2_infeasibility_certificate.json); standalone verifiers requiring only the Python 3 standard library (verify_i3322_certificate.py, verify_level2_certificate.py); and the generating scripts (certify_landmark.py, certify_level2.py). See README_ancillary.txt for which artifact proves which theorem and how to run the verifiers. v2: corrects the mechanism attribution in Sec. 5 (anatomy) and adds the archive reference to Data Availability; theorems, certificates, and verifiers unchanged.

•Jul 24, 2026•3 citations

Semidefinite block-matrix relaxations for computing quantum correlations

Nicola D'Alessandro, Carles Roch i Carceller, Armin Tavakoli

Bounding the correlations predicted by quantum theory is an important challenge in quantum information science. Today's leading approach is semidefinite programming relaxations, but existing methods still cannot account for many relevant types of constraints. Here, we propose a semidefinite relaxation methodology that can incorporate a breadth of constraints needed in various quantum correlation problems, thereby generalising the seminal Navascués-Pironio-Acín hierarchy. It yields useful results at reasonable computational cost. We showcase the methodology and its features by using it to address five different quantum information problems. These are (i) entanglement witnessing from imperfect measurement devices, (ii) certifying measurements from fidelity-constrained sources, (iii) computing dimensionality in genuine multi-particle entangled states, (iv) benchmarking dimensionality for state preparation devices, and (v) finding uncertainty relations for nearly anti-commuting observables. These applications reflect both the usefulness and versatility of the methodology, as well as its potential for broader relevance in the field.

quant-pharXiv:2603.19388•Physical Review X•Mar 23, 2026•5 citations

Semidefinite programming hierarchies for quantum error correction

Mario Berta, Francesco Borderi, Omar Fawzi +1 more

We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form $\mathrm{Tr}\big[M(X\otimes Y)\big]$, maximized with respect to semidefinite constraints on $X$ and $Y$. Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans.~Inf.~Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brand\~ao & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from $O(d^{k/2})$ to $\mathrm{poly}(d,k)$, where $d$ denotes local dimension and $k$ the number of copies.

•Jan 23, 2019•5 citations

Bounding the Sets of Classical and Quantum Correlations in Networks

Alejandro Pozas-Kerstjens, Rafael Rabelo, Łukasz Rudnicki +4 more

We present a method that allows the study of classical and quantum correlations in networks with causally independent parties, such as the scenario underlying entanglement swapping. By imposing relaxations of factorization constraints in a form compatible with semidefinite programing, it enables the use of the Navascués-Pironio-Acín hierarchy in complex quantum networks. We first show how the technique successfully identifies correlations not attainable in the entanglement-swapping scenario. Then we use it to show how the nonlocal power of measurements can be activated in a network: there exist measuring devices that, despite being unable to generate nonlocal correlations in the standard Bell scenario, provide a classical-quantum separation in an entanglement swapping configuration.

arXiv:1904.08943•Physical Review Letters•Oct 3, 2019•73 citations
Almost-quantum correlations form the 1+AB\mathtt{1+AB}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∈[N]s,t\in[N]s,t∈[N], N≥3N\ge3N≥3; after one bit from Alice, Bob must decide whether s=ts=ts=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/N1/N1/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/191/191/19 for every NNN. For certificates of equality from binary-outcome boxes, we solve the underlying semidefinite programs in closed form. The almost-quantum optimum equals N2/(17N2−80N+64)N^2/(17N^2-80N+64)N2/(17N2−80N+64) for N≥8N\ge8N≥8 and tends to 1/171/171/17. The first level of the hierarchy, which coincides with the set singled out by macroscopic locality, attains N/[8(N−2)]N/[8(N-2)]N/[8(N−2)], which tends to 1/81/81/8; its optimal boxes lie outside the almost-quantum set for every N≥5N\ge5N≥5. 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 nnn-bit strings from nnn bits to at most 131313. 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+AB1+AB1+AB) correlations can outperform quantum correlations in zero-error communication. Alice and Bob receive labels s,t∈[N]s,t\in[N]s,t∈[N]; after one classical bit from Alice, Bob must decide whether s=ts=ts=t, allowing abstention but no errors. Performance is the worst-case probability of a conclusive answer.
For every N≥3N\ge3N≥3, the optimal efficiency is exactly 1/N1/N1/N with shared randomness, entanglement, or commuting-operator correlations. Explicit binary-output AQ boxes instead achieve efficiency 1/191/191/19 for every NNN, giving an unbounded ratio of at least N/19N/19N/19. For the restricted problem of certifying equality through a single joint outcome of a binary-output box, the AQ optimum is 1/N1/N1/N for N≤8N\le8N≤8 and N2/(17N2−80N+64)N^2/(17N^2-80N+64)N2/(17N2−80N+64) for N≥8N\ge8N≥8, approaching 1/171/171/17. The corresponding NPA level-1 optimum is N/[8(N−2)]N/[8(N-2)]N/[8(N−2)] for N≥4N\ge4N≥4, approaching 1/81/81/8. For equality of nnn-bit strings with abstention probability at most 1/21/21/2, one-way classical communication costs exactly nnn bits with quantum resources, versus at most 131313 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.
We are interested in the problem of characterizing the correlations that arise when performing local measurements on separate quantum systems. In a previous work (Navascués et al 2007 Phys. Rev. Lett. 98 010401), we introduced an infinite hierarchy of conditions necessarily satisfied by any set of quantum correlations. Each of these conditions could be tested using semidefinite programming. We present here new results concerning this hierarchy. We prove in particular that it is complete, in the sense that any set of correlations satisfying every condition in the hierarchy has a quantum representation in terms of commuting measurements. Although our tests are conceived to rule out non-quantum correlations, and can in principle certify that a set of correlations is quantum only in the asymptotic limit where all tests are satisfied, we show that in some cases it is possible to conclude that a given set of correlations is quantum after performing only a finite number of tests. We provide a criterion to detect when such a situation arises, and we explain how to reconstruct the quantum states and measurement operators reproducing the given correlations. Finally, we present several applications of our approach. We use it in particular to bound the quantum violation of various Bell inequalities.
Information causality (IC) posits that communicating m classical bits cannot give the receiver access to more than m bits of information about the sender's independent data. Although IC holds in quantum theory and excludes a broad class of supra-quantum correlations, its validity for the almost-quantum set has remained open. This semidefinite relaxation of the quantum set satisfies nontrivial communication complexity, no advantage for non-local computation, macroscopic locality, local orthogonality, and numerical evidence has suggested that it may also satisfy IC. Here we show that almost-quantum correlations violate IC, and do so without bound. Unlike earlier violations of IC, which rely on biased guesses, ours is driven by zero-error certificates: each is rare but never wrong, carries information linear in its probability, and vouches for many of the sender's bits at once. This establishes a sharp dichotomy: either IC is a valid physical principle that excludes these correlations, or any nonsignalling theory realizing them admits no mutual information obeying consistency, data processing and the chain rule. In the latter case, we discuss why the chain rule is the natural property to relinquish, and how this possibility relates to histories-based formulations and to locality defined relative to the state rather than presupposed in a fixed spacetime.
We give exact rational certificates for two results in the bipartite Bell scenario with three two-outcome measurements per party. First, the maximum of the I3322I_{3322}I3322​ (Froissart) functional over the almost-quantum set -- the 1+AB1{+}AB1+AB level of the Navascues-Pironio-Acin (NPA) hierarchy -- is certified to lie between 0.25147088380.25147088380.2514708838 and 0.25147090160.25147090160.2514709016 (width <2×10−8<2\times10^{-8}<2×10−8), in the normalization with classical bound 000 and quantum maximum ≈0.2508754\approx0.2508754≈0.2508754; to our knowledge no value for this landmark had been published. Second, we exhibit a single exact rational behavior T∗T^{*}T∗ carrying certificates in both directions: a rational moment matrix proving T∗T^{*}T∗ almost-quantum, and a rational dual object proving that every NPA level-2 completion of T∗T^{*}T∗ requires slack at least q=4.5934×10−4q=4.5934\times10^{-4}q=4.5934×10−4, so that T∗T^{*}T∗ is not quantum. The strict inclusion Q⊊Q~Q\subsetneq\tilde{Q}Q⊊Q~​ in the minimal three-setting scenario is thereby established end-to-end with no reliance on floating-point computation. Anatomically, the witness is locally quantum: all nine of its 2×22\times22×2 correlator subtables pass the Tsirelson-Landau-Masanes criterion, so its non-quantumness is irreducibly a three-setting phenomenon, concentrated in ordering-dependent pseudo-moments coupling each party's third setting to the other's first two; the level-2 certificate is equivalently an exact sum-of-squares identity that any quantum state values nonnegatively and the witness is forced to value at −q-q−q. The certificates follow the rational rounding-projection-lifting programme recently developed for noncommutative optimization; for NPA moment matrices in canonical form the required projection reduces to a per-moment uniform shift, making certification essentially free at these sizes, and we work the programme in both the feasibility and infeasibility directions on one witness. Machine-checkable certificates and verifiers requiring only the Python standard library accompany the paper. Files in this record: the paper (PDF); exact rational certificates for both theorems (i3322_1AB_certificate.json, i3322_level2_infeasibility_certificate.json); standalone verifiers requiring only the Python 3 standard library (verify_i3322_certificate.py, verify_level2_certificate.py); and the generating scripts (certify_landmark.py, certify_level2.py). See README_ancillary.txt for which artifact proves which theorem and how to run the verifiers. v2: corrects the mechanism attribution in Sec. 5 (anatomy) and adds the archive reference to Data Availability; theorems, certificates, and verifiers unchanged.
Bounding the correlations predicted by quantum theory is an important challenge in quantum information science. Today's leading approach is semidefinite programming relaxations, but existing methods still cannot account for many relevant types of constraints. Here, we propose a semidefinite relaxation methodology that can incorporate a breadth of constraints needed in various quantum correlation problems, thereby generalising the seminal Navascués-Pironio-Acín hierarchy. It yields useful results at reasonable computational cost. We showcase the methodology and its features by using it to address five different quantum information problems. These are (i) entanglement witnessing from imperfect measurement devices, (ii) certifying measurements from fidelity-constrained sources, (iii) computing dimensionality in genuine multi-particle entangled states, (iv) benchmarking dimensionality for state preparation devices, and (v) finding uncertainty relations for nearly anti-commuting observables. These applications reflect both the usefulness and versatility of the methodology, as well as its potential for broader relevance in the field.
We give asymptotically converging semidefinite programming hierarchies of outer bounds on bilinear programs of the form Tr[M(X⊗Y)]\mathrm{Tr}\big[M(X\otimes Y)\big]Tr[M(X⊗Y)], maximized with respect to semidefinite constraints on XXX and YYY. Applied to the problem of quantum error correction this gives hierarchies of efficiently computable outer bounds on the optimal fidelity for any message dimension and error model. The first level of our hierarchies corresponds to the non-signalling assisted fidelity previously studied by [Leung & Matthews, IEEE Trans.~Inf.~Theory 2015], and positive partial transpose constraints can be added and used to give a sufficient criterion for the exact convergence at a given level of the hierarchy. To quantify the worst case convergence speed of our hierarchies, we derive novel quantum de Finetti theorems that allow imposing linear constraints on the approximating state. In particular, we give finite de Finetti theorems for quantum channels, quantifying closeness to the convex hull of product channels as well as closeness to local operations and classical forward communication assisted channels. As a special case this constitutes a finite version of Fuchs-Schack-Scudo's asymptotic de Finetti theorem for quantum channels. Finally, our proof methods also allow us to answer an open question from [Brand\~ao & Harrow, STOC 2013] by improving the approximation factor of de Finetti theorems with no symmetry from O(dk/2)O(d^{k/2})O(dk/2) to poly(d,k)\mathrm{poly}(d,k)poly(d,k), where ddd denotes local dimension and kkk the number of copies.
We present a method that allows the study of classical and quantum correlations in networks with causally independent parties, such as the scenario underlying entanglement swapping. By imposing relaxations of factorization constraints in a form compatible with semidefinite programing, it enables the use of the Navascués-Pironio-Acín hierarchy in complex quantum networks. We first show how the technique successfully identifies correlations not attainable in the entanglement-swapping scenario. Then we use it to show how the nonlocal power of measurements can be activated in a network: there exist measuring devices that, despite being unable to generate nonlocal correlations in the standard Bell scenario, provide a classical-quantum separation in an entanglement swapping configuration.