All the Bell inequalities – Open Quantum Problems

Cite this problem as Problem 1.

Problem

Find all those linear inequalities characterizing the existence of joint probability distributions for all variables in a correlation experiment. The title was taken from a recent exposition by A. Peres [1].

More specifically, suppose that measurements are made on systems, which are decomposed into N subsystems. On each of these subsystems one out of M observables is measured, producing K outcomes each. Thus we consider $M^N$ different experimental setups, each of which may lead to $K^N$ different outcomes, so all in all $(M K)^N$ probabilities are measured. Classically (in a “realistic local theory”) these numbers would be generated by specifying probabilities for each “classical configuration”, i. e. every assignment of one of the K values to each of the N M observables. Thus the task is to characterize a convex polyhedron in $(M K)^N$ dimensions (minus a few for normalization constraints), which is generated by $K^{(N M)}$ explicitly known extreme points, in terms of linear inequalities.

For (N,M,K)=(2,2,2) this is solved by the CHSH inequalities. A general solution for all N,M,K is highly unlikely to exist. Therefore we pose the following more manageable tasks:

*Find complete solutions for other small values of (N,M,K).

*Find efficient ways of generating new inequalities, i. e., inequalities which cannot be written as convex combinations of lower order ones.

*Find infinite families of new inequalities. These could be complete families of inequalities with certain additional symmetries.

*Restrict to “full correlation functions”, i. e., disregard constraints on marginal distributions.

*Do the same for the special case of correlation inequalities. These belong to the case K=2, and are unchanged, when, for an even number of subsystems, all measurement outputs are interchanged. Such inequalities are best written in terms of the expectations of $A_1 A_2 ... A_N$ , where each Ai takes values +1,-1, resp. $-1 \leq A_i \leq 1$ .

*Decide by what margin these can be violated by quantum states, or by quantum states with special properties (e. g., fixed Hilbert space dimension, invariance under symmetry transformations or positive partial transposes).

Background

This is a special instance of a standard problem in convex geometry: compute the (maximal) faces of a polyhedron given in terms of its extreme points. That is: given R vectors $e_k$ in a finite dimensional real vector space, find the extreme points of the convex set of vectors $f$ such that $f \cdot e_k \leq 1$ for all $k$ . By the Bipolar Theorem [2] (or “Farkas’ Lemma”, a special case for polyhedral cones), $x$ then lies in the convex hull of the $e_k$ and the origin, if and only if $f \cdot x \leq 1$ for all extremal $f$ . It is easy to decide when such a vector f is extremal: in that case f must be uniquely determined by the equations $f \cdot e_k =1$ it satisfies.

