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

Bell inequalities and the cut polytope : bridging quantum information science and combinatorial optimization

剛志 伊藤

Published Jan 1, 2007• 1 citation
OpenAlex

Related papers

Combinatorial Optimization and Quantum Computers

Alexandre Gondran, Michel Gondran

•Feb 7, 2020•0 citations

On the relationship between convex bodies related to correlation experiments with dichotomic observables

David Avis, Hiroshi Imai, Tsuyoshi Ito

In this paper we explore further the connections between convex bodies related to quantum correlation experiments with dichotomic variables and related bodies studied in combinatorial optimization, especially cut polyhedra. Such a relationship was established in Avis et al ( 2005 J. Phys. A: Math. Gen. 38 10971–87 ) with respect to Bell inequalities. We show that several well-known bodies related to cut polyhedra are equivalent to bodies such as those defined by Tsirelson (1993 Hadronic J. Suppl. 8 329–45) to represent hidden deterministic behaviours, quantum behaviours and no-signalling behaviours. Among other things, our results allow a unique representation of these bodies, give a necessary condition for vertices of the no-signalling polytope, and give a method for bounding the quantum violation of Bell inequalities by means of a body that contains the set of quantum behaviours. Optimization over this latter body may be performed efficiently by semidefinite programming. In the second part of the paper we apply these results to the study of classical correlation functions. We provide a complete list of tight inequalities for the two party case with ( m , n ) dichotomic observables when m = 4, n = 4 and when min{ m , n } ⩽ 3, and give a new general family of correlation inequalities.

arXiv:quant-ph/0605148•Journal of Physics A Mathematical and General•Aug 18, 2006•61 citations

Quantum Logic, Probability, and Information: The Relation with the Bell Inequalities

Emilio Santos

International Journal of Theoretical Physics•Oct 1, 2003•9 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

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

From Quantum State Targeting to Bell Inequalities

H. Bechmann-Pasquinucci

arXiv:quant-ph/0406106•Foundations of Physics•Nov 1, 2005•4 citations
In this paper we explore further the connections between convex bodies related to quantum correlation experiments with dichotomic variables and related bodies studied in combinatorial optimization, especially cut polyhedra. Such a relationship was established in Avis et al ( 2005 J. Phys. A: Math. Gen. 38 10971–87 ) with respect to Bell inequalities. We show that several well-known bodies related to cut polyhedra are equivalent to bodies such as those defined by Tsirelson (1993 Hadronic J. Suppl. 8 329–45) to represent hidden deterministic behaviours, quantum behaviours and no-signalling behaviours. Among other things, our results allow a unique representation of these bodies, give a necessary condition for vertices of the no-signalling polytope, and give a method for bounding the quantum violation of Bell inequalities by means of a body that contains the set of quantum behaviours. Optimization over this latter body may be performed efficiently by semidefinite programming. In the second part of the paper we apply these results to the study of classical correlation functions. We provide a complete list of tight inequalities for the two party case with ( m , n ) dichotomic observables when m = 4, n = 4 and when min{ m , n } ⩽ 3, and give a new general family of correlation inequalities.
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.
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.