NPAHierarchy - Revision history

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

2022-11-11T12:39:56Z

Argument descriptions: K=0 doesn't exist anymore

Araujoms: update page to reflect new code

2022-11-11T11:13:35Z

update page to reflect new code

Nathaniel at 17:40, 22 January 2015

2015-01-22T17:40:34Z

Nathaniel at 17:39, 22 January 2015

2015-01-22T17:39:28Z

Nathaniel at 18:04, 14 January 2015

2015-01-14T18:04:37Z

Nathaniel: Added reference

2014-12-17T21:37:05Z

Added reference

Nathaniel: Added BellInequalityMax to rel

2014-12-17T18:54:24Z

Added BellInequalityMax to rel

Nathaniel: /* Can be used within CVX */ fixed typo

2014-12-16T18:22:00Z

Can be used within CVX: fixed typo

Nathaniel: Created page with "{{Function |name=NPAHierarchy |desc=Determines whether or not a set of probabilities satisfy the conditions of the NPA hierarchy |rel=XORQuantumValue |req=[http://cvxr.com..."

2014-12-16T18:08:59Z

Created page with "{{Function |name=NPAHierarchy |desc=Determines whether or not a set of probabilities satisfy the conditions of the NPA hierarchy |rel=XORQuantumValue |req=[http://cvxr.com..."

New page