To find some extreme point is not so difficult: there is a standard algorithm for maximizing an affine functional on a convex set given in this way known as the Simplex Algorithm, which runs into an extreme point. It is an entirely different matter, however, to ask for all extreme points. A straightforward method would be to list all subsets of $\{ 1,...,R \}$ with (#elements)=(#dimensions), and to check for each whether the corresponding set of equations determines an inequality vector $f$ . It is immediately clear that such a brute force approach to the above problem will end in an exponential-of-exponential explosion of computing time, and is bound to fail. There are more intelligent algorithms (e. g. the packages available on [http://www.netlib.org/voronoi/hull.html netlib] or [http://www.ifor.math.ethz.ch/~fukuda/cdd_home/cdd.html C++]), but they, too, all run into serious growth problems for very small (N,M,K). In fact, there is a theorem by Pitovski to the effect that in a closely related problem finding the inequalities would also solve some known hard problems in computational complexity (e. g. to the notorious NP = P, resp. NP = coNP questions [3]).

So a solution of the problem as posed here necessarily makes use of the structure of these particular convex sets.

Partial Results

Constraints on the possible range of values of correlations in the form of inequalities have been investigated for many years (see the monograph by Frechet [4]), even before physicists developed an interest in that subject due to the work of Bell [5]. The convex geometry aspect of the above problem was seen clearly by many authors in the last two decades (e. g. [6], [7], [8], [3], [1]). Undoubtedly some of these have conducted numerical searches for new Bell inequalities. However, there is only little knowledge about inequalities beyond the case (N,M,K)=(2,2,2). Posing this problem is intended as a focal point for putting together the compilations, and the existing general observations, so that the state of the art becomes accessible to a wider community.

As there were many new results obtained during the last years the list below is far from complete. It is rather aimed to provide an overview about the current state of knowledge. Please don’t hesitate to contact us if you have, or know about some interesting results (old or new) which makes the list more accurate.

The first to consider all the possible correlation functions as a convex set surrounded by the faces of a polyhedron apparently was M. Froissart [6]. He identified these faces with extremal generalizations of Bell’s inequalities and gave some examples up to the case where (N,M,K)=(2,3,2).
The case (2,2,2) was analyzed completely by Fine [9]. There are only two types of inequalities: one type just expresses positivity of measured probabilities, the second is the CHSH-inequality.
Tsirelson took up Froissart’s idea and concentrated on the quantum analogue of Bell’s inequalities. He pointed out that quantum theory leads to a convex body wich is in general not a polytope and thus cannot be described by a finite number of inequalities. His most complete results were on bipartite correlation inequalities (N=K=2), where the extremal quantum correlations are attained by states on Clifford algebras. The precise structure of the extremal quantum correlations remained unclear, though. For example, it is not known whether it admits a description by a finite number of analytic, or even polynomial, inequalities [7].
In the work of work of Garg and Mermin [8] the case K>2 was considered, in order to study higher spin analogues of the standard spin-1/2 situation, and maybe find the signs of a classical limit. From the point of view of the problem stated here, the symmetry assumptions of Garg and Mermin are rather strong, so that the inequalities obtained describe only a low dimensional section of the convex body under investigation.
Building on [8], Peres recently claimed “a graphical method giving a large number of Bell inequalities of the Clauser-Horne type [1]” Unfortunately, in that paper he merely applies it to show how to find inequalities for small (N,M,K) again in larger systems, i. e., he does not give any new inequalities in the above technical sense. Peres agrees with Pitovsky that an algorithm for algebraic construction of these Farkas vectors runs into serious computational problems unless one does not use special symmetry properties of these particular convex sets in order to obtain a more efficient algorithm.
Pitowsky and Svozil [10] recently numerically derived a complete set of inequalities for (N,M,K)=(3,2,2) and (2,3,2) taking into account constraints on the marginal distributions. Their results (the coefficients of 53856 inequalities) can be found on their website ((3,2,2) and (2,3,2)).
The complete set of correlation inequalities for all N with M=K=2 was recently computed by Werner and Wolf [11]. This is somewhat surprising, since the worst growth of the problem is expected in the parameter N. There are $2^{(2^N)}$ inequalities on the 2N-dimensional set of correlations corresponding to the maximal faces of a hyper-octahedron, which can thus be characterized by a single albeit non-linear inequality. Any of these inequalities is maximally violated for the generalized GHZ state. Moreover, one can show that these inequalities are satisfied if all the partial transposes of the state are positive semi-definite operators. For the construction and algebraic manipulation of these inequalities a Mathematica 4.0 notebook is provided.
For N=2, M=4, besides the CHSH inequality, we get the following extremal correlation inequalities (E stands for expectation, A for observables of the first and B for observables of the second subsystem):

$\textbf{E} \Big(A_1 (2B_1+B_2-B_3) + A_4(B_2+B_3) + A_3(-B_1+B_2-B_3+B_4)+ A_2(B_1-B_2+B_3+B_4)\Big)\leq 6,$

$\textbf{E} \Big(A_2 (B_1+ 2 B_2+B_3-2 B_4) + A_4 (2 B_1-2B_2 +B_3-B_4)+ A_3 (2B_1+B_2-2 B_3 +B_4)+ A_1 (B_1+B_2+2 B_3 +2B_4)\Big) \leq 10.$

In [40], it is established that the greatest quantum violations of each of the above inequalities are, respectively, $10\sqrt{\frac{2}{3}}$ and $4\sqrt{10+\sqrt{2}}$ .

Recently, the relation between the inequalities derived in [11] for (N,M,K)=(N,2,2) and distillability has been investigated. It was first shown by Dür [12] that the Mermin-Klyshko inequality can be violated by multipartite states, which are not N-partite distillable due to the positivity of the partial transposes with respect to any 1|(N-1) partition. For the case of two qubit systems it has then been shown in [13], [14], [15] that every state violating any (N,M,K)=(N,2,2) inequality is at least bipartite distillable. It is also proven that there exists a link between the amount of the Bell inequality violation and the size of the groups, which have to join in order to be capable of distilling a multipartite GHZ state. Thus, a strong violation is always sufficient for full N-partite distillability.
For the case of (N,M,K)=(2,2,2), (2,3,2) the complete set of correlation inequalities giving the constraint for local hidden variable models, where one additional bit of classical communication is allowed, has been constructed in [16]. It is also shown there that quantum theory satisfies all of these inequalities.
Bell inequalities for bipartite systems and more than two outcomes per observable (and their resistance to noise) have recently been studied in [17] and [18] (see also references therein).
Independently in [19] and [20], it is shown that for the (N,M,K)=(2,3,2)-case only one new Bell-inequality, called I3322, beside the CHSH-inequality exists. The inequality is relevant in the sense that there are quantum states violating no CHSH-inequality but violate the I3322-inequality. A generalization of the inequality to the (2,M,2)-case is presented in [19], as well as its combination with a (2,2,K) generalization of the one presented in [17], to obtain a new Bell-inequality for the general (2,M,K)-case.
It is remarkable that the maximal quantum violation of the I3322 inequality is still unknown (October 2010). In [21], they found the currently best value by a numerical approximation, in which they construct explicitly POVM’s and quantum states. Because the method reveals the highest violation in the limit where the dimension of the Hilbert space tends to infinity, they conjectured that an infinite-dimensional Hilbert space is needed for maximal violation.
In [19] complete sets of Bell inequalities for N=2 parties with small numbers of measurements and outcomes are determined with an exact computational approach. They also analyzed a lot of asymmetric setups, where the number of measurements and outcomes of the two parties are di_erent. For instance, it is proven that if one party has two binary measurements and the other party arbitrary many binary measurements no relevant Bell-inequality except the CHSH exists(see also [20]).
In [22], a connection between the so-called cut polytope in polyhedral combinatorics and the correlation polytope for N=2 parties and MA (MB) dichotomic measurements on Alice’s (Bob’s) site was established. Using results known for cut polytopes, they derived a punch of new tight Bell-inequalities. They gave also explicit characterizations for two classes of Bell-inequalities. The relation between Bell inequalities and cut polytopes also allowed them to analyze properties of Bell-inequalities. For instance, they could show tightness of some Bell inequalities for which it was not known before. Based on this relation they also gave upper bounds for quantum violations [23].
After the breakthrough in the (N,2,2)-case in [24], the multiparty setup was considered for more settings and outcomes. An overview of what have been done until 2005 is given in [25]. Among others, it also contains a method to construct series of Bell-inequalities.
In [26], a method to derive the full set of tight Bell-inequalities for the (N,M,K)=(N,3,2) setup is presented. They introduce the method by determining them for the (2,3,2)-case. Based on these results explicit Bell-inequalities for the (3,3,2)-case are constructed in [27].
In [28], a family of tight Bell-inequality parameterized by the number of parties and dichotomic measurements is constructed, which have the property that no PPT state is violating them. The family contains many of already known Bell-inequalities but also a lot of new ones.
There was a big progress in providing methods for systematical computations of maximal quantum violation of a given Bell inequality. Here, an important step was achieved by applying techniques from linear programming. The restricted case of correlations in the (2,M,2) setup is considered in [29], where results by Tsirelson [7] are used. For the general (N,M,K)-case, hierarchies of semidefinite programs which converge to the maximal quantum violation from above are developed in [30], [31].
In [32], a technique is provided to generate from a tight N-party Bell inequality a (N + 1)-party Bell inequality which is tight as well, and relevant in the sense that it can be violated stronger by quantum mechanics than the given one.
Interested in the question about the dimensionality of the quantum system necessary to generate all correlations, in [33], they present families of Bell inequalities for the case of N=2 parties with generically di_erent number of dichotomic measurements at each site. The construction is build on the connection between c-systems of vectors in an Euclidean vector space and correlations established by Tsirelson [7]. Another family of asymmetric Bell inequalities was constructed in order to study non-local correlations of W-states [34].
In [35], new Bell inequalities for the (2,4,2)-setting are derived. The paper contains also a review of the known Bell inequalities with low numbers of measurements.
A family of Bell-inequalities in the (2,d,d) setup (parameterized by d) as introduced in [36], was intensively studied in [37]. They checked tightness of the inequalities up to d _ 13 as well as maximal quantum violation. The paper [37] contains also a lot of references and can be seen as a good overview of the current state of knowledge.
In [38] numerical methods are applied to construct 129 new Bell inequalities in the (2,4,2) case. The main goal of the paper was to compute quantum bounds of Bell inequalities with 2 Parties, small numbers of measurements and two outcomes. They computed lower bounds by explicit construction of measurement operators and states. Upper bounds are achieved via hierarchies of semide_nite programs [30], [31]. In most of the cases (241) this strategy enabled them to actually _nd the maximal quantum bounds. The paper contains many references and is appropriated to give an overview of Bell inequalities in the setup with 2 parties and a small numbers of dichotomic measurements.
The computational hardness to generate all Bell-inequalities could remarkably be reduced by restricting to Bell inequalities symmetric under exchange of the parties [39]. In the paper, they symmetrize the classical polytope such that it lies in the symmetric subspace only. This reduces the complexity of the computation of all faces, especially in a multiparty setup. Using the introduced method they found many symmetric Bell inequalities (see symmetric Bell inequalities) for various numbers of parties, measurements and outcomes.

References

[1] A. Peres , Found. Phys. 29, 589 (1999)

[2] H. H. Schaefer, Springer (Berlin) 1980

[3] I. Pitovsky , Springer (Berlin) 1989

[4] M. Frechet, Hermann (Paris) 1940

[5] J. S. Bell, Physics 1 (1964)

[6] M. Froissart , Nuovo Cimento B 64

[7] B. S. Tsirelson , J. Sov. Math. 36 (1987)

[8] A. Garg, N. D. Mermin , Found. Phys. 14, 1 (1984)

[9] A. Fine , Phys. Rev. Lett. 48, 291 (1982)

[10] I. Pitowsky and K. Svozil, Phys. Rev. A 64, 014102 (2001)

[11] R. F. Werner and M. M. Wolf, Phys. Rev. A 64, 032112 (2001)

[12] W. Dür , Phys. Rev. Lett. 87, 230402 (2001)

[13] A. Acin, Phys. Rev. Lett. 88, 027901 (2002)

[14]· A. Acín, V. Scarani, M. M. Wolf, J. Phys. A: Math. Gen. 36, L21 (2003)

[15] A. Acín, V. Scarani, M. M. Wolf, Phys. Rev. A 66

[16] D. Bacon, B. F. Toner , Phys. Rev. Lett. 90

[17] D. Collins, N. Gisin, N. Linden, S. Massar, S. Popescu , Phys. Rev. Lett 88

[18] S. Massar, S. Pironio, J. Roland, B. Gisin , quant-ph/0205130 (2002)

[19] D. Collins and N. Gisin, J. Phys. A: Math. Gen. 37 1775 (2004)

[20] Sliwa, Phys. Lett. A, 317: 165 (2003)

[21] K. F. Pál. and T. Vértesi, arXiv:1006.3032(2010)

[22] D. Avis, H. Imai, T. Ito, Y. Sasaki, J. Phys. A: Math. Gen. 38, 10971–87 (2005)

[23] D. Avis, H. Imai, T. Ito, J. Phys. A: Math. Gen. 39, 11283 (2006)

[24] R. F. Werner and M. M. Wolf, Quant. Inf. Comp. 1 (3), 1 (2002)

[25] T. Paterek, W. Laskowski, M. Zukowski, Mod. Phys. Lett. A. 21, 111 (2006) and quant-ph/0512011 (2006)

[26] M. Zukowski, Quant. Inf. Proc. 5, 287 (2006) and quant-ph/0611086 (2006)

[27] M. Wiesniak, P. Badziag, M. Zukowski, Phys. Rev. A 76, 012110 (2007) and quant-ph/0611083

[28] K. Nagata, W. Laskowski and T. Paterek, Phys. Rev. A 74, 062109 (2006) and quant-ph/0601107 (2006)

[29] S. Wehner, Phys. Rev. A, 73, 022110 (2006) and quant-ph/0510076 (2006)

[30] M. Navascues, S. Pironio, A. Acin, New J. Phys. 10, 073013 (2008) and arXiv:0803.4290 (2008)

[31] A. Doherty, Y. Liang, B. Toner, S. Wehner, In Proc. of the 23rd Annual IEEE Conference on Computational Complexity, pages 199-210 (2008) and arXiv:0803.4373 (2008)

[32] Y. Wu, P. Badziag, M. Wiesniak, M. Zukowski, Phys. Rev. A 77, 032105 (2008) and arXiv:0712.3666 (2007)

[33] T. Vértesi and K.F. Pál, Phys. Rev. A 77, 042106 (2008) and arXiv:0712.4225 (2007); and “Bounding the dimension of bipartite quantum systems”, Phys. Rev. A 79, 042106 (2009) and arXiv:0812.1572 (2008)

[34] T. Vértesi, Phys. Rev. A 78, 032112 (2008) and arXiv:0806.0096 (2008)

[35] N. Brunner, N. Gisin, Phys. Lett. A 372, 3162 (2008) and arXiv:0711.3362 (2007)

[36] S.-W. Ji, J. Lee, J. Lim, K. Nagata, and H.-W. Lee, Phys. Rev. A 78, 052103 (2008) and arXiv:0810.2838 (2008)

[37] Y.-C. Liang, C.-W. Lim, D.-L. Deng, Phys. Rev. A 80, 052116 (2009) and arXiv:0903.4964 (2009)

[38] K. F. Pál, T. Vértesi, Phys. Rev. A 79, 022120 (2009) and arXiv:0810.1615 (2008)

[39] J.-D. Bancal, N. Gisin, S. Pironio, J. Phys. A: Math. Theor. 43, 385303 (2010) and arXiv:1004.4146 (2010).

[40] B. Li, Exact values of quantum violations in low-dimensional Bell correlation inequalities, arXiv:1712.08506 (2017).