IMaPh : Quantum Information Problems 1 2 3 4 5
All the Bell Inequalities

Formats for viewing: Plain HTML Nice HTML and for printout: PS PDF. If you encounter display problems viewing 'Nice HTML', please consult this page.

Remarks   Problem   Background   Partial Solutions   Literature

Top of page

Remarks

The title was taken from a recent exposition by A. Peres [Pe].

Top of page

Problem

Find all those linear inequalities characterizing the existence of joint probability distributions for all variables in a correlation experiment.

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 managable 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₁ A₂ ... A_N, where each A_i takes values +1,-1, resp. -1 <= A_i <= 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).

Top of page

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 <= 1 for all k. By the Bipolar Theorem [Sc], (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 <= 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 netlib, C++ or in Mathematica), 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 [Pi]).

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

Top of page

Partial Solutions

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 [Fre]), even before physicists developed an interest in that subject due to the work of Bell [Be]. The convex geometry aspect of the above problem was seen clearly by many authors in the last two decades (e. g. [Fr], [Ci], [GM], [Pi], [Pe]). 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.

• The first to consider all the possible correlation functions as a convex set surrounded by the faces of a polyhedron apparently was M. Froissart [Fr]. 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 [Fi]. 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 [Ci].

• In the work of work of Garg and Mermin [GM] 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 [GM], Peres recently claimed "a graphical method giving a large number of Bell inequalities of the Clauser-Horne type [Pe]''. 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 [PS] 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 [WW]. This is somewhat surprising, since the worst growth of the problem is expected in the parameter N. There are 2^(2N) inequalities on the 2^N-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, 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):

  E(A1 (2 B1+B2-B3) + A4 (B2+B3)	+	A3 (-B1+B2-B3+B4)
  	+	A2 (B1-B2+B3+B4)) <= 6,

  E(A2 (B1+ 2 B2 +B3-2 B4)	+	A4 (2 B1-2 B2 +B3-B4)
  	+	A3 (2 B1+B2-2 B3 +B4)
  	+	A1 (B1+B2+2 B3 +2 B4)) <= 10.

• Recently, the relation between the inequalities derived in [WW] for (N,M,K)=(N,2,2) and distillability has been investigated. It was first shown by Dür [Du] 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 [Ac,ASWa,ASWb] 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 [BT]. 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 [CGLMP] and [MPRG] (see also references therein).

Can anyone add to this list?

Top of page

Literature

[Ac]	A. Acin, »Distillability, Bell inequalities and multiparticle bound entanglement«, Phys. Rev. Lett. 88, 027901 (2002) and quant-ph/0108029 (2001).
[ASWa]	A. Acin, V. Scarani, M. M. Wolf, »Violation of Bell's inequalities implies distillability for N qubits«, quant-ph/0112102 (2001).
[ASWb]	A. Acin, V. Scarani, M. M. Wolf, »Bell inequalities and distillability in N-quantum-bit systems«, quant-ph/0206084 (2002).
[Be]	J. S. Bell, »On the Einstein Podolsky Rosen Paradox«, Physics 1 (1964).
[BT]	D. Bacon, B. F. Toner, »Bell inequalities with communication«, quant-ph/0208057 (2002).
[CGLMP]	D. Collins, N. Gisin, N. Linden, S. Massar, S. Popescu, »Bell Inequalities for Arbitrarily High-Dimensional Systems«, Phys. Rev. Lett 88, 040404 (2002) and quant-ph/0106024 (2001).
[Fr]	M. Froissart, »Constructive generalization of Bell's inequalities«, Nuovo Cimento B 64, 241 (1981).
[CB]	M. Zukowski, C. Brukner, »Bell's theorem for general N-qubit states«, Phys. Rev. Lett. 88, 210401 (2002) and quant-ph/0102039 (2001).
[Ci]	B. S. Tsirelson, »Quantum Analogues to the Bell Inequalities«, J. Sov. Math. 36 (1987); B. S. Tsirelson, L. A. Khalfin, »Quantum/Classical Correspondence in the Light of Bell's Inequalities«, Found. Phys. 22, 879 (1992).
[Du]	W. Dür, »Multipartite bound entangled states that violate Bell's inequality«, Phys. Rev. Lett. 87, 230402 (2001) and quant-ph/0107050 (2001).
[Fi]	A. Fine, »Hidden Variables, Joint Probability, and the Bell Inequalities«, Phys. Rev. Lett. 48, 291 (1982).
[GM]	A. Garg, N. D. Mermin, »Farkas's lemma and the nature of reality: Statistical implications of quantum correlations«, Found. Phys. 14, 1 (1984).
[MPRG]	S. Massar, S. Pironio, J. Roland, B. Gisin, »A Zoology of Bell inequalities resistant to detector inefficiency«, quant-ph/0205130 (2002).
[Pe]	A. Peres, »All the Bell Inequalities«, Found. Phys. 29, 589 (1999) and quant-ph/9807017 (1998).
[Pi]	I. Pitovsky, »Quantum Probability - Quantum Logic«, Springer (Berlin) 1989.
[Fre]	M. Fr\'echet, »Les Probabilit\'es Associ\'ees a un Syst\`eme D'\'Ev\'entments Compatibles et D\'epandants«, Hermann (Paris) 1940.
[Sc]	H. H. Schaefer, »Topological Vector Spaces«, Springer (Berlin) 1980.
[PS]	I. Pitowsky and K. Svozil, »New optimal tests of quantum nonlocality«, quant-ph/0011060 (2000).
[WW]	R. F. Werner and M. M. Wolf, »All multipartite Bell correlation inequalities for two dichotomic observables per site«, quant-ph/0102024 (2001).
[WWa]	R. F. Werner and M. M. Wolf, »Bell inequalities and Entanglement«, Quant. Inf. Comp. 1 (3), 1 (2002) and quant-ph/0107093 (2001).

Questions and comments

Last modified: 24 Jun 2003

Sponsored by QUIPROCONE

Top of page