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:math/0505143

New Classes of Facets of Cut Polytope and Tightness of I_{mm22} Bell Inequalities

David Avis, Tsuyoshi Ito

Published May 9, 2005• 0 citations
arXivHTMLPDF

Abstract

The Grishukhin inequality Gr_7 is a facet of CutP_7, the cut polytope on seven points, which is ``sporadic'' in the sense that its proper generalization has not been known. In this paper, we extend Gr_7 to an inequality I(G,H) valid for CutP_{n+1} where G and H are graphs with n nodes satisfying certain conditions, and prove a necessary and sufficient condition for I(G,H) to be a facet. This result combined with the triangular elimination theorem of Avis, Imai, Ito and Sasaki settles Collins and Gisin's conjecture in quantum theory affirmatively: the I_{mm22} Bell inequality is a facet of the correlation polytope CorP(K_{m,m}) of the complete bipartite graph K_{m,m} for all m>=1. We also extend the Gr_8 facet inequality of CutP_8 to an inequality I'(G,H,C) valid for CutP_{n+2}, and provide a sufficient condition for I'(G,H,C) to be a facet.

DOI
10.48550/arxiv.math/0505143

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

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

Tight Bell inequality for d-outcome measurements correlations

Lluís Masanes

In this paper we prove that the inequality introduced by Collins, Gisin, Linden, Massar and Popescu is tight, or in other words, it is a facet of the convex polytope generated by all local-realistic joint probabilities of d-outcomes. This means that this inequality is optimal. We also show that, for correlation functions generalized to deal with three-outcome measurements, the satisfyability of this inequality is a necessary and sufficient condition for the existence of a local-realistic model accounting for them.

arXiv:quant-ph/0210073•Quantum Information and Computation•Jul 1, 2003•92 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•7 citations
The Grishukhin inequality Gr_7 is a facet of CutP_7, the cut polytope on seven points, which is ``sporadic'' in the sense that its proper generalization has not been known. In this paper, we extend Gr_7 to an inequality I(G,H) valid for CutP_{n+1} where G and H are graphs with n nodes satisfying certain conditions, and prove a necessary and sufficient condition for I(G,H) to be a facet. This result combined with the triangular elimination theorem of Avis, Imai, Ito and Sasaki settles Collins and Gisin's conjecture in quantum theory affirmatively: the I_{mm22} Bell inequality is a facet of the correlation polytope CorP(K_{m,m}) of the complete bipartite graph K_{m,m} for all m>=1. We also extend the Gr_8 facet inequality of CutP_8 to an inequality I'(G,H,C) valid for CutP_{n+2}, and provide a sufficient condition for I'(G,H,C) to be a facet.
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.
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.
In this paper we prove that the inequality introduced by Collins, Gisin, Linden, Massar and Popescu is tight, or in other words, it is a facet of the convex polytope generated by all local-realistic joint probabilities of d-outcomes. This means that this inequality is optimal. We also show that, for correlation functions generalized to deal with three-outcome measurements, the satisfyability of this inequality is a necessary and sufficient condition for the existence of a local-realistic model accounting for them.
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.