# Naturally restricted subsets of nonsignaling correlations: typicality and
convergence

Pei-Sheng Lin  Department of Physics and Center for Quantum Frontiers of
Research & Technology (QFort), National Cheng Kung University, Tainan 701,
Taiwan  Tamás Vértesi  MTA Atomki Lendület Quantum Correlations Research
Group, Institute for Nuclear Research, P.O. Box 51, H-4001 Debrecen, Hungary
Yeong-Cherng Liang<EMAIL_ADDRESS>Department of Physics and Center
for Quantum Frontiers of Research & Technology (QFort), National Cheng Kung
University, Tainan 701, Taiwan  Physics Division, National Center for
Theoretical Sciences, Taipei 10617, Taiwan

(August 28, 2024)

###### Abstract

It is well-known that in a Bell experiment, the observed correlation between
measurement outcomes—as predicted by quantum theory—can be stronger than that
allowed by local causality, yet not fully constrained by the principle of
relativistic causality. In practice, the characterization of the set
$\mathcal{Q}$ of quantum correlations is carried out, often, through a
converging hierarchy of outer approximations. On the other hand, some subsets
of $\mathcal{Q}$ arising from additional constraints [e.g., originating from
quantum states having positive-partial-transposition (PPT) or being finite-
dimensional maximally entangled (MES)] turn out to be also amenable to similar
numerical characterizations. How, then, at a quantitative level, are all these
naturally restricted subsets of nonsignaling correlations different? Here, we
consider several bipartite Bell scenarios and numerically estimate their
volume relative to that of the set of nonsignaling correlations. Within the
number of cases investigated, we have observed that (1) for a given number of
inputs $n_{s}$ (outputs $n_{o}$), the fraction of both the Bell-local set and
the quantum set increases (decreases) rapidly with increasing $n_{o}$
($n_{s}$) (2) although the so-called macroscopically local set
$\mathcal{Q}_{1}$ may approximate $\mathcal{Q}$ well in the two-input
scenarios, it can be a very poor approximation of the quantum set when
$n_{s}>n_{o}$ (3) the almost-quantum set $\widetilde{\mathcal{Q}}_{1}$ is an
exceptionally-good approximation to the quantum set (4) the difference between
$\mathcal{Q}$ and the set of correlations originating from MES is most
significant when $n_{o}=2$, whereas (5) the difference between the Bell-local
set and the PPT set generally becomes more significant with increasing
$n_{o}$. This last comparison, in particular, allows us to identify Bell
scenarios where there is little hope of realizing the Bell violation by PPT
states and those that deserve further exploration.

##  I Introduction

The fact that Bell inequalities Bell (1964)—constraints derived from the
assumption of Bell-locality Brunner  _et al._ (2014)—can be violated by
quantum theory indicates that the set of quantum correlations $\mathcal{Q}$ is
intrinsically different from the set of correlations $\mathcal{L}$ allowed by
a locally-causal theory Bell (2004). However, it is also known—from the
pioneering work of Popescu and Rohrlich Popescu and Rohrlich (1994)—that
quantum theory is not the most Bell-nonlocal (hereafter abbreviated as
nonlocal) among all physical theories that respect the principle of
relativistic causality. In bipartite Bell scenarios, this principle gives rise
to the so-called nonsignaling (NS) conditions Barrett  _et al._ (2005), and
hence a superset of $\mathcal{Q}$ known as the nonsignaling polytope
$\mathcal{NS}$.

Since then, a lot of effort (see, e.g., Brassard  _et al._ (2006); Linden  _et
al._ (2007); Pawlowski  _et al._ (2009); Navascués and Wunderlich (2009);
Fritz  _et al._ (2013); Navascués  _et al._ (2015); Gonda  _et al._ (2018))
has been devoted to understand if additional physical, or information-
theoretic principles can be supplemented to recover from $\mathcal{NS}$ the
set of quantum correlations. In fact, the so-called almost-quantum set of
correlations Navascués  _et al._ (2015)—known to be a strict superset to
$\mathcal{Q}$—apparently satisfies all information-theoretic principles
proposed to date. Nonetheless, the extent to which this set, hereafter denoted
by $\widetilde{\mathcal{Q}}_{1}$, differs from $\mathcal{Q}$ itself is not
well understood. Indeed, Vallins  _et al._ (2017) seems to be the only work to
date reporting a systematic investigation of the difference in Bell values
achievable by these sets.

So far, the only known means that we have in characterizing $\mathcal{Q}$ is
via a hierarchy of outer approximations, such as that proposed by Navascués,
Pironio, and Acín (NPA) Navascués  _et al._ (2007). The NPA hierarchy is known
to converge Navascués  _et al._ (2008) (see also Doherty  _et al._ (2008))—in
the asymptotic limit—to the set of correlations $\mathcal{Q}_{[\cdot,\cdot]}$
achievable assuming quantum theory and with the measurements between spatially
separated parties modeled by commuting operators, rather than tensor products.
Note that the two different formulations of spatially separated measurements
generally lead to different Slofstra (2019, 2020); Coladangelo and Stark
(2020) sets of correlations, i.e.,
$\mathcal{Q}\neq\mathcal{Q}_{[\cdot,\cdot]}$, thereby manifesting the
complication of the geometry of these sets Goh  _et al._ (2018). Moreover,
very little is known Harrow  _et al._ (2019) regarding the rate of convergence
of this hierarchy towards $\mathcal{Q}_{[\cdot,\cdot]}$.

On the other hand, a few other subsets of $\mathcal{Q}$ are naturally also of
interest. For example, a somewhat different formulation Moroder  _et al._
(2013) of the NPA hierarchy has made it possible to characterize—also via a
converging hierarchy of outer approximations—the set of correlations
$\mathcal{P}$ arising from quantum states having positive partial
transposition Peres (1996) (PPT). The interest in this stems from a conjecture
of Peres Peres (1999)—disproved in Vertesi and Brunner (2014)—concerning the
impossibility of bound entangled Horodecki  _et al._ (1998) states violating
Bell inequalities. Known counterexamples to Peres’ conjecture are, however,
too fragile to be demonstrated in any experiment, thus making it desirable to
understand how $\mathcal{P}$, being a restricted subset of $\mathcal{Q}$,
differs from the set of Bell-local correlations $\mathcal{L}$.

Besides, the fact that certain nonlocal features only seem to exist for
partially entangled states is also intriguing. One of the first hints along
this line is the Hardy paradox Hardy (1993). Later, the existence of such
correlations was explicitly shown, independently, in Liang  _et al._ (2011);
Vidick and Wehner (2011); Junge and Palazuelos (2011) (see also Christensen
_et al._ (2015)), under the name of more nonlocality with less entanglement.
Interestingly, the set of correlations $\mathcal{M}$ arising from finite-
dimensional maximally entangled states, or more precisely its convex hull—as
with $\mathcal{Q}$ and $\mathcal{P}$—can also be characterized Lang  _et al._
(2014) via a hierarchy of outer approximations, each corresponds to the
feasible set of a semidefinite program Boyd and Vandenberghe (2004). To
achieve a better understanding of the precise relationship between
entanglement and nonlocality, any quantitative estimate of the difference
between $\mathcal{M}$ and $\mathcal{Q}$ is surely welcome.

Apart from fundamental interests, nonlocal correlations also play an
indispensable role in the context of device-independent quantum information
Scarani (2012); Brunner  _et al._ (2014). For instance, from the observation
of a Bell violation itself, one can certify the generation of unpredictable
random bits Colbeck (2009); Pironio  _et al._ (2010), guarantee the sharing of
truly unconditional secured keys Acín  _et al._ (2007), certify various
desired features of the underlying systems (see, e.g., Bancal  _et al._
(2011); Moroder  _et al._ (2013); Liang  _et al._ (2015); Chen  _et al._
(2016); Arnon-Friedman and Bancal (2019); Chen  _et al._ (2018a)),
measurements (see, e.g., Rabelo  _et al._ (2011); Chen  _et al._ (2016);
Bancal  _et al._ (2018); Chen  _et al._ (2021)) or even other more general
types of operations Sekatski  _et al._ (2018); Wagner  _et al._ (2020). In its
strongest form, one could achieve so-called self-testing Mayers and Yao
(2004), where the underlying system and measurements are identified uniquely,
modulo unimportant local degrees of freedom. For a comprehensive review on
this last topic, see Šupić and Bowles (2020).

To this end, it is worth noting that the quantitative differences between the
“size” of the Bell-local set $\mathcal{L}$, the quantum set $\mathcal{Q}$, and
the nonsignaling set $\mathcal{NS}$ has been investigated in Cabello (2005);
Wolfe and Yelin (2012); Duarte  _et al._ (2018). Specifically, in the simplest
Bell scenario involving two parties, each performing two binary-outcome
measurements, the volume of $\mathcal{L}$ and that of $\mathcal{Q}$, relative
to $\mathcal{NS}$, in the subspace of “full” correlation functions Werner and
Wolf (2001) was first determined in Cabello (2005). Then, for the same Bell
scenario, the analysis has been generalized Wolfe and Yelin (2012) to include
also the subspace spanned by marginal correlations. Beyond this, numerical
estimation of the relative volume of $\mathcal{L}$ to $\mathcal{NS}$ was
carried out in Duarte  _et al._ (2018) for a few Bell scenarios with either
only two measurement settings or outcomes; some analytic results were also
presented therein when restricted to the subspace of full correlations.

Here, we generalize the analysis of Cabello (2005); Wolfe and Yelin (2012);
Duarte  _et al._ (2018) in two directions. Firstly, we consider a more
extensive list of Bell scenarios, including a few with multiple measurement
settings and outcomes, which allows us to make observations that were not
possible in prior works. Secondly, we consider not only $\mathcal{L}$,
$\mathcal{Q}$ (approximated by relevant outer approximations), and
$\mathcal{NS}$, but also the set of correlations $\mathcal{P}$ achievable by
PPT quantum states, the (convex hull of the) set of correlations achievable by
locally measuring finite-dimensional maximally entangled states with
projective measurements $\mathcal{M}^{\text{\tiny P}}$, the set
$\mathcal{Q}_{1}$ associated with the principle of macroscopic locality
Navascués and Wunderlich (2009), the almost-quantum set
$\widetilde{\mathcal{Q}}_{1}$, and more generally the first few levels of the
outer approximations of $\mathcal{Q}$ given by the NPA hierarchy Navascués
_et al._ (2007) as well as the hierarchy of Moroder et al. Moroder  _et al._
(2013). This last consideration, in particular, allows us to learn the
fraction of points in $\mathcal{NS}$ that can be further excluded from
$\mathcal{Q}$ as we consider increasingly tighter outer approximations to
$\mathcal{Q}$. Clearly, such information is highly relevant for device-
independent analyses that rely on the above hierarchies to outer-approximate
$\mathcal{Q}$.

The rest of this paper is structured as follows. In Section II, we introduce
the notations used throughout the paper and the different Bell scenarios
considered. Then, we present in Section III our main results on the relative
volume for the different sets of correlations mentioned above. In Section IV,
we give further discussions and comment on some possible directions for future
research.

##  II Preliminaries

###  II.1 Notations and Naturally Restricted Subsets of $\mathcal{NS}$

Consider a bipartite Bell experiment where each spatially separated party has
a choice over $n_{s}$ measurement settings where each measurement results in
$n_{o}$ possible outcomes. We shall denote such a Bell scenario by
($n_{s},n_{o}$). Correlation between the observed outcomes for given
measurement settings of the two parties (conventionally called Alice and Bob)
may be described by $\vec{P}=\\{P(a,b|x,y)\\}_{a,b,x,y}$ where we label the
measurement settings and outcomes for Alice (Bob), respectively, as $x$ ($y$)
and $a$ ($b$). Throughout, we consider only Bell scenarios where $x,y,a$, and
$b$ take a finite number of values.

Our starting point is the set of nonsignaling correlations Popescu and
Rohrlich (1994); Barrett  _et al._ (2005), $\mathcal{NS}$, which are all those
$\vec{P}$ that satisfy the so-called nonsignaling conditions Barrett  _et al._
(2005):

$\begin{split}\sum_{a}P(a,b|x,y)&\overset{\mathcal{NS}}{=}\sum_{a}P(a,b|x^{\prime},y)\;\;\forall\;b,y,x,x^{\prime},\\\
\sum_{b}P(a,b|x,y)&\overset{\mathcal{NS}}{=}\sum_{b}P(a,b|x,y^{\prime})\;\;\forall\;a,x,y,y^{\prime}.\end{split}$
(1)

Physically, these conditions were initially Popescu and Rohrlich (1994)
proposed to exclude the possibility of communication by making different local
choices of $x,y$. Since $\mathcal{NS}$ is the intersection of a finite number
of hyperplanes defined by Eq. 1 and the direct sum of $n_{s}^{2}$ probability
simplices, it is a convex polytope.

An important subset of $\mathcal{NS}$ is the Bell-local Brunner  _et al._
(2014) set $\mathcal{L}$. For any $\vec{P}\in\mathcal{L}$, it can be shown
Fine (1982); Pitowsky (1989) (see also Ref. Wiseman (2014)) that there exists
normalized weights $q(\lambda)\geq\;0$ for all $\lambda$ and
$\sum_{\lambda}q(\lambda)=1$ such that

$\begin{split}&P(a,b|x,y)\overset{\mathcal{L}}{=}\sum_{\lambda}q(\lambda)\delta_{a,f_{A}(x,\lambda)}\delta_{b,f_{B}(y,\lambda)},\\\
\end{split}$ (2)

for some choice of local response functions $f_{A}(x,\lambda)$ and
$f_{B}(y,\lambda)$. Clearly, $\mathcal{L}$ is convex. Since there are only
finite possibilities of $x,y,a$, and $b$, the set $\mathcal{L}$ forms Pitowsky
(1989) a convex polytope, with its extreme points correspond to local
deterministic strategies given by the Kronecker deltas:
$\delta_{a,f_{A}(x,\lambda)}$ and $\delta_{b,f_{B}(y,\lambda)}$.

Suppose now that the two parties share a quantum state $\rho$, then quantum
theory dictates that the observed correlation follows Born’s rule:

$P(a,b|x,y)\overset{\mathcal{Q}}{=}{\rm tr}\left[\rho\,M^{(A)}_{a|x}\otimes
M^{(B)}_{b|y}\right],$ (3)

where $\\{M^{(A)}_{a|x}\\}_{a}$ $\left(\\{M^{(B)}_{b|y}\\}_{b}\right)$ are
positive-operator-valued measures (POVMs) associated with Alice’s (Bob’s)
$x$-th ($y$-th) measurement. We denote the set of such correlations by
$\mathcal{Q}$. Importantly, in the definition of $\mathcal{Q}$, there is no
constraint imposed on the (local) Hilbert space dimension. This, in turn,
guarantees the convexity Pitowsky (1989) of $\mathcal{Q}$ and the sufficiency
of projective measurements (via Naimark’s extension Peres (1990)) on pure
state $\rho=\rho^{2}$ in the membership test of $\mathcal{Q}$. Even then, the
characterization of $\mathcal{Q}$ is by no means computationally easy.

To this end, NPA Navascués  _et al._ (2007) first pointed out that
$\mathcal{Q}$, or more precisely, $\mathcal{Q}_{[\cdot,\cdot]}$ can be
characterized Navascués  _et al._ (2008) asymptotically (see also Doherty  _et
al._ (2008)) by solving a hierarchy of semidefinite programs (SDPs). The
feasible sets corresponding to these SDPs then define a series of outer
approximations
$\mathcal{Q}_{1}\supseteq\mathcal{Q}_{2}\supseteq\cdots\supseteq\mathcal{Q}_{\infty}=\mathcal{Q}_{[\cdot,\cdot]}\supset\mathcal{Q}$,
where $\mathcal{Q}_{k}$ is referred conventionally as NPA level $k$ with $k$
signifying the highest degree of the operator used in defining some matrix of
moments (see Navascués  _et al._ (2007, 2008) for details). $\mathcal{Q}_{1}$,
incidentally, is exactly the set of correlations that respects the principle
of macroscopic locality Navascués and Wunderlich (2009). Intermediate levels
can also be considered and a prominent example is the so-called NPA level
$1+AB$, which happens to be the lowest level of another converging hierarchy
of outer approximations
$\widetilde{\mathcal{Q}}_{1}\supseteq\widetilde{\mathcal{Q}}_{2}\supseteq\cdots\supseteq\widetilde{\mathcal{Q}}_{\infty}=\mathcal{Q}_{[\cdot,\cdot]}\supset\mathcal{Q}$
due to Moroder et al. Moroder  _et al._ (2013). The specific outer
approximation $\mathcal{Q}_{1+AB}=\widetilde{\mathcal{Q}}_{1}$ is known in the
literature as the almost quantum Navascués  _et al._ (2015) set of
correlations, as it seems to satisfy all principles that have been proposed to
date to distinguish $\mathcal{Q}$ from $\mathcal{NS}$. In the bipartite
scenario, the sets associated with the two hierarchies are known Moroder  _et
al._ (2013) to satisfy the inclusion relations
$\mathcal{Q}_{1}\supset\widetilde{\mathcal{Q}}_{1}$ and
$\widetilde{\mathcal{Q}}_{k}\supset\mathcal{Q}_{2k}$ for all integers $k\geq
1$.

