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

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.

Related papers:

title: All the Bell Inequalities
abstract: Bell inequalities are derived for any number of observers, any number of alternative setups for each one of them and any number of distinct outcomes for each experiment. It is shown that if a physical system consists of several distant subsystems, and if the results of tests performed on the latter are determined by local variables with objective values, then the joint probabilities for triggering any given set of distant detectors are convex combinations of a finite number of Boolean arrays, whose components are either 0 or 1 according to a simple rule. This convexity property is both necessary and sufficient for the existence of local objective variables. It leads to a simple graphical method which produces a large number of generalized Clauser-Horne inequalities corresponding to the faces of a convex polytope. It is plausible that quantum systems whose density matrix has a positive partial transposition satisfy all these inequalities, and therefore are compatible with local objective variables, even if their quantum properties are essentially non-local.

title: Geometry of cuts and metrics
abstract: Cuts and metrics are well-known objects that arise - independently, but with many deep and fascinating connections - in diverse fields: in graph theory, combinatorial optimization, geometry of numbers, distance geometry, combinatorial matrix theory, statistical physics, VLSI design etc. A main feature of this book is its interdisciplinarity. The book contains a wealth of results, from different mathematical disciplines, which are presented here in a unified and comprehensive manner. Geometric representations and methods turn out to be the linking theme. This book will provide a unique and invaluable source for researchers and graduate students. From the Reviews: "This book is definitely a milestone in the literature of integer programming and combinatorial optimization. It draws from the interdisciplinarity of these fields as it gathers methods and results from polytope theory, geometry of numbers, probability theory, design and graph theory around two objects, cuts and metrics.  The book is very nicely written [ ] The book is also very well structured. With knowledge about the relevant terms, one can enjoy special subsections without being entirely familiar with the rest of the chapter. This makes it not only an interesting research book but even a dictionary.  In my opinion, the book is a beautiful piece of work. The longer one works with it, the more beautiful it becomes." Robert Weismantel, Optima 56 (1997) " In short, this is a very interesting book which is nice to have." Alexander I. Barvinok, MR 1460488 (98g:52001) " This is a large and fascinating book. As befits a book which contains material relevant to so many areas of mathematics (and related disciplines such as statistics, physics, computing science, and economics), it is self-contained and written in a readable style. Moreover, the index, bibliography, and table of contents are all that they should be in such a work; it is easy to find as much or as little introductory material as needed." R.Dawson,

title: Lifting facets of the cut polytope
abstract: The cut polytope P"c(G) of a graph G is the convex hull of the incidence vectors of the edge sets of all cuts of G. We give a sufficient condition for an inequality defining a facet of P"c(G) to define a facet of the cut polytope of a graph containing G as an induced subgraph. Our result generalizes a result of Deza stating that if G is a complete graph with more than two vertices, then an inequality defines a facet of P"c(G) if and only if it defines a facet of the cut polytope of every complete graph containing G.

title: The cut cone, L1 embeddability, complexity, and multicommodity flows
abstract: A finite metric (or more properly semimetric) on n points is a nonnegative vector d = (dij) 1 ⩽ i < j ⩽ n that satisfies the triangle inequality dij ⩽ dik + djk. The L1 (or Manhattan) distance ‖x − y‖1 between two vectors x = (xi) and y = (yi) in Rm is given by ‖x − y‖1 = ∑1⩽i⩽m |xi − yi|. A metric d is L1-embeddable if there exist vectors z1, z2,…, zn in Rm for some m, such that dij = ‖zi − zj‖1 for 1 ⩽ i < j ⩽ n. A cut metric is a metric with all distances zero or one and corresponds to the incidence vector of a cut in the complete graph on n vertices. The cut cone Hn is the convex cone formed by taking all nonnegative combinations of cut metrics. It is easily shown that a metric is L1-embeddable if and only if it is contained in the cut cone. In this expository paper, we provide a unified setting for describing a number of results related to L1-embeddability and the cut cone. We collect and describe results on the facial structure of the cut cone and the complexity of testing the L1-embeddability of a metric. One of the main sections of the paper describes the role of L1-embeddability in the feasibility problem for multi-commodity flows. The Ford and Fulkerson theorem for the existence of a single commodity flow can be restated as an inequality that must be valid for all cut metrics. A more general result, known as the Japanese theorem, gives a condition for the existence of a multicommodity flow. This theorem gives an inequality that must be satisfied by all metrics. For multicommodity flows involving a small number of terminals, it is known that the condition of the Japanese theorem can be replaced with one of the Ford–Fulkerson type. We review these results and show that the existence of such Ford–Fulkerson-type conditions for flows with few terminals depends critically on the fact that certain metrics are L1-embeddable.

title: Symmetries of the Bell correlation inequalities
abstract: Classes of equivalent Bell inequalities are considered. For two-way measurements and three observables at each of two sites, the class of inequalities non-trivially depending on all observables is unique. The observables are found for which, in the singlet state of two qubits, a maximal violation of those inequalities is attained.

title: Optimal tests of quantum nonlocality
abstract: We present a general method for obtaining all Bell inequalities for a given experimental setup. Although the algorithm runs slowly, we apply it to two cases. First, the Greenberger-Horne-Zeilinger setup with three observers each performing one of two possible measurements. Second, the case of two observers each performing one of three possible experiments. In both cases we obtain hundreds of inequalities. Since this is the set of all inequalities, the one that is maximally violated in a given quantum state must be among them. We demonstrate this fact with a few examples. We also note the deep connection between the inequalities and classical logic, and their violation with quantum logic.

title: A relevant two qubit Bell inequality inequivalent to the CHSH inequality
abstract: We computationally investigate the complete polytope of Bell inequalities for two particles with small numbers of possible measurements and outcomes. Our approach is limited by Pitowsky's connection of this problem to the computationally hard NP problem. Despite this, we find that there are very few relevant inequivalent inequalities for small numbers. For example, in the case with three possible 2-outcome measurements on each particle, there is just one new inequality. We describe mixed 2-qubit states which violate this inequality but not the CHSH. The new inequality also illustrates a sharing of bi-partite non-locality between three qubits: something not seen using the CHSH inequality. It also inspires us to discover a class of Bell inequalities with m possible n-outcome measurements on each particle.

title: All-multipartite Bell-correlation inequalities for two dichotomic observables per site
abstract: We construct a set of ${2}^{{2}^{n}}$ independent Bell-correlation inequalities for n-partite systems with two dichotomic observables each, which is complete in the sense that the inequalities are satisfied if and only if the correlations considered allow a local classical model. All these inequalities can be summarized in a single, albeit nonlinear inequality. We show that quantum correlations satisfy this condition provided the state has positive partial transpose with respect to any grouping of the n systems into two subsystems. We also provide an efficient algorithm for finding the maximal quantum-mechanical violation of each inequality, and show that the maximum is always attained for the generalized GHZ state.

title: Tight Bell inequality for d-outcome measurements correlations
abstract: In this paper we prove that the inequality introduced by Collins, Gisin, Linden, Massar and Popescu [11] 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.