Jump to navigation Jump to search
Determines whether or not a set of probabilities satisfy the conditions of the NPA hierarchy

Other toolboxes required CVX
Related functions BellInequalityMax
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[1][2], 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).


  • 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-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, 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.


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


  1. M. Navascués, S. Pironio, and A. Acín. Bounding the set of quantum correlations. Phys. Rev. Lett., 98:010401, 2007. E-print: arXiv:quant-ph/0607119
  2. M. Navascués, S. Pironio, and A. Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New J. Phys., 10:073013, 2008. E-print: arXiv:0803.4290 [quant-ph]