As Bell showed in his seminal work Bell (1964), there exist quantum
correlations arising from entangled quantum states that do not admit a convex
decomposition in the form of LABEL:eq:LHV. At the same time, by considering
trivial POVMs consisting only of the identity operator and the null operator,
it is straightforward to see that all $\vec{P}\in\mathcal{L}$ can always be
cast in the form of Eq. 3. Similarly, all $\vec{P}\in\mathcal{Q}$ are easily
seen to satisfy Eq. 1, while Popescu and Rohrlich Popescu and Rohrlich (1994)
showed that there exists $\vec{P}\in\mathcal{NS}\setminus\mathcal{Q}$.
Together, one arrives at the strict inclusion relations
$\mathcal{L}\subsetneq\mathcal{Q}\subsetneq\widetilde{\mathcal{Q}}_{1}\subsetneq\mathcal{Q}_{1}\subsetneq\mathcal{NS}$.

Even if we restrict our attention to $\mathcal{Q}$ itself, its relationship
with the set of quantum states has not been fully understood. For example,
although entanglement is necessary Werner (1989) for Bell-nonlocality, some
entangled states (see, e.g., Werner (1989); Barrett (2002)) are known to
produce only $\vec{P}\in\mathcal{L}$. In fact, even if Alice and Bob are
allowed to share an arbitrary finite-dimensional maximally entangled state
$|\Psi_{d}\rangle=\frac{1}{\sqrt{d}}\sum_{i=1}^{d}|i\rangle|i\rangle$, it is
impossible for them to reproduce all $\vec{P}\in\mathcal{Q}$ Liang  _et al._
(2011); Vidick and Wehner (2011); Junge and Palazuelos (2011); Christensen
_et al._ (2015). To facilitate subsequent discussions, we denote by
$\mathcal{M}^{\text{\tiny P}}$ the convex hull of the set of correlations
attainable by performing projective measurements on $|\Psi_{d}\rangle$, with
$d$ finite. On the contrary, even the weakest form of entanglement given by
PPT entangled states may generate nonlocal correlations Vértesi and Brunner
(2012); Vertesi and Brunner (2014). Hereafter, we denote by $\mathcal{P}$ the
subset of $\mathcal{Q}$ which arises from $\rho$ being a PPT state, i.e.,
$\rho^{\text{\tiny T}_{A}}\succeq 0$ where ${}^{\text{\tiny T}_{A}}$ stands
for the partial transposition operation on Alice’s Hilbert space.

A schematic diagram explaining the relationships among the various naturally
restricted subsets $\mathcal{T}$ of $\mathcal{NS}$ considered in this work is
provided in Fig. 1.

Figure 1:  Schematic illustration of the relationships among the various
subsets $\mathcal{T}\subset\mathcal{NS}$ considered here. Starting from
$\mathcal{NS}$ and moving inwards, we have in solid lines, respectively, the
boundary of the quantum set of correlations $\mathcal{Q}$ [Eq. 3, blue], the
convex hull $\mathcal{M}^{\text{\tiny P}}$ (red) of the set of correlations
attainable by finite-dimensional maximally entangled states in conjunction
with projective measurements, the set of correlations attainable by PPT
entangled state $\mathcal{P}$ (green), and the Bell-local polytope
$\mathcal{L}$ (skyblue). Dashed (pink) and dotted (brown) lines lying between
the boundary of $\mathcal{Q}$ and that of $\mathcal{NS}$ mark the boundary of
the lowest-level outer approximation of $\mathcal{Q}$, respectively, due to
NPA Navascués  _et al._ (2007) ($\mathcal{Q}_{1}$) and Moroder et al. Moroder
_et al._ (2013) ($\widetilde{\mathcal{Q}}_{1}$).

###  II.2 Membership Tests

Our goal is to estimate the relative volume of various subsets
$\mathcal{T}\in\\{\mathcal{L},\mathcal{P},\mathcal{M}^{\text{\tiny
P}},\mathcal{Q},\widetilde{\mathcal{Q}}_{1},\mathcal{Q}_{1}\\}$ of
$\mathcal{NS}$. To this end, we perform the membership test
$\vec{P}\overset{?}{\in}\mathcal{T}$ for each sampled $\vec{P}\in\mathcal{NS}$
by solving the following optimization problem:

$\displaystyle\sup\;\;$ $\displaystyle v$ (4a) $\displaystyle{\rm
s.t.}\;\;v\vec{P}+(1-$ $\displaystyle v)\vec{P}_{w}\in\mathcal{T},$ (4b)

where $\vec{P}_{w}$ is the uniform probability distribution, i.e.,
$P_{w}(a,b|x,y)=1/n_{o}^{2}\;\forall\;x,y$. As $\vec{P}_{w}$ lies strictly in
$\mathcal{L}$, it must also lie in all sets $\mathcal{T}$ that are of our
interest. Hence, the above optimization problem, which we solve using the
optimization software MOSEK implemented in MATLAB, is always feasible by
setting $v=0$. Also, if $\vec{P}\in\mathcal{T}$ then all mixtures with
$v\in[0,1]$ are inside $\mathcal{T}$, i.e., the optimum $v$ (denoted by
$v^{*}$) would be greater than or equal to 1. Hence, $v^{*}<1$ indicates that
$\vec{P}\not\in\mathcal{T}$. Notice that $v^{*}$, often called the white-noise
visibility, can be understood as the “maximal” weight that can be assigned to
$\vec{P}$ when it is admixed with white noise while ensuring that the mixture
lies within $\mathcal{T}$. A smaller value of $v^{*}$, which corresponds to a
larger value of $1-v^{*}$, then indicates that the correlation is more robust
(in terms of preserving its nonlocal nature) against the mixing with
$\vec{P}_{w}$.

Among the different sets of interest, $\mathcal{L}$ is a convex polytope, and
thus its membership test, cf. Eq. 4 is an instance of a linear program Boyd
and Vandenberghe (2004). For relatively simple Bell scenarios, this
optimization problem can be efficiently solved on a computer. In contrast, for
the other sets of interest, including
$\mathcal{T}\in\\{\mathcal{P},\mathcal{M}^{\text{\tiny P}},\mathcal{Q}\\}$, we
rely on a hierarchy of outer approximations, each of which is amenable to
semidefinite programming characterizations. In the case of $\mathcal{Q}$, we
use both the NPA hierarchy Navascués  _et al._ (2007, 2008) and its variant
due to Moroder et al. Moroder  _et al._ (2013) for membership tests. For
definiteness, we denote by $\mathcal{Q}_{k}$ and
$\widetilde{\mathcal{Q}}_{\ell}$, respectively, the level $k$ and the level
$\ell$ outer approximation of $\mathcal{Q}$ based on the NPA hierarchy and the
hierarchy of Moroder et al. (a summary of both hierarchies can be found in
Table V, Appendix B of Ref. Chen  _et al._ (2018b)). By further requiring the
moment matrix $\widetilde{\mathcal{Q}}_{\ell}$ to be PPT, one immediately
obtains a characterization of $\mathcal{P}_{\ell}$, i.e., the level $\ell$
outer approximation of $\mathcal{P}$. Notice that all these SDPs can be
implemented using the $\mathsf{Ncpol2sdpa}$ toolbox developed by Wittek Wittek
(2015). For the set of correlations $\mathcal{M}^{\text{\tiny P}}$ associated
with local projective measurements on finite-dimensional maximally entangled
states, we make use of a hierarchy adapted from that presented in Ref. Lang
_et al._ (2014), the details of which are given in Appendix A. We refer to the
level $h$ outer approximation of $\mathcal{M}^{\text{\tiny P}}$ obtained
thereof as $\mathcal{M}^{\text{\tiny P}}_{h}$.

###  II.3 Metrics and Relative Volume

The notion of volume for any given region in a space $\mathscr{P}$ is metric-
dependent. In our case, $\mathscr{P}$ is the set of conditional probability
distributions $\vec{P}=\\{P(a,b|x,y)\\}_{a,b,x,y}$ where
$a,b\in\\{1,\ldots,n_{o}\\}$ and $x,y\in\\{1,2,\ldots,n_{s}\\}$. The
normalization requirement $\sum_{a,b}P(a,b|x,y)=1$ for all $x$ and $y$ implies
that $\mathscr{P}$ is $(n_{s}^{2})(n_{o}^{2}-1)$-dimensional. Moreover, we are
only interested in $\vec{P}$ that satisfy the nonsignaling constraints of Eq.
1. The nonsignaling polytope $\mathcal{NS}$ and hence the various subsets of
interest all lie in a $d$-dimensional subspace $\mathscr{P}_{\mathcal{NS}}$ of
$\mathscr{P}$ where Collins and Gisin (2004)
$d=(n_{o}-1)^{2}n_{s}^{2}+2n_{s}(n_{o}-1)$.

A convenient, minimal parametrization of any $\vec{P}\in\mathcal{NS}$ is given
by Collins and Gisin (2004):

$\vec{P}=\\{P(a|x),P(b|y),P(a,b|x,y)\\}_{a,b,x,y}$ (5)

where $P(a|x)=\sum_{b}P(a,b|x,y)$ and $P(b|y)=\sum_{a}P(a,b|x,y)$ are,
respectively, the marginal conditional probability distributions of Alice and
Bob. Note that in this parameterization, the labels $a,b$ in Eq. 5 take only
values from $\\{1,\dots,n_{o}-1\\}$. Indeed, the conditional probability
distributions for the omitted outcome corresponding to $a$ and/or $b=n_{o}$
can be determined easily from the components $P_{i}$ of $\vec{P}$ in Eq. 5 via
the normalization of probabilities and the nonsignaling conditions of Eq. 1.

Like in previous works Cabello (2005); Wolfe and Yelin (2012); Duarte  _et
al._ (2018), we adopt the Euclidean metric in our computation of the relative
volumes (though other options may also be considered, see our remark in
Section IV). In this metric ${\rm d}s_{\text{\tiny E}}^{2}$, all components of
$\vec{P}$ in Eq. 5 are treated on equal footing. Explicitly, ${\rm
d}s_{\text{\tiny E}}^{2}$ and the corresponding volume element ${\rm
d}V_{\text{\tiny E}}$ are given, respectively, by:

${\rm d}s_{\text{\tiny E}}^{2}=\sum_{i}{{\rm d}}P_{i}^{2}\quad\text{ and
}\quad{\rm d}V_{\text{\tiny E}}=\prod_{i}{{\rm d}}P_{i}.$ (6)

When there is no risk of confusion, the subscript ${}_{\text{E}}$ is omitted
to simplify the presentation.

We then define the relative volume (RV) for each set
$\mathcal{T}\subset\mathcal{NS}$ as:

$\text{RV}(\mathcal{T})\equiv\frac{V(\mathcal{T})}{V(\mathcal{NS})}$ (7)

where $V(\mathcal{S})$ is the volume of a set $\mathcal{S}$ in accordance to
the (Euclidean) metric. To numerically estimate these RVs, it suffices to
sample points $\vec{P}\in\mathcal{NS}$ _uniformly_ according to the metric,
and determine the fraction of such points that lie in $\mathcal{T}$ via the
method explained in Section II.2. For this purpose, we make use of the MATLAB
function $\mathsf{cprnd}$ developed by Benham Benham (2014), and in particular
its _Gibbs sampler_ algorithm to perform uniform sampling of $\vec{P}$ in
$\mathcal{NS}$. In Appendix B, we give further details on how we generate
uniform samples in $\mathcal{NS}$ using the $\mathsf{cprnd}$ function. Note
that each membership test with respect to $\mathcal{T}$ is exactly a Bernoulli
trial with a success probability given by $\text{RV}(\mathcal{T})$.

For each Bell scenario considered, we estimate the RV of $\mathcal{L}$,
$\mathcal{Q}_{l}$, $\widetilde{\mathcal{Q}}_{k}$, $\mathcal{P}_{k}$ and
$\mathcal{M}^{\text{\tiny P}}_{h}$. In Table 1, we list all the bipartite Bell
scenarios considered in this work, the number of samples used in estimating
the RV of each target set, the highest level of each type of hierarchies
considered, as well as the corresponding RVs. In Appendix C, we further
provide the relevant parameters characterizing the size of the optimization
problem. In the next section, we present our main results across 23 Bell
scenarios.

For all but two of these Bell scenarios, we use $N_{\text{\scriptsize
tot}}=10^{6}$ sampled correlations in our estimation of the relative volumes.
The only exceptions are the (5,4) and the (6,3) Bell scenario where we employ,
instead, $3.05\times 10^{5}$ and $7.85\times 10^{5}$ samples, respectively.
Even in these latter cases, the estimates have converged well with the
employed samples (see Fig. 8 in Appendix D for details). Importantly, as we
can see in these plots, the number of samples required to reach a good
precision does not seem to depend on the complexity of the Bell scenario, but
rather more on the success probability itself.

##  III Numerical Estimates of Relative Volumes

