QETLAB - User contributions [en]

BellInequalityMax

2022-11-14T13:32:21Z

Araujoms: /* The I3322 inequality */ we need "cvx_precision high" for "format long" to make sense

{{Function
|name=BellInequalityMax
|desc=Computes the maximum value of a Bell inequality
|rel=[[NPAHierarchy]] [[ParallelRepetition]] [[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=January 22, 2015
|cvx=no}}
<tt>'''BellInequalityMax'''</tt> is a [[List of functions|function]] that computes the maximum possible value of a given [http://en.wikipedia.org/wiki/Bell%27s_theorem 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 [[NPAHierarchy|NPA hierarchy]]).

==Syntax==
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE,K)</tt>

==Argument descriptions==
* <tt>COEFFICIENTS</tt>: A matrix or tensor that specifies the coefficients of the Bell inequality in either full probability, full correlator, or Collins-Gisin notation.
* <tt>DESC</tt>: 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.
* <tt>NOTATION</tt>: A string indicating in which notation are the coefficients of the Bell inequality given. Must be one of <tt>'fp'</tt>, <tt>'fc'</tt>, or <tt>'cg'</tt>, for full probability, full correlator, or Collins-Gisin, respectively.
* <tt>MTYPE</tt> (optional, default <tt>'classical'</tt>): A string indicating which type of theory should be used when computing the maximum value of the Bell inequality. Must be one of <tt>'classical'</tt>, <tt>'quantum'</tt>, or <tt>'nosignal'</tt>. If <tt>MTYPE = 'quantum'</tt> then only an upper bound on the Bell inequality is computed, not necessarily is best upper bound (see the argument <tt>K</tt> below).
* <tt>K</tt> (optional, default <tt>1</tt>): If <tt>MTYPE = 'quantum'</tt> then this is a positive integer indicating what level of the NPA hierarchy should be used when bounding the Bell inequality. Higher values of <tt>K</tt> give better bounds, but require more memory and time. Alternatively, <tt>K</tt> can be a string of a form like <tt>'1+ab+aab'</tt>, 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 <tt>MTYPE</tt> is anything other than <tt>'quantum'</tt> then <tt>K</tt> has no effect.

==Examples==
===The CHSH inequality===
One formulation of the [http://en.wikipedia.org/wiki/CHSH_inequality CHSH inequality]<ref>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.</ref> 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:
: <math>\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.</math>
Similarly, the best bound on this quantity is $2\sqrt{2}$ in a quantum mechanical setting (this is [http://en.wikipedia.org/wiki/Tsirelson%27s_bound Tsirelson's bound])<ref>B.S. Tsirelson. Quantum generalizations of Bell's inequality. Lett. Math. Phys., 4:93, 1980. [http://www.tau.ac.il/~tsirel/download/qbell80.pdf E-print]</ref>, and it is $4$ in no-signalling theories. All three of these bounds can be found as follows:
<syntaxhighlight>
>> M = [0 0 0;0 1 1;0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fc','classical')

ans =

2

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

ans =

2.8284

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

ans =

4
</syntaxhighlight>

===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:
: <math> p(11|11) + p(11|12) + p(11|21) - p(11|22) - p_A(1|1) - p_B(1|1) \leq 0.</math>
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:
<syntaxhighlight>
>> M = [0 -1 0; -1 1 1; 0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'cg','classical')

ans =

0

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

ans =

0.2071

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

ans =

0.5000
</syntaxhighlight>

===The CHSH game===
The CHSH inequality can be reformulated as a nonlocal game, as is favoured in computer science<ref>Richard Cleve, Peter Hoyer, Ben Toner, John Watrous. Consequences and Limits of Nonlocal Strategies. E-print: [http://arxiv.org/abs/quant-ph/0404076 arXiv:quant-ph/0404076]</ref>. 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:
<syntaxhighlight>
>> M = chshd(2);
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fp','classical')

ans =

0.7500

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

ans =

0.8536

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

ans =

1
</syntaxhighlight>
The auxiliary function <tt>chshd()</tt> 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$.<ref>M. Howard. Maximum nonlocality and minimum uncertainty using magic states. E-print: [http://arxiv.org/abs/1501.05319 arXiv:arXiv:1501.05319] [quant-ph], 2015.</ref> The algorithm used to calculate the classical bound is parallelized and slightly smarter than naïve brute force<ref>M. Araújo, F. Hirsch, and M. T. Quintino. Bell nonlocality with a single shot. E-print: [https://arxiv.org/abs/2005.13418 arXiv:2005.13418]</ref>. It can handle up to $d=8$ quickly:
<syntaxhighlight>
>> 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 =

0.4688
</syntaxhighlight>
===The I3322 inequality===
The I3322 inequality<ref>M. Froissart. Constructive generalization of Bell's inequalities. Nuov. Cim. B, 64:241, 1981</ref><ref>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: [http://arxiv.org/abs/quant-ph/0306129 arXiv:quant-ph/0306129]</ref> 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:
: <math>-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.</math>
Similarly, it is known that a value of (strictly) larger than $1+1/4$ is possible in quantum mechanics<ref name="palvertes">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: [http://arxiv.org/abs/1006.3032 arXiv:1006.3032] [quant-ph]</ref>, 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:
<syntaxhighlight>
>> 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 =

1

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

ans =

1.374999999999371

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

ans =

1.251470897748553

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

ans =

1.250939721643942

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

ans =

1.250875562046812

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

ans =

1.250875384515790

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

ans =

2

</syntaxhighlight>

We note that the values provided for the quantum upper bound above for <tt>K = '1+ab'</tt>, <tt>K = 2</tt>, and <tt>K = 3</tt> agree with the values found in <ref name="npa2">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: [http://arxiv.org/abs/0803.4290 arXiv:0803.4290] [quant-ph]</ref> (subtracted 1 to account for the different form of the inequality). Furthermore, the value when <tt>K = 4</tt> agrees with the value found in <ref name="palvertes"></ref>. The exact value of the best upper bound in the quantum setting is an open problem, but is known to be approximately $1.250875384514$.
{{SourceCode|name=BellInequalityMax}}

==Notes==
In practice, <tt>K</tt> probably can't be any larger than 4 when <tt>MTYPE = 'quantum'</tt>.

==References==
<references />

BellInequalityMax

2022-11-11T12:40:35Z

Araujoms: /* Argument descriptions */ K cannot be zero

{{Function
|name=BellInequalityMax
|desc=Computes the maximum value of a Bell inequality
|rel=[[NPAHierarchy]] [[ParallelRepetition]] [[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=January 22, 2015
|cvx=no}}
<tt>'''BellInequalityMax'''</tt> is a [[List of functions|function]] that computes the maximum possible value of a given [http://en.wikipedia.org/wiki/Bell%27s_theorem 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 [[NPAHierarchy|NPA hierarchy]]).

==Syntax==
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE,K)</tt>

==Argument descriptions==
* <tt>COEFFICIENTS</tt>: A matrix or tensor that specifies the coefficients of the Bell inequality in either full probability, full correlator, or Collins-Gisin notation.
* <tt>DESC</tt>: 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.
* <tt>NOTATION</tt>: A string indicating in which notation are the coefficients of the Bell inequality given. Must be one of <tt>'fp'</tt>, <tt>'fc'</tt>, or <tt>'cg'</tt>, for full probability, full correlator, or Collins-Gisin, respectively.
* <tt>MTYPE</tt> (optional, default <tt>'classical'</tt>): A string indicating which type of theory should be used when computing the maximum value of the Bell inequality. Must be one of <tt>'classical'</tt>, <tt>'quantum'</tt>, or <tt>'nosignal'</tt>. If <tt>MTYPE = 'quantum'</tt> then only an upper bound on the Bell inequality is computed, not necessarily is best upper bound (see the argument <tt>K</tt> below).
* <tt>K</tt> (optional, default <tt>1</tt>): If <tt>MTYPE = 'quantum'</tt> then this is a positive integer indicating what level of the NPA hierarchy should be used when bounding the Bell inequality. Higher values of <tt>K</tt> give better bounds, but require more memory and time. Alternatively, <tt>K</tt> can be a string of a form like <tt>'1+ab+aab'</tt>, 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 <tt>MTYPE</tt> is anything other than <tt>'quantum'</tt> then <tt>K</tt> has no effect.

==Examples==
===The CHSH inequality===
One formulation of the [http://en.wikipedia.org/wiki/CHSH_inequality CHSH inequality]<ref>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.</ref> 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:
: <math>\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.</math>
Similarly, the best bound on this quantity is $2\sqrt{2}$ in a quantum mechanical setting (this is [http://en.wikipedia.org/wiki/Tsirelson%27s_bound Tsirelson's bound])<ref>B.S. Tsirelson. Quantum generalizations of Bell's inequality. Lett. Math. Phys., 4:93, 1980. [http://www.tau.ac.il/~tsirel/download/qbell80.pdf E-print]</ref>, and it is $4$ in no-signalling theories. All three of these bounds can be found as follows:
<syntaxhighlight>
>> M = [0 0 0;0 1 1;0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fc','classical')

ans =

2

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

ans =

2.8284

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

ans =

4
</syntaxhighlight>

===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:
: <math> p(11|11) + p(11|12) + p(11|21) - p(11|22) - p_A(1|1) - p_B(1|1) \leq 0.</math>
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:
<syntaxhighlight>
>> M = [0 -1 0; -1 1 1; 0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'cg','classical')

ans =

0

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

ans =

0.2071

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

ans =

0.5000
</syntaxhighlight>

===The CHSH game===
The CHSH inequality can be reformulated as a nonlocal game, as is favoured in computer science<ref>Richard Cleve, Peter Hoyer, Ben Toner, John Watrous. Consequences and Limits of Nonlocal Strategies. E-print: [http://arxiv.org/abs/quant-ph/0404076 arXiv:quant-ph/0404076]</ref>. 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:
<syntaxhighlight>
>> M = chshd(2);
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fp','classical')

ans =

0.7500

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

ans =

0.8536

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

ans =

1
</syntaxhighlight>
The auxiliary function <tt>chshd()</tt> 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$.<ref>M. Howard. Maximum nonlocality and minimum uncertainty using magic states. E-print: [http://arxiv.org/abs/1501.05319 arXiv:arXiv:1501.05319] [quant-ph], 2015.</ref> The algorithm used to calculate the classical bound is parallelized and slightly smarter than naïve brute force<ref>M. Araújo, F. Hirsch, and M. T. Quintino. Bell nonlocality with a single shot. E-print: [https://arxiv.org/abs/2005.13418 arXiv:2005.13418]</ref>. It can handle up to $d=8$ quickly:
<syntaxhighlight>
>> 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 =

0.4688
</syntaxhighlight>
===The I3322 inequality===
The I3322 inequality<ref>M. Froissart. Constructive generalization of Bell's inequalities. Nuov. Cim. B, 64:241, 1981</ref><ref>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: [http://arxiv.org/abs/quant-ph/0306129 arXiv:quant-ph/0306129]</ref> 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:
: <math>-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.</math>
Similarly, it is known that a value of (strictly) larger than $1+1/4$ is possible in quantum mechanics<ref name="palvertes">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: [http://arxiv.org/abs/1006.3032 arXiv:1006.3032] [quant-ph]</ref>, 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:
<syntaxhighlight>
>> format long
>> 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 =

1

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

ans =

1.374999892449922

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

ans =

1.251470917522884

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

ans =

1.250939790350636

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

ans =

1.250875663436317

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

ans =

1.250875380616149

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

ans =

2.000000000005738
</syntaxhighlight>

We note that the values provided for the quantum upper bound above for <tt>K = '1+ab'</tt>, <tt>K = 2</tt>, and <tt>K = 3</tt> agree with the values found in <ref name="npa2">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: [http://arxiv.org/abs/0803.4290 arXiv:0803.4290] [quant-ph]</ref> (subtracted 1 to account for the different form of the inequality). Furthermore, the value when <tt>K = 4</tt> agrees with the value found in <ref name="palvertes"></ref>. The exact value of the best upper bound in the quantum setting is an open problem, but is known to be approximately $1.250875$.
{{SourceCode|name=BellInequalityMax}}

==Notes==
In practice, <tt>K</tt> probably can't be any larger than 4 when <tt>MTYPE = 'quantum'</tt>.

==References==
<references />

NPAHierarchy

2022-11-11T12:39:56Z

Araujoms: /* Argument descriptions */ K=0 doesn't exist anymore

{{Function
|name=NPAHierarchy
|desc=Determines whether or not a set of probabilities satisfy the conditions of the NPA hierarchy
|rel=[[BellInequalityMax]] [[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=November 11, 2022
|cvx=yes (concave)}}
<tt>'''NPAHierarchy'''</tt> is a [[List of functions|function]] that determines whether or not a given set of probabilities satisfy the constraints specified by the NPA hierarchy<ref name="npa">M. Navascués, S. Pironio, and A. Acín. Bounding the set of quantum correlations. ''Phys. Rev. Lett.'', 98:010401, 2007. E-print: [http://arxiv.org/abs/quant-ph/0607119/ arXiv:quant-ph/0607119]</ref><ref name="npa2">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: [http://arxiv.org/abs/0803.4290 arXiv:0803.4290] [quant-ph]</ref>, which are a set of necessary conditions that probabilities arising from quantum mechanics must satisfy. That is, given a set of probabilities $\{p(a,b|x,y)\}$, this function tries to determine whether or not there is a quantum state $\rho$ shared between Alice and Bob, and sets of measurement operators $\{M_{a|x}\}$ for Alice and $\{M_{b|y}\}$ for Bob such that $p(a,b|x,y) = \mathrm{Tr}(\rho(M_{a|x} \otimes M_{b|y}))$ for all $a,b,x,y$ (here $x$ indexes the different measurement settings for Alice, while $a$ indexes the different measurement outcomes within that setting, and similarly for $y$ and $b$ for Bob).

==Syntax==
* <tt>IS_NPA = NPAHierarchy(P,desc)</tt>
* <tt>IS_NPA = NPAHierarchy(P,desc,K)</tt>

==Argument descriptions==
* <tt>P</tt>: A behaviour in Collins-Gisin notation. That is, a matrix with components
:<math>
\begin{pmatrix}
1 & p_B(0|0) & p_B(1|0) & \ldots & p_B(0|1) & p_B(1|1) & \ldots \\
p_A(0|0) & p(00|00) & p(01|00) & \ldots & p(00|01) & p(01|01) &\ldots \\
p_A(1|0) & p(10|00) & p(11|00) & \ldots & p(10|01) & p(11|01) &\ldots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\vdots \\
p_A(0|1) & p(00|10) & p(01|10) & \ldots & p(00|11) & p(01|11) &\ldots \\
p_A(1|1) & p(10|10) & p(11|10) & \ldots & p(10|11) & p(11|11) &\ldots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\ddots \\
\end{pmatrix}
</math>
* <tt>DESC</tt>: 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.
* <tt>K</tt> (optional, default 1): A positive integer that determines the level of the NPA hierarchy to use. Alternatively, <tt>K</tt> 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.

==Examples==
===Can be used within CVX===
Within CVX, this function is treated as any other concave function (so you can use it as an equality or <tt>>=</tt> constraint, or maximize it subject to other constraints). It is used inside the function [[BellInequalityMax]] to upperbound the Tsirelson bound. One can use it to maximize a Bell inequality subject to further constraints, or to determine whether a behaviour belongs to the quantum set of correlations.

For example, one might wonder what is the maximal violation of the CHSH inequality if Alice and Bob obtain equal outcomes with probability 1 in one of the settings. Translating into Collins-Gisin notation, this is the condition that <math>2p(00|xy) = p_A(0|x) + p_B(0|y)</math> for some x,y.:

<syntaxhighlight>
>> B = [0, -1, 0; -1, 1, 1; 0, 1, -1]; %CHSH functional in Collins-Gisin form
desc = [2 2 2 2];
cvx_begin
variable p(3,3);
objective = B(:)'*p(:);
maximize objective
subject to
p(1,1) == 1; %the top left element of the behaviour must always be equal to 1
NPAHierarchy(p,desc,2) == 1; %here we impose level 2 of the NPA hierarchy
2*p(2,2) == p(1,2) + p(2,1); %this is the constraint that Alice and Bob have equal outcomes
cvx_end

Optimal value (cvx_optval): +0.125009
</syntaxhighlight>

One can see that the SDP solver runs into numerical problems and delivers a solution that is not so close to the analytical one, 1/8. This is not a problem with the code, but a fundamental problem with semidefinite programming: this problem is not strictly feasible, and the interior-point algorithms relies on strict feasibility to obtain a reliable solution. In order to obtain a reliable solution numerically one needs to reformulate the problem to make it strictly feasible, for example using facial reduction<ref>Dmitriy Drusvyatskiy, Henry Wolkowicz. The many faces of degeneracy in conic optimization. E-print: [http://arxiv.org/abs/1706.03705 arXiv:1706.03705]</ref>.

In order to test whether a given behaviour belongs to the quantum set, one must also be careful to formulate the problem in a strictly feasible way. One way to do that is ask how much of the uniformly random behaviour must be mixed with P in order to make it fall into the quantum set. If the answer is zero, it means that the behaviour was already quantum. The following code shows that the PR-box is not in the quantum set:

<syntaxhighlight>
>> prbox = [2, 1, 1;1, 1, 1;1,1,0]/2; %PR box
p_random = [4, 2, 2;2, 1, 1;2, 1, 1]/4; %uniformly random behaviour
desc = [2 2 2 2];
cvx_begin
variable lambda;
minimize lambda;
subject to
NPAHierarchy(lambda*p_random + (1-lambda)*prbox,desc,2) == 1;
cvx_end

Optimal value (cvx_optval): +0.292893
</syntaxhighlight>
{{SourceCode|name=NPAHierarchy}}

==References==
<references />

ParallelRepetition

2022-11-11T12:39:14Z

Araujoms: created page to document new

{{Function
|name=ParallelRepetition
|desc=Computes coefficients of parallel repetition of a nonlocal game
|rel=[[BCSGameValue]] [[BellInequalityMax]] [[NPAHierarchy]] [[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=March 6, 2015
|cvx=no}}

<tt>'''ParallelRepetition'''</tt> is a [[List of functions|function]] that generates the coefficients of the parallel repetition of a nonlocal game, a concept widely used in computer science.

==Syntax==
* <tt>NGVAL = NonlocalGameValue(G,REPT)</tt>

==Argument descriptions==
* <tt>G</tt>: A 4-D array whose $(a,b,x,y)$-entry gives the coefficient needed to compute the probability of winning the nonlocal game. It is defined as <math>G(a,b,x,y) = \mu(x,y)V(a,b,x,y)</math>, where <math>\mu(x,y)</math> is the probability that the referee asks Alice question $x$ and Bob question $y$, and V(a,b,x,y) is the probability Alice and Bob win the game if they reply with answers $(a,b)$ to questions $(x,y)$.
* <tt>REPT</tt>: A positive integer indicating the number of parallel copies of the nonlocal game.

==Examples==
===The CHSH game===
A well-known result is that the parallel repetition of the CHSH game has local bound higher then the product of the local bounds<ref>J. Barrett, D. Collins, L. Hardy, A. Kent and S. Popescu. ‘Quantum nonlocality, Bell inequalities, and the memory loophole’. Physical Review A 66 042111 (2002). [http://arxiv.org/abs/quant-ph/0205016 arXiv:quant-ph/0205016]</ref>. We can do 2 parallel repetitions:
<syntaxhighlight>
>> G = chshd(2);
>> G2 = ParallelRepetition(G,2);
>> desc = size(G2);
>> BellInequalityMax(G2,desc,'fp','classical')

ans =

0.6250

</syntaxhighlight>
We see that the local bound is 10/16, which is larger than <math>(3/4)^2</math>. We can also do 3 parallel repetitions:
<syntaxhighlight>
>> G = chshd(2);
>> G3 = ParallelRepetition(G,3);
>> desc = size(G3);
>> BellInequalityMax(G3,desc,'fp','classical')
Starting parallel pool (parpool) using the 'local' profile ...
connected to 2 workers.

ans =

0.4844

</syntaxhighlight>
We see that the local bound is 31/64, which is larger than <math>(3/4)^3</math>. The code cannot handle 4 or more parallel repetitions.

===The Fortnow-Feige-Lovász game===
The Fortnow-Feige-Lovász (FFL) game<ref>U. Feige, L. Lovász, In Proceedings of the 24th ACM STOC, pages 733-744, 1992.</ref><ref>L. Fortnow, PhD thesis, Massachusetts Institute of Technology, Technical Report MIT/LCS/TR-447, May 1989.</ref> is well-known example of a non-local game for which perfect parallel repetition does not hold (i.e., quantum players playing two copies of the game in parallel can do better than they can by playing the games in succession).

The game has binary inputs and outputs, and is defined by the rule that the referee asks Alice and Bob the question pair $(x,y) = (0,0)$, $(0,1)$, or $(1,0)$ with probability $1/3$ each, and Alice and Bob win if and only if their answers satisfy $x \vee a \neq y \vee b$, where $\vee$ denotes the bitwise OR operation.

It is known that both the classical value and quantum value of this game equal $2/3$, which we can verify as follows:
<syntaxhighlight>
>> G = ffl();
>> desc = size(G);
>> BellInequalityMax(G,desc,'fp','classical')

ans =

0.6667

>> BellInequalityMax(G,desc,'fp','quantum',2)

ans =

0.6667

</syntaxhighlight>

The FFL game is interesting because the classical value of two parallel repetitions is still $2/3$:<ref>R. Cleve, W. Slofstra, F. Unger, and S. Upadhyay. Perfect parallel repetition theorem for quantum XOR proof systems. ''Computational Complexity'', 17:282–299, 2008. E-print: [http://arxiv.org/abs/quant-ph/0608146 arXiv:quant-ph/0608146]</ref>.
<syntaxhighlight>
>> G = ffl();
>> G2 = ParallelRepetition(G,2);
>> desc = size(G2);
>> BellInequalityMax(G2,desc,'fp','classical')

ans =

0.6667

</syntaxhighlight>
We can also compute the classical value of three parallel repetitions, which decreases to $14/27$:
<syntaxhighlight>
>> G = ffl();
>> G3 = ParallelRepetition(G,3);
>> desc = size(G3);
>> BellInequalityMax(G3,desc,'fp','classical')

ans =

0.5185

</syntaxhighlight>

{{SourceCode|name=ParallelRepetition}}

==Notes==
* The algorithm for computing the classical value is parallelized, which leads to much faster performance on computers with multiple CPUs. Nevertheless, the complexity is still superexponential in <tt>REPT</tt>, making 4 or more parallel repetitions intractable.
==References==
<references />

NPAHierarchy

2022-11-11T11:13:35Z

Araujoms: update page to reflect new code

{{Function
|name=NPAHierarchy
|desc=Determines whether or not a set of probabilities satisfy the conditions of the NPA hierarchy
|rel=[[BellInequalityMax]] [[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=November 11, 2022
|cvx=yes (concave)}}
<tt>'''NPAHierarchy'''</tt> is a [[List of functions|function]] that determines whether or not a given set of probabilities satisfy the constraints specified by the NPA hierarchy<ref name="npa">M. Navascués, S. Pironio, and A. Acín. Bounding the set of quantum correlations. ''Phys. Rev. Lett.'', 98:010401, 2007. E-print: [http://arxiv.org/abs/quant-ph/0607119/ arXiv:quant-ph/0607119]</ref><ref name="npa2">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: [http://arxiv.org/abs/0803.4290 arXiv:0803.4290] [quant-ph]</ref>, which are a set of necessary conditions that probabilities arising from quantum mechanics must satisfy. That is, given a set of probabilities $\{p(a,b|x,y)\}$, this function tries to determine whether or not there is a quantum state $\rho$ shared between Alice and Bob, and sets of measurement operators $\{M_{a|x}\}$ for Alice and $\{M_{b|y}\}$ for Bob such that $p(a,b|x,y) = \mathrm{Tr}(\rho(M_{a|x} \otimes M_{b|y}))$ for all $a,b,x,y$ (here $x$ indexes the different measurement settings for Alice, while $a$ indexes the different measurement outcomes within that setting, and similarly for $y$ and $b$ for Bob).

==Syntax==
* <tt>IS_NPA = NPAHierarchy(P,desc)</tt>
* <tt>IS_NPA = NPAHierarchy(P,desc,K)</tt>

==Argument descriptions==
* <tt>P</tt>: A behaviour in Collins-Gisin notation. That is, a matrix with components
:<math>
\begin{pmatrix}
1 & p_B(0|0) & p_B(1|0) & \ldots & p_B(0|1) & p_B(1|1) & \ldots \\
p_A(0|0) & p(00|00) & p(01|00) & \ldots & p(00|01) & p(01|01) &\ldots \\
p_A(1|0) & p(10|00) & p(11|00) & \ldots & p(10|01) & p(11|01) &\ldots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\vdots \\
p_A(0|1) & p(00|10) & p(01|10) & \ldots & p(00|11) & p(01|11) &\ldots \\
p_A(1|1) & p(10|10) & p(11|10) & \ldots & p(10|11) & p(11|11) &\ldots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots &\ddots \\
\end{pmatrix}
</math>
* <tt>DESC</tt>: 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.
* <tt>K</tt> (optional, default 1): A non-negative integer that determines the level of the NPA hierarchy to use. Alternatively, <tt>K</tt> 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.

==Examples==
===Can be used within CVX===
Within CVX, this function is treated as any other concave function (so you can use it as an equality or <tt>>=</tt> constraint, or maximize it subject to other constraints). It is used inside the function [[BellInequalityMax]] to upperbound the Tsirelson bound. One can use it to maximize a Bell inequality subject to further constraints, or to determine whether a behaviour belongs to the quantum set of correlations.

For example, one might wonder what is the maximal violation of the CHSH inequality if Alice and Bob obtain equal outcomes with probability 1 in one of the settings. Translating into Collins-Gisin notation, this is the condition that <math>2p(00|xy) = p_A(0|x) + p_B(0|y)</math> for some x,y.:

<syntaxhighlight>
>> B = [0, -1, 0; -1, 1, 1; 0, 1, -1]; %CHSH functional in Collins-Gisin form
desc = [2 2 2 2];
cvx_begin
variable p(3,3);
objective = B(:)'*p(:);
maximize objective
subject to
p(1,1) == 1; %the top left element of the behaviour must always be equal to 1
NPAHierarchy(p,desc,2) == 1; %here we impose level 2 of the NPA hierarchy
2*p(2,2) == p(1,2) + p(2,1); %this is the constraint that Alice and Bob have equal outcomes
cvx_end

Optimal value (cvx_optval): +0.125009
</syntaxhighlight>

One can see that the SDP solver runs into numerical problems and delivers a solution that is not so close to the analytical one, 1/8. This is not a problem with the code, but a fundamental problem with semidefinite programming: this problem is not strictly feasible, and the interior-point algorithms relies on strict feasibility to obtain a reliable solution. In order to obtain a reliable solution numerically one needs to reformulate the problem to make it strictly feasible, for example using facial reduction<ref>Dmitriy Drusvyatskiy, Henry Wolkowicz. The many faces of degeneracy in conic optimization. E-print: [http://arxiv.org/abs/1706.03705 arXiv:1706.03705]</ref>.

In order to test whether a given behaviour belongs to the quantum set, one must also be careful to formulate the problem in a strictly feasible way. One way to do that is ask how much of the uniformly random behaviour must be mixed with P in order to make it fall into the quantum set. If the answer is zero, it means that the behaviour was already quantum. The following code shows that the PR-box is not in the quantum set:

<syntaxhighlight>
>> prbox = [2, 1, 1;1, 1, 1;1,1,0]/2; %PR box
p_random = [4, 2, 2;2, 1, 1;2, 1, 1]/4; %uniformly random behaviour
desc = [2 2 2 2];
cvx_begin
variable lambda;
minimize lambda;
subject to
NPAHierarchy(lambda*p_random + (1-lambda)*prbox,desc,2) == 1;
cvx_end

Optimal value (cvx_optval): +0.292893
</syntaxhighlight>
{{SourceCode|name=NPAHierarchy}}

==References==
<references />

BellInequalityMax

2022-11-10T11:23:07Z

Araujoms: /* The I3322 inequality */

{{Function
|name=BellInequalityMax
|desc=Computes the maximum value of a Bell inequality
|rel=[[NPAHierarchy]] [[ParallelRepetition]] [[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=January 22, 2015
|cvx=no}}
<tt>'''BellInequalityMax'''</tt> is a [[List of functions|function]] that computes the maximum possible value of a given [http://en.wikipedia.org/wiki/Bell%27s_theorem 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 [[NPAHierarchy|NPA hierarchy]]).

==Syntax==
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE,K)</tt>

==Argument descriptions==
* <tt>COEFFICIENTS</tt>: A matrix or tensor that specifies the coefficients of the Bell inequality in either full probability, full correlator, or Collins-Gisin notation.
* <tt>DESC</tt>: 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.
* <tt>NOTATION</tt>: A string indicating in which notation are the coefficients of the Bell inequality given. Must be one of <tt>'fp'</tt>, <tt>'fc'</tt>, or <tt>'cg'</tt>, for full probability, full correlator, or Collins-Gisin, respectively.
* <tt>MTYPE</tt> (optional, default <tt>'classical'</tt>): A string indicating which type of theory should be used when computing the maximum value of the Bell inequality. Must be one of <tt>'classical'</tt>, <tt>'quantum'</tt>, or <tt>'nosignal'</tt>. If <tt>MTYPE = 'quantum'</tt> then only an upper bound on the Bell inequality is computed, not necessarily is best upper bound (see the argument <tt>K</tt> below).
* <tt>K</tt> (optional, default <tt>1</tt>): If <tt>MTYPE = 'quantum'</tt> then this is a non-negative integer indicating what level of the NPA hierarchy should be used when bounding the Bell inequality. Higher values of <tt>K</tt> give better bounds, but require more memory and time. Alternatively, <tt>K</tt> can be a string of a form like <tt>'1+ab+aab'</tt>, 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 <tt>MTYPE</tt> is anything other than <tt>'quantum'</tt> then <tt>K</tt> has no effect.

==Examples==
===The CHSH inequality===
One formulation of the [http://en.wikipedia.org/wiki/CHSH_inequality CHSH inequality]<ref>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.</ref> 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:
: <math>\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.</math>
Similarly, the best bound on this quantity is $2\sqrt{2}$ in a quantum mechanical setting (this is [http://en.wikipedia.org/wiki/Tsirelson%27s_bound Tsirelson's bound])<ref>B.S. Tsirelson. Quantum generalizations of Bell's inequality. Lett. Math. Phys., 4:93, 1980. [http://www.tau.ac.il/~tsirel/download/qbell80.pdf E-print]</ref>, and it is $4$ in no-signalling theories. All three of these bounds can be found as follows:
<syntaxhighlight>
>> M = [0 0 0;0 1 1;0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fc','classical')

ans =

2

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

ans =

2.8284

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

ans =

4
</syntaxhighlight>

===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:
: <math> p(11|11) + p(11|12) + p(11|21) - p(11|22) - p_A(1|1) - p_B(1|1) \leq 0.</math>
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:
<syntaxhighlight>
>> M = [0 -1 0; -1 1 1; 0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'cg','classical')

ans =

0

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

ans =

0.2071

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

ans =

0.5000
</syntaxhighlight>

===The CHSH game===
The CHSH inequality can be reformulated as a nonlocal game, as is favoured in computer science<ref>Richard Cleve, Peter Hoyer, Ben Toner, John Watrous. Consequences and Limits of Nonlocal Strategies. E-print: [http://arxiv.org/abs/quant-ph/0404076 arXiv:quant-ph/0404076]</ref>. 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:
<syntaxhighlight>
>> M = chshd(2);
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fp','classical')

ans =

0.7500

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

ans =

0.8536

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

ans =

1
</syntaxhighlight>
The auxiliary function <tt>chshd()</tt> 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$.<ref>M. Howard. Maximum nonlocality and minimum uncertainty using magic states. E-print: [http://arxiv.org/abs/1501.05319 arXiv:arXiv:1501.05319] [quant-ph], 2015.</ref> The algorithm used to calculate the classical bound is parallelized and slightly smarter than naïve brute force<ref>M. Araújo, F. Hirsch, and M. T. Quintino. Bell nonlocality with a single shot. E-print: [https://arxiv.org/abs/2005.13418 arXiv:2005.13418]</ref>. It can handle up to $d=8$ quickly:
<syntaxhighlight>
>> 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 =

0.4688
</syntaxhighlight>
===The I3322 inequality===
The I3322 inequality<ref>M. Froissart. Constructive generalization of Bell's inequalities. Nuov. Cim. B, 64:241, 1981</ref><ref>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: [http://arxiv.org/abs/quant-ph/0306129 arXiv:quant-ph/0306129]</ref> 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:
: <math>-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.</math>
Similarly, it is known that a value of (strictly) larger than $1+1/4$ is possible in quantum mechanics<ref name="palvertes">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: [http://arxiv.org/abs/1006.3032 arXiv:1006.3032] [quant-ph]</ref>, 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:
<syntaxhighlight>
>> format long
>> 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 =

1

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

ans =

1.374999892449922

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

ans =

1.251470917522884

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

ans =

1.250939790350636

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

ans =

1.250875663436317

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

ans =

1.250875380616149

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

ans =

2.000000000005738
</syntaxhighlight>

We note that the values provided for the quantum upper bound above for <tt>K = '1+ab'</tt>, <tt>K = 2</tt>, and <tt>K = 3</tt> agree with the values found in <ref name="npa2">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: [http://arxiv.org/abs/0803.4290 arXiv:0803.4290] [quant-ph]</ref> (subtracted 1 to account for the different form of the inequality). Furthermore, the value when <tt>K = 4</tt> agrees with the value found in <ref name="palvertes"></ref>. The exact value of the best upper bound in the quantum setting is an open problem, but is known to be approximately $1.250875$.
{{SourceCode|name=BellInequalityMax}}

==Notes==
In practice, <tt>K</tt> probably can't be any larger than 4 when <tt>MTYPE = 'quantum'</tt>.

==References==
<references />

BellInequalityMax

2022-11-10T11:22:00Z

Araujoms: /* The I3322 inequality */ fix typo in the inequality and update values for the new code

{{Function
|name=BellInequalityMax
|desc=Computes the maximum value of a Bell inequality
|rel=[[NPAHierarchy]] [[ParallelRepetition]] [[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=January 22, 2015
|cvx=no}}
<tt>'''BellInequalityMax'''</tt> is a [[List of functions|function]] that computes the maximum possible value of a given [http://en.wikipedia.org/wiki/Bell%27s_theorem 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 [[NPAHierarchy|NPA hierarchy]]).

==Syntax==
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE,K)</tt>

==Argument descriptions==
* <tt>COEFFICIENTS</tt>: A matrix or tensor that specifies the coefficients of the Bell inequality in either full probability, full correlator, or Collins-Gisin notation.
* <tt>DESC</tt>: 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.
* <tt>NOTATION</tt>: A string indicating in which notation are the coefficients of the Bell inequality given. Must be one of <tt>'fp'</tt>, <tt>'fc'</tt>, or <tt>'cg'</tt>, for full probability, full correlator, or Collins-Gisin, respectively.
* <tt>MTYPE</tt> (optional, default <tt>'classical'</tt>): A string indicating which type of theory should be used when computing the maximum value of the Bell inequality. Must be one of <tt>'classical'</tt>, <tt>'quantum'</tt>, or <tt>'nosignal'</tt>. If <tt>MTYPE = 'quantum'</tt> then only an upper bound on the Bell inequality is computed, not necessarily is best upper bound (see the argument <tt>K</tt> below).
* <tt>K</tt> (optional, default <tt>1</tt>): If <tt>MTYPE = 'quantum'</tt> then this is a non-negative integer indicating what level of the NPA hierarchy should be used when bounding the Bell inequality. Higher values of <tt>K</tt> give better bounds, but require more memory and time. Alternatively, <tt>K</tt> can be a string of a form like <tt>'1+ab+aab'</tt>, 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 <tt>MTYPE</tt> is anything other than <tt>'quantum'</tt> then <tt>K</tt> has no effect.

==Examples==
===The CHSH inequality===
One formulation of the [http://en.wikipedia.org/wiki/CHSH_inequality CHSH inequality]<ref>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.</ref> 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:
: <math>\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.</math>
Similarly, the best bound on this quantity is $2\sqrt{2}$ in a quantum mechanical setting (this is [http://en.wikipedia.org/wiki/Tsirelson%27s_bound Tsirelson's bound])<ref>B.S. Tsirelson. Quantum generalizations of Bell's inequality. Lett. Math. Phys., 4:93, 1980. [http://www.tau.ac.il/~tsirel/download/qbell80.pdf E-print]</ref>, and it is $4$ in no-signalling theories. All three of these bounds can be found as follows:
<syntaxhighlight>
>> M = [0 0 0;0 1 1;0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fc','classical')

ans =

2

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

ans =

2.8284

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

ans =

4
</syntaxhighlight>

===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:
: <math> p(11|11) + p(11|12) + p(11|21) - p(11|22) - p_A(1|1) - p_B(1|1) \leq 0.</math>
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:
<syntaxhighlight>
>> M = [0 -1 0; -1 1 1; 0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'cg','classical')

ans =

0

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

ans =

0.2071

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

ans =

0.5000
</syntaxhighlight>

===The CHSH game===
The CHSH inequality can be reformulated as a nonlocal game, as is favoured in computer science<ref>Richard Cleve, Peter Hoyer, Ben Toner, John Watrous. Consequences and Limits of Nonlocal Strategies. E-print: [http://arxiv.org/abs/quant-ph/0404076 arXiv:quant-ph/0404076]</ref>. 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:
<syntaxhighlight>
>> M = chshd(2);
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fp','classical')

ans =

0.7500

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

ans =

0.8536

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

ans =

1
</syntaxhighlight>
The auxiliary function <tt>chshd()</tt> 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$.<ref>M. Howard. Maximum nonlocality and minimum uncertainty using magic states. E-print: [http://arxiv.org/abs/1501.05319 arXiv:arXiv:1501.05319] [quant-ph], 2015.</ref> The algorithm used to calculate the classical bound is parallelized and slightly smarter than naïve brute force<ref>M. Araújo, F. Hirsch, and M. T. Quintino. Bell nonlocality with a single shot. E-print: [https://arxiv.org/abs/2005.13418 arXiv:2005.13418]</ref>. It can handle up to $d=8$ quickly:
<syntaxhighlight>
>> 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 =

0.4688
</syntaxhighlight>
===The I3322 inequality===
The I3322 inequality<ref>M. Froissart. Constructive generalization of Bell's inequalities. Nuov. Cim. B, 64:241, 1981</ref><ref>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: [http://arxiv.org/abs/quant-ph/0306129 arXiv:quant-ph/0306129]</ref> 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:
: <math>-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.</math>
Similarly, it is known that a value of (strictly) larger than $1+1/4$ is possible in quantum mechanics<ref name="palvertes">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: [http://arxiv.org/abs/1006.3032 arXiv:1006.3032] [quant-ph]</ref>, 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:
<syntaxhighlight>
>> format long
>> 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 =

1

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

ans =

1.374999892449922

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

ans =

1.251470917522884

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

ans =

1.250939790350636

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

ans =

1.250875663436317

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

ans =

1.250875380616149

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

ans =

2.000000000005738
</syntaxhighlight>

We note that the values provided for the quantum upper bound above for <tt>K = '1+ab'</tt>, <tt>K = 2</tt>, and <tt>K = 3</tt> agree with the values found in <ref name="npa2">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: [http://arxiv.org/abs/0803.4290 arXiv:0803.4290] [quant-ph]</ref> (subtracted 1 to account for the different form of the inequality). Furthermore, the value when <tt>K = 4</tt> agrees with the value found in <ref name="palvertes"></ref>. The exact value of the best upper bound in the quantum setting is an open problem, but is known to be approximately $1.250875$.
{{SourceCode|name=BellInequalityMax}}

==Notes==
In practice, <tt>K</tt> probably can't be any larger than 4 when <tt>MTYPE = 'quantum'</tt>.

==References==
<references />

BellInequalityMax

2022-09-17T12:52:16Z

Araujoms: /* The I3322 inequality */ switch I3322 inequality to symmetric form

{{Function
|name=BellInequalityMax
|desc=Computes the maximum value of a Bell inequality
|rel=[[NonlocalGameValue]] [[NPAHierarchy]] [[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=January 22, 2015
|cvx=no}}
<tt>'''BellInequalityMax'''</tt> is a [[List of functions|function]] that computes the maximum possible value of a given [http://en.wikipedia.org/wiki/Bell%27s_theorem 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 [[NPAHierarchy|NPA hierarchy]]).

==Syntax==
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE,K)</tt>

==Argument descriptions==
* <tt>COEFFICIENTS</tt>: A matrix or tensor that specifies the coefficients of the Bell inequality in either full probability, full correlator, or Collins-Gisin notation.
* <tt>DESC</tt>: 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.
* <tt>NOTATION</tt>: A string indicating in which notation are the coefficients of the Bell inequality given. Must be one of <tt>'fp'</tt>, <tt>'fc'</tt>, or <tt>'cg'</tt>, for full probability, full correlator, or Collins-Gisin, respectively.
* <tt>MTYPE</tt> (optional, default <tt>'classical'</tt>): A string indicating which type of theory should be used when computing the maximum value of the Bell inequality. Must be one of <tt>'classical'</tt>, <tt>'quantum'</tt>, or <tt>'nosignal'</tt>. If <tt>MTYPE = 'quantum'</tt> then only an upper bound on the Bell inequality is computed, not necessarily is best upper bound (see the argument <tt>K</tt> below).
* <tt>K</tt> (optional, default <tt>1</tt>): If <tt>MTYPE = 'quantum'</tt> then this is a non-negative integer indicating what level of the NPA hierarchy should be used when bounding the Bell inequality. Higher values of <tt>K</tt> give better bounds, but require more memory and time. Alternatively, <tt>K</tt> can be a string of a form like <tt>'1+ab+aab'</tt>, 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 <tt>MTYPE</tt> is anything other than <tt>'quantum'</tt> then <tt>K</tt> has no effect.

==Examples==
===The CHSH inequality===
One formulation of the [http://en.wikipedia.org/wiki/CHSH_inequality CHSH inequality]<ref>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.</ref> 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:
: <math>\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.</math>
Similarly, the best bound on this quantity is $2\sqrt{2}$ in a quantum mechanical setting (this is [http://en.wikipedia.org/wiki/Tsirelson%27s_bound Tsirelson's bound])<ref>B.S. Tsirelson. Quantum generalizations of Bell's inequality. Lett. Math. Phys., 4:93, 1980. [http://www.tau.ac.il/~tsirel/download/qbell80.pdf E-print]</ref>, and it is $4$ in no-signalling theories. All three of these bounds can be found as follows:
<syntaxhighlight>
>> M = [0 0 0;0 1 1;0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fc','classical')

ans =

2

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

ans =

2.8284

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

ans =

4
</syntaxhighlight>

===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:
: <math> p(11|11) + p(11|12) + p(11|21) - p(11|22) - p_A(1|1) - p_B(1|1) \leq 0.</math>
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:
<syntaxhighlight>
>> M = [0 -1 0; -1 1 1; 0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'cg','classical')

ans =

0

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

ans =

0.2071

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

ans =

0.5000
</syntaxhighlight>

===The CHSH game===
The CHSH inequality can be reformulated as a nonlocal game, as is favoured in computer science<ref>Richard Cleve, Peter Hoyer, Ben Toner, John Watrous. Consequences and Limits of Nonlocal Strategies. E-print: [http://arxiv.org/abs/quant-ph/0404076 arXiv:quant-ph/0404076]</ref>. 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:
<syntaxhighlight>
>> M = chshd(2);
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fp','classical')

ans =

0.7500

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

ans =

0.8536

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

ans =

1
</syntaxhighlight>
The auxiliary function <tt>chshd()</tt> 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$.<ref>M. Howard. Maximum nonlocality and minimum uncertainty using magic states. E-print: [http://arxiv.org/abs/1501.05319 arXiv:arXiv:1501.05319] [quant-ph], 2015.</ref> The algorithm used to calculate the classical bound is parallelized and slightly smarter than naïve brute force<ref>M. Araújo, F. Hirsch, and M. T. Quintino. Bell nonlocality with a single shot. E-print: [https://arxiv.org/abs/2005.13418 arXiv:2005.13418]</ref>. It can handle up to $d=8$ quickly:
<syntaxhighlight>
>> 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 =

0.4688
</syntaxhighlight>
===The I3322 inequality===
The I3322 inequality<ref>M. Froissart. Constructive generalization of Bell's inequalities. Nuov. Cim. B, 64:241, 1981</ref><ref>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: [http://arxiv.org/abs/quant-ph/0306129 arXiv:quant-ph/0306129]</ref> 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:
: <math>-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.</math>
Similarly, it is known that a value of (strictly) larger than $1+1/4$ is possible in quantum mechanics<ref name="palvertes">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: [http://arxiv.org/abs/1006.3032 arXiv:1006.3032] [quant-ph]</ref>, 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:
<syntaxhighlight>
>> format long
>> 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 =

1

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

ans =

1.366025379559893

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

ans =

1.251470960767171

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

ans =

1.250939737834008

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

ans =

1.250875720765148

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

ans =

1.250875328899517

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

ans =

2
</syntaxhighlight>

We note that the values provided for the quantum upper bound above for <tt>K = '1+ab'</tt>, <tt>K = 2</tt>, and <tt>K = 3</tt> agree with the values found in <ref name="npa2">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: [http://arxiv.org/abs/0803.4290 arXiv:0803.4290] [quant-ph]</ref> (subtracted 1 to account for the different form of the inequality). Furthermore, the value when <tt>K = 4</tt> agrees with the value found in <ref name="palvertes"></ref>. The exact value of the best upper bound in the quantum setting is an open problem, but is known to be approximately $1.250875$.
{{SourceCode|name=BellInequalityMax}}

==Notes==
In practice, <tt>K</tt> probably can't be any larger than 4 when <tt>MTYPE = 'quantum'</tt>.

==References==
<references />

BellInequalityMax

2022-09-16T21:37:13Z

Araujoms: rewrite to agree with the new input form for the function

{{Function
|name=BellInequalityMax
|desc=Computes the maximum value of a Bell inequality
|rel=[[NonlocalGameValue]] [[NPAHierarchy]] [[XORGameValue]]
|req=[http://cvxr.com/cvx/ CVX]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=January 22, 2015
|cvx=no}}
<tt>'''BellInequalityMax'''</tt> is a [[List of functions|function]] that computes the maximum possible value of a given [http://en.wikipedia.org/wiki/Bell%27s_theorem 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 [[NPAHierarchy|NPA hierarchy]]).

==Syntax==
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE)</tt>
* <tt>BMAX = BellInequalityMax(COEFFICIENTS,DESC,NOTATION,MTYPE,K)</tt>

==Argument descriptions==
* <tt>COEFFICIENTS</tt>: A matrix or tensor that specifies the coefficients of the Bell inequality in either full probability, full correlator, or Collins-Gisin notation.
* <tt>DESC</tt>: 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.
* <tt>NOTATION</tt>: A string indicating in which notation are the coefficients of the Bell inequality given. Must be one of <tt>'fp'</tt>, <tt>'fc'</tt>, or <tt>'cg'</tt>, for full probability, full correlator, or Collins-Gisin, respectively.
* <tt>MTYPE</tt> (optional, default <tt>'classical'</tt>): A string indicating which type of theory should be used when computing the maximum value of the Bell inequality. Must be one of <tt>'classical'</tt>, <tt>'quantum'</tt>, or <tt>'nosignal'</tt>. If <tt>MTYPE = 'quantum'</tt> then only an upper bound on the Bell inequality is computed, not necessarily is best upper bound (see the argument <tt>K</tt> below).
* <tt>K</tt> (optional, default <tt>1</tt>): If <tt>MTYPE = 'quantum'</tt> then this is a non-negative integer indicating what level of the NPA hierarchy should be used when bounding the Bell inequality. Higher values of <tt>K</tt> give better bounds, but require more memory and time. Alternatively, <tt>K</tt> can be a string of a form like <tt>'1+ab+aab'</tt>, 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 <tt>MTYPE</tt> is anything other than <tt>'quantum'</tt> then <tt>K</tt> has no effect.

==Examples==
===The CHSH inequality===
One formulation of the [http://en.wikipedia.org/wiki/CHSH_inequality CHSH inequality]<ref>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.</ref> 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:
: <math>\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.</math>
Similarly, the best bound on this quantity is $2\sqrt{2}$ in a quantum mechanical setting (this is [http://en.wikipedia.org/wiki/Tsirelson%27s_bound Tsirelson's bound])<ref>B.S. Tsirelson. Quantum generalizations of Bell's inequality. Lett. Math. Phys., 4:93, 1980. [http://www.tau.ac.il/~tsirel/download/qbell80.pdf E-print]</ref>, and it is $4$ in no-signalling theories. All three of these bounds can be found as follows:
<syntaxhighlight>
>> M = [0 0 0;0 1 1;0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fc','classical')

ans =

2

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

ans =

2.8284

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

ans =

4
</syntaxhighlight>

===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:
: <math> p(11|11) + p(11|12) + p(11|21) - p(11|22) - p_A(1|1) - p_B(1|1) \leq 0.</math>
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:
<syntaxhighlight>
>> M = [0 -1 0; -1 1 1; 0 1 -1];
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'cg','classical')

ans =

0

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

ans =

0.2071

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

ans =

0.5000
</syntaxhighlight>

===The CHSH game===
The CHSH inequality can be reformulated as a nonlocal game, as is favoured in computer science<ref>Richard Cleve, Peter Hoyer, Ben Toner, John Watrous. Consequences and Limits of Nonlocal Strategies. E-print: [http://arxiv.org/abs/quant-ph/0404076 arXiv:quant-ph/0404076]</ref>. 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:
<syntaxhighlight>
>> M = chshd(2);
>> desc = [2 2 2 2];
>> BellInequalityMax(M,desc,'fp','classical')

ans =

0.7500

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

ans =

0.8536

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

ans =

1
</syntaxhighlight>
The auxiliary function <tt>chshd()</tt> 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$.<ref>M. Howard. Maximum nonlocality and minimum uncertainty using magic states. E-print: [http://arxiv.org/abs/1501.05319 arXiv:arXiv:1501.05319] [quant-ph], 2015.</ref> The algorithm used to calculate the classical bound is parallelized and slightly smarter than naïve brute force<ref>M. Araújo, F. Hirsch, and M. T. Quintino. Bell nonlocality with a single shot. E-print: [https://arxiv.org/abs/2005.13418 arXiv:2005.13418]</ref>. It can handle up to $d=8$ quickly:
<syntaxhighlight>
>> 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 =

0.4688
</syntaxhighlight>
===The I3322 inequality===
The I3322 inequality<ref>M. Froissart. Constructive generalization of Bell's inequalities. Nuov. Cim. B, 64:241, 1981</ref><ref>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: [http://arxiv.org/abs/quant-ph/0306129 arXiv:quant-ph/0306129]</ref> is a Bell inequality where each of Alice and Bob has three possible inputs and 2 possible outputs. Written in Collins-Gisin notation, it is given by:
: <math>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|2) - p_B(1|1) - 2p_B(1|2) \leq 0.</math>
Similarly, it is known that a value of (strictly) larger than $1/4$ is possible in quantum mechanics<ref name="palvertes">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: [http://arxiv.org/abs/1006.3032 arXiv:1006.3032] [quant-ph]</ref>, and the best possible bound is $1$ 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:
<syntaxhighlight>
>> format long
>> M = [0 -1 -2 0;0 1 1 -1;-1 1 1 1;0 -1 1 0];
>> desc = [2 2 3 3];
>> BellInequalityMax(M,desc,'cg','classical')

ans =

3.330669073875470e-16

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

ans =

0.366025400377779

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

ans =

0.251470925489524

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

ans =

0.250939729037211

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

ans =

0.250875635269154

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

ans =

0.250875356409269

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

ans =

1
</syntaxhighlight>

We note that the values provided for the quantum upper bound above for <tt>K = '1+ab'</tt>, <tt>K = 2</tt>, and <tt>K = 3</tt> agree with the values found in <ref name="npa2">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: [http://arxiv.org/abs/0803.4290 arXiv:0803.4290] [quant-ph]</ref>. Furthermore, the value when <tt>K = 4</tt> agrees with the value found in <ref name="palvertes"></ref>. The exact value of the best upper bound in the quantum setting is an open problem, but is known to be approximately $0.250875$.
{{SourceCode|name=BellInequalityMax}}

==Notes==
In practice, <tt>K</tt> probably can't be any larger than 4 when <tt>MTYPE = 'quantum'</tt>.

==References==
<references />

List of functions

2022-09-16T20:15:06Z

Araujoms: /* Nonlocality and Bell inequalities */

This is a '''list of functions''' provided by QETLAB, arranged by category. If you would prefer an alphabetical list of all functions please see [[:Category:Functions|this page]]. Brief descriptions of these functions are provided here, as well as links to their documentation pages, where full details and numerous examples can be found.

==Basic operations==
* <tt>[[IsPSD]]</tt>: Determines whether or not a matrix is positive semidefinite
* <tt>[[Tensor]]</tt>: Kronecker tensor product of two or more matrices
* <tt>[[TensorSum]]</tt>: Computes a vector or operator from its tensor decomposition

==Coherence and incoherence==
* <tt>[[L1NormCoherence]]</tt>: Computes the ℓ1-norm of coherence of a quantum state
* <tt>[[RelEntCoherence]]</tt>: Computes the relative entropy of coherence of a quantum state
* <tt>[[RobustnessCoherence]]</tt>: Computes the robustness of coherence of a quantum state
* <tt>[[TraceDistanceCoherence]]</tt>: Computes the trace distance of coherence of a quantum state

==Distinguishing objects==
* <tt>[[ChannelDistinguishability]]</tt>: Computes the maximum probability of distinguishing two quantum channels
* <tt>[[Distinguishability]]</tt>: Computes the maximum probability of distinguishing quantum states
* <tt>[[LocalDistinguishability]]</tt>: Computes the maximum probability of distinguishing quantum states by symmetric-extendible and/or PPT measurements
* <tt>[[UPBSepDistinguishable]]</tt>: Determines whether or not an unextendible product basis is distinguishable by separable measurements

==Entanglement and separability==
===Pure states===
* <tt>[[IsProductVector]]</tt>: Determines if a pure state is a product vector
* <tt>[[SchmidtDecomposition]]</tt>: Computes the Schmidt decomposition of a bipartite vector
* <tt>[[SchmidtRank]]</tt>: Computes the Schmidt rank of a bipartite vector

===Mixed states===
* <tt>[[FilterNormalForm]]</tt>: Computes the filter normal form of an operator
* <tt>[[IsBlockPositive]]</tt>: Determines whether or not an operator is block positive
* <tt>[[IsEntanglingGate]]</tt>: Determines if a unitary is an entangling gate
* <tt>[[IsPPT]]</tt>: Determines whether or not a matrix has positive partial transpose
* <tt>[[IsProductOperator]]</tt>: Determines if an operator is an elementary tensor
* <tt>[[IsSeparable]]</tt>: Determines whether or not a bipartite operator is separable
* <tt>[[OperatorSchmidtDecomposition]]</tt>: Computes the operator Schmidt decomposition of a bipartite operator
* <tt>[[OperatorSchmidtRank]]</tt>: Computes the operator Schmidt rank of a bipartite operator
* <tt>[[SymmetricExtension]]</tt>: Determines whether or not an operator has a symmetric extension
* <tt>[[SymmetricInnerExtension]]</tt>: Determines whether or not an operator has a symmetric inner extension

===Ball of separability===
* <tt>[[AbsPPTConstraints]]</tt>: Builds the eigenvalue matrices that determine whether or not a state is absolutely PPT
* <tt>[[InSeparableBall]]</tt>: Checks whether or not an operator is in the ball of separability centered at the maximally-mixed state
* <tt>[[IsAbsPPT]]</tt>: Determines whether or not a density matrix is absolutely PPT

===Entanglement measures===
* <tt>[[Concurrence]]</tt>: Computes the concurrence of a 2-qubit state
* <tt>[[EntFormation]]</tt>: Computes the entanglement of formation of a bipartite quantum state
* <tt>[[Negativity]]</tt>: Computes the negativity of a bipartite density matrix
* <tt>[[RandomRobustnessEntanglement]]</tt>: Computes the random robustness of entanglement of a bipartite quantum state

==Information theory==
* <tt>[[Entropy]]</tt>: Computes the von Neumann or Rényi entropy of a density matrix

==Nonlocality and Bell inequalities==
* <tt>[[BCSGameLB]]</tt>: Computes a lower bound on the quantum value of a binary contraint system (BCS) game
* <tt>[[BCSGameValue]]</tt>: Computes the maximum value of a binary constraint system (BCS) game
* <tt>[[BellInequalityMax]]</tt>: Computes the maximum value of a Bell inequality or nonlocal game
* <tt>[[BellInequalityMaxQubits]]</tt>: Approximates the optimal value of a Bell inequality in qubit (i.e., 2-dimensional quantum) settings
* <tt>[[NonlocalGameLB]]</tt>: Computes a lower bound on the quantum value of a non-local game
* <tt>[[NonlocalGameValue]]</tt>: Computes the value of a two-player non-local game
* <tt>[[NPAHierarchy]]</tt>: Determines whether or not a set of probabilities satisfy the conditions of the NPA hierarchy
* <tt>[[XORGameValue]]</tt>: Computes the classical or quantum value of a non-local binary XOR game

==Norms and distance measures==
===Vectors and pure states===
* <tt>[[SkVectorNorm]]</tt>: Computes the s(k)-norm of a vector

===Operators and mixed states===
* <tt>[[Fidelity]]</tt>: Computes the (Uhlmann) fidelity of two density matrices
* <tt>[[InducedMatrixNorm]]</tt>: Computes a lower bound of the induced p→q norm of a matrix
* <tt>[[kpNorm]]</tt>: Computes the (k,p)-norm of a vector or matrix
* <tt>[[kpNormDual]]</tt>: Computes the dual of the (k,p)-norm of a vector or matrix
* <tt>[[KyFanNorm]]</tt>: Computes the Ky Fan k-norm of an operator
* <tt>[[MatsumotoFidelity]]</tt>: Computes the Matsumoto fidelity of two density matrices
* <tt>[[SkOperatorNorm]]</tt>: Bounds the S(k)-norm of an operator
* <tt>[[SchattenNorm]]</tt>: Computes the Schatten p-norm of an operator
* <tt>[[TraceNorm]]</tt>: Computes the trace norm of an operator

===Superoperators and channels===
* <tt>[[CBNorm]]</tt>: Computes the completely bounded norm of a superoperator
* <tt>[[DiamondNorm]]</tt>: Computes the diamond norm of a superoperator
* <tt>[[InducedSchattenNorm]]</tt>: Computes a lower bound of the induced Schatten p→q norm of a superoperator
* <tt>[[MaximumOutputFidelity]]</tt>: Computes the maximum output fidelity of two quantum channels

==Permutations and symmetry of subsystems==
* <tt>[[AntisymmetricProjection]]</tt>: Produces the projection onto the antisymmetric subspace
* <tt>[[PermutationOperator]]</tt>: Produces a unitary operator that permutes subsystems
* <tt>[[PermuteSystems]]</tt>: Permutes subsystems within a state or operator
* <tt>[[Swap]]</tt>: Swaps two subsystems within a state or operator
* <tt>[[SwapOperator]]</tt>: Produces a unitary operator that swaps two subsystems
* <tt>[[SymmetricProjection]]</tt>: Produces the projection onto the symmetric subspace

==Random things==
* <tt>[[RandomDensityMatrix]]</tt>: Generates a random density matrix
* <tt>[[RandomPOVM]]</tt>: Generates a random POVM (positive-operator valued measure)
* <tt>[[RandomProbabilities]]</tt>: Computes a random probability vector, distributed uniformly on the unit simplex
* <tt>[[RandomStateVector]]</tt>: Generates a random pure state vector
* <tt>[[RandomSuperoperator]]</tt>: Generates a random superoperator (completely positive map)
* <tt>[[RandomUnitary]]</tt>: Generates a random unitary or orthogonal matrix

==Special states, vectors, and operators==
===Pure states===
* <tt>[[Bell]]</tt>: Produces a Bell state
* <tt>[[BrauerStates]]</tt>: Produces all Brauer states
* <tt>[[DickeState]]</tt>: Generates a Dicke state
* <tt>[[GHZState]]</tt>: Generates a (generalized) GHZ state
* <tt>[[MaxEntangled]]</tt>: Produces a maximally entangled bipartite pure state
* <tt>[[WState]]</tt>: Generates a (generalized) W-state

===Mixed states===
* <tt>[[BreuerState]]</tt>: Generates a Breuer state, which is a specific family of bound entangled states on even local dimensions
* <tt>[[ChessboardState]]</tt>: Produces a chessboard state
* <tt>[[GisinState]]</tt>: Generates a 2-qubit Gisin state
* <tt>[[HorodeckiState]]</tt>: Generates a bound entangled "Horodecki" state
* <tt>[[IsotropicState]]</tt>: Produces an isotropic state
* <tt>[[WernerState]]</tt>: Produces a Werner state

===Other operators===
* <tt>[[FourierMatrix]]</tt>: Generates the unitary matrix that implements the quantum Fourier transform
* <tt>[[GellMann]]</tt>: Produces a Gell-Mann operator
* <tt>[[GenGellMann]]</tt>: Produces a generalized Gell-Mann operator
* <tt>[[GenPauli]]</tt>: Produces a generalized Pauli operator (sometimes called a Weyl operator)
* <tt>[[Pauli]]</tt>: Produces a Pauli operator

==Superoperators==
* <tt>[[ApplyMap]]</tt>: Applies a superoperator to an operator
* <tt>[[ChoiMatrix]]</tt>: Computes the Choi matrix of a superoperator
* <tt>[[ChoiMap]]</tt>: Produces the Choi map or one of its generalizations
* <tt>[[ComplementaryMap]]</tt>: Computes the complementary map of a superoperator
* <tt>[[DephasingChannel]]</tt>: Produces a dephasing channel
* <tt>[[DepolarizingChannel]]</tt>: Produces a depolarizing channel
* <tt>[[DualMap]]</tt>: Computes the dual of a superoperator in the Hilbert-Schmidt inner product
* <tt>[[IsCP]]</tt>: Determines whether or not a superoperator is completely positive
* <tt>[[IsHermPreserving]]</tt>: Determines whether or not a superoperator is Hermiticity preserving
* <tt>[[KrausOperators]]</tt>: Computes a set of Kraus operators for a superoperator
* <tt>[[PartialMap]]</tt>: Applies a superoperator to a subsystem of an operator
* <tt>[[PartialTrace]]</tt>: Computes the partial trace of a vector or a matrix
* <tt>[[PartialTranspose]]</tt>: Computes the partial transpose of a matrix
* <tt>[[PauliChannel]]</tt>: Generates a Pauli channel (i.e., a quantum channel with Pauli Kraus operators)
* <tt>[[Realignment]]</tt>: Computes the realignment of a bipartite operator
* <tt>[[ReductionMap]]</tt>: Produces the reduction map
* <tt>[[Twirl]]</tt>: Twirls a bipartite or multipartite operator

==Unextendible product bases==
* <tt>[[IsUPB]]</tt>: Determines whether or not a set of product vectors form a UPB
* <tt>[[MinUPBSize]]</tt>: Gives the minimum cardinality of an unextendible product basis in given dimensions
* <tt>[[UPB]]</tt>: Generates an unextendible product basis

==Miscellaneous==
* <tt>[[Commutant]]</tt>: Computes the commutant of a set of matrices
* <tt>[[IsTotallyNonsingular]]</tt>: Determines whether or not a matrix is totally nonsingular
* <tt>[[IsTotallyPositive]]</tt>: Determines whether or not a matrix is totally positive
* <tt>[[Majorizes]]</tt>: Determines whether or not a vector or matrix majorizes another
* <tt>[[OperatorSinkhorn]]</tt>: Performs the operator Sinkhorn iteration, making all single-party reduced states proportional to the identity
* <tt>[[Purity]]</tt>: Computes the purity of a quantum state

==Helper functions==
These are functions that only serve auxiliary roles within other functions of QETLAB. As an end-user of QETLAB, you likely won't have any use for these functions, but they are listed here anyway just in case.
* <tt>[[bcs_to_nonlocal]]</tt>: Converts a constraint description of a binary constraint system (BCS) game to a general non-local game description
* <tt>[[dec_to_bin]]</tt>: Converts a decimal number to a binary number in a similar way to `de2bi' in MATLAB
* <tt>[[iden]]</tt>: Computes a sparse or full identity matrix
* <tt>[[jacobi_poly]]</tt>: Computes the coefficients of Jacobi polynomials
* <tt>[[normalize_cols]]</tt>: Scales the columns of a matrix to have norm 1
* <tt>[[one_factorization]]</tt>: Computes a 1-factorization of a list of objects
* <tt>[[opt_args]]</tt>: Handles optional input arguments for functions
* <tt>[[opt_disp]]</tt>: Display a message to the user (sometimes)
* <tt>[[pad_array]]</tt>: Pads an array with zeroes in a similar way to `padarray' in MATLAB
* <tt>[[perfect_matchings]]</tt>: Gives all perfect matchings of N objects
* <tt>[[perm_inv]]</tt>: Computes the inverse of a permutation
* <tt>[[perm_sign]]</tt>: Computes the sign of a permutation
* <tt>[[pure_to_mixed]]</tt>: Converts a state vector or density matrix representation of a state to a density matrix
* <tt>[[sk_iterate]]</tt>: Computes a lower bound of the S(k)-norm of an operator
* <tt>[[spnull]]</tt>: Returns a sparse orthonormal basis for the null space
* <tt>[[sporth]]</tt>: Returns a sparse orthonormal basis for the range
* <tt>[[superoperator_dims]]</tt>: Computes the input, output, and environment dimensions of a superoperator
* <tt>[[unique_perms]]</tt>: Computes all distinct permutations of a given vector
* <tt>[[update_odometer]]</tt>: Increases the entries of a vector subject to constraints on how large the entries of that vector can be
* <tt>[[vec_partitions]]</tt>: Produces all possible partitions of a vector