Jump to navigation Jump to search
Computes the maximum value of a Bell inequality

Other toolboxes required CVX
Related functions NPAHierarchy
Function category Nonlocality and Bell inequalities
Usable within CVX? no

BellInequalityMax is a function that computes the maximum possible value of a given Bell inequality or nonlocal game under either classical mechanics, quantum mechanics, or general no-signalling theories. In the classical and non-signalling cases, an exact value is computed, whereas the value computed in the quantum case is only an upper bound (found using the NPA hierarchy).



Argument descriptions

  • COEFFICIENTS: A matrix or tensor that specifies the coefficients of the Bell inequality in either full probability, full correlator, or Collins-Gisin notation.
  • DESC: A vector of 4 elements describing the number of outputs of Alice, number of outputs of Bob, number of inputs of Alice, and number of inputs of Bob, in this order.
  • NOTATION: A string indicating in which notation are the coefficients of the Bell inequality given. Must be one of 'fp', 'fc', or 'cg', for full probability, full correlator, or Collins-Gisin, respectively.
  • MTYPE (optional, default 'classical'): A string indicating which type of theory should be used when computing the maximum value of the Bell inequality. Must be one of 'classical', 'quantum', or 'nosignal'. If MTYPE = 'quantum' then only an upper bound on the Bell inequality is computed, not necessarily is best upper bound (see the argument K below).
  • K (optional, default 1): If MTYPE = 'quantum' then this is a positive integer indicating what level of the NPA hierarchy should be used when bounding the Bell inequality. Higher values of K give better bounds, but require more memory and time. Alternatively, K can be a string of a form like '1+ab+aab', which indicates that an intermediate level of the hierarchy should be used, where this example uses all products of 1 measurement, all products of one Alice and one Bob measurement, and all products of two Alice and one Bob measurement. Use plus signs to separate the different categories of products, as above. The first character of this string should always be a number, indicating the base level to use. If MTYPE is anything other than 'quantum' then K has no effect.


The CHSH inequality