{{Function
|name=NPAHierarchy
|desc=Determines whether or not a set of probabilities satisfy the conditions of the NPA hierarchy
|rel=[[XORQuantumValue]]
|req=[http://cvxr.com/cvx/ cvx]
|cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
|upd=December 9, 2014
|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>, 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)</tt>
* <tt>IS_NPA = NPAHierarchy(P,K)</tt>

==Argument descriptions==
* <tt>P</tt>: A 4D array such that <tt>P(a,b,x,y)</tt> is the probability that Alice and Bob obtain measurement result <tt>(a,b)</tt> when they use measurement setting <tt>(x,y)</tt> (i.e., this is equal to $p(a,b|x,y)$ from above).
* <tt>K</tt> (optional, default 1): A non-negative integer that determines the level of the NPA hierarchy to use. If <tt>K = 0</tt> then the NPA hierarchy isn't use at all, and this function just checks whether or not <tt>P</tt> is a valid probability array that satisfies non-signally constraints (i.e., all entries are non-negative, each matrix face sums to 1, and the marginal probabilities for Alice and Bob are consistent with each other).

==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). Maximizing it has the interpretation of trying to find a set of probabilities that satisfy the constraints of the NPA hierarchy, as well as whatever other constraints you specify. For example, the following code finds a $2$-measurement, $2$-outcome probability array satisfying the constraints of the second level of the hierarchy and also has $p(1,1|1,1) = p(1,2|1,1) + 0.1$ and $p(1,2|1,2) = p(2,2|1,2) - 0.2$ (these last two constraints have no special significance; they are just there for illustrative purposes):
<syntaxhighlight>

>> cvx_begin sdp quiet
variable p(2,2,2,2); % 2 measurements, 2 outcomes each
maximize NPAHierarchy(p,2) % seconds level of the hierarchy
subject to
% these constraints do not have any particular significance
p(1,1,1,1) == p(1,2,1,1) + 0.1;
p(1,2,1,2) == p(2,2,1,2) - 0.2;
cvx_end
cvx_optval

cvx_optval =

1 % a value of 1 indicates that a probability array satisfying the constraints exists

>> p % let's have a look at it

p(:,:,1,1) =

0.2637 0.1637
0.2698 0.3029

p(:,:,2,1) =

0.2667 0.2333
0.2667 0.2333

p(:,:,1,2) =

0.2692 0.1582
0.2145 0.3582

p(:,:,2,2) =

0.2418 0.2582
0.2418 0.2582
</syntaxhighlight>

{{SourceCode|name=NPAHierarchy}}

==References==
<references />

@@ Line 27: / Line 27: @@
 </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.
+* <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==

@@ Line 2: / Line 2: @@
 |name=NPAHierarchy
 |desc=Determines whether or not a set of probabilities satisfy the conditions of the NPA hierarchy
-|rel=[[BellInequalityMax]]<br />[[XORQuantumValue]]
+|rel=[[BellInequalityMax]]<br />[[XORGameValue]]
 |req=[http://cvxr.com/cvx/ CVX]
 |cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]

@@ Line 5: / Line 5: @@
 |req=[http://cvxr.com/cvx/ CVX]
 |cat=[[List of functions#Nonlocality_and_Bell_inequalities|Nonlocality and Bell inequalities]]
-|upd=January 22, 2015
+|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)</tt>
+* <tt>IS_NPA = NPAHierarchy(P,desc)</tt>
-* <tt>IS_NPA = NPAHierarchy(P,K)</tt>
+* <tt>IS_NPA = NPAHierarchy(P,desc,K)</tt>
 ==Argument descriptions==
-* <tt>P</tt>: A 4D array such that <tt>P(a,b,x,y)</tt> is the probability that Alice and Bob obtain measurement result <tt>(a,b)</tt> when they use measurement setting <tt>(x,y)</tt> (i.e., this is equal to $p(a,b|x,y)$ from above).
+* <tt>P</tt>: A behaviour in Collins-Gisin notation. That is, a matrix with components
-* <tt>K</tt> (optional, default 1): A non-negative integer that determines the level of the NPA hierarchy to use. If <tt>K = 0</tt> then the NPA hierarchy isn't use at all, and this function just checks whether or not <tt>P</tt> is a valid probability array that satisfies non-signalling constraints (i.e., all entries are non-negative, each matrix face sums to 1, and the marginal probabilities for Alice and Bob are consistent with each other). 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.
+:<math>
 ==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). Maximizing it has the interpretation of trying to find a set of probabilities that satisfy the constraints of the NPA hierarchy, as well as whatever other constraints you specify. For example, the following code finds a $2$-measurement, $2$-outcome probability array satisfying the constraints of the second level of the hierarchy and also has $p(1,1|1,1) = p(1,2|1,1) + 0.1$ and $p(1,2|1,2) = p(2,2|1,2) - 0.2$ (these last two constraints have no special significance; they are just there for illustrative purposes):
+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.
 <syntaxhighlight>
+>> B = [0, -1, 0; -1, 1, 1; 0, 1, -1]; %CHSH functional in Collins-Gisin form
->> cvx_begin sdp quiet
+   desc = [2 2 2 2];
-    variable p(2,2,2,2); % 2 measurements, 2 outcomes each
+   cvx_begin
-    maximize NPAHierarchy(p,2) % second level of the hierarchy
+    variable p(3,3);
     subject to
-       % these constraints do not have any particular significance
+	p(1,1) == 1; %the top left element of the behaviour must always be equal to 1
-       p(1,1,1,1) == p(1,2,1,1) + 0.1;
+	NPAHierarchy(p,desc,2) == 1; %here we impose level 2 of the NPA hierarchy
-       p(1,2,1,2) == p(2,2,1,2) - 0.2;
+*p(2,2) == p(1,2) + p(2,1); %this is the constraint that Alice and Bob have equal outcomes
     cvx_end
-cvx_optval =
+Optimal value (cvx_optval): +0.125009
-% a value of 1 indicates that a probability array satisfying the constraints exists
+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>.
->> p % let's have a look at it
+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:
-p(:,:,1,1) =
+<syntaxhighlight>
+>> prbox = [2, 1, 1;1, 1, 1;1,1,0]/2; %PR box
-.2637    0.1637
+   p_random = [4, 2, 2;2, 1, 1;2, 1, 1]/4; %uniformly random behaviour
-.2698    0.3029
+   desc = [2 2 2 2];
+Optimal value (cvx_optval): +0.292893
 </syntaxhighlight>
 {{SourceCode|name=NPAHierarchy}}
 ==References==
 <references />