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:quant-ph/0505060 · Journal of Physics A Mathematical and General

Two-party Bell inequalities derived from combinatorics via triangular elimination

David Avis, Hiroshi Imai, Tsuyoshi Ito, Yuuya Sasaki

Published Nov 30, 2005• 48 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1088/0305-4470/38/50/007

Related papers

Two-Party Bell Inequalities Derived from Combinatorics via Triangular Elimination

David Avis, Hiroshi Imai, Tsuyoshi Ito +1 more

Bell inequalities, originally introduced as a method to prove that some quantum states show nonlocal behavior, are now studied as a method to capture the extent of the nonlocality of quantum states. Tight Bell inequalities are considered to be more important than redundant ones. Despite the increasing importance of the study of Bell inequalities, few kinds of tight Bell inequalities have been found. Examples include the Clauser-Horne-Shimony-Holt inequality, the I_{mmvv} inequalities, the CGLMP inequalities, and the Bell inequalities in systems small enough to generate all the Bell inequalities by exhaustive search. In this paper, 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 formulas which represent families of infinitely many Bell inequalities. These results can be used to examine general properties of Bell inequalities.

•Jan 1, 2005•39 citations

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

David Avis, Hiroshi Imai, Tsuyoshi Ito +1 more

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.

•Jan 1, 2004•0 citations

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•14 citations

Bell Inequalities from Polyhedral Sampling

Christian Staufenbiel

Bell inequalities play a central role in certifying quantum correlations and underpin protocols such as device-independent quantum key distribution. However, enumerating all Bell inequalities for a given scenario remains intractable beyond the simplest cases, as it requires solving a computationally hard facet enumeration problem on the associated Bell polytope. We propose the Adjacency Sampling method, which builds on the Adjacency Decomposition method but sacrifices completeness for speed. On previously solved Bell polytopes, the method reproduces every known class of inequalities. For scenarios where no complete enumeration exists, it greatly exceeds existing partial results: in $\mathcal{L}_{3,3,3,3}$ we obtain over $1.29 \times 10^8$ classes, more than 25 times the previous count; in $\mathcal{L}_{4,5,2,2}$ we nearly triple the known list to 49\,358 classes; and for $\mathcal{L}_{4,6,2,2}$ we report over 4.3 million classes.

quant-pharXiv:2604.22859•Apr 24, 2026•0 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•20 citations

Looking for symmetric Bell inequalities

Jean-Daniel Bancal, Nicolas Gisin, Stefano Pironio

Finding all Bell inequalities for a given number of parties, measurement settings and measurement outcomes is in general a computationally hard task. We show that all Bell inequalities which are symmetric under the exchange of parties can be found by examining a symmetrized polytope which is simpler than the full Bell polytope. As an illustration of our method, we generate 238 885 new Bell inequalities and 1085 new Svetlichny inequalities. We find, in particular, facet inequalities for Bell experiments involving two parties and two measurement settings that are not of the Collins–Gisin–Linden–Massar–Popescu type.

arXiv:1004.4146•Journal of Physics A Mathematical and Theoretical•Aug 6, 2010•77 citations
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.
Bell inequalities, originally introduced as a method to prove that some quantum states show nonlocal behavior, are now studied as a method to capture the extent of the nonlocality of quantum states. Tight Bell inequalities are considered to be more important than redundant ones. Despite the increasing importance of the study of Bell inequalities, few kinds of tight Bell inequalities have been found. Examples include the Clauser-Horne-Shimony-Holt inequality, the I_{mmvv} inequalities, the CGLMP inequalities, and the Bell inequalities in systems small enough to generate all the Bell inequalities by exhaustive search. In this paper, 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 formulas which represent families of infinitely many Bell inequalities. These results can be used to examine general properties of Bell inequalities.
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.
Bell inequalities play a central role in certifying quantum correlations and underpin protocols such as device-independent quantum key distribution. However, enumerating all Bell inequalities for a given scenario remains intractable beyond the simplest cases, as it requires solving a computationally hard facet enumeration problem on the associated Bell polytope. We propose the Adjacency Sampling method, which builds on the Adjacency Decomposition method but sacrifices completeness for speed. On previously solved Bell polytopes, the method reproduces every known class of inequalities. For scenarios where no complete enumeration exists, it greatly exceeds existing partial results: in L3,3,3,3\mathcal{L}_{3,3,3,3}L3,3,3,3​ we obtain over 1.29×1081.29 \times 10^81.29×108 classes, more than 25 times the previous count; in L4,5,2,2\mathcal{L}_{4,5,2,2}L4,5,2,2​ we nearly triple the known list to 49\,358 classes; and for L4,6,2,2\mathcal{L}_{4,6,2,2}L4,6,2,2​ we report over 4.3 million classes.
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.
Finding all Bell inequalities for a given number of parties, measurement settings and measurement outcomes is in general a computationally hard task. We show that all Bell inequalities which are symmetric under the exchange of parties can be found by examining a symmetrized polytope which is simpler than the full Bell polytope. As an illustration of our method, we generate 238 885 new Bell inequalities and 1085 new Svetlichny inequalities. We find, in particular, facet inequalities for Bell experiments involving two parties and two measurement settings that are not of the Collins–Gisin–Linden–Massar–Popescu type.