NPAHierarchy

NPAHierarchy
Determines whether or not a set of probabilities satisfy the conditions of the NPA hierarchy
Other toolboxes required	CVX
Related functions	BellInequalityMax XORGameValue
Function category	Nonlocality and Bell inequalities
Usable within CVX?	yes (concave)

NPAHierarchy is a function that determines whether or not a given set of probabilities satisfy the constraints specified by the NPA hierarchy, 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

• IS_NPA = NPAHierarchy(P,desc)
• IS_NPA = NPAHierarchy(P,desc,K)

Argument descriptions

• P: A behaviour in Collins-Gisin notation. That is, a matrix with components

\[ \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} \]

• DESC: A vector of 4 elements describing the number of outputs of Alice, number of outputs of Bob, number of inputs of Alice, and number of inputs of Bob, in this order.
• K (optional, default 1): A positive integer that determines the level of the NPA hierarchy to use. Alternatively, K can be a string of a form like '1+ab+aab', which indicates that an intermediate level of the hierarchy should be used, where this example uses all products of 1 measurement, all products of one Alice and one Bob measurement, and all products of two Alice and one Bob measurement. Use plus signs to separate the different categories of products, as above. The first character of this string should always be a number, indicating the base level to use.

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 >= 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 \(2p(00|xy) = p_A(0|x) + p_B(0|y)\) for some x,y.:

>> 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

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.

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:

>> 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

Source code

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