$(n_{s},n_{o})$ | $N_{\text{\scriptsize tot}}\leavevmode\nobreak\ (\times 10^{5})$ | $\mathcal{Q}_{1}$ | $\widetilde{\mathcal{Q}}_{1}$ | $\mathcal{Q}_{*}$ | $\widetilde{\mathcal{Q}}_{*}$ | $\mathcal{P}_{*}$ | $\mathcal{M}^{\text{\tiny P}}_{*}\cap\mathcal{Q}_{**}$ | $\mathcal{L}$
---|---|---|---|---|---|---|---|---
(2,2) | $10$ | 99.80% | 99.25% | 99.17% ($\mathcal{Q}_{4}$) | 99.17% ($\widetilde{\mathcal{Q}}_{4}$) | 94.15% ($\mathcal{P}_{4}$) | 98.68% ($\mathcal{M}^{\text{\tiny P}}_{4}\cap\widetilde{\mathcal{Q}}_{4}$) | 94.15%
(2,3) | $10$ | 99.98% | 99.80% | 99.74% ($\mathcal{Q}_{3}$) | 99.74% ($\widetilde{\mathcal{Q}}_{2}$) | 93.84% ($\mathcal{P}_{2}$) | 99.50% ($\mathcal{M}^{\text{\tiny P}}_{2}\cap\widetilde{\mathcal{Q}}_{2}$) | 93.84%
(2,4) | $10$ | 100.00∗% | 99.99% | 99.99% ($\mathcal{Q}_{2}$) | 99.99% ($\widetilde{\mathcal{Q}}_{1}$) | 97.41% ($\mathcal{P}_{2}$) | 99.95% ($\mathcal{M}^{\text{\tiny P}}_{2}\cap\mathcal{Q}_{2}$) | 97.41%
(2,5) | $10$ | 100.00∗∗% | 100.00∗% | 100.00∗% ($\mathcal{Q}_{2}$) | 100.00∗% ($\widetilde{\mathcal{Q}}_{1}$) | 99.41% ($\mathcal{P}_{1.5}$) | 100.00∗% ($\mathcal{M}^{\text{\tiny P}}_{2}\cap\mathcal{Q}_{2}$) | 99.41%
(2,6) | $10$ | 100.00∗∗% | 100.00∗∗% | 100.00∗∗ ($\mathcal{Q}_{2}$) | 100.00∗∗% ($\widetilde{\mathcal{Q}}_{1}$) | 99.90% ($\mathcal{P}_{1.5}$) | 100.00∗∗% ($\mathcal{M}^{\text{\tiny P}}_{1}\cap\mathcal{Q}_{2}$) | 99.90%
(2,7) | $10$ | 100.00∗∗% | 100.00∗∗% | 100.00∗∗ ($\mathcal{Q}_{2}$) | 100.00∗∗% ($\widetilde{\mathcal{Q}}_{1}$) | 99.98% ($\mathcal{P}_{1}$) | 100.00∗∗% ($\mathcal{M}^{\text{\tiny P}}_{1}\cap\mathcal{Q}_{2}$) | 99.98%
(2,8) | $10$ | - | - | - | - | - | - | 100.00∗%
(2,9) | $10$ | - | - | - | - | - | - | 100.00∗%
(3,2) | $10$ | 97.23% | 92.11% | 91.19% ($\mathcal{Q}_{3}$) | 91.19% ($\widetilde{\mathcal{Q}}_{2}$) | 62.18% ($\mathcal{P}_{2}$) | 88.13% ($\mathcal{M}^{\text{\tiny P}}_{3}\cap\widetilde{\mathcal{Q}}_{2}$) | 62.18%
(3,3) | $10$ | 99.78% | 97.90% | 97.52% ($\mathcal{Q}_{2}$) | 97.90% ($\widetilde{\mathcal{Q}}_{1}$) | 59.88% ($\mathcal{P}_{2}$) | 95.16% ($\mathcal{M}^{\text{\tiny P}}_{2}\cap\mathcal{Q}_{2}$) | 59.88%
(3,4) | $10$ | 100.00∗% | 99.93% | 99.91% ($\mathcal{Q}_{2}$) | 99.93% ($\widetilde{\mathcal{Q}}_{1}$) | 81.27% ($\mathcal{P}_{1.25}$) | 99.65% ($\mathcal{M}^{\text{\tiny P}}_{1.5}\cap\mathcal{Q}_{2}$) | 79.79%
(3,5) | $10$ | - | - | - | - | - | - | 94.93%
(3,6) | $10$ | - | - | - | - | - | - | 99.16%
(3,7) | $10$ | - | - | - | - | - | - | 99.89%
(4,2) | $10$ | 84.62% | 69.45% | 67.80% ($\mathcal{Q}_{2}$) | 69.45% ($\widetilde{\mathcal{Q}}_{1}$) | 21.14% ($\mathcal{P}_{2}$) | 61.75% ($\mathcal{M}^{\text{\tiny P}}_{2}\cap\mathcal{Q}_{2}$) | 21.14%
(4,3) | $10$ | 98.39% | 88.69% | 98.39% ($\mathcal{Q}_{1}$) | 88.69% ($\widetilde{\mathcal{Q}}_{1}$) | 20.22% ($\mathcal{P}_{1.2}$) | 88.69% ($\mathcal{M}^{\text{\tiny P}}_{1}\cap\widetilde{\mathcal{Q}}_{1}$) | 16.58%
(4,4) | $10$ | 99.99% | 99.59% | 99.99% ($\mathcal{Q}_{1}$) | 99.59% ($\widetilde{\mathcal{Q}}_{1}$) | 50.16% ($\mathcal{P}_{1}$) | 99.59% ($\mathcal{M}^{\text{\tiny P}}_{1}\cap\widetilde{\mathcal{Q}}_{1}$) | 41.07%
(4,5) | $10$ | - | - | - | - | - | - | 80.34%
(5,2) | $10$ | 53.47% | 34.49% | 32.35% ($\mathcal{Q}_{2}$) | 34.49% ($\widetilde{\mathcal{Q}}_{1}$) | 3.09% ($\mathcal{P}_{1.5}$) | 27.12% ($\mathcal{M}^{\text{\tiny P}}_{2}\cap\mathcal{Q}_{2}$) | 2.96%
(5,3) | $10$ | 89.91% | 59.29% | 89.91% ($\mathcal{Q}_{1}$) | 59.29% ($\widetilde{\mathcal{Q}}_{1}$) | 3.16% ($\mathcal{P}_{1}$) | 59.29% ($\mathcal{M}^{\text{\tiny P}}_{1}\cap\widetilde{\mathcal{Q}}_{1}$) | 1.22%
(5,4) | $3.05$ | 99.94% | 97.03% | 99.94% ($\mathcal{Q}_{1}$) | 97.03% ($\widetilde{\mathcal{Q}}_{1}$) | 18.28% ($\mathcal{P}_{1}$) | 97.03% ($\mathcal{M}^{\text{\tiny P}}_{1}\cap\widetilde{\mathcal{Q}}_{1}$) | 6.31%
(6,2) | $10$ | 18.11% | 8.80% | 7.73% ($\mathcal{Q}_{2}$) | 8.80% ($\widetilde{\mathcal{Q}}_{1}$) | 0.22% ($\mathcal{P}_{1}$) | 5.93% ($\mathcal{M}^{\text{\tiny P}}_{2}\cap\mathcal{Q}_{2}$) | 0.15%
(6,3) | $7.85$ | 56.67% | 17.20% | 56.67% ($\mathcal{Q}_{1}$) | 17.20% ($\widetilde{\mathcal{Q}}_{1}$) | 0.12% ($\mathcal{P}_{1}$) | 17.20% ($\mathcal{M}^{\text{\tiny P}}_{1}\cap\widetilde{\mathcal{Q}}_{1}$) | 0.01%
Table 1:  Summary of the numerically estimated relative volume
$\text{RV}(\mathcal{T})$ for various naturally restricted subsets
$\mathcal{T}$ of the set of nonsignaling correlations $\mathcal{NS}$. The
second column gives the number of $\vec{P}$ uniformly sampled from
$\mathcal{NS}$ using $\mathsf{cprnd}$. From the third column to the rightmost
column, we have the estimated relative volume (RV) for, respectively, the
macroscopically local set $\mathcal{Q}_{1}$, the almost quantum set
$\widetilde{\mathcal{Q}}_{1}$, our tightest approximation to $\mathcal{Q}$
based on outer approximations of NPA Navascués  _et al._ (2007) (denoted by
$\mathcal{Q}_{*}$), our tightest approximation to $\mathcal{Q}$ based on outer
approximations of Moroder et al. Moroder  _et al._ (2013) (denoted
by$\widetilde{\mathcal{Q}}_{*}$), our tightest approximation to $\mathcal{P}$
(denoted by $\mathcal{P}_{*}$), our tightest approximation to
$\mathcal{M}^{\text{\tiny P}}$ intersecting with $\mathcal{Q}_{**}$ (denoted
by $\mathcal{M}^{\text{\tiny P}}_{*}\cap\mathcal{Q}_{**}$), and the Bell-local
set $\mathcal{L}$. In the fifth to the eighth column, we include also in
bracket the highest level of the SDP hierarchy used in the computation (for an
explanation of the various levels and the complexity involved in the
computation, see Appendix C). In particular, our best approximation to
$\text{RV}(\mathcal{Q})$, given either in the fifth or the sixth column, is
highlighted in yellow. For example, in our characterization of $\mathcal{Q}$
in the $(2,3)$ Bell scenario, we are not able to go beyond $\mathcal{Q}_{3}$
nor $\widetilde{\mathcal{Q}}_{2}$, neither of which is, a priori, a subset of
the other. However, since $\widetilde{\mathcal{Q}}_{2}$ gives a smaller RV
(see Table 2), we use it as our $\mathcal{Q}_{**}$ in this Bell scenario. We
use 100.00∗% and 100.00∗∗% to denote entries where the estimated
$\text{RV}(\mathcal{T})$ satisfies, respectively,
$\text{RV}(\mathcal{T})>99.995\%$ and
$\text{RV}(\mathcal{T})>100\%\left(1-\frac{1}{N_{\text{\scriptsize
tot}}}\right)$. Similarly, all other estimates reported here have a
fundamental imprecision of $\frac{100}{N_{\text{\scriptsize tot}}}\%$. Here
and below, entries marked with “-” means the corresponding computation has
been left out.

In Table 1, we provide a summary of $\text{RV}(\mathcal{T})$ for
$\mathcal{T}\in\\{\mathcal{Q}_{1},\widetilde{\mathcal{Q}}_{1},\mathcal{L}\\}$
and certain approximations to $\mathcal{Q}$, $\mathcal{P}$, and
$\mathcal{M}^{\text{\tiny P}}$ for the various Bell scenarios considered. Note
that for 6 of the 23 Bell scenarios, we compute only $\text{RV}(\mathcal{L})$
as it becomes too time consuming to compute the other $\text{RV}(\mathcal{T})$
with a statistically significant number of trials. Throughout, we use
$\mathcal{Q}_{**}$, $\mathcal{M}^{\text{\tiny P}}_{*}$, and $\mathcal{P}_{*}$,
respectively, to denote the tightest approximation that we are able to compute
for $\mathcal{Q}$, $\mathcal{M}^{\text{\tiny P}}$, and $\mathcal{P}$. In the
following subsections, we describe in details how the RV of these sets changes
in different Bell scenarios. To best illustrate these trends, we make use of
line plots showing how each of these relative volumes varies with respect to
the relevant parameters.

###  III.1 $\mathcal{L}$ vs $\mathcal{NS}$

Quantitative estimate of $\text{RV}(\mathcal{L})$ in the 8-dimensional space
of $\mathscr{P}_{\mathcal{NS}}$ for the (2,2) Bell scenario was first
determined in Ref. Wolfe and Yelin (2012). This analysis was then generalized
in Ref. Duarte  _et al._ (2018) to include the (3,2), (4,2), (5,2), (2,3), and
the (2,4) Bell scenarios. Among their findings is the observation that for
$n_{o}=2$, $\text{RV}(\mathcal{L})$ rapidly decreases as $n_{s}$ increases
from 2 to 5. Our findings, as can be seen in Fig. 2, show that this trend
holds also for Bell scenarios with $n_{o}=3,4$ (and possibly $n_{o}=5$).

######  Observation 1.

For Bell scenarios with fixed outputs, $\text{RV}(\mathcal{L})$ decreases
monotonically with increasing $n_{s}$ (see Fig. 2).

Hence, 1 generalizes the observation from Duarte  _et al._ (2018) for
$n_{o}=2$. For example, in the $n_{o}=3$ case, we observe that
$\text{RV}(\mathcal{L})$ decreases from 93.84% (for $n_{s}=2$) to 0.01% (for
$n_{s}=6$), likewise for the $n_{o}=4$ case, which decreases from 97.41% (for
$n_{s}=2$) to 6.31% (for $n_{s}=5$), etc.

Before discussing this observed trend, note that our estimate for
$\text{RV}(\mathcal{L})$ in the (2,2) and the (3,2) Bell scenario is
consistent with that obtained analytically from the software $\mathsf{lrs}$
Avis (1999), which gives $\text{RV}(\mathcal{L})=\frac{16}{17}\approx 94.12\%$
and $\text{RV}(\mathcal{L})=\frac{18\leavevmode\nobreak\
176}{29\leavevmode\nobreak\ 205}\approx 62.24\%$ respectively. Similarly, our
estimate of $\text{RV}(\mathcal{L})$ in the $(2,3)$ Bell scenario (see Table
1) is consistent with that determined from the software $\mathsf{vinci}$
Büeler  _et al._ (2000), giving $\text{RV}(\mathcal{L})\approx 93.82\%$.

$2$$3$$4$$5$$6$$7$$8$$9$$0$%$10$%$20$%$30$%$40$%$50$%$60$%$70$%$80$%$90$%$100$%$n_{o}$$\text{RV}(\mathcal{L})$$n_{s}=2$$n_{s}=3$$n_{s}=4$$n_{s}=5$$n_{s}=6$
Figure 2:  Plots of estimated $\text{RV}(\mathcal{L})$ vs
$n_{o}\in\\{2,3,\ldots,9\\}$ for $n_{s}\in\\{2,3,\ldots,6\\}$.
$\text{RV}(\mathcal{L})$ for scenarios $(2,5),(2,6),\dots,(2,9)$, $(3,6)$ and
$(3,7)$ is very close to 100% but not exactly 100%.

How do we understand the observed decreasing trend? Let us remind that for any
Bell scenario ($n_{s}^{\prime},n_{o}$) with $n_{s}^{\prime}>n_{s}$, any sub-
correlation $\vec{P}$ extracted from $\vec{P}^{\prime}$ by considering only
$n_{s}$ out of the $n_{s}^{\prime}$ measurement settings (for both Alice and
Bob) is a legitimate correlation for the _simpler_ Bell scenario
($n_{s},n_{o}$). Moreover, for $\vec{P}^{\prime}$ to be in $\mathcal{L}$, all
these $\binom{n_{s}^{\prime}}{n_{s}}^{2}$ sub-correlations $\vec{P}$
extractable from $\vec{P}^{\prime}$ must also be Bell-local.

Let $\text{RV}(\mathcal{L})=p$ be the success probability of a Bernoulli trial
in the ($n_{s},n_{o}$) Bell scenario. If all such $\vec{P}$ that may be
extracted from $\vec{P}^{\prime}$ could be thought of as being sampled
independently and uniformly from the $\mathcal{NS}$ polytope in the
($n_{s},n_{o}$) Bell scenario, the success probability of a Bernoulli trial in
the ($n_{s}^{\prime},n_{o}$) Bell scenario would scale as

$p^{\binom{n_{s}^{\prime}}{n_{s}}^{2}}=p^{\frac{(n_{s}^{\prime}!)^{2}}{(n_{s}!)^{2}[(n_{s}^{\prime}-n_{s})!]^{2}}}.$
(8)

Applying this naïve reasoning to the (2,2) and the (3,2) Bell scenario would
suggest a decrease of $\text{RV}(\mathcal{L})$ from $\frac{16}{17}\approx
94.12\%$ to $57.95\%$, which is not too far off from our exact finding that
$\text{RV}(\mathcal{L})=\frac{18\leavevmode\nobreak\
176}{29\leavevmode\nobreak\ 205}\approx 62.24\%$ in the (3,2) case. Clearly,
part of this discrepancy stems from the fact the sub-correlations $\vec{P}$
extractable from $\vec{P}^{\prime}$ are not entirely independent from one
another – all these different $\vec{P}$ share a common input with the other
$\vec{P}$. Moreover, even if all these sub-correlations $\vec{P}$ are Bell-
local, $\vec{P}^{\prime}$ may still be Bell-nonlocal.

On the other hand, Fig. 2 shows an opposite trend for Bell scenarios with
fixed $n_{s}$.

######  Observation 2.

For Bell scenarios with fixed inputs, $\text{RV}(\mathcal{L})$ first decreases
when $n_{o}$ varies from $2$ to $3$, but increases monotonically thereafter
with increasing $n_{o}$ (see Fig. 2).

This observation generalizes the observation from Duarte  _et al._ (2018) for
$n_{s}=2$. Since the way $\text{RV}(\mathcal{L})$ changes with increasing
$n_{o}$ is opposite to that with increasing $n_{s}$, it is natural to wonder
how $\text{RV}(\mathcal{L})$ changes when $n_{s}=n_{o}=k$ increases. To this
end, we have the following observation.

######  Observation 3.

As $n_{s}=n_{o}=k$ increases, $\text{RV}(\mathcal{L})$ decreases steadily with
increasing $k$. That is, the effect of increasing $n_{s}$ on
$\text{RV}(\mathcal{L})$ dominates over that of increasing $n_{o}$.

###  III.2 $\mathcal{Q}$ vs $\mathcal{NS}$ and $\mathcal{L}$

####  III.2.1 Convergence of outer approximations towards
$\mathcal{Q}_{[\cdot,\cdot]}$

Before discussing how $\text{RV}(\mathcal{Q})$ changes across different Bell
scenarios, let us first make a digression to investigate how well the various
$\mathcal{Q}_{k}$ and $\widetilde{\mathcal{Q}}_{\ell}$ outer-approximate
$\mathcal{Q}$ in each Bell scenario. Again, their relative volume is a useful
figure of merit in this context. From here, we can learn how
$\text{RV}(\mathcal{T})$ converges to $\mathcal{Q}$ when we consider
approximations $\mathcal{T}$ of $\mathcal{Q}$ with increasing complexity. For
definiteness, we make use of the number of real moment variables involved in
the SDP characterization of $\mathcal{T}$ to serve as our measure of
complexity.

Recall from our discussion in Section III.1 that $\mathcal{L}$ makes up a
substantial fraction of $\mathcal{NS}$ for many of the Bell scenarios
considered. Thus, to better manifest the convergence graphically, we focus on
the nonlocal region of $\mathcal{NS}$, i.e.,
$\mathcal{NS}\setminus\mathcal{L}$. In other words, for any given outer
approximation $\mathcal{T}=\mathcal{Q}_{k}$ or
$\widetilde{\mathcal{Q}}_{\ell}$, we are interested in the volume of
$\mathcal{T}\setminus\mathcal{L}$ relative to that of
$\mathcal{NS}\setminus\mathcal{L}$, i.e.,

$f(\mathcal{T})=\frac{\text{RV}(\mathcal{T}\setminus\mathcal{L})}{\text{RV}(\mathcal{NS}\setminus\mathcal{L})}=\frac{\text{RV}(\mathcal{T}\setminus\mathcal{L})}{1-\text{RV}(\mathcal{L})}.$
(9)

Evidently, for each given Bell scenario, there is some $\mathcal{Q}_{k}$ or
$\widetilde{\mathcal{Q}}_{\ell}$ considered that gives the smallest
$f(\mathcal{T})$. Denoting them, respectively, by $\mathcal{Q}_{*}$ and
$\widetilde{\mathcal{Q}}_{*}$, then our tightest approximation to
$\mathcal{Q}$ is simply $\mathcal{Q}_{**}:=\operatorname*{\text{\small
argmin}}_{\mathcal{T}\in\\{\mathcal{Q}_{*},\widetilde{\mathcal{Q}}_{*}\\}}\text{RV}(\mathcal{T})$.
The actual $\mathcal{Q}_{**}$ in each case can be read off from the
corresponding highlighted entry in Table 1. We show in Fig. 3 how
$f(\mathcal{T})$ changes with $\mathcal{T}$ for all those Bell scenarios where
we have computed at least two different approximations $\mathcal{T}$’s to
$\mathcal{Q}$. For these scenarios, we thus have
$\mathcal{Q}_{**}\subsetneq\mathcal{Q}_{1}$.