One formulation of the CHSH inequality[1] says that if $\{A_1,A_2\}$ and $\{B_1,B_2\}$ are $\{-1,+1\}$-valued measurement settings, then in classical physics the following inequality holds: \[\langle A_1 B_1 \rangle + \langle A_1 B_2 \rangle + \langle A_2 B_1 \rangle - \langle A_2 B_2 \rangle \leq 2.\] Similarly, the best bound on this quantity is $2\sqrt{2}$ in a quantum mechanical setting (this is Tsirelson's bound)[2], and it is $4$ in no-signalling theories. All three of these bounds can be found as follows:

>> M = [0 0 0;0 1 1;0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fc','classical')

ans =


>> BellInequalityMax(M,desc,'fc','quantum')         

ans =


>> BellInequalityMax(M,desc,'fc','nosignal')       

ans =


The CHSH inequality again

Another (equivalent) formulation of the CHSH inequality is in Collins-Gisin notation. We write in terms of only the probabilities of obtaining one of the outcomes, as the other probabilities are redundant given the normalization and no-signalling conditions. In this formulation, the following inequality holds in classical theories: \[ p(11|11) + p(11|12) + p(11|21) - p(11|22) - p_A(1|1) - p_B(1|1) \leq 0.\] Similarly, the best bound on this quantity is $1/\sqrt{2} - 1/2$ in a quantum mechanical setting, and it is $1/2$ in no-signalling settings. These three bounds can be verified as follows:

>> M = [0 -1 0; -1 1 1; 0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'cg','classical')        

ans =


>> BellInequalityMax(M,desc,'cg','quantum')         

ans =


>> BellInequalityMax(M,desc,'cg','nosignal')       

ans =


The CHSH game

The CHSH inequality can be reformulated as a nonlocal game, as is favoured in computer science[3]. The rules of the game are as follows:

  • A referee asks Alice a question $x \in \{0,1\}$ and Bob a question $y \in \{0,1\}$ with uniform probability.
  • Alice and Bob then reply with answers $a \in \{0,1\}$ and $b \in \{0,1\}$ respectively.
  • Alice and Bob win if and only if $a \oplus b = xy$.

The optimal probability with which Alice and Bob can win this game in classical, quantum, and no-signalling theories are as follows:

>> M = chshd(2);
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fp','classical')  

ans =


>> BellInequalityMax(M,desc,'fp','quantum')         

ans =


>> BellInequalityMax(M,desc,'fp','nosignal')       

ans =


The auxiliary function chshd() above produces the predicate of the CHSH-d game, an intensively studied variant of the CHSH game that generalizes it to a larger alphabet. The rules are analogous, with the difference that each of $a,b,x,y$ are taken from the set $\{0,1,\ldots,d-1\}$ and sum is done modulo $d$.[4] The algorithm used to calculate the classical bound is parallelized and slightly smarter than naïve brute force[5]. It can handle up to $d=8$ quickly:

>> M = chshd(8);                             
>> desc = [8 8 8 8];
>> BellInequalityMax(M,desc,'fp','classical')
Starting parallel pool (parpool) using the 'local' profile ... connected to 2 workers.

ans =


The I3322 inequality

The I3322 inequality[6][7] is a Bell inequality where each of Alice and Bob has three possible inputs and 2 possible outputs. Its symmetric version in Collins-Gisin notation is given by: \[-p(11|11) - p(11|12) - p(11|13) - p(11|21) - p(11|22) + p(11|23) - p(11|31) + p(11|32) + p_A(1|1) + p_B(1|1) \leq 1.\] Similarly, it is known that a value of (strictly) larger than $1+1/4$ is possible in quantum mechanics[8], and the best possible bound is $2$ in no-signalling theories. The following code computes the best possible classical and no-signalling bounds exactly, and computes several different upper bounds for the quantum mechanical setting:

>> format long
>> cvx_precision high
>> M = [0 1 0 0;1 -1 -1 -1;0 -1 -1 1;0 -1 1 0];
>> desc = [2 2 3 3];
>> BellInequalityMax(M,desc,'cg','classical')

ans =


>> BellInequalityMax(M,desc,'cg','quantum',1)

ans =


>> BellInequalityMax(M,desc,'cg','quantum','1+ab')

ans =


>> BellInequalityMax(M,desc,'cg','quantum',2)

ans =


>> BellInequalityMax(M,desc,'cg','quantum',3)

ans =


>> BellInequalityMax(M,desc,'cg','quantum',4)

ans =


>> BellInequalityMax(M,desc,'cg','nosignal') 

ans =


We note that the values provided for the quantum upper bound above for K = '1+ab', K = 2, and K = 3 agree with the values found in [9] (subtracted 1 to account for the different form of the inequality). Furthermore, the value when K = 4 agrees with the value found in [8]. The exact value of the best upper bound in the quantum setting is an open problem, but is known to be approximately $1.250875384514$.

Source code

Click here to view this function's source code on github.


In practice, K probably can't be any larger than 4 when MTYPE = 'quantum'.


  1. J.F. Clauser, M.A. Horne, A. Shimony, R.A. Holt. Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett., 23(15):880–884, 1969.
  2. B.S. Tsirelson. Quantum generalizations of Bell's inequality. Lett. Math. Phys., 4:93, 1980. E-print
  3. Richard Cleve, Peter Hoyer, Ben Toner, John Watrous. Consequences and Limits of Nonlocal Strategies. E-print: arXiv:quant-ph/0404076
  4. M. Howard. Maximum nonlocality and minimum uncertainty using magic states. E-print: arXiv:arXiv:1501.05319 [quant-ph], 2015.
  5. M. Araújo, F. Hirsch, and M. T. Quintino. Bell nonlocality with a single shot. E-print: arXiv:2005.13418
  6. M. Froissart. Constructive generalization of Bell's inequalities. Nuov. Cim. B, 64:241, 1981
  7. D. Collins and N. Gisin. A relevant two qubit Bell inequality inequivalent to the CHSH inequality. J. Phys. A: Math. Gen., 37(5):1175, 2004. E-print: arXiv:quant-ph/0306129
  8. 8.0 8.1 K.F. Pál and T. Vértesi. Maximal violation of a bipartite three-setting, two-outcome Bell inequality using infinite-dimensional quantum systems. Phys. Rev. A, 82:022116, 2010. E-print: arXiv:1006.3032 [quant-ph]
  9. M. Navascués, S. Pironio, and A. Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New J. Phys., 10:073013, 2008. E-print: arXiv:0803.4290 [quant-ph]