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

for 2 Parties with Many 2-valued Observables from Facets of Cut Polytopes

David Avis, Hiroshi Imai, Tsuyoshi Ito, Yuuya Sasaki

Published Jan 1, 2004• 0 citations
OpenAlex

Abstract

Relatively few families of Bell inequalities have previously been identified. Some examples are the trivial, CHSH, Imm22, and CGLMP inequalities. This paper presents a large number of new families of tight Bell inequalities for the case of many observables. For example, 44,368,793 inequivalent tight Bell inequalities other than CHSH are obtained for the case of 2 parties each with 10 2-valued observables. This is accomplished by first establishing a relationship between the Bell inequalities and the facets of the cut polytope, a well studied object in polyhedral combinatorics. We then prove a theorem allowing us to derive new facets of cut polytopes from facets of smaller polytopes by a process derived from FourierMotzkin elimination, which we call triangular elimination. These new facets in turn give new tight Bell inequalities. We give additional results for projections, liftings, and the complexity of membership testing for the associated Bell polytope.

Related papers

Deriving Tight Bell Inequalities for 2 Parties with Many 2-valued Observables from Facets of Cut Polytopes

David Avis, Imai, Hiroshi, Tsuyoshi Ito +1 more

Relatively few families of Bell inequalities have previously been identified. Some examples are the trivial, CHSH, I_{mm22}, and CGLMP inequalities. This paper presents a large number of new families of tight Bell inequalities for the case of many observables. For example, 44,368,793 inequivalent tight Bell inequalities other than CHSH are obtained for the case of 2 parties each with 10 2-valued observables. This is accomplished by first establishing a relationship between the Bell inequalities and the facets of the cut polytope, a well studied object in polyhedral combinatorics. We then prove a theorem allowing us to derive new facets of cut polytopes from facets of smaller polytopes by a process derived from Fourier-Motzkin elimination, which we call triangular elimination. These new facets in turn give new tight Bell inequalities. We give additional results for projections, liftings, and the complexity of membership testing for the associated Bell polytope.

arXiv:quant-ph/0404014•Apr 2, 2004•23 citations

Two-party Bell inequalities derived from combinatorics via triangular elimination

David Avis, Hiroshi Imai, Tsuyoshi Ito +1 more

We establish a relation between the two-party Bell inequalities for two-valued measurements and a high-dimensional convex polytope called the cut polytope in polyhedral combinatorics. Using this relation, we propose a method, triangular elimination , to derive tight Bell inequalities from facets of the cut polytope. This method gives two hundred million inequivalent tight Bell inequalities from currently known results on the cut polytope. In addition, this method gives general formulae which represent families of infinitely many Bell inequalities. These results can be used to examine general properties of Bell inequalities.

arXiv:quant-ph/0505060•Journal of Physics A Mathematical and General•Nov 30, 2005•50 citations

Bell inequalities stronger than the Clauser-Horne-Shimony-Holt inequality for three-level isotropic states

Tsuyoshi Ito, Hiroshi Imai, David Avis

We show that some two-party Bell inequalities with two-valued observables are stronger than the CHSH inequality for $3\ensuremath{\bigotimes}3$ isotropic states in the sense that they are violated by some isotropic states in the $3\ensuremath{\bigotimes}3$ system that do not violate the CHSH inequality. These Bell inequalities are obtained by applying triangular elimination to the list of known facet inequalities of the cut polytope on nine points. This gives a partial solution to an open problem posed by Collins and Gisin. The results of numerical optimization suggest that they are candidates for being stronger than the ${\mathrm{I}}_{3322}$ Bell inequality for $3\ensuremath{\bigotimes}3$ isotropic states. On the other hand, we found no Bell inequalities stronger than the CHSH inequality for $2\ensuremath{\bigotimes}2$ isotropic states. In addition, we illustrate an inclusion relation among some Bell inequalities derived by triangular elimination.

arXiv:quant-ph/0508210•Physical Review A•Apr 21, 2006•21 citations

Tightness of correlation inequalities with no quantum violation

Ravishankar Ramanathan, Marco Túlio Quintino, Ana Belén Sainz +2 more