$(n_{s},n_{o})$ | $\mathcal{NS}\setminus\mathcal{Q}_{1}$ | $\mathcal{Q}_{1}\setminus\widetilde{\mathcal{Q}}_{1}$ | $\widetilde{\mathcal{Q}}_{1}\setminus\mathcal{Q}_{2}$ | $\mathcal{Q}_{2}\setminus\mathcal{Q}_{3}$ | $\widetilde{\mathcal{Q}}_{1}\setminus\widetilde{\mathcal{Q}}_{2}$ | $\mathcal{Q}_{**}\setminus\mathcal{L}$
---|---|---|---|---|---|---
(2,2) | 2 001 | 5 458 | 581 | 305 | 886 | 50 116
(2,3) | 187 | 1781 | 271 | 359 | 631 | 59 000
(2,4) | 1 | 85 | 12 | - | - | 25 808
(2,5) | 0 | 1 | 0 | - | - | 5 887
(2,6) | 0 | 0 | 0 | - | - | 994
(2,7) | 0 | 0 | 0 | - | - | 151
(3,2) | 27 711 | 51 209 | 5 364 | 3 818 | 9 185 | 290 053
(3,3) | 2 190 | 18 766 | 3 889 | - | - | 376 374
(3,4) | 10 | 672 | 259 | - | - | 201 161
(4,2) | 153 800 | 151 686 | 16 481 | - | - | 466 675
(4,3) | 16 131 | 96 990 | - | - | - | 721 076
(4,4) | 96 | 3 982 | - | - | - | 585 222
(5,2) | 465 263 | 189 827 | 21 394 | - | - | 293 933
(5,3) | 100 943 | 306 120 | - | - | - | 580 700
(5,4) | 186 | 8 883 | - | - | - | 276 676
(6,2) | 818 872 | 93 083 | 10 792 | - | - | 75 773
(6,3) | 340 105 | 309 851 | - | - | - | 134 960
Table 2:  Summary of the number of correlations $\vec{P}$ excluded from one
approximation of $\mathcal{Q}_{[\cdot,\cdot]}$ to a tighter one. The leftmost
column gives the Bell scenario. Except for the Bell scenario (5,4) and (6,3),
the total number $N_{\text{\scriptsize tot}}$ of correlations sampled from
$\mathcal{NS}$ is $10^{6}$ (see Table 1). Further to the right, we have,
respectively, the number of $\vec{P}\in\mathcal{NS}$ excluded from
$\mathcal{Q}_{1}$, the number of $\vec{P}\in\mathcal{Q}_{1}$ excluded from
$\widetilde{\mathcal{Q}}_{1}$, the number of
$\vec{P}\in\widetilde{\mathcal{Q}}_{1}$ excluded from $\mathcal{Q}_{2}$, the
number of $\vec{P}\in\mathcal{Q}_{2}$ excluded from $\mathcal{Q}_{3}$, the
number of $\vec{P}\in\widetilde{\mathcal{Q}}_{1}$ excluded from
$\widetilde{\mathcal{Q}}_{2}$, and the number of nonlocal $\vec{P}$ that lie
in our tightest approximation $\mathcal{Q}_{**}$ (see Table 1). For the Bell
scenario (2,2), we have also performed the membership test for
$\widetilde{\mathcal{Q}}_{3}$, $\mathcal{Q}_{4}$ and
$\widetilde{\mathcal{Q}}_{4}$. However, no $\vec{P}$ was further excluded from
these higher-level relaxations to $\mathcal{Q}_{[\cdot,\cdot]}$. For a
graphical representation focussing on the nonlocal region, see Fig. 3.

$10^{1}$$10^{2}$$10^{3}$$90$%$100$%Number of optimization variables used in
characterizing $\mathcal{T}$$f(\mathcal{T})$ for
$n_{s}=2$$n_{o}=5$$n_{o}=4$$n_{o}=3$$n_{o}=2$

$10^{2}$$10^{3}$$10^{4}$$80$%$90$%$100$%Number of real moment variables used
in characterizing $\mathcal{T}$$f(\mathcal{T})$ for
$n_{s}=3$$n_{o}=4$$n_{o}=3$$n_{o}=2$

$10^{2}$$10^{3}$$10^{4}$$60$%$70$%$80$%$90$%$100$%Number of real moment
variables used in characterizing $\mathcal{T}$$f(\mathcal{T})$ for
$n_{s}=4$$n_{o}=4$$n_{o}=3$$n_{o}=2$

$10^{2}$$10^{3}$$10^{4}$$0$%$10$%$20$%$30$%$40$%$50$%$60$%$70$%$80$%$90$%$100$%Number
of real moment variables used in characterizing $\mathcal{T}$$f(\mathcal{T})$
for $n_{s}=5$$n_{o}=4$$n_{o}=3$$n_{o}=2$

$10^{2}$$10^{3}$$10^{4}$$0$%$10$%$20$%$30$%$40$%$50$%$60$%Number of real
moment variables used in characterizing $\mathcal{T}$$f(\mathcal{T})$ for
$n_{s}={6}$$n_{o}=3$$n_{o}=2$

Figure 3:  Numerical estimate of
$f(\mathcal{T})=\frac{\text{RV}(\mathcal{T}\setminus\mathcal{L})}{1-\text{RV}(\mathcal{L})}$
for various outer approximations $\mathcal{T}$ of $\mathcal{Q}$, where
$\mathcal{T}$ is any member of $\\{\mathcal{Q}_{k}\\}_{k}$ or
$\\{\widetilde{\mathcal{Q}}_{\ell}\\}_{\ell}$. In each plot, we use filled
(hollow) markers to represent $\mathcal{Q}_{k}$
($\widetilde{\mathcal{Q}}_{\ell}$). The leftmost filled (hollow) marker
corresponds to the first level of the NPA Navascués  _et al._ (2007) (Moroder
et al. Moroder  _et al._ (2013)) hierarchy $\mathcal{Q}_{1}$
($\widetilde{\mathcal{Q}}_{1}$). When an increasingly higher level of either
hierarchy is considered, the respective SDP characterization involves an
increasingly larger number of real (optimization) moment variables (see
Appendix C), thus giving rise to markers that are placed more and more to the
right of the plot. Plots for the (2,6) and (2,7) Bell scenario have been
omitted as $f(\mathcal{T})=100\%$ for all approximations considered for these
Bell scenarios. As guide for the eye, we have also included a fitting curve
(dashed line) in each case. For Bell scenarios with more than three data
points, we use the $\mathsf{pchip}$ (piecewise cubic Hermite interpolating
polynomial) function in MATLAB to generate the respective fitting curve
whereas for the other scenarios, we simply use a straight line to join the two
data points.

As is evident from the plots (see also Table 2 and Table 3), the first level
of the NPA hierarchy $\mathcal{Q}_{1}$ (corresponding to the first filled
symbol on each line) generally does not serve as a very good approximation to
$\mathcal{Q}$. In fact, it largely overestimates $\text{RV}(\mathcal{Q})$ for
several Bell scenarios.

######  Observation 4.

For two-input Bell scenarios, $\mathcal{Q}_{1}$ approximates
$\mathcal{Q}_{**}$ well but for $n_{s}>3\geq n_{o}$,
$\text{RV}(\mathcal{Q}_{1})$ overestimates $\text{RV}(\mathcal{Q})$ by at
least 9.69%. This overestimation even exceeds 30% in both the (5.3) and (6,4)
Bell scenario, see Table 3.

From Fig. 3 as well as Table 2 and Table 3, we also see that the almost
quantum set $\widetilde{\mathcal{Q}}_{1}$ (corresponding to the first hollow
symbol on each line) generally offers a much better approximation to
$\mathcal{Q}$ than $\mathcal{Q}_{1}$ does. For instance, in all the $n_{o}=2$
scenarios considered, $\mathcal{Q}_{1}$ occupies between 9 to 20% more of the
nonlocal region compared to $\widetilde{\mathcal{Q}}_{1}$, whereas in general,
$f(\widetilde{\mathcal{Q}}_{1})-f(\mathcal{Q}_{**})<5\%$. Even if we measure
according to $\text{RV}(\mathcal{T})$, the difference between
$\widetilde{\mathcal{Q}}_{1}$ and $\mathcal{Q}_{**}$ remains small for all the
12 Bell scenarios explored beyond $\widetilde{\mathcal{Q}}_{1}$.

######  Observation 5.

For all the Bell scenarios investigated,
$\text{RV}(\widetilde{\mathcal{Q}}_{1})-\text{RV}(\mathcal{Q}_{**})$ is larger
than 1% only for the (4,2), (5,2), and the (6,2) Bell scenario. The largest
difference is found in the (5,2) Bell scenario, giving $\approx$ 2.14%, see
Table 3.

$(n_{s},n_{o})$ | $\mathcal{Q}_{1}\setminus\mathcal{Q}_{**}$ | $\widetilde{\mathcal{Q}}_{1}\setminus\mathcal{Q}_{**}$ | $\mathcal{Q}_{**}\setminus(\mathcal{M}^{\text{\tiny P}}_{*}\cap\mathcal{Q}_{**})$ | $\mathcal{P}_{*}\setminus\mathcal{L}$
---|---|---|---|---
(2,2) | 0.6344% | 0.0886% | 0.4817% | 0%
(2,3) | 0.2412% | 0.0631% | 0.2429% | 0.0012%
(2,4) | 0.0097% | 0.0012% | 0.0364% | 0.0012%
(2,5) | 0.0001% | 0% | 0.0016% | 0.0017%
(2,6) | 0% | 0% | 0% | 0.0003%
(2,7) | 0% | 0% | 0% | 0%
(3,2) | 6.0394% | 0.9185% | 3.06% | 0%
(3,3) | 2.2655% | 0.3889% | 2.3560% | 0.0002%
(3,4) | 0.0931% | 0.0259% | 0.2601% | 1.4790%
(4,2) | 16.8167% | 1.6481% | 6.0515% | 0.0001%
(4,3) | 9.6990% | - | 0% | 3.6441%
(4,4) | 0.3982% | - | 0% | 9.0878%
(5,2) | 21.1221% | 2.1394% | 5.2313% | 0.1267%
(5,3) | 30.6120% | - | 0% | 1.9341%
(5,4) | 2.9124% | - | 0% | 11.968%
(6,2) | 10.3875% | 1.0792% | 1.7932% | 0.0679%
(6,3) | 39.4714% | - | 0% | 0.1088%
Table 3:  Summary of the difference between the relative volume (RV) of
several sets of interest. The leftmost column gives the Bell scenario
considered. From the second to the rightmost column, we have, respectively,
the difference in the RV between the set associated with the principle of
macroscopic locality $\mathcal{Q}_{1}$ and our tightest approximation to the
quantum set $\mathcal{Q}_{**}$, the difference in the RV between the almost
quantum set $\widetilde{\mathcal{Q}}_{1}$ and $\mathcal{Q}_{**}$, the
difference in the RV between $\mathcal{Q}_{**}$ and our tightest approximation
of the set producible by maximally entangled states with projective
measurements $\mathcal{M}^{\text{\tiny P}}_{*}$, and the difference in the RV
between our tightest approximation to the set $\mathcal{P}_{*}$ producible by
PPT quantum states and the Bell-local set $\mathcal{L}$.

####  III.2.2 $\mathcal{Q}_{**}$ vs $\mathcal{NS}$

Next, we focus on determining how $\text{RV}(\mathcal{Q}_{**})$ varies across
the different Bell scenarios. The trend of how $\text{RV}(\mathcal{Q}_{**})$
changes, with $\mathcal{L}$ included, is similar to that of $\mathcal{L}$
shown in Fig. 2. In a close parallel to 1, we have the following observation
for $\mathcal{Q}_{**}$ from Fig. 4.

######  Observation 6.

For Bell scenarios with the same output $n_{o}$, $\text{RV}(\mathcal{Q}_{**})$
decreases monotonically with increasing $n_{s}$.

Moreover, since $\mathcal{L}$ is a strict subset of
$\mathcal{Q}\subset\mathcal{Q}_{**}$, the following observation may have been
anticipated from 2.

######  Observation 7.

For Bell scenarios with the same input $n_{s}$, $\text{RV}(\mathcal{Q}_{**})$
increases monotonically with increasing $n_{o}$.

$2$$3$$4$$5$$0$%$10$%$20$%$30$%$40$%$50$%$60$%$70$%$80$%$90$%$100$%$n_{o}$$\text{RV}(\mathcal{Q}_{**})$$n_{s}=2$$n_{s}=3$$n_{s}=4$$n_{s}=5$$n_{s}=6$
Figure 4:  Plots of estimated $\text{RV}(\mathcal{Q}_{**})$ vs
$n_{o}\in\\{2,3,\ldots,5\\}$ for $n_{s}\in\\{2,3,\ldots,6\\}$. The plots for
the (2,6) and (2,7) Bell scenarios are omitted as
$\text{RV}(\mathcal{Q}_{**})=100\%$ in both cases.

Despite these similarities, there are also subtle differences. For example,
even though for fixed $n_{s}$, $\text{RV}(\mathcal{L})$ generally increases
with $n_{o}$, it does so after a dip when $n_{o}$ increases from $2$ to $3$.
More importantly, for Bell scenarios with $n_{s}=n_{o}=k$, while
$\text{RV}(\mathcal{L})$ appears to decrease monotonically with increasing
$k$, $\text{RV}(\mathcal{Q}_{**})$ never seems to get far away from 1. This
suggests that for any given $n_{s}$, if $n_{o}\geq n_{s}$ is large enough, a
generic $\vec{P}\in\mathcal{NS}$ is also likely to be a member of
$\mathcal{Q}$, i.e., $\text{RV}(\mathcal{NS}\setminus\mathcal{Q})$ may become
vanishingly small.

####  III.2.3 $\mathcal{Q}_{**}$ vs $\mathcal{L}$

What about the the Bell-nonlocal part of the quantum set, i.e.,
$\mathcal{Q}\setminus\mathcal{L}$? As can be seen from Fig. 5, for all $n_{s}$
investigated,
$\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})=\text{RV}(\mathcal{Q}_{**})-\text{RV}(\mathcal{L})$
first increases when $n_{o}$ increases from $2$ to $3$. However, for
$n_{s}\leq 4$, this difference in RVs decreases for subsequent values of
$n_{o}$. Since this is in agreement with the trend of $\text{RV}(\mathcal{L})$
shown in Fig. 2, the current observation suggests that the trend of
$\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})$ for fixed $n_{s}\leq 4$ is
dominated by the trend of $\text{RV}(\mathcal{L})$. In contrast, the behavior
of $\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})$ for varying $n_{s}$ does
not seem to follow immediately from that of $\text{RV}(\mathcal{Q}_{**})$ nor
$\text{RV}(\mathcal{L})$. In particular, for both the $n_{o}=2$ and the
$n_{o}=3$ case, we see that $\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})$
first increases with $n_{s}$ (from $2$ to $4$) but decreases monotonically
after that, which differs from the trend found for the $n_{o}=4$ scenarios.

######  Observation 8.

$\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})$ increases monotonically with
$n_{s}$ for the ($n_{s}$,4) Bell scenarios and reaches $>90\%$ for the (5,4)
Bell scenario.

A large value of $\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})$ is, a
priori, unexpected as it requires $\text{RV}(\mathcal{Q}_{**})$ to be large
and $\text{RV}(\mathcal{L})$ to be small at the same time. However, both
requirements happen to hold for the (5,4) Bell scenario.

$2$$3$$4$$5$$6$$7$$0$%$10$%$20$%$30$%$40$%$50$%$60$%$70$%$80$%$90$%$100$%$n_{o}$$\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})$$n_{s}=2$$n_{s}=3$$n_{s}=4$$n_{s}=5$$n_{s}=6$
Figure 5:  Plots of estimated
$\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})$ vs
$n_{o}\in\\{2,3,\ldots,7\\}$ for $n_{s}\in\\{2,3,\ldots,6\\}$. Here
$\mathcal{Q}_{**}=\widetilde{\mathcal{Q}}_{1}$ for the (4,3), (4,4), (5,3),
(5,4), and (6,3) Bell scenario whereas
$\mathcal{Q}_{**}\subsetneq\widetilde{\mathcal{Q}}_{1}$ for all the other Bell
scenarios considered.

Let us further remark that when comparing different Bell scenarios, the value
of $\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})$ need not correlate with
the nonlocality of the correlations contained therein. For example, one might
expect that the larger $\text{RV}(\mathcal{Q}_{**}\setminus\mathcal{L})$, the
stronger is the average resistance of the associated nonlocal correlations to
white noise $\vec{P}_{w}$. If so, then one might expect the correlations in
$\mathcal{Q}_{**}\setminus\mathcal{L}$ for the (5,4) scenario to display the
smallest average white-noise visibility [cf. Eq. 4] but the results summarized
in Table 4 show otherwise.

