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)
• IS_NPA = NPAHierarchy(P,K)

Argument descriptions

• P: A 4D array such that P(a,b,x,y) is the probability that Alice and Bob obtain measurement result (a,b) when they use measurement setting (x,y) (i.e., this is equal to $p(a,b|x,y)$ from above).
• K (optional, default 1): A non-negative integer that determines the level of the NPA hierarchy to use. If K = 0 then the NPA hierarchy isn't use at all, and this function just checks whether or not P 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 >= 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):

>> cvx_begin sdp quiet
   variable p(2,2,2,2); % 2 measurements, 2 outcomes each
   maximize NPAHierarchy(p,2) % second 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

Source code

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