We study the faces of the set of quantum correlations, i.e., the Bell and noncontextuality inequalities without any quantum violation. First, we investigate the question of whether every proper (facet-defining) Bell inequality for two parties, other than the trivial ones from positivity, normalization, and no-signaling, can be violated by quantum correlations, i.e., whether the classical Bell polytope or the smaller correlation polytope share any facets with their respective quantum sets. To do this, we develop a recently derived bound on the quantum value of linear games based on the norms of game matrices to give a simple sufficient condition to identify linear games with no quantum advantage. Additionally we show how this bound can be extended to the general class of unique games. We then show that the paradigmatic examples of correlation Bell inequalities with no quantum violation, namely the nonlocal computation games, do not constitute facet-defining Bell inequalities, not even for the correlation polytope. We also extend this to an arbitrary prime number of outcomes for a specific class of these games. We then study the faces in the simplest Clauser-Horne-Shimony-Holt Bell scenario of binary dichotomic measurements, and identify edges in the set of quantum correlations in this scenario. Finally, we relate the noncontextual polytope of single-party correlation inequalities with the cut polytope $\text{CUT}(\mathbf{\ensuremath{\nabla}}G)$, where $G$ denotes the compatibility graph of observables in the contextuality scenario and $\mathbf{\ensuremath{\nabla}}G$ denotes the suspension graph of $G$. We observe that there exist facet-defining noncontextuality inequalities with no quantum violation, and furthermore that this set of inequalities is beyond those implied by the consistent exclusivity principle.

arXiv:1607.05714•Physical Review A•Jan 27, 2017•9 citations

Bell inequalities from outcome equalities

Ricardo Faleiro, Flavien Hirsch, Emmanuel Zambrini Cruzeiro +1 more

In this work, we study a particular class of Bell inequalities involving only direct equality-comparisons of outcomes. In the bipartite case, the scenario can be interpreted as a natural generalization of full-correlator in- equalities (XOR games) beyond binary outputs. We define the sub-polytope of the local polytope corresponding to this scenario and solve it for several bipartite and multipartite scenarios by leveraging some structural prop- erties. In doing so, we obtain thousands of new tight inequalities, many of which are also facets of the standard local polytope. We also define unanimous Bell inequalities, a particular case of the previous class applied to the multipartite setting in which only full-equality events (all outcomes equal) are considered. We show that such inequalities can always be written as deterministic nonlocal games, and we give a simple multipartite unanimous family and prove its local bound. We show that most of these inequalities admit quantum violations, and we also display aspects of their importance for nonlocality. For instance, we identify examples where such inequalities can act as dimension witnesses, outcome witnesses, witnesses of genuine multipartite nonlocality, as well as being relevant to CHSH. These results show that these simple and elegant inequalities by themselves provide a powerful tool for discovering new Bell inequalities and device-independent witnesses.

quant-pharXiv:2603.17030•Physical Review A•Mar 19, 2026•1 citation

Polyhedral duality in Bell scenarios with two binary observables

Tobias Fritz

For the Bell scenario with two parties and two binary observables per party, it is known that the no-signaling polytope is the polyhedral dual (polar) of the Bell polytope. Computational evidence suggests that this duality also holds for three parties. Using ideas of Werner, Wolf, Żukowski, and Brukner, we prove this for any number of parties by describing a simple linear bijection mapping (facet) Bell inequalities to (extremal) no-signaling boxes and vice versa. Furthermore, a symmetry-based technique for extending Bell inequalities (respectively, no-signaling boxes) with two binary observables from n parties to n + 1 parties is described; the Mermin–Klyshko family of Bell inequalities arises in this way, as well as 11 of the 46 classes of facet Bell inequalities for three parties. Finally, we ask whether the set of quantum correlations is self-dual with respect to our transformation. We find this not to be the case in general, although it holds for two parties on the level of correlations. This self-duality implies Tsirelson's bound for the CHSH inequality.