Scenario | $\mathcal{Q}_{**}$ | Max | Min | Mean | $\sigma$ | Within 1 $\sigma$
---|---|---|---|---|---|---
(2,2) | $\widetilde{\mathcal{Q}}_{4}$ | 1.0000 | 0.7300 | 0.9265 | 0.0538 | 64.75%
(2,3) | $\widetilde{\mathcal{Q}}_{2}$ | 1.0000 | 0.7429 | 0.9411 | 0.0461 | 67.40%
(2,4) | $\mathcal{Q}_{2}$ | 1.0000 | 0.7529 | 0.9540 | 0.0393 | 72.42%
(2,5) | $\mathcal{Q}_{2}$ | 1.0000 | 0.7964 | 0.9653 | 0.0308 | 75.37%
(2,6) | $\mathcal{Q}_{2}$ | 1.0000 | 0.8265 | 0.9720 | 0.0261 | 78.17%
(2,7) | $\mathcal{Q}_{2}$ | 0.9999 | 0.8742 | 0.9789 | 0.0226 | 87.42%
(3,2) | $\widetilde{\mathcal{Q}}_{2}$ | 1.0000 | 0.7214 | 0.9144 | 0.0563 | 62.69%
(3,3) | $\mathcal{Q}_{2}$ | 1.0000 | 0.7303 | 0.9318 | 0.0482 | 64.49%
(3,4) | $\mathcal{Q}_{2}$ | 1.0000 | 0.7286 | 0.9519 | 0.0394 | 70.67%
(4,2) | $\mathcal{Q}_{2}$ | 1.0000 | 0.7179 | 0.8979 | 0.0572 | 62.47%
(4,3) | $\widetilde{\mathcal{Q}}_{1}$ | 1.0000 | 0.7241 | 0.9136 | 0.0489 | 63.33%
(4,4) | $\widetilde{\mathcal{Q}}_{1}$ | 1.0000 | 0.7267 | 0.9439 | 0.0411 | 67.29%
(5,2) | $\mathcal{Q}_{2}$ | 1.0000 | 0.7195 | 0.8810 | 0.0538 | 65.02%
(5,3) | $\widetilde{\mathcal{Q}}_{1}$ | 1.0000 | 0.7336 | 0.8936 | 0.0416 | 67.83%
(5,4) | $\widetilde{\mathcal{Q}}_{1}$ | 1.0000 | 0.7468 | 0.9265 | 0.0403 | 66.17%
(6,2) | $\mathcal{Q}_{2}$ | 1.0000 | 0.7252 | 0.8672 | 0.0471 | 68.18%
(6,3) | $\widetilde{\mathcal{Q}}_{1}$ | 0.9998 | 0.7464 | 0.8833 | 0.0301 | 71.60%
Table 4:  Summary of sample statistics associated with the distribution of
$v^{*}$ to $\mathcal{L}$ for all those $\vec{P}$ found to lie in
$\mathcal{Q}_{**}\setminus\mathcal{L}$.

An illustration of how various supersets $\mathcal{T}$ of $\mathcal{L}$
contribute towards $\mathcal{NS}\setminus\mathcal{L}$, as measured according
to $f(\mathcal{T}\setminus\mathcal{L})=f(\mathcal{T})-f(\mathcal{L})$, can be
found in the stacked bar chart displayed in Fig. 6 and Fig. 7.

(2,2)(2,3)(2,4)(2,5)(2,6)(2,7)(3,2)(3,3)(3,4)(4,2)(4,3)(4,4)(5,2)(5,3)(5,4)(6,2)(6,3)$0$%$10$%$20$%$30$%$40$%$50$%$60$%$70$%$80$%$90$%$100$%Different
Bell scenarios $(n_{s},n_{o})$$f(\mathcal{T})$ for various
$\mathcal{T}\subseteq\mathcal{NS}$$\mathcal{NS}$$\mathcal{Q}_{1}$$\widetilde{\mathcal{Q}}_{1}$$\widetilde{\mathcal{Q}}_{*}$$\mathcal{P}_{*}$$\mathcal{Q}_{**}$$\mathcal{M}^{\text{\tiny
P}}_{*}$ Figure 6: Stacked bar charts showing contributions of various subsets
$\mathcal{T}\subseteq\mathcal{NS}$ towards $\mathcal{T}\setminus\mathcal{L}$
where $\mathcal{T}$ is either $\mathcal{M}^{\text{\tiny P}}_{*}$ or any of the
subsets listed in the chain of inclusion relations
$\mathcal{P}_{*}\subsetneq\widetilde{\mathcal{Q}}_{*}\subseteq\widetilde{\mathcal{Q}}_{1}\subsetneq\mathcal{Q}_{1}\subsetneq\mathcal{NS}$.
The RV of a given $\mathcal{T}$ in the nonlocal region, and hence
$f(\mathcal{T})$, is the sum over that due to the other sets contained within
it. For example, in the (2,2) Bell scenario, $f(\mathcal{Q}_{1})$ has
contributions from the orange bar as well as all the other bars (turqoise and
blue) stacked below it. As $\mathcal{M}^{\text{\tiny P}}_{*}$ and
$\mathcal{Q}_{**}$ are not directly comparable to some of the aforementioned
sets, we use, respectively, dashed and dotted line to represent them
separately. Note also that we have only performed computation for higher
levels from the hierarchy of Moroder et al. for the (2,2), (2,3), and (3,2)
Bell scenarios.
(2,2)(3,2)(4,2)(5,2)(6,2)(2,3)(3,3)(4,3)(5,3)(6,3)(2,4)(3,4)(4,4)(5,4)(2,5)(2,6)(2,7)$0$%$10$%$20$%$30$%$40$%$50$%$60$%$70$%$80$%$90$%$100$%Different
Bell scenarios $(n_{s},n_{o})$$f(\mathcal{T})$ for various
$\mathcal{T}\subseteq\mathcal{NS}$$\mathcal{NS}$$\mathcal{Q}_{1}$$\widetilde{\mathcal{Q}}_{1}$$\widetilde{\mathcal{Q}}_{*}$$\mathcal{P}_{*}$$\mathcal{Q}_{**}$$\mathcal{M}^{\text{\tiny
P}}_{*}$ Figure 7:  The stacked bar charts of Fig. 6 sorted first in
increasing $n_{s}$, then followed by increasing $n_{o}$.

###  III.3 Other Naturally Restricted Subsets of $\mathcal{Q}$

Next, let us consider $\mathcal{M}^{\text{\tiny P}}$ and $\mathcal{P}$, two
naturally restricted subsets of $\mathcal{Q}$. Again, our tightest outer
approximation to these sets are denoted, respectively, by
$\mathcal{M}^{\text{\tiny P}}_{*}$ and $\mathcal{P}_{*}$.

####  III.3.1 $\mathcal{Q}_{**}$ vs $\mathcal{M}^{\text{\tiny P}}_{*}$

Formally, as introduced in Section II, $\mathcal{M}^{\text{\tiny P}}$ is the
convex hull of the set of correlations attainable using finite-dimensional
maximally entangled states in conjunction with projective measurements. As was
first noted in Lang  _et al._ (2014), a hierarchy of (increasingly tighter)
outer approximations to $\mathcal{M}$ (the analog of $\mathcal{M}^{\text{\tiny
P}}$ without the assumption of measurements being projective) can be obtained
via SDPs. In Appendix A, we explain our simplified formulation when the
measurement are further assumed to be projective.

Note that the hierarchy of SDPs used for the computation of $\mathcal{Q}_{**}$
and that of $\mathcal{M}^{\text{\tiny P}}_{*}$ are independent. Consequently,
the two sets $\mathcal{M}^{\text{\tiny P}}_{*}$ and $\mathcal{Q}_{**}$ are
generally incomparable, i.e., neither of them is necessarily included in the
other, despite the fact that $\mathcal{M}^{\text{\tiny
P}}\subseteq\mathcal{M}\subsetneq\mathcal{Q}$. To quantitatively understand
the difference between $\mathcal{Q}$ and $\mathcal{M}^{\text{\tiny P}}$, we
thus focus on the difference between $\mathcal{Q}_{**}$ and
$\mathcal{M}^{\text{\tiny P}}_{*}\cap\mathcal{Q}_{**}$, i.e., the membership
test of any given $\vec{P}$ with respect to $\mathcal{M}^{\text{\tiny P}}_{*}$
is carried out only when it passes the membership test with respect to
$\mathcal{Q}_{**}$. For a summary of $\mathcal{Q}_{**}$,
$\mathcal{M}^{\text{\tiny P}}_{*}$ involved in the calculation and the sample
statistics associated with the distribution of $v^{*}$ to
$\mathcal{M}^{\text{\tiny P}}_{*}$, see Table 5.

Scenario | $\mathcal{Q}_{**}$ | $\mathcal{M}^{\text{\tiny P}}_{*}$ | Max | Min | Mean | $\sigma$ | Within 1 $\sigma$
---|---|---|---|---|---|---|---
(2,2) | $\widetilde{\mathcal{Q}}_{4}$ | $\mathcal{M}^{\text{\tiny P}}_{4}$ | 1.3268 | 0.9405 | 1.0434 | 0.0459 | 77.26%
(2,3) | $\widetilde{\mathcal{Q}}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{2}$ | 1.2230 | 0.9419 | 1.0247 | 0.0262 | 82.44%
(2,4) | $\mathcal{Q}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{2}$ | 1.1437 | 0.9470 | 1.0145 | 0.0151 | 85.03%
(2,5) | $\mathcal{Q}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{2}$ | 1.0942 | 0.9574 | 1.0094 | 0.0096 | 86.34%
(2,6) | $\mathcal{Q}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{1}$ | 1.0462 | 1.0000 | 1.0064 | 0.0066 | 85.81%
(2,7) | $\mathcal{Q}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{1}$ | 1.0353 | 1.0000 | 1.0054 | 0.0055 | 87.42%
(3,2) | $\widetilde{\mathcal{Q}}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{3}$ | 1.3526 | 0.9312 | 1.0364 | 0.0403 | 77.87%
(3,3) | $\mathcal{Q}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{2}$ | 1.2109 | 0.9343 | 1.0155 | 0.018 | 81.52%
(3,4) | $\mathcal{Q}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{1.5}$ | 1.1167 | 0.9298 | 1.0084 | 0.009 | 85.50%
(4,2) | $\mathcal{Q}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{2}$ | 1.3296 | 0.9348 | 1.0283 | 0.0339 | 78.20%
(4,3) | $\widetilde{\mathcal{Q}}_{1}$ | $\mathcal{M}^{\text{\tiny P}}_{1}$ | 1.1658 | 1.0000 | 1.0125 | 0.0124 | 85.33%
(4,4) | $\widetilde{\mathcal{Q}}_{1}$ | $\mathcal{M}^{\text{\tiny P}}_{1}$ | 1.0741 | 1.0000 | 1.0056 | 0.0056 | 86.45%
(5,2) | $\mathcal{Q}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{2}$ | 1.2661 | 0.9368 | 1.0204 | 0.0275 | 78.34%
(5,3) | $\widetilde{\mathcal{Q}}_{1}$ | $\mathcal{M}^{\text{\tiny P}}_{1}$ | 1.1157 | 1.0000 | 1.0093 | 0.0092 | 84.77%
(5,4) | $\widetilde{\mathcal{Q}}_{1}$ | $\mathcal{M}^{\text{\tiny P}}_{1}$ | 1.0480 | 1.0000 | 1.0039 | 0.0039 | 86.18%
(6,2) | $\mathcal{Q}_{2}$ | $\mathcal{M}^{\text{\tiny P}}_{2}$ | 1.2116 | 0.9412 | 1.0141 | 0.0218 | 78.53%
(6,3) | $\widetilde{\mathcal{Q}}_{1}$ | $\mathcal{M}^{\text{\tiny P}}_{1}$ | 1.0815 | 1.0000 | 1.0075 | 0.0073 | 83.98%
Table 5: Summary of sample statistics associated with the distribution of
$v^{*}$ to $\mathcal{M}^{\text{\tiny P}}_{*}$ of all those $\vec{P}$ found to
lie in $\mathcal{Q}_{**}$. The tightest approximations $\mathcal{Q}_{**}$ and
$\mathcal{M}^{\text{\tiny P}}_{*}$ are included, respectively, in the second
and the third column for ease of reference. The notation for
$\mathcal{M}^{\text{\tiny P}}_{h}$ is further explained in Appendix C.

Our findings (see Table 1 and Table 3) reveal that the difference between the
relative volume of these sets, i.e.,
$\text{RV}(\mathcal{Q}_{*})-\text{RV}(\mathcal{M}^{\text{\tiny
P}}_{*}\cap\mathcal{Q}_{*})$ is rather small.

######  Observation 9.

For all the 17 Bell scenarios considered, the largest value of
$\text{RV}(\mathcal{Q}_{*})-\text{RV}(\mathcal{M}^{\text{\tiny
P}}_{*}\cap\mathcal{Q}_{*})$ ($\approx$ 6.1%) is found for the Bell scenario
(4,2). The Bell scenario (5,2) gives a comparable difference $\approx$ 5.2%
whereas for 12 other Bell scenarios, this difference is less than 0.27%. In
general, the difference decreases with increasing $n_{o}$, see Table 3.

However, if we restrict our attention to only the nonlocal region of
$\mathcal{NS}$, then the difference as quantified by
$f(\mathcal{Q}_{*})-f(\mathcal{M}^{\text{\tiny P}}_{*}\cap\mathcal{Q}_{*})$ is
most pronounced ($\approx$8.2%) in the $(2,2)$ Bell scenario, where the
original Hardy paradox Hardy (1993) was proposed, see Fig. 6.

###  III.4 $\mathcal{P}_{*}$ vs $\mathcal{L}$

Finally, let us focus on the difference between the set of Bell-local
correlations $\mathcal{L}$ and that attainable by locally measuring a PPT
(entangled) state $\mathcal{P}$. For a long time, it was believed Peres (1999)
that no bound entangled state can violate a Bell inequality. Since all PPT
entangled states are bound entangled Horodecki  _et al._ (1998), this so-
called Peres conjecture would imply that $\mathcal{P}=\mathcal{L}$. Indeed, in
the simplest (2,2) Bell scenario, it was shown by Werner and Wolf Werner and
Wolf (2000) that these sets do coincide. Even for the (3,2) Bell scenario,
numerical results from Moroder  _et al._ (2013) again indicate that
$\mathcal{P}=\mathcal{L}$.

That this conjecture does not hold in full generality was first shown Vértesi
and Brunner (2012) in a tripartite Bell scenario using a three-qubit bound
entangled state. Later, the conjecture was also disproved Vertesi and Brunner
(2014) in a bipartite setting by considering a two-qutrit PPT entangled state
and an asymmetric Bell scenario $\\{[2\leavevmode\nobreak\
2\leavevmode\nobreak\ 2]\leavevmode\nobreak\ [3\leavevmode\nobreak\ 2]\\}$,
where the number of entries in each square bracket denotes the number of
settings for each party and the actual numbers listed are the number of
measurement outcomes for each setting.111The notation adopted here for this
asymmetric Bell scenario follows that introduced in Ref. Barnea  _et al._
(2013). Consequently, for any symmetric Bell scenario with $n_{s},n_{o}\geq
3$, we must have $\mathcal{L}\subsetneq\mathcal{P}$. Moreover, it can be shown
from the results of Ref. Vertesi and Brunner (2014) and Eq. 4 that the
corresponding $\vec{P}\in\mathcal{P}$ has a visibility $v^{*}$ to
$\mathcal{L}$ that is approximately 0.9996.

Here, we make use of the outer approximations proposed in Moroder  _et al._
(2013) to quantitatively survey the difference between $\mathcal{P}$ and
$\mathcal{L}$. Interestingly, even though $\mathcal{P}_{*}$ only outer
approximates $\mathcal{P}$, we see from Table 6 that for the (2,2) and the
(3,2) Bell scenario, these approximations work extremely well: among all the
$10^{6}$ samples generated for each of these Bell scenarios, there is not even
a single $\vec{P}\not\in\mathcal{P}_{*}$ that lies outside $\mathcal{L}$. This
is, of course, consistent with the known results given, respectively, in Ref.
Werner and Wolf (2000) and Ref. Moroder  _et al._ (2013). In fact, for the
(2,2) scenario, even the lowest-level approximation given by $\mathcal{P}_{1}$
does not give rise to any $\vec{P}\not\in\mathcal{L}$ from $10^{6}$ samples.

In contrast, except the (2,7) Bell scenario, we do find instances of
$\vec{P}\in\mathcal{P}_{*}\setminus\mathcal{L}$ for all other Bell scenarios
investigated, see Table 6. For this exceptional case, we note from Table 1
that $\mathcal{L}$ almost spans the entire non-signaling set, thus leaving
very little room for $\mathcal{NS}\setminus\mathcal{L}$, let alone
$\mathcal{P}\setminus\mathcal{L}$. For most of the other Bell scenarios, even
though we know from Table 6 that $\mathcal{P}_{*}\neq\mathcal{L}$, the
difference between $\text{RV}(\mathcal{P}_{*})$ and $\text{RV}(\mathcal{L})$
is tiny, if not vanishingly small.

######  Observation 10.

For all the 17 Bell scenarios considered, the largest value of
$\text{RV}(\mathcal{P}_{*}\setminus\mathcal{L})$ ($\approx$ 12%) is found for
the Bell scenario (5,4). The Bell scenario (4,4) shows a comparable difference
of $\approx$ 9.1% whereas for 12 other Bell scenarios, this difference is less
than 0.15%. Except the $n_{s}=2$ Bell scenarios,
$\text{RV}(\mathcal{P}_{*}\setminus\mathcal{L})$ increases with increasing
$n_{o}$, see Table 3.

