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:1112.5876 · Journal of Physics A Mathematical and Theoretical

Bell inequalities from variable-elimination methods

Costantino Budroni, Adán Cabello

Published Sep 5, 2012• 20 citations
arXivHTMLPDF

Abstract

Tight Bell inequalities are facets of Pitowsky's correlation polytope and are usually obtained from its extreme points by solving the hull problem.Here, we present an alternative method based on a combination of algebraic results on extensions of measures and variable-elimination methods, e.g., the Fourier-Motzkin method.Our method is shown to overcome some of the computational difficulties associated with the hull problem in some nontrivial cases.Moreover, it provides an explanation for the arising of only a finite number of families of Bell inequalities in measurement scenarios where one experimenter can choose between an arbitrary number of different measurements.

DOI
10.1088/1751-8113/45/38/385304

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

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

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

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

Avenues to generalising Bell inequalities

Marcin Karczewski, Giovanni Scala, Antonio Mandarino +2 more

Abstract Characterizing the set of all Bell inequalities is a notably hard task. An insightful method of solving it in case of Bell correlation inequalities for scenarios with two dichotomic measurements per site—for arbitrary number of parties—was given in references [2001 Phys. Rev. A 64 010102(R)] and [2001 Phys. Rev. A 64 032112]. Using complex-valued correlation functions, we generalize their approach to a broader class of Bell scenarios, in which the parties may choose from more than two multi-outcome measurements. Although the resulting families of Bell inequalities are not always tight, their coefficients have an intuitively understandable structure. We probe their usefulness by numerically testing their ability to detect Bell nonclassicality in simple interferometric experiments. Moreover, we identify a similar structure in the CGLMP inequality expressed in a correlation-based form, which allows us to generalise it to three parties.

arXiv:2202.06606•Journal of Physics A Mathematical and Theoretical•Aug 16, 2022•10 citations
Tight Bell inequalities are facets of Pitowsky's correlation polytope and are usually obtained from its extreme points by solving the hull problem.Here, we present an alternative method based on a combination of algebraic results on extensions of measures and variable-elimination methods, e.g., the Fourier-Motzkin method.Our method is shown to overcome some of the computational difficulties associated with the hull problem in some nontrivial cases.Moreover, it provides an explanation for the arising of only a finite number of families of Bell inequalities in measurement scenarios where one experimenter can choose between an arbitrary number of different measurements.
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.
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.
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 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.
Abstract Characterizing the set of all Bell inequalities is a notably hard task. An insightful method of solving it in case of Bell correlation inequalities for scenarios with two dichotomic measurements per site—for arbitrary number of parties—was given in references [2001 Phys. Rev. A 64 010102(R)] and [2001 Phys. Rev. A 64 032112]. Using complex-valued correlation functions, we generalize their approach to a broader class of Bell scenarios, in which the parties may choose from more than two multi-outcome measurements. Although the resulting families of Bell inequalities are not always tight, their coefficients have an intuitively understandable structure. We probe their usefulness by numerically testing their ability to detect Bell nonclassicality in simple interferometric experiments. Moreover, we identify a similar structure in the CGLMP inequality expressed in a correlation-based form, which allows us to generalise it to three parties.