arXiv:1202.0141•Journal of Mathematical Physics•Jul 1, 2012•47 citations
Relatively few families of Bell inequalities have previously been identified. Some examples are the trivial, CHSH, Imm22, and CGLMP inequalities. This paper presents a large number of new families of tight Bell inequalities for the case of many observables. For example, 44,368,793 inequivalent tight Bell inequalities other than CHSH are obtained for the case of 2 parties each with 10 2-valued observables. This is accomplished by first establishing a relationship between the Bell inequalities and the facets of the cut polytope, a well studied object in polyhedral combinatorics. We then prove a theorem allowing us to derive new facets of cut polytopes from facets of smaller polytopes by a process derived from FourierMotzkin elimination, which we call triangular elimination. These new facets in turn give new tight Bell inequalities. We give additional results for projections, liftings, and the complexity of membership testing for the associated Bell polytope.
Relatively few families of Bell inequalities have previously been identified. Some examples are the trivial, CHSH, I_{mm22}, and CGLMP inequalities. This paper presents a large number of new families of tight Bell inequalities for the case of many observables. For example, 44,368,793 inequivalent tight Bell inequalities other than CHSH are obtained for the case of 2 parties each with 10 2-valued observables. This is accomplished by first establishing a relationship between the Bell inequalities and the facets of the cut polytope, a well studied object in polyhedral combinatorics. We then prove a theorem allowing us to derive new facets of cut polytopes from facets of smaller polytopes by a process derived from Fourier-Motzkin elimination, which we call triangular elimination. These new facets in turn give new tight Bell inequalities. We give additional results for projections, liftings, and the complexity of membership testing for the associated Bell polytope.
We establish a relation between the two-party Bell inequalities for two-valued measurements and a high-dimensional convex polytope called the cut polytope in polyhedral combinatorics. Using this relation, we propose a method, triangular elimination , to derive tight Bell inequalities from facets of the cut polytope. This method gives two hundred million inequivalent tight Bell inequalities from currently known results on the cut polytope. In addition, this method gives general formulae which represent families of infinitely many Bell inequalities. These results can be used to examine general properties of Bell inequalities.
We show that some two-party Bell inequalities with two-valued observables are stronger than the CHSH inequality for $3\ensuremath{\bigotimes}3$ isotropic states in the sense that they are violated by some isotropic states in the $3\ensuremath{\bigotimes}3$ system that do not violate the CHSH inequality. These Bell inequalities are obtained by applying triangular elimination to the list of known facet inequalities of the cut polytope on nine points. This gives a partial solution to an open problem posed by Collins and Gisin. The results of numerical optimization suggest that they are candidates for being stronger than the I3322{\mathrm{I}}_{3322}I3322​ Bell inequality for $3\ensuremath{\bigotimes}3$ isotropic states. On the other hand, we found no Bell inequalities stronger than the CHSH inequality for $2\ensuremath{\bigotimes}2$ isotropic states. In addition, we illustrate an inclusion relation among some Bell inequalities derived by triangular elimination.
We study the faces of the set of quantum correlations, i.e., the Bell and noncontextuality inequalities without any quantum violation. First, we investigate the question of whether every proper (facet-defining) Bell inequality for two parties, other than the trivial ones from positivity, normalization, and no-signaling, can be violated by quantum correlations, i.e., whether the classical Bell polytope or the smaller correlation polytope share any facets with their respective quantum sets. To do this, we develop a recently derived bound on the quantum value of linear games based on the norms of game matrices to give a simple sufficient condition to identify linear games with no quantum advantage. Additionally we show how this bound can be extended to the general class of unique games. We then show that the paradigmatic examples of correlation Bell inequalities with no quantum violation, namely the nonlocal computation games, do not constitute facet-defining Bell inequalities, not even for the correlation polytope. We also extend this to an arbitrary prime number of outcomes for a specific class of these games. We then study the faces in the simplest Clauser-Horne-Shimony-Holt Bell scenario of binary dichotomic measurements, and identify edges in the set of quantum correlations in this scenario. Finally, we relate the noncontextual polytope of single-party correlation inequalities with the cut polytope $\text{CUT}(\mathbf{\ensuremath{\nabla}}G)$, where GGG denotes the compatibility graph of observables in the contextuality scenario and $\mathbf{\ensuremath{\nabla}}G$ denotes the suspension graph of GGG. We observe that there exist facet-defining noncontextuality inequalities with no quantum violation, and furthermore that this set of inequalities is beyond those implied by the consistent exclusivity principle.
In this work, we study a particular class of Bell inequalities involving only direct equality-comparisons of outcomes. In the bipartite case, the scenario can be interpreted as a natural generalization of full-correlator in- equalities (XOR games) beyond binary outputs. We define the sub-polytope of the local polytope corresponding to this scenario and solve it for several bipartite and multipartite scenarios by leveraging some structural prop- erties. In doing so, we obtain thousands of new tight inequalities, many of which are also facets of the standard local polytope. We also define unanimous Bell inequalities, a particular case of the previous class applied to the multipartite setting in which only full-equality events (all outcomes equal) are considered. We show that such inequalities can always be written as deterministic nonlocal games, and we give a simple multipartite unanimous family and prove its local bound. We show that most of these inequalities admit quantum violations, and we also display aspects of their importance for nonlocality. For instance, we identify examples where such inequalities can act as dimension witnesses, outcome witnesses, witnesses of genuine multipartite nonlocality, as well as being relevant to CHSH. These results show that these simple and elegant inequalities by themselves provide a powerful tool for discovering new Bell inequalities and device-independent witnesses.
For the Bell scenario with two parties and two binary observables per party, it is known that the no-signaling polytope is the polyhedral dual (polar) of the Bell polytope. Computational evidence suggests that this duality also holds for three parties. Using ideas of Werner, Wolf, Żukowski, and Brukner, we prove this for any number of parties by describing a simple linear bijection mapping (facet) Bell inequalities to (extremal) no-signaling boxes and vice versa. Furthermore, a symmetry-based technique for extending Bell inequalities (respectively, no-signaling boxes) with two binary observables from n parties to n + 1 parties is described; the Mermin–Klyshko family of Bell inequalities arises in this way, as well as 11 of the 46 classes of facet Bell inequalities for three parties. Finally, we ask whether the set of quantum correlations is self-dual with respect to our transformation. We find this not to be the case in general, although it holds for two parties on the level of correlations. This self-duality implies Tsirelson's bound for the CHSH inequality.