Zooming into the behavior of the individual correlation, we see from Table 6
that within these approximations, one can find
$\vec{P}\in(\mathcal{P}_{*}\setminus\mathcal{L})$ that are far more robust
with respect to the mixing with white noise in more complex Bell scenarios.
For example, in the (4,4) Bell scenario, the most robust
$\vec{P}\in\mathcal{P}_{*}$ was found to give a visibility of 0.9037, as
compared with a visibility of 0.9996 found Vertesi and Brunner (2014) in the
(3,3) Bell scenario.

Scenario | $\mathcal{P}_{*}$ | Max | Min | Mean | $\sigma$ | Within 1 $\sigma$
---|---|---|---|---|---|---
(2,3) | $\mathcal{P}_{2}$ | 0.9998 | 0.9963 | 0.9983 | 0.0010 | 66.67%
(2,4) | $\mathcal{P}_{2}$ | 0.9999 | 0.9972 | 0.9986 | 0.0008 | 66.67%
(2,5) | $\mathcal{P}_{1.5}$ | 1.0000 | 0.9908 | 0.9970 | 0.0034 | 76.47%
(2,6) | $\mathcal{P}_{1.5}$ | 0.9999 | 0.9985 | 0.9993 | 0.0008 | 66.67%
(3,3) | $\mathcal{P}_{2}$ | 1.0000 | 0.9994 | 0.9997 | 0.0004 | 100%
(3,4) | $\mathcal{P}_{1.25}$ | 1.0000 | 0.9326 | 0.9883 | 0.0094 | 70.18%
(4,2) | $\mathcal{P}_{2}$ | 1.0000 | 0.9999 | 1.0000 | 0.0001 | 66.67%
(4,3) | $\mathcal{P}_{1.2}$ | 1.0000 | 0.9194 | 0.9856 | 0.0109 | 69.05%
(4,4) | $\mathcal{P}_{1}$ | 1.0000 | 0.9037 | 0.9819 | 0.0141 | 67.90%
(5,2) | $\mathcal{P}_{1.5}$ | 1.0000 | 0.9536 | 0.9918 | 0.0081 | 83.50%
(5,3) | $\mathcal{P}_{1}$ | 1.0000 | 0.9088 | 0.9751 | 0.0157 | 64.64%
(5,4) | $\mathcal{P}_{1}$ | 1.0000 | 0.9041 | 0.9772 | 0.014 | 62.32%
(6,2) | $\mathcal{P}_{1}$ | 0.9999 | 0.9087 | 0.9752 | 0.0179 | 65.39%
(6,3) | $\mathcal{P}_{1}$ | 0.9996 | 0.9213 | 0.9691 | 0.0139 | 66.86%
Table 6:  Summary of sample statistics associated with the distribution of
$v^{*}$ to $\mathcal{L}$ of all those $\vec{P}$ found to lie in
$\mathcal{P}_{*}\setminus\mathcal{L}$. For the Bell scenarios (2,2), (2,7) and
(3,2), we do not find any correlation
$\vec{P}\in\mathcal{P}_{*}\setminus\mathcal{L}$, thus the respective rows are
omitted. The tightest approximation $\mathcal{P}_{*}$ is included in the
second column for ease of reference. The notation for $\mathcal{P}_{z}$ is
further explained in Appendix C.

##  IV Discussions

In the studies of Bell-nonlocality Brunner  _et al._ (2014) and its
applications in device-independent quantum information Scarani (2012) (DIQI),
one often exploits the geometrical features associated with the correlation
$\vec{P}$ or the set(s) in which they belong to draw conclusions. For example,
the convexity of $\mathcal{L}$, $\mathcal{Q}$, and $\mathcal{NS}$ and the
possibility to describe $\mathcal{L}$ and $\mathcal{NS}$ using a finite number
of extreme points are often invoked to simplify the analyses in DIQI.
Nonetheless, despite the numerous efforts devoted to these lines of research,
much about the geometry of these sets remain to be understood, see, e.g., Ref.
Goh  _et al._ (2018).

In fact, even though the inclusion relations
$\mathcal{L}\subsetneq\mathcal{M}^{\text{\tiny
P}}\subsetneq\mathcal{Q}\subsetneq\widetilde{\mathcal{Q}}_{1}\subsetneq\mathcal{Q}_{1}\subsetneq\mathcal{NS}$
and $\mathcal{L}\subseteq\mathcal{P}\subsetneq\mathcal{Q}$ are long known, we
do not have any quantitative understanding of their difference beyond the
extremely limited exploration carried out in Refs. Cabello (2005); Wolfe and
Yelin (2012); Duarte  _et al._ (2018) for $\mathcal{L}$, $\mathcal{Q}$, and
$\mathcal{NS}$. In this work, by determining the relative volume (RV) of these
sets or their outer approximations, we aim to fill this gap by putting some of
the intuitions that the community has developed over the years on more
quantitative grounds. As $\text{RV}(\mathcal{T})$ can be interpreted as the
success probability of a Bernoulli trial, if $\text{RV}(\mathcal{T})\geq
100\%-\epsilon$ for some $\mathcal{T}\subseteq\mathcal{NS}$, the operational
task of finding a correlation in $\mathcal{NS}\setminus\mathcal{T}$ by a
uniform sampling in $\mathcal{NS}$ can only succeed with probability at most
$\epsilon$. En route to the above goal, several intriguing observations are
noted.

Firstly, our results suggest that, the fraction of $\mathcal{L}$ in
$\mathcal{NS}$ becomes vanishingly small (1) as we fix the number of outputs
$n_{o}$ but increases the number of inputs $n_{s}$. A similar monotonic
behavior is also observed for the macroscopically-local set $\mathcal{Q}_{1}$,
the almost-quantum set $\widetilde{\mathcal{Q}}_{1}$ (see Table 1), as well as
our tightest approximation to the quantum set $\mathcal{Q}_{**}$ (6). Although
the two-output case of 1 was already noted in Ref. Duarte  _et al._ (2018),
our results provide further evidence this trend could well be generic, i.e.,
independent of the actual value of $n_{o}$. Moreover, we demonstrate how a
combinatoric argument can be used to understand this decreasing trend.

Interestingly, apart from a dip at the beginning, an essentially opposite
trend for $\text{RV}(\mathcal{L})$ is found when we fix the number of inputs
$n_{s}$ but increases the number of outputs $n_{o}$ (2). This increasing trend
is even found to be monotonic for several supersets of $\mathcal{L}$,
including $\mathcal{Q}_{1}$, $\widetilde{\mathcal{Q}}_{1}$ (see Table 1), and
$\mathcal{Q}_{**}$ (7). Again, this suggests that the trend—already noted in
Ref. Duarte  _et al._ (2018) for the special case of $n_{s}=2$—could well be
generic and independent of the specific value of $n_{s}$. If so, then for any
given $n_{s}$, the quantum set $\mathcal{Q}$ and its superset $\mathcal{NS}$
may become essentially indistinguishable when $n_{o}$ is sufficiently large.
While we do not have an intuitive explanation for this observation, it seems
plausible that it can lead to interesting consequences on the power of
nonlocal quantum resources.

What about the quality of various outer approximations of $\mathcal{Q}$, which
is especially relevant for a variety of tasks in DIQI? Our results suggest
that for two-input Bell scenarios, $\mathcal{Q}_{1}$ already provides a superb
outer approximation, with
$\text{RV}(\mathcal{Q}_{1})-\text{RV}(\mathcal{Q}_{**})<0.7\%$, but for Bell
scenarios with $n_{s}>3\geq n_{o}$, the reliability of $\mathcal{Q}_{1}$ as an
outer approximation becomes questionable (4). In these cases, the difference
$\text{RV}(\mathcal{Q}_{1})-\text{RV}(\mathcal{Q}_{**})$ can even get as large
as $\approx 39.5\%$. In contrast, the almost-quantum set
$\widetilde{\mathcal{Q}}_{1}$, as its name suggests, gives consistently a tiny
deviations, if at all, from our tightest quantum approximation (5). Still, our
results (see Table 3) suggest that a more noticeable difference may be found
in a Bell scenario with two outputs but a larger number of inputs, say,
$n_{s}=5$.

Moving on to naturally restricted subsets of $\mathcal{Q}$, it is known from
the work of Ref. Liang  _et al._ (2011) and Ref. Vidick and Wehner (2011) that
$\mathcal{M}^{\text{\tiny P}}\subseteq\mathcal{M}\subsetneq\mathcal{Q}$,
respectively, in the (2,2) and the (3,2) Bell scenario. Our results indicate
that for fixed $n_{s}$, the difference between $\mathcal{M}^{\text{\tiny P}}$
and $\mathcal{Q}$ may diminish following the increase in $n_{o}$ (9). If so,
in a Bell scenario where $n_{s}\ll n_{o}$, it may be sufficient to consider
only finite-dimensional maximally entangled states in conjunction with
projective measurements for various tasks in DIQI. However, our observation
should not be taken to imply that $\mathcal{M}^{\text{\tiny P}}\to\mathcal{Q}$
for any Bell scenario with large enough $n_{o}$, see, e.g., Ref. Junge and
Palazuelos (2011).

In contrast, our results do suggest that the difference between $\mathcal{P}$
and $\mathcal{L}$ may become noticeable only when the Bell scenario involved
is sufficiently complex (10). In particular, for the $(n_{s},2)$ and
$(2,n_{o})$ Bell scenarios that we have investigated, the respective
$\text{RV}(\mathcal{P}_{*})-\text{RV}(\mathcal{L})$ is always found to be tiny
($<0.17\%$). For all but two of the remaining Bell scenarios, this difference
is also never more than $3.7\%$. That leaves us only with the (4,4) and the
(5,4) Bell scenario—among all those computed—as the most promising candidate
for an experimental demonstration of the Peres conjecture violation. Still,
even though we get, respectively,
$\text{RV}(\mathcal{P}_{*}\setminus\mathcal{L})\approx 9\%$ and $\approx
12\%$, and a minimum visibility of $\approx 0.90$ for both Bell scenarios,
further investigation is clearly needed to confirm its experimental viability.

Apart from this, a few other closely-related research directions may be worth
pursuing. For example, even though both $\mathcal{P}$ and
$\mathcal{M}^{\text{\tiny P}}$ are known to be subsets of $\mathcal{Q}$, their
precise relationship is not known. Intuitively, one would expect $\mathcal{P}$
to be a strict subset of $\mathcal{M}^{\text{\tiny P}}$, which is supported by
our observation that
$\text{RV}(\mathcal{Q}_{**})-\text{RV}(\mathcal{M}^{\text{\tiny P}}_{*})$ and
$\text{RV}(\mathcal{P}_{*})-\text{RV}(\mathcal{L})$ are typically small, but
proving this does not seem to be trivial. Evidently, a comprehensive
estimation of the relative volume of various naturally restricted subsets in
the multipartite setting is also desirable. Due to the rich structure in
multipartite entanglement Lu  _et al._ (2018) and multipartite nonlocality
Curchod  _et al._ (2015), there will be many more natural subsets of
$\mathcal{NS}$ to consider in those cases.

Another direction that deserves further investigation is that related to the
choice of metric in our sampling. In this work, we have opted for the
Euclidean metric defined in the space of $\mathscr{P}_{\mathcal{NS}}$.
However, since the space of interest $\mathscr{P}$ is a probability space, an
arguably more natural Acín  metric is the so-called Fisher (information)
metric ${\rm d}s_{\text{\tiny F}}^{2}$. For a set of unconditional probability
distributions $q_{i}$ such that $q_{i}\geq 0$ and $\sum_{i}q_{i}=1$, the
Fisher metric and hence the corresponding volume element are given,
respectively, by Acín (2001):

${\rm d}s_{\text{\tiny F}}^{2}=\sum_{i}\frac{{\rm
d}q_{i}^{2}}{q_{i}}\quad\text{ and }\quad{\rm d}V_{\text{\tiny
F}}=\prod_{i}\left(\frac{{\rm d}q_{i}}{\sqrt{q_{i}}}\right).$ (10)

Recall from Section II that we are interested in conditional distributions
lying in the non-signaling subspace, cf. Eq. 1. These requirements, together
with a nontrivial dependence of the metric on the coordinate in $\mathscr{P}$,
however, make it unclear how we can perform a uniform sampling according to
this metric (e.g., using an existing software package like $\mathsf{cprnd}$).
Similarly, a careful reader would have noticed that if we work in the space of
$\mathscr{P}$, the uniform distribution $\vec{P}_{w}$ has the same Euclidean
distance to all extreme points of $\mathcal{L}$ (see Appendix E) but if we
make use of the parametrization given in Eq. 5, then this invariance is lost.
As such, it would be interesting to find a parameterization of
$\mathscr{P}_{\mathcal{NS}}$ where this invariance is preserved and repeat the
calculation performed here.

Finally, recall that in our studies of convergence of the outer approximations
of $\mathcal{Q}$ (see Section III.2.1), we use the hierarchies of SDPs defined
by NPA Navascués  _et al._ (2007) as well as those given in Moroder et al.
Moroder  _et al._ (2013). These are, however, not the only outer
approximations of $\mathcal{Q}$ that discussed in the literature. For example,
the SDPs defined by Berta et al. Berta  _et al._ (2016) are also known to
define a converging hierarchy of outer approximations. Moreover, in comparison
with the NPA hierarchy, the approximations of Berta et al. are known to be
(possibly) tighter as they include further non-negativity requirement of
certain elements of the moment matrix (see also Ref. Sikora and Varvitsiotis
(2017)). It could thus also be interesting to investigate, how this, and other
hierarchies of outer approximations (e.g., those discussed in Chen  _et al._
(2018b)) appear to converge.

###### Acknowledgements.

We are grateful to Tulja Varun Kondra for his contribution at the initial
stage of this research project, to Antonio Acín, Jean-Daniel Bancal, Elie
Wolfe, and Denis Rosset for their suggestions on how uniform sampling on
convex sets (of correlations) may be performed. Part of this work was
completed during PSL’s visit to the Institute of Photonic Sciences (ICFO),
Spain and YCL’s visit to the Perimeter Institute for Theoretical Physics,
Canada. The hospitality of both institutes is greatly appreciated. This work
is supported by the Ministry of Science and Technology, Taiwan (Grants No.
104-2112-M-006-021-MY3, 107-2112-M-006-005-MY2, and 109-2112-M006-010-MY3),
the EU (QuantERA eDICT) and the National Research, Development and Innovation
Office NKFIH (No. 2019-2.1.7-ERA-NET-2020-00003).

## References

  * Bell (1964) J. S. Bell, Physics 1, 195 (1964).
  * Brunner  _et al._ (2014) N. Brunner _et al._ , Rev. Mod. Phys. 86, 419 (2014).
  * Bell (2004) J. S. Bell,  _Speakable and Unspeakable in Quantum Mechanics: Collected Papers on Quantum Philosophy_, 2nd ed. (Cambridge University Press, 2004).
  * Popescu and Rohrlich (1994) S. Popescu and D. Rohrlich, Found. Phys. 24, 379 (1994).
  * Barrett  _et al._ (2005) J. Barrett, N. Linden, S. Massar, S. Pironio, S. Popescu, and D. Roberts, Phys. Rev. A 71, 022101 (2005).
  * Brassard  _et al._ (2006) G. Brassard, H. Buhrman, N. Linden, A. A. Méthot, A. Tapp, and F. Unger, Phys. Rev. Lett. 96, 250401 (2006).
  * Linden  _et al._ (2007) N. Linden, S. Popescu, A. J. Short, and A. Winter, Phys. Rev. Lett. 99, 180502 (2007).
  * Pawlowski  _et al._ (2009) M. Pawlowski, T. Paterek, D. Kaszlikowski, V. Scarani, A. Winter, and M. Zukowski, Nature 461, 1101 (2009).
  * Navascués and Wunderlich (2009) M. Navascués and H. Wunderlich, Proc. R. Soc. A 466, 881 (2009).
  * Fritz  _et al._ (2013) T. Fritz, A. B. Sainz, R. Augusiak, J. B. Brask, R. Chaves, A. Leverrier, and A. Acín, Nat. Commun. 4, 2263 (2013).
  * Navascués  _et al._ (2015) M. Navascués, Y. Guryanova, M. J. Hoban, and A. Acín, Nat. Commun. 6, 6288 (2015).
  * Gonda  _et al._ (2018) T. Gonda, R. Kunjwal, D. Schmid, E. Wolfe, and A. B. Sainz, Quantum 2, 87 (2018).
  * Vallins  _et al._ (2017) J. Vallins, A. B. Sainz, and Y.-C. Liang, Phys. Rev. A 95, 022111 (2017).
  * Navascués  _et al._ (2007) M. Navascués, S. Pironio, and A. Acín, Phys. Rev. Lett. 98, 010401 (2007).
  * Navascués  _et al._ (2008) M. Navascués, S. Pironio, and A. Acín, New J. Phys. 10, 073013 (2008).
  * Doherty  _et al._ (2008) A. C. Doherty, Y.-C. Liang, B. Toner, and S. Wehner, in  _23rd Annu. IEEE Conf. on Comput. Comp, 2008, CCC’08_ (Los Alamitos, CA, 2008) pp. 199–210.
  * Slofstra (2019) W. Slofstra,  _Forum of Mathematics, Pi_ ,  7, e1 (2019).
  * Slofstra (2020) W. Slofstra, J. Amer. Math. Soc. 33, 1 (2020).
  * Coladangelo and Stark (2020) A. Coladangelo and J. Stark, Nature Communications 11, 3335 (2020).
  * Goh  _et al._ (2018) K. T. Goh, J. Kaniewski, E. Wolfe, T. Vértesi, X. Wu, Y. Cai, Y.-C. Liang, and V. Scarani, Phys. Rev. A 97, 022104 (2018).
  * Harrow  _et al._ (2019) A. W. Harrow, A. Natarajan, and X. Wu, Commun. Math. Phys. 366, 423 (2019).
  * Moroder  _et al._ (2013) T. Moroder, J.-D. Bancal, Y.-C. Liang, M. Hofmann, and O. Gühne, Phys. Rev. Lett. 111, 030501 (2013).
  * Peres (1996) A. Peres, Phys. Rev. Lett. 77, 1413 (1996).
  * Peres (1999) A. Peres, Found. Phys. 29, 589 (1999).
  * Vertesi and Brunner (2014) T. Vertesi and N. Brunner, Nat. Commun. 5, 5297 (2014).
  * Horodecki  _et al._ (1998) M. Horodecki, P. Horodecki, and R. Horodecki, Phys. Rev. Lett. 80, 5239 (1998).
  * Hardy (1993) L. Hardy, Phys. Rev. Lett. 71, 1665 (1993).
  * Liang  _et al._ (2011) Y.-C. Liang, T. Vértesi, and N. Brunner, Phys. Rev. A 83, 022108 (2011).
  * Vidick and Wehner (2011) T. Vidick and S. Wehner, Phys. Rev. A 83, 052310 (2011).
  * Junge and Palazuelos (2011) M. Junge and C. Palazuelos, Commun. Math. Phys. 306, 695 (2011).
  * Christensen  _et al._ (2015) B. G. Christensen, Y.-C. Liang, N. Brunner, N. Gisin, and P. G. Kwiat, Phys. Rev. X 5, 041052 (2015).
  * Lang  _et al._ (2014) B. Lang, T. Vértesi, and M. Navascués, J. Phys. A Math. Theor. 47, 424029 (2014).
  * Boyd and Vandenberghe (2004) S. Boyd and L. Vandenberghe,  _Convex Optimization_ , 1st ed. (Cambridge University Press, Cambridge, 2004).
  * Scarani (2012) V. Scarani, Acta Physica Slovaca 62, 347 (2012).
  * Colbeck (2009) R. Colbeck, PhD thesis, arXiv:0911.3814 (2009).
  * Pironio  _et al._ (2010) S. Pironio, A. Acín, S. Massar, A. B. d. l. Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, Nature (London) 464, 1021 (2010).
  * Acín  _et al._ (2007) A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, Phys. Rev. Lett. 98, 230501 (2007).
  * Bancal  _et al._ (2011) J.-D. Bancal, N. Gisin, Y.-C. Liang, and S. Pironio, Phys. Rev. Lett. 106, 250404 (2011).
  * Liang  _et al._ (2015) Y.-C. Liang, D. Rosset, J.-D. Bancal, G. Pütz, T. J. Barnea, and N. Gisin, Phys. Rev. Lett. 114, 190401 (2015).
  * Chen  _et al._ (2016) S.-L. Chen, C. Budroni, Y.-C. Liang, and Y.-N. Chen, Phys. Rev. Lett. 116, 240401 (2016).
  * Arnon-Friedman and Bancal (2019) R. Arnon-Friedman and J.-D. Bancal, New J. Phys. 21, 033010 (2019).
  * Chen  _et al._ (2018a) S.-L. Chen, C. Budroni, Y.-C. Liang, and Y.-N. Chen, Phys. Rev. A 98, 042127 (2018a).
  * Rabelo  _et al._ (2011) R. Rabelo, M. Ho, D. Cavalcanti, N. Brunner, and V. Scarani, Phys. Rev. Lett. 107, 050502 (2011).
  * Bancal  _et al._ (2018) J.-D. Bancal, N. Sangouard, and P. Sekatski, Phys. Rev. Lett. 121, 250506 (2018).
  * Chen  _et al._ (2021) S.-L. Chen, N. Miklin, C. Budroni, and Y.-N. Chen, Phys. Rev. Research 3, 023143 (2021).
  * Sekatski  _et al._ (2018) P. Sekatski, J.-D. Bancal, S. Wagner, and N. Sangouard, Phys. Rev. Lett. 121, 180505 (2018).
  * Wagner  _et al._ (2020) S. Wagner, J.-D. Bancal, N. Sangouard, and P. Sekatski, Quantum 4, 243 (2020).
  * Mayers and Yao (2004) D. Mayers and A. Yao, Quantum Info. Comput. 4, 273 (2004).
  * Šupić and Bowles (2020) I. Šupić and J. Bowles, Quantum 4, 337 (2020).
  * Cabello (2005) A. Cabello, Phys. Rev. A 72, 012113 (2005).
  * Wolfe and Yelin (2012) E. Wolfe and S. F. Yelin, Phys. Rev. A 86, 012123 (2012).
  * Duarte  _et al._ (2018) C. Duarte _et al._ , Phys. Rev. A 98, 062114 (2018).
  * Werner and Wolf (2001) R. F. Werner and M. M. Wolf, Phys. Rev. A 64, 032112 (2001).
  * Fine (1982) A. Fine, Phys. Rev. Lett. 48, 291 (1982).
  * Pitowsky (1989) I. Pitowsky,  _Quantum Probability - Quantum Logic_ (Springer, Berlin, 1989).
  * Wiseman (2014) H. M. Wiseman, J. Phys. A Math. Theor. 47, 424001 (2014).
  * Peres (1990) A. Peres, Found. Phys. 20, 1441 (1990).
  * Werner (1989) R. F. Werner, Phys. Rev. A 40, 4277 (1989).
  * Barrett (2002) J. Barrett, Phys. Rev. A 65, 042302 (2002).
  * Vértesi and Brunner (2012) T. Vértesi and N. Brunner, Phys. Rev. Lett. 108, 030403 (2012).
  * Chen  _et al._ (2018b) S.-L. Chen, C. Budroni, Y.-C. Liang, and Y.-N. Chen, Phys. Rev. A 98, 042127 (2018b).
  * Wittek (2015) P. Wittek, ACM Trans. Math. Softw. 41 (2015).
  * Collins and Gisin (2004) D. Collins and N. Gisin, J. Phys. A: Math. Theo. 37, 1775 (2004).
  * Benham (2014) T. Benham, “Uniform distribution over a convex polytope,” MATLAB central file exchange (2014).
  * Avis (1999) D. Avis, “lrs: A revised implementation of the reverse search vertex enumeration algorithm,” (unpublished) (1999).
  * Büeler  _et al._ (2000) B. Büeler, A. Enge, and K. Fukuda, “Exact volume computation for polytopes: A practical study,” in  _Polytopes —Combinatorics and Computation_, edited by G. Kalai and G. M. Ziegler (Birkhäuser Basel, Basel, 2000) pp. 131–154.
  * Werner and Wolf (2000) R. F. Werner and M. M. Wolf, Phys. Rev. A 61, 062102 (2000).
  * Barnea  _et al._ (2013) T. J. Barnea, J.-D. Bancal, Y.-C. Liang, and N. Gisin, Phys. Rev. A 88, 022123 (2013).
  * Lu  _et al._ (2018) H. Lu, Q. Zhao, Z.-D. Li, X.-F. Yin, X. Yuan, J.-C. Hung, L.-K. Chen, L. Li, N.-L. Liu, C.-Z. Peng, Y.-C. Liang, X. Ma, Y.-A. Chen, and J.-W. Pan, Phys. Rev. X 8, 021072 (2018).
  * Curchod  _et al._ (2015) F. J. Curchod, N. Gisin, and Y.-C. Liang, Phys. Rev. A 91, 012121 (2015).
  * (71) A. Acín, (private communication).
  * Acín (2001) A. Acín, Phys. Rev. Lett. 87, 177901 (2001).
  * Berta  _et al._ (2016) M. Berta, O. Fawzi, and V. B. Scholz, Siam J. Optim. 26, 1529 (2016).
  * Sikora and Varvitsiotis (2017) J. Sikora and A. Varvitsiotis, Math. Program., Ser. A 162, 431 (2017).
  * Wilson (1927) E. B. Wilson, J. Amer. Statist. Assoc 22, 209 (1927).

##  Appendix A Approximation to the $\mathcal{M}^{\text{\tiny P}}$

In this section, we explain how our approximations to the convex hull of the
set of correlations attainable by finite-dimensional maximally entangled
quantum states $\mathcal{M}$ are defined. As was pointed out in Ref. Lang  _et
al._ (2014), $\mathcal{M}$ can be outer approximated by a hierarchy of
correlations, each amenable to an SDP characterization. Here, we focus on a
subset $\mathcal{M}^{\text{\tiny P}}$ of $\mathcal{M}$, where the local POVM
elements are further assumed to projectors.

To appreciate how the hierarchy works, let us first remind that for any local
POVM element $E_{a|x}$ $E_{b|y}$ acting on a bipartite $d$-dimensional
maximally entangled state
$|\Psi_{d}\rangle=\frac{1}{\sqrt{d}}\sum_{i=1}^{d}|i\rangle|i\rangle$, we
have:

$\begin{split}P(a,b|x,y)=\langle\Psi_{d}|E_{a|x}\otimes
E_{b|y}|\Psi_{d}\rangle=\tfrac{{\rm tr}\left(E_{a|x}E_{b|y}^{\text{\tiny
T}}\right)}{d},\end{split}$ (11)

where $(\cdot)^{\text{\tiny T}}$ denotes transposition.

The essence of the characterization of $\mathcal{M}$, and hence of our
characterization of $\mathcal{M}^{\text{\tiny P}}$, is an approximation of the
trace function in Eq. 11 by a linear function acting on the POVM elements. To
this end, let us define $M_{0}=\\{\mathbb{I}_{d}\\}$, which is the set
consisting of only the $d$-dimensional identity operator, and its union with a
set of projective POVM elements

$M_{1}=\\{\mathbb{I}_{d}\\}\cup\\{\tilde{E}_{a|x}\\}_{a,x}\cup\\{\tilde{E}_{b|y}\\}_{b,y}$
(12)

where $a,b=1,2,\ldots,n_{o}-1$, $x,y=1,2,\ldots,n_{s}$. Here, the projective
nature of the POVM elements implies

$\tilde{E}_{a|x}\tilde{E}_{a^{\prime}|x}=\tilde{E}_{a|x}\delta_{a,a^{\prime}},\quad\tilde{E}_{b|y}\tilde{E}_{b^{\prime}|y}=\tilde{E}_{b|y}\delta_{b,b^{\prime}}.$
(13)

More generally, for any positive integer $k>1$, let us define the set of
operators with degree $k$ or less as

$M_{k}=\cup_{i}\,\left\\{\Pi_{i}(\tilde{E}^{1}\dots\tilde{E}^{k})\right\\},$
(14)

where the union is over all possible permutations $\Pi_{i}$ of $k$-fold
product of operators chosen from $M_{1}$. Notice that as both
$\tilde{E}_{a|x}$ and $\tilde{E}_{b|y}$ act on the same Hilbert space, they
generally do not commute.

Now, in analogy to the work of Ref. Lang  _et al._ (2014), we define a
bipartite correlation $\vec{P}$ to be a member of $\mathcal{M}^{\text{\tiny
P}}_{k}$, $k\geq 1$, if there exists an integer $d\geq 2$ and a linear
functional $L:M_{k}\times M_{k}\rightarrow\mathscr{P}_{\mathcal{NS}}$ such
that the following properties hold:

  1. 1.

$L(\mathbb{I}_{d})=1$.

  2. 2.

$L(ff^{\dagger})\geq 0$ for any $f\in M_{k}$.

  3. 3.

$L(f\tilde{E}_{a|x}f^{\dagger}),L(f\tilde{E}_{b|y}f^{\dagger})\geq 0$ for any
$f\in{M}_{k-1}$.

  4. 4.

$L(f\tilde{E}_{a|x}f^{\dagger}\tilde{E}_{a^{\prime}|x^{\prime}}),L(f\tilde{E}_{b|y}f^{\dagger}\tilde{E}_{b^{\prime}|y^{\prime}})\geq
0$ and $\\\
L(f\tilde{E}_{a|x}f^{\dagger}\tilde{E}_{b|y}),L(f\tilde{E}_{b|y}f^{\dagger}\tilde{E}_{a|x})\geq
0$ for any $f\in{M}_{k-1}$.

  5. 5.

$L(ST)=L(TS)$ where $ST\in M_{2k}$.

  6. 6.

$L(\tilde{E}_{a|x}\tilde{E}_{b|y})=P(a,b|x,y)$ for all $a,b,x,y$.

Clearly, if $\vec{P}\in\mathcal{M}^{\text{\tiny P}}$, then by Eq. 11, a linear
functional satisfying all the above properties is guaranteed to exist by
taking $L(\cdot)=\frac{1}{d}\operatorname{tr}(\cdot)$ and setting
$\tilde{E}_{a|x}=E_{a|x}$ and $\tilde{E}_{b|y}=E^{\text{\tiny T}}_{b|y}$. In
other words, $\vec{P}\in\mathcal{M}^{\text{\tiny
P}}\implies\vec{P}\in\mathcal{M}^{\text{\tiny P}}_{k}$ for all $k\geq 1$.
Importantly, for any given integer $k\geq 1$, the membership of any given
$\vec{P}\stackrel{{\scriptstyle?}}{{\in}}\mathcal{M}^{\text{\tiny P}}_{k}$ can
be determined by solving an SDP that amounts to requiring the existence of a
positive semidefinite moment matrix $\Gamma$ with its entries given by
$\Gamma_{ij}=L(f_{i}f_{j}^{\dagger})$ where $f_{i},f_{j}\in M_{k}$ and where
all these entries are required to satisfy the linear constraints listed above.

A few remarks are now in order. Firstly, as oppose to the NPA hierarchy where
the convexity of $\mathcal{Q}_{[\cdot,\cdot]}$ (and hence of
$\mathcal{Q}_{k}$) is promised by not restricting the underlying Hilbert space
dimension, convexity has to be assumed in the formulation of $\mathcal{M}$ or
$\mathcal{M}^{\text{\tiny P}}$ by considering the convex hull of the set of
correlations attainable from $|\Psi_{d}\rangle$. Secondly, in the formulation
of $\mathcal{M}$, the projective nature of the POVM elements cannot be taken
for granted, since a naïve application of Naimark’s extension Peres (1990)
does not guarantee that the state to which the extended projective POVM
elements are applied is maximally entangled.

Bell Scenario | $k$ | ($D_{\mathcal{Q}_{k}}$, $N_{\mathcal{Q}_{k}}$) | $l$ | ($D_{\widetilde{\mathcal{Q}}_{l}}$, $N_{\widetilde{\mathcal{Q}}_{l}}$) | $z$ | ($D_{\mathcal{P}_{z}}$, $N_{\mathcal{P}_{z}}$) | $h$ | ($D_{\mathcal{M}^{\text{\tiny P}}_{h}}$, $N_{\mathcal{M}^{\text{\tiny P}}_{h}}$, $N_{\mathcal{M}^{\text{\tiny P}}_{h}}^{\geq 0}$) | ($D_{\mathcal{L}}$, $N_{\text{\tiny ext}}^{\mathcal{L}}$)
---|---|---|---|---|---|---|---|---|---
(2,2) | 4 | (41, 101) | 4 | (81, 185) | 4 | (81, 185) | 4 | (161, 806, 239) | (8, 16)
(2,3) | 3 | (137, 1 449) | 2 | (169, 1 945) | 2 | (169, 1 945) | 2 | (57, 311, 177) | (24, 81)
(2,4) | 2 | (85, 1 003) | 1 | (49, 337) | 2 | (625, 29 353) | 2 | (121, 1 282, 553) | (48, 256)
(2,5) | 2 | (145, 2 833) | 1 | (81, 881) | 1.5 | (256, 9 106) | 2 | (209, 3 657, 1 265) | (80, 625)
(2,6) | 2 | (221, 6 471) | 1 | (121, 19 21) | 1.5 | (1 296, 17 946) | 1 | (21, 171, 171) | (120, 1 296)
(2,7) | 2 | (313, 12 841) | 1 | (169, 3 697) | 1 | (169, 3 697) | 1 | (25, 241, 241) | (168, 2 401)
(2,8) | 1 | (29, 323) | 1 | (225, 6 497) | 1 | (225, 6 497) | 1 | (29, 323, 323) | (224, 4 096)
(2,9) | 1 | (33, 417) | 1 | (289, 10 657) | 1 | (289, 10 657) | 1 | (33, 417, 417) | (288, 6 561)
(3,2) | 3 | (88, 868) | 2 | (100, 1 108) | 2 | (100, 1 108) | 3 | (187, 1 979, 472) | (15, 64)
(3,3) | 2 | (97, 1 729) | 1 | (49, 505) | 2 | (961, 131 041) | 2 | (133, 1 808, 673) | (48, 729)
(3,4) | 2 | (208, 7 822) | 1 | (100, 2 098) | 1.25 | (576, 12 456) | 1.5 | (154, 6 643, 1567) | (99, 4 096)
(3,5) | 1 | (25, 265) | 1 | (169, 6 025) | 1 | (169, 6 025) | 1 | (25, 265, 265) | (168, 15 625)
(3,6) | 1 | (31, 406) | 1 | (256, 13 906) | 1 | (256, 13 906) | 1 | (31, 406, 406) | (255, 46 656)
(3,7) | 1 | (37, 577) | 1 | (361, 27 793) | 1 | (361, 27 793) | 1 | (37, 577, 577) | (360, 117 649)
(4,2) | 2 | (49, 505) | 1 | (25, 157) | 2 | (289, 13 105) | 2 | (65, 499, 233) | (24, 256))
(4,3) | 1 | (17, 129) | 1 | (81, 1 665) | 1.2 | (361, 7 993) | 1 | (17, 129, 129) | (80, 6 561)
(4,4) | 1 | (25, 277) | 1 | (169, 74 05) | 1 | (169, 7 405) | 1 | (25, 277, 277) | (168, 65 536)
(5,2) | 2 | (76, 1 276) | 1 | (36, 356) | 1.5 | (256, 9 106) | 2 | (101, 1 211, 461) | (35, 1 024)
(5,3) | 1 | (21, 201) | 1 | (121, 4 201) | 1 | (121, 4 201) | 1 | (21, 201, 201) | (120, 59 049)
(5,4) | 1 | (31, 436) | 1 | (256, 19 336) | 1 | (256, 19 336) | 1 | (31, 436, 436) | (255, 1 048 576)
(6,2) | 2 | (109, 2 719) | 1 | (49, 709) | 1 | (49, 709) | 2 | (145, 2 510, 805) | (48, 4 096)
(6,3) | 1 | (25, 289) | 1 | (169, 8 929) | 1 | (169, 8 929) | 1 | (25, 289, 289) | (168, 531 441)
Table 7:  Summary of the Bell scenarios considered in this work (leftmost
column), the highest level of the SDP relaxation considered (second, fourth,
sixth, and the eighth column), and the corresponding parameters characterizing
the complexity of the computation (third, fifth, seventh, and the ninth
column). In particular, for the NPA hierarchy (the second and third column),
the Moroder hierarchy for $\mathcal{Q}$ (the fourth and fifth column), the
Moroder hierarchy for $\mathcal{P}$ (the eighth and ninth column), we provide
in bracket the size of the respective moment matrix $D$ and the number of
(real) moment variables involved in the corresponding optimization. Similarly,
for the hierarchy of SDPs characterizing $\mathcal{M}^{\text{\tiny P}}$ (the
fifth and sixth column), we provide in bracket the size of the respective
moment matrix $D_{\mathcal{T}}$, the number of (real) moment variables
$N_{\mathcal{T}}$ involved in the corresponding optimization, and the number
of moments that are further required to be non-negative
$N_{\mathcal{M}^{\text{\tiny P}}_{h}}^{\geq 0}$. In the last column, we list,
accordingly, the key parameters characterizing the complexity of the linear
program involved in solving the membership problem
$\vec{P}\stackrel{{\scriptstyle?}}{{\in}}\mathcal{L}$, i.e., the size
$D_{\mathcal{L}}$ of $\vec{P}$, which equals to the dimension $d$ of
$\mathcal{NS}$ and the number of extreme points $N_{\text{\tiny
ext}}^{\mathcal{L}}$ of the respective local polytope $\mathcal{L}$. For
completeness, we also include in gray the parameters characterizing the
complexity of the various level-1 SDPs for the (2,8), (2,9), (3,5), (3,6),
(3,7) Bell scenarios that we did not compute.

Consequently, our characterization differs from that given in Ref. Lang  _et
al._ (2014) in two aspects: (1) our formulation assumes that $\tilde{E}_{a|x}$
and $\tilde{E}_{b|y}$ are projective while that of Ref. Lang  _et al._ (2014)
does not (2) the formulation given in Ref. Lang  _et al._ (2014) actually
imposes in property 3. above the more stringent requirement that $f$ can be
any linear combination of elements in $M_{k-1}$. Since one of these
differences is more constraining while the other is less constraining, our
hierarchy $\mathcal{M}^{\text{\tiny P}}_{k}$ is neither a subset nor a
superset of the corresponding set $\mathcal{Q}^{k}_{+}$ defined in Ref. Lang
_et al._ (2014). Empirically, we have also found that if we keep difference
(2) and drop the assumption of $\tilde{E}_{a|x}$, $\tilde{E}_{b|y}$ being
projective, then the resulting relaxation of $\mathcal{Q}^{k}_{+}$ appears to
be hardly constraining. Finally, notice that except for some additional
positivity requirement due to property 4 above, the SDP for
$\mathcal{M}^{\text{\tiny P}}_{1}$ is the same as that for NPA level 1.

##  Appendix B Sampling methods

To obtain uniformly sampled correlations in $\mathcal{NS}$ using the
$\mathsf{cprnd}$ function, we make use of the minimal parametrization given in
Eq. 5. For this purpose, it suffices to input to $\mathsf{cprnd}$ (1) the
total number of samples $N_{\text{\scriptsize tot}}$ required (2) the sampling
algorithm to be employed,222In our work, we use “Gibbs” sampler that gives,
empirically, better convergence properties than the default “hit-and-run”
sampler. and (3) a complete description of the nonsignaling polytope
$\mathcal{NS}$ in terms of its positivity (facet) constraints.

Explicitly, these positivity constraints are

$P(a|x)\geq 0,\quad P(b|y)\geq 0,\quad P(a,b|x,y)\geq 0,$ (15)

in addition to

$\displaystyle P(a=n_{o}|x)$
$\displaystyle=1-\sum_{a^{\prime}=1}^{n_{o}-1}P(a^{\prime}|x)\geq 0,$ (16)
$\displaystyle P(b=n_{o}|y)$
$\displaystyle=1-\sum_{b^{\prime}=1}^{n_{o}-1}P(b^{\prime}|y)\geq 0,$

and

$\displaystyle P(a,b=n_{o}|x,y)$
$\displaystyle=P(a|x)-\sum_{b^{\prime}=1}^{n_{o}-1}P(a,b^{\prime}|x,y)\geq 0,$
(17) $\displaystyle P(a=n_{o},b|x,y)$
$\displaystyle=P(b|y)-\sum_{a^{\prime}=1}^{n_{o}-1}P(a^{\prime},b|x,y)\geq 0,$
$\displaystyle P(a=n_{o},b=n_{o}|x,y)$
$\displaystyle=1-\sum_{a^{\prime}=1}^{n_{o}-1}P(a^{\prime}|x)-\sum_{b^{\prime}=1}^{n_{o}-1}P(b^{\prime}|y)$
$\displaystyle+\sum_{a^{\prime},b^{\prime}=1}^{n_{o}-1}P(a^{\prime},b^{\prime}|x,y)\geq
0$

for all $a,b\in\\{1,\ldots,n_{o}-1\\}$ and $x,y\in\\{1,2,\ldots,n_{s}\\}$.

##  Appendix C Bell scenarios considered and the complexity involved in the
characterization of various sets

We consider bipartite Bell scenarios where each party has $n_{s}$ measurement
settings and where each measurement gives $n_{o}$ outcomes. Bearing in mind
that the generating POVM elements may be chosen to be projectors, the size of
the Moroder Moroder  _et al._ (2013) level $\ell$ moment matrix, denoted by
$D_{\widetilde{\mathcal{Q}}_{\ell}}$, can be shown to be:

$D_{\widetilde{\mathcal{Q}}_{\ell}}=\left[1+\sum_{j=1}^{\ell}n_{s}(n_{s}-1)^{j-1}(n_{o}-1)^{j}\right]^{2}.$
(18)

Similarly, the size of the NPA level $k$ moment matrix, denoted by
$D_{\mathcal{Q}_{k}}$ can be shown to be:

$\begin{split}D_{\mathcal{Q}_{k}}&=1+2n_{s}\sum_{j=1}^{k}(n_{s}-1)^{j-1}(n_{o}-1)^{j}\\\
&+n_{s}^{2}\sum_{j=2}^{k}(j-1)(n_{s}-1)^{j-2}(n_{o}-1)^{j},\end{split}$ (19)

where the first sum consists of only contributions of $k$-fold products of
operators from the same party, the last sum consists of $k$-fold products of
operators originating from both parties, and the factor $(j-1)$ in the last
sum accounts for different possibilities in terms of the number of Alice’s and
Bob’s operators.

Finally, the size of the moment matrix corresponding to the characterization
of level $h$ of $\mathcal{M}^{\text{\tiny P}}$, denoted by
$D_{\mathcal{M}^{\text{\tiny P}}_{h}}$ is:

$\begin{split}D_{\mathcal{M}^{\text{\tiny
P}}_{h}}&=1+2n_{s}\sum_{j=1}^{h}(2n_{s}-1)^{j-1}(n_{o}-1)^{j}.\end{split}$
(20)

From the expressions given above, it is clear that for all these hierarchies,
the size of the SDP moment matrix increases exponentially with the level of
the hierarchy. As such, due to limitation in computational resources, it is
also expedient to consider intermediate, non-integer level of these
hierarchies in order to obtain a tighter approximation.

For both hierarchies of SDPs due to Moroder et al., let

$D_{\text{\scriptsize
local},\ell}=1+\sum_{j=1}^{\ell}n_{s}(n_{s}-1)^{j-1}(n_{o}-1)^{j}.$ (21)

Furthermore, let us denote by $\lfloor q\rfloor$ be the integer part of a
positive number $q\geq 1$. Then, we say that an outer approximation is of
level $q$ if the considered moment matrix $\Gamma_{q}$ contains
$\Gamma_{\lfloor q\rfloor}$ as a submatrix while $\Gamma_{q}$ itself is a
submatrix of $\Gamma_{\lfloor q\rfloor+1}$. Moreover, the moment matrix of
$\Gamma_{q}$ is formed by considering only (approximately) the first
$(q-\lfloor q\rfloor)(D_{\text{\scriptsize local},\lfloor
q\rfloor+1}-D_{\text{\scriptsize local},\lfloor q\rfloor})$ level-$(\lfloor
q\rfloor+1)$ local operators in addition to all the level-$\lfloor q\rfloor$
local operators.333Note that our level-$\ell$ local operators
$A_{a_{1}|x_{1}}A_{a_{2}|x_{2}}\cdots A_{a_{\ell}|x_{\ell}}$ are ordered by
first increasing the index of $a_{1}$, followed by $x_{1}$, followed by
$a_{2}$, etc.

In a similar manner, for the hierarchy defined in Appendix A, we say that an
outer approximation for $\mathcal{M}^{\text{\tiny P}}$ is of an intermediate
level $q$ if the considered moment matrix $\Gamma_{q}$ contains
$\Gamma_{\lfloor q\rfloor}$ as a submatrix while $\Gamma_{q}$ itself is a
submatrix of $\Gamma_{\lfloor q\rfloor+1}$. Moreover, the moment matrix of
$\Gamma_{q}$ is formed by taking the upper-left submatrix of $\Gamma_{\lfloor
q\rfloor+1}$ with (approximately) $D_{\mathcal{M}^{\text{\tiny P}}_{\lfloor
q\rfloor}}+(q-\lfloor q\rfloor)(D_{\mathcal{M}^{\text{\tiny P}}_{\lfloor
q\rfloor+1}}-D_{\mathcal{M}^{\text{\tiny P}}_{\lfloor q\rfloor}})$ rows and
columns.444Here, our level-$h$ operators $A_{a_{1}|x_{1}}\cdots
A_{a_{h-1}|x_{h-1}}A_{a_{h}|x_{h}}$ are ordered by first increasing the index
of $a_{h}$, followed by $x_{h}$, followed by $a_{h-1}$, etc. Moreover, we
adopt the convention that $A_{a_{i}|x_{i}}=B_{a_{i}|x_{i}-n_{s}}$ for
$x_{i}>n_{s}$ where $A_{a|x}\leftrightarrow\tilde{E}_{a|x}$,
$B_{b|y}\leftrightarrow\tilde{E}_{b|y}$, see Appendix A.

Figure 8:  Plots showing how the estimated relative volume
$\text{RV}(\mathcal{L})$ converges to the reported value as the number of
samples $N$ used in the estimation increases towards $N_{\text{\scriptsize
tot}}$. More precisely, in each subfigure, we plot
RV${}_{N}(\mathcal{L})-\text{RV}(\mathcal{L})$ as a function of $\log_{10}N$,
where RV${}_{N}(\mathcal{L})$ is the value of $\text{RV}(\mathcal{L})$
estimated using the first $N$ correlations $\vec{P}$ sampled uniformly from
$\mathcal{NS}$. As a reference, note that $\text{RV}(\mathcal{L})$ lies,
respectively, within $[93\%,\leavevmode\nobreak\ 100\%]$,
$[59\%,\leavevmode\nobreak\ 100\%]$, $[16\%,\leavevmode\nobreak\ 81\%]$,
$[1\%,\leavevmode\nobreak\ 7\%]$, and $[0.01\%,\leavevmode\nobreak\ 0.15\%]$
for $n_{s}=2,3,4,5,$ and $6$. For these two latter cases, an inset showing the
plots from $\log_{10}N\in[5,\leavevmode\nobreak\ 6]$ is included to show that
$\text{RV}(\mathcal{L})$ has converged to within $10\%$ of its value. As an
alternative way to see that our estimated RVs have converged well, one can
also employ, e.g., the Wilson score interval Wilson (1927) to verify that our
estimate fits well within the 99% confidence interval of the corresponding
estimate.

Of course, the size of the moment matrix $D_{\mathcal{T}}$ for a set
$\mathcal{T}$ is not only the parameter that determines the computational
resource required to solve each of these SDPs. In particular, for the
membership test corresponding to
$T\in\\{\mathcal{Q}_{k},\widetilde{\mathcal{Q}}_{\ell},\mathcal{M}^{\text{\tiny
P}}_{h},\mathcal{P}_{z}\\}$, the number $N_{\mathcal{T}}$ of real variables
(independent moments) involved in the corresponding moment matrix also plays a
crucial role. In the case of $\mathcal{M}^{\text{\tiny P}}_{h}$, the number
$N_{\mathcal{M}^{\text{\tiny P}}_{h}}^{\geq 0}$ of moments that are further
required to be non-negative also play a part in the complexity of the problem.
In Table 7, we provide a summary of the Bell scenarios considered in this work
as well as these key parameters relevant to solving the corresponding
optimization problems.

##  Appendix D Convergence analysis

In Fig. 8, we provide details showing how our estimates of the relative volume
converge as a function of $N_{\text{\scriptsize tot}}$, i.e., the number of
sampled correlations.

##  Appendix E Distance from $\vec{P}_{w}$ to extreme points of $\mathcal{NS}$

In the probability space $\mathscr{P}$ parametrized by all the full
conditional distributions $\\{P(a,b|x,y)\\}_{a,b,x,y}$, the Euclidean distance
between two correlations $\vec{P}_{1}$ and $\vec{P}_{2}$ is given by:

$\mathfrak{D}_{\text{\tiny
E}}(\vec{P}_{1}|\vec{P}_{2})=\sqrt{\sum_{a,b,x,y}\left[P_{1}(a,b|x,y)-P_{2}(a,b|x,y)\right]^{2}}.$
(22)

In any Bell scenario, any Bell-local extreme point of $\mathcal{NS}$, which is
also an extreme point of $\mathcal{L}$, can be obtained from

$P_{\mathcal{L}}(a,b|x,y)=\delta_{a,1}\delta_{b,1}$ (23)

via a relabeling of measurement settings, outcomes, and/or parties. Since the
uniform distribution $P_{w}(a,b|x,y)=\frac{1}{n_{o}^{2}}$ is always invariant
under such a relabeling, we see that their Euclidean distance is invariant
under relabeling, and is easily shown to be $\mathfrak{D}_{\text{\tiny
E}}(\vec{P}_{\mathcal{L}}|\vec{P}_{w})=n_{s}\sqrt{1-\frac{1}{n_{o}^{2}}}$.

Similarly, in the $(2,n_{o})$ Bell scenarios, all nonlocal extreme points of
$\mathcal{NS}$ can be obtained from one of the followings Barrett  _et al._
(2005):

$P_{\mathcal{NS}}^{k}(a,b|x,y)=\frac{1}{k}\delta_{(b-a)\,\text{mod}\,k,\,xy},\quad
k\in{2,\dots,n_{o}}$ (24)

via a relabeling. It then follows from Eq. 22 that $\mathfrak{D}_{\text{\tiny
E}}(\vec{P}^{k}_{\mathcal{NS}}|\vec{P}_{w})=2\sqrt{\frac{1}{k}-\frac{1}{n_{o}^{2}}}$.
Comparing with $\mathfrak{D}_{\text{\tiny
E}}(\vec{P}_{\mathcal{L}}|\vec{P}_{w})$, we thus see that all nonlocal extreme
points in the $(2,n_{o})$ Bell scenario are actually nearer to
$\mathcal{P}_{w}$ than the local ones.