# Characterising and bounding the set of quantum behaviours in contextuality
scenarios

Anubhav Chaturvedi<EMAIL_ADDRESS>Institute of
Theoretical Physics and Astrophysics, National Quantum Information Centre,
Faculty of Mathematics, Physics and Informatics, University of Gdansk, 80-952
Gdansk, Poland  International Centre for Theory of Quantum Technologies,
University of Gdansk, 80-308, Gdansk, Poland  Máté Farkas  ICFO-Institut de
Ciencies Fotoniques, The Barcelona Institute of Science and Technology, 08860
Castelldefels, Spain  Victoria J Wright  International Centre for Theory of
Quantum Technologies, University of Gdansk, 80-308, Gdansk, Poland

###### Abstract

The predictions of quantum theory resist generalised noncontextual
explanations. In addition to the foundational relevance of this fact, the
peculiar extent to which quantum theory violates noncontextuality limits
available quantum advantage in communication and information processing. In
this work, we situate the set of contextual quantum behaviours in the
landscape of general contextual behaviours by considering prepare-and-measure
experiments. We formulate semi-definite programming relaxations for bounding
the set and significant subsets of quantum contextual behaviours. We
demonstrate the efficacy of these relaxations by obtaining tight upper bounds
on the quantum violation of several noncontextuality inequalities, and
identifying novel maximally contextual quantum strategies. Moreover, we
discover contextuality scenarios, and associated noncontextuality inequalities
that require for their violation individual quantum preparation and
measurement procedures to be mixed states, and unsharp measurements. To
further illustrate the versatility of these relaxations, we switch to a
tripartite setting, wherein we present the possibility of secure quantum key
distribution schemes powered by violation of noncontextuality inequalities.

††preprint: APS/123-QED

##  I Introduction

The Leibnizian methodological principle of “ontological identity of empirical
indiscernibles” [1] creates a bridge across the schism dividing the
“empiricist”, and “realist” viewpoints on physics [2]. Generalised
noncontextuality [3] embodies this principle, and serves to characterise
operational physical theories that allow for simultaneously realist and
Leibnizian explanations.

Although born of metaphysical considerations, noncontextuality has been shown
to be equivalent to a natural operational notion of classicality, namely,
simplex embeddability of convex general stochastic operational theories [4,
5]. It is then not surprising that the quantum _violation of noncontextuality_
111Quantum theory is said to violate noncontextuality as shorthand for
admitting no simultaneously Leibnizian and realist explanation. More
explicitly, it cannot be explained by a noncontextual ontological (hidden
variable) model [3]. can be seen to power quantum advantage in broad classes
of information processing, and cryptographically significant communication
tasks [6, 7, 8, 7, 9, 10, 11, 12, 13, 14].

There is, therefore, both foundational and technological motivation for
characterising the peculiar nature of contextual quantum behaviour and
quantifying its violation of _noncontextuality inequalities_. In analogy with
quantum non-locality [15], quantum theory surpasses these noncontextual
limitations, but not necessarily to the maximum mathematically possible extent
[16]. Bounding this violation provides foundational insights, such as,
establishing how distinct operationally indistinguishable entities must be in
order to explain quantum predictions [17], and finds technological
applications in capping quantum advantage. Despite this motivation, the nature
of quantum contextuality in a general situations remains largely
uncharacterised until now.

In an effort to address this shortcoming, in the first part of this work, we
explore and elucidate the rich landscape of contextual behaviours by formally
defining contextuality scenarios via prepare-and-measure experiments (see Fig.
1 for a brief overview of our findings).

In the second part, we present hierarchies of semidefinite relaxations for
bounding the set of quantum contextual behaviours and some natural subsets
thereof. We benchmark these relaxations by recovering maximal quantum
violations (both known and novel), and identifying optimal quantum protocols
with respect to several noncontextuality inequalities in a diverse selection
of contextuality scenarios.

Furthermore, we reveal some hitherto unconfirmed features of quantum
contextuality, most significantly (i) the necessity of mixed quantum
preparation procedures, and unsharp measurements in obtaining certain extremal
quantum contextual behaviours, and (ii) the inability of quantum theory to
saturate a maximum contextual bound in contextuality scenarios which _cannot_
be mapped to Bell scenarios. Finally, to demonstrate the relevance of these
relaxations to real-world applications, we present a secure, _semi-device-
independent_ one-way quantum key distribution scheme based on preparation
contextuality.

Figure 1:  The landscape of contextual behaviour:  The graphic illustrates the
relationships between set of behaviours achievable in different theories in a
generic contextuality scenario. In direct analogy with the polytopes of no-
signalling and local-causal correlations in Bell experiments, the set of all
valid contextual behaviours, $\mathcal{C}$, and the set of noncontextual
behaviours, $\mathcal{NC}$, form polytopes. Accordingly, the set of quantum
behaviours, $\mathcal{Q}$, although convex does not form a polytope and
satisfies $\mathcal{NC}\subsetneq\mathcal{Q}\subsetneq\mathcal{C}$, in
general. We find contextuality scenarios in which the subsets of behaviours
obtained from pure quantum states $\mathcal{Q}^{\Psi}$ (possibly convex), and
projective measurements $\mathcal{Q}^{\Pi}$ (convex) form strict subsets of
the set of quantum contextual behaviours (see Props. 6 and 7), thereby
demonstrating that in such scenarios mixed quantum states, and unsharp
measurements can access greater contextuality.

##  II Contextuality scenarios

###  II.1 Prepare-and-measure experiments

In this work, we consider experiments consisting of a set of $X$ preparation
procedures, $\\{P_{x}\\}^{X-1}_{x=0}$, and a set of $Y$ measurement
procedures, $\\{M_{y}\\}^{Y-1}_{y=0}$. Each measurement is described by $K$
measurement effects, $\\{[k|M_{y}]\\}_{k=0}^{K-1}$, corresponding to $K$
possible outcomes. The experiment yields the observed statistics (or
behaviour), $p(k|x,y)\equiv p(k|P_{x},M_{y})$, i.e., the probability of
observing the outcome $k$, given the measurement $M_{y}$ was performed on the
preparation $P_{x}$. We may write the statistics as a vector
$\mathbf{p}\in\mathbb{R}^{XYK}$.

One may view prepare and measure experiments as one-way communication tasks,
wherein the sender (Alice) encodes her input $x\in[X]$ (where $[X]$ denotes
the set $\\{0,\ldots,X-1\\}$) onto the preparations $\\{P_{x}\\}_{x}$, and
transmits them to a spatially separated receiver (Bob). Bob decodes the
message by performing a measurement $M_{y}$, and obtains an outcome $k\in[K]$.
The performance of different operational theories in such tasks can be
measured by linear functionals on the behaviour, called success metrics. These
are of the form
$S(\mathbf{p})=\mathbf{c}\cdot\mathbf{p}=\sum_{x,y,k}c_{x,y,k}p(k|x,y)$, where
$\mathbf{c}\in\mathbb{R}^{XYK}$ is a vector of real coefficients $c_{x,y,k}$.

###  II.2 Operational equivalences and contextuality scenarios

First, note that we assume the preparation and measurement procedures in our
experiment are modelled by some operational theory in which classical mixtures
of procedures are possible. Hence the preparations, measurements and effects
are members of convex sets, denoted $\mathcal{P}$, $\mathcal{M}$ and
$\mathcal{E}$, respectively.

Experimental tests of generalised contextuality require the imposition of
equivalences between these preparations and/or measurement effects. In the
operational theory, two preparations, $P_{1},P_{2}\in\mathcal{P}$, are said to
be operationally equivalent, $P_{1}\simeq P_{2}$, if they yield identical
statistics for all measurements and outcomes, i.e.,
$p(k|P_{1},M)=p(k|P_{2},M)$ for all effects $[k|M]\in\mathcal{E}$. Similarly,
two measurement effects, $[k_{1}|M_{1}],[k_{2}|M_{2}]\in\mathcal{E}$, are
operationally equivalent, $[k_{1}|M_{1}]\simeq[k_{2}|M_{2}]$, if all
preparations assign identical probability of occurrence to them, i.e.,
$p(k_{1}|P,M_{1})=p(k_{2}|P,M_{2})$ for all $P\in\mathcal{P}$.

We define a contextuality scenario as a prepare-and-measure experiment with
some operational equivalences imposed on the preparations and measurements. A
scenario is therefore identified by a tuple,
$T\equiv(X,Y,K,\mathcal{OE}_{P},\mathcal{OE}_{M})$ where $\mathcal{OE}_{P}$
and $\mathcal{OE}_{M}$ describe preparation and measurement equivalences,
respectively.

A single preparation equivalence in a contextuality scenario consists of two
distinct decompositions of a _hypothetical_ 222The hypothetical preparations
are part of the operational theory but do not explicitly feature in the
experiment. preparation $Q\in\mathcal{P}$ in terms of the preparations
$P_{x}$:

$Q\simeq\sum_{x\in[X]}\alpha_{1}(x)P_{x}\simeq\sum_{x\in[X]}\alpha_{2}(x)P_{x}\,,$
(1)

where $\alpha_{1},\alpha_{2}$ are distinct probability distributions on $[X]$.

In a given contextuality scenario, we take $V$ distinct hypothetical
preparations $\\{Q_{v}\\}_{v\in[V]}$ and require that $Q_{v}$ can be
decomposed into $V_{v}\geq 2$ distinct mixtures of the preparations
$\\{P_{x}\\}$ for each $v\in[V]$. Thus, we describe all the preparation
equivalences of the scenario by

$\begin{gathered}\forall v\in[V],\forall j\in[V_{v}]:\\\
Q_{v}\simeq\sum_{x\in[X]}\alpha^{v}_{j}(x)P_{x}\,,\end{gathered}$ (2)

where $\alpha^{v}_{j}$ is a probability distribution on $[X]$ for all
$v\in[V]$ and all $j\in[V_{v}]$. We then take $\mathcal{OE}_{P}$ to be the set
$\left\\{\left\\{\alpha^{v}_{j}\right\\}_{j\in[V_{v}]}\right\\}_{v\in[V]}$,
which uniquely defines the equivalences (2).

Likewise, the set

$\mathcal{OE}_{M}=\left\\{\left\\{\beta^{w}_{j}(y,k)\right\\}_{j\in[W_{w}]}\right\\}_{w\in[W]}$
(3)

determines the measurement equivalences

$\begin{gathered}\forall w\in[W],\forall j\in[W_{w}]:\\\
E_{w}\simeq\sum_{k\in[K],y\in[Y]}\beta^{w}_{j}(k,y)[k|M_{y}]\,,\end{gathered}$
(4)

where $\\{E_{w}\\}_{w\in[W]}$ is a set of $W$ hypothetical effects in
$\mathcal{E}$ and $W_{w}\geq 2$ for all $w\in W$.

We have formulated the equivalences as in Eqs. (2) and (4), as opposed to
pairwise, to enable easy distinction between scenarios which can be mapped to
Bell scenarios, and those which cannot. Specifically, only contextuality
scenarios in which $V=1$ and $W=0$ can be “isomorphic” to Bell scenarios [12].

###  II.3 Contextual polytope

The operational equivalences (2) and (4) yield the following constraints on
any behaviour $\mathbf{p}$:

$\displaystyle\forall y\in[Y],k\in[K],v\in[V],\forall j\in[V_{v}]:$
$\displaystyle q_{v}=\sum_{x}\alpha^{v}_{j}(x)p(k|x,y)$ (5)
$\displaystyle\forall x\in[X],w\in[W],\forall j\in[W_{w}]:$ $\displaystyle
e_{w}=\sum_{k,y}\beta^{w}_{j}(k,y)p(k|x,y)$ (6)

where $q_{v},e_{w}\in[0,1]$. The set of behaviours $\mathbf{p}$ that satisfy
these constraints is a convex polytope $\mathcal{C}\subset\mathbb{R}^{XYK}$,
called the contextual polytope (note that this set depends on the tuple $T$
specifying the contextuality scenario, but we will not reflect this in the
notation for simplicity). Since the constraints are linear, evaluating the
maximal value,
$S_{\mathcal{C}}=\max_{\mathbf{p}\in\mathcal{C}}\\{S(\mathbf{p})\\}$, of any
success metric $S$ on this set constitutes a linear program [18].

###  II.4 Noncontextual polytope and inequalities

A noncontextual ontological model for an operational theory consists of the
following elements. A measurable space, $\Lambda$, known as the _ontic state
space_. A probability measure $\mu_{P}$ on $\Lambda$ describing the _epistemic
state_ of the system for each preparation $P$, satisfying
$\mu_{P}=\mu_{P^{\prime}}$ if $P\simeq P^{\prime}$. A probability distribution
$\xi_{k|M}(\lambda)$ over $\Lambda$, known as a _response scheme_ , for each
effect $[k|M]$, satisfying $\xi_{k|M}=\xi_{k^{\prime}|M^{\prime}}$ if
$[k|M]\simeq[k^{\prime}|M^{\prime}]$.

The set of behaviours $\mathbf{p}$ that admit a noncontextual explanation,
i.e., for which
$p(k|x,y)=\int_{\Lambda}\xi_{k|M^{y}}(\lambda)d\mu_{P_{x}}(\lambda)$ for some
epistemic states and response schemes satisfying the equivalence conditions
(2) and (4), is also a convex polytope, $\mathcal{NC}\subset\mathbb{R}^{XYK}$,
called the noncontextual polytope [19]. Evaluating the maximal value of any
success metric over the noncontextual ontological realisations,
$S_{\mathcal{NC}}=\max_{\mathbf{p}\in\mathcal{NC}}\\{S(\mathbf{p})\\}$, also
constitutes a linear program [19]. In general,
$\mathcal{NC}\subsetneq\mathcal{C}$, which can be witnessed by some success
metric. The consequent inequalities of the form $S(\mathbf{p})\leq
S_{\mathcal{NC}}$ are typically called noncontextuality inequalities, and
their violation $S(\mathbf{p})>S_{\mathcal{NC}}$ implies that the observed
behaviour is contextual, i.e.,
$\mathbf{p}\in\mathcal{C}\setminus\mathcal{NC}$.

###  II.5 Quantum contextual set and subsets

In quantum theory, both preparations and measurement effects are elements of
the set of positive semidefinite operators $\mathcal{B}_{+}(\mathcal{H})$ on
some Hilbert space $\mathcal{H}$ that we assume to be finite dimensional.
Preparations are described by density operators,
$\\{\rho_{x}\in\mathcal{B}_{+}(\mathcal{H})\\}_{x}$ such that for all $x$,
$\tr(\rho_{x})=1$. Measurements are defined by measurement operators
$\\{\\{M^{y}_{k}\in\mathcal{B}_{+}(\mathcal{H})\\}_{k}\\}_{y}$, such that for
all $y$, $\sum_{k}M^{y}_{k}=\mathbb{I}$ is the identity on $\mathcal{H}$. The
operational equivalences (2) and (4) imply the following constraints on
quantum states and measurements:

$\displaystyle\forall v\in[V],\forall j\in[V_{v}]:$
$\displaystyle\sigma_{v}=\sum_{x}\alpha^{v}_{j}(x)\rho_{x}$ (7)
$\displaystyle\forall w\in[W],\forall j\in[W_{w}]:$ $\displaystyle
F_{w}=\sum_{k,y}\beta^{v}_{j}(k,y)M^{y}_{k},$ (8)

where $\sigma_{v}$ are hypothetical quantum states and $F_{w}$ are
hypothetical measurement operators. The set of behaviours with a quantum
realisation, i.e., those in which $p(k|x,y)=\tr(\rho_{x}M^{y}_{k})$ for some
quantum states and measurements satisfying the constraints (II.5) and (II.5),
form the _quantum contextual_ set $\mathcal{Q}$.

It is known that there exist contextuality scenarios in which
$\mathcal{Q}\subsetneq\mathcal{C}$, specifically those which can be mapped to
Bell scenarios [12] (where this statement is equivalent to quantum theory not
being maximally non-local). We demonstrate that this strict inclusion
continues to hold in more general scenarios, for example, see Table 1.

Apart from $\mathcal{Q}$ itself, we study two natural subsets of it: (i) the
set of behaviours realised by pure quantum states $\rho^{2}_{x}=\rho_{x}$,
denoted by $\mathcal{Q}^{\Psi}$, and (ii) the set of behaviours realised by
projective (sharp) measurements, i.e., those in which
$(M^{y}_{k})^{2}=M^{y}_{k}$, denoted by $\mathcal{Q}^{\Pi}$.

We present the following new observations regarding the set of quantum
behaviours in contextuality scenarios:

######  Proposition 1.

For all contextuality scenarios the set of quantum behaviours $\mathcal{Q}$ is
convex.

######  Proposition 2.

For all contextuality scenarios the subset of quantum behaviours
$\mathcal{Q}^{\Pi}$ is convex.

######  Proposition 3.

For all contextuality scenarios with only trivial equivalences of measurement
effects $T\equiv(X,Y,Z,\mathcal{OE}_{P},\emptyset)$, projective measurements
are sufficent to recover the quantum set, i.e.,
$\mathcal{Q}=\mathcal{Q}^{\Pi}$.

######  Proposition 4.

For all contextuality scenarios with only trivial equivalences of
preparations, $T=(X,Y,Z,\emptyset,\mathcal{OE}_{M})$, all behaviours are
noncontextual, i.e., $\mathcal{NC}=\mathcal{Q}=\mathcal{C}$.

######  Proposition 5.

For all contextuality scenarios with three or fewer preparation procedures,
$T=(X\leq 3,Y,Z,\mathcal{OE}_{P},\mathcal{OE}_{M})$, all behaviours are
noncontextual, i.e., $\mathcal{NC}=\mathcal{Q}=\mathcal{C}$.

######  Proposition 6.

In general, for contextuality scenarios with non-trivial equivalences of
measurement effects, projective measurements cannot produce all quantum
contextual behaviours, i.e., $\mathcal{Q}^{\Pi}\subsetneq\mathcal{Q}$.

######  Proposition 7.

In general, for contextuality scenarios with non-trivial equivalences of
preparations, pure states cannot produce all quantum contextual behaviours,
i.e., $\mathcal{Q}^{\Psi}\subsetneq\mathcal{Q}$.

The proofs have been deferred to appendix A for brevity. These observations
yield a rich landscape of contextual behaviour (see Fig. 1). Due to the fact
that the Hilbert space dimension of the quantum systems remains unbounded in
contextuality scenarios, evaluating the maximum value of a generic success
metric over all quantum realisations,
$S_{\mathcal{Q}}=\max_{\mathbf{p}\in\mathcal{Q}}\\{S(\mathbf{p})\\}$, is a
remarkably hard problem. However, internal maximisation techniques, such as
the see-saw semidefinite programming method, yield efficient dimension-
dependent lower bounds, $S_{\mathcal{Q}}\geq S_{\mathcal{Q}_{L}}$, for any
success metric $S$.

##  III Semidefinite programming relaxations of quantum contextual sets

In order to outer approximate the set $\mathcal{Q}$, i.e., provide upper
bounds on success metrics, we employ semidefinite relaxation techniques. A
crucial concept in these relaxation techniques is that of moment matrices. For
a given density operator $\rho$, and a set of linear operators $\mathcal{O}$
on $\mathcal{H}$, the _moment matrix hinged on $\rho$_, $\Gamma_{\rho}$, is a
matrix with elements indexed by the operators in $\mathcal{O}$, given by
$(\Gamma_{\rho})_{O,O^{\prime}}=\tr(\rho{O}^{\dagger}{O^{\prime}})$ for
$O,O^{\prime}\in\mathcal{O}$. Due to the positivity of $\rho$, any such moment
matrix is positive semidefinite333Any positive operator $\rho$ can be written
as its spectral decomposition
$\rho=\sum_{k}\lambda_{k}\outerproduct{\psi_{k}}{\psi_{k}}$, where
$\outerproduct{\psi_{k}}{\psi_{k}}$ is the rank-1 projector onto the vector
$\ket{\psi_{k}}\in\mathcal{H}$, and $\lambda_{k}\geq 0$ for all $k$. The
moment matrix hinged on $\outerproduct{\psi_{k}}{\psi_{k}}$, $\Gamma_{k}$, is
the Gram matrix of the vectors $\\{O\ket{\psi_{k}}\\}_{O\in\mathcal{O}}$, and
is therefore positive semidefinite. It follows that
$\Gamma_{\rho}=\sum_{k}\lambda_{k}\Gamma_{k}$ is positive semidefinite,
$\Gamma_{\rho}\geq 0$. Given a contextuality scenario, consider a set of $X$
moment matrices $\\{\Gamma_{x}\\}_{x}$, hinged on the density operators
$\\{\rho_{x}\\}_{x}$ that satisfy certain operational equivalences of the form
(II.5), each constructed from an identical list of linear operators,
$\mathcal{O}$. The moment matrices $\Gamma_{x}$ then necessarily satisfy

$\displaystyle\forall v\in[V],\forall j,\in[V_{v}]:$
$\displaystyle\Theta_{v}=\sum_{x}\alpha_{j}^{v}(x)\Gamma_{x},$ (9)

where $\\{\Theta_{j}\\}$ are hypothetical moment matrices hinged on the
hypothetical quantum states $\\{\sigma_{j}\\}$ from Eq. (II.5). Standard
semidefinite relaxations utilise operators $O$ that are monomials of the
measurement operators $M^{y}_{k}$ of various lengths (including the length-
zero monomial $\mathbb{I}$). Certain elements in the moment matrices will
therefore correspond to the outcome statistics,
$(\Gamma_{x})_{\mathbb{I},M^{y}_{k}}=p(k|x,y)$. It follows that for a given
behaviour $\mathbf{p}\in\mathcal{Q}$, there must exist moment matrices
$\Gamma_{x}$ indexed by monomials of $\\{M^{y}_{k}\\}_{y,k}$ that are positive
semidefinite. Moreover, this fact provides an efficiently computable means of
certifying that a behaviour $\mathbf{p}$ lies outside of $\mathcal{Q}$: it is
a semidefinite feasibility problem to decide whether a set of positive
semidefinite moment matrices $\Gamma_{x}$ exist such that they satisfy
$(\Gamma_{x})_{\mathbb{I},M^{y}_{k}}=p(k|x,y)$ for all $x,y$ and $k$, and
potential further linear constraints (such as the ones in Eq. (III)). If for a
given $\mathbf{p}$ such moment matrices do not exist, then it must hold that
$\mathbf{p}\notin\mathcal{Q}$, and there exist efficient algorithms to decide
these type of problems [18].

Furthermore, similar techniques can be used to upper bound the value of an
arbitrary success metric $S(\mathbf{p})=\mathbf{c}\cdot\mathbf{p}$ over the
behaviours $\mathbf{p}\in\mathcal{Q}$. In the case of operational equivalences
of preparations of the form in Eq. (II.5), the semidefinite program (SDP)

$\begin{split}\max_{\\{\Gamma_{x}\\}}~{}~{}&\left.\sum_{x,y,k}c_{x,y,k}(\Gamma_{x})_{\mathbb{I},M^{y}_{k}}\right.\\\
\text{s.t.}~{}~{}&\left.\Gamma_{x}\geq 0~{}~{}\forall x\right.\\\
&\left.\sum_{x}\alpha_{j}^{v}(x)\Gamma_{x}=\sum_{x}\alpha_{j^{\prime}}^{v}(x)\Gamma_{x}~{}~{}\forall
v\in[V],\forall j,j^{\prime}\in[V_{v}]\right.\end{split}$ (10)

indeed provides an upper bound on $S_{\mathcal{Q}}$. The idea of SDP
hierarchies is to define different levels of the hierarchy, where level $l$
uses moment matrices built from monomials of the set $\\{M^{y}_{k}\\}_{y,k}$
of length $l$ [20]. In the current work, for simplicity, we restrict to the
discussion of SDP relaxations involving monomials of length one.

Note that due to Proposition 6, in order to upper bound success metrics, one
cannot restrict to projective measurements (an assumption often used to
facilitate the implementation of SDP hierarchies in nonlocal scenarios [20]).
There exist methods to tackle such scenarios in SDP hierarchies, introducing
additional moment matrices hinged on the measurement operators $M^{y}_{k}$
(localisation) [18, 21, 22], however, the resultant hierarchy of relaxation is
difficult to implement, and is relatively inefficient.

One of the main difficulties that arises from non-projective measurement
operators is that one cannot fix the diagonal elements of the moment matrices,
$(\Gamma_{x})_{M^{y}_{k},M^{y}_{k}}=\tr[\rho_{x}(M^{y}_{k})^{2}]$ (which for
projective measurements would simply be equal to $p(k|x,y)$). The following
lemma lets us overcome this drawback:

######  Lemma 1.

Any operator $0\leq M\leq\mathbb{I}$ on a finite dimensional Hilbert space
$\mathcal{H}$ can be written as
$M=\frac{\mathbb{I}}{2}+\frac{U+U^{\dagger}}{4}$, where $U$ is a unitary
operator on $\mathcal{H}$.

For the proof, see the appendix A. This lemma allows for an alternative
formulation of moment matrices in terms of unitary matrices. Since every
measurement operator $M^{y}_{k}$ corresponds to some unitary operator
$U^{y}_{k}$, we consider moment matrices $\\{\Gamma_{x}\\}_{x}$ labelled by
the list of operators
$\mathcal{O}=\\{\mathbb{I},\\{U^{y}_{k},{U^{y}_{k}}^{\dagger}\\}^{Y-1,K-2}_{y=0,k=0}\\}$
(note that due to the relations $\sum_{k}M^{y}_{k}=\mathbb{I}$, we do not need
to specify the last operator $M^{y}_{K-1}$—or the corresponding unitary
$U^{y}_{K-1}$—of the measurements). This unitary parametrisation allows us to
fix the diagonal elements of these moment matrices, since now it holds that
$(\Gamma_{x})_{O,O}=1$ for all $x\in[X]$ and $O\in\mathcal{O}$.

The operational equivalences of the preparations still imply constraints of
the form (III) for these moment matrices. Furthermore, the constraints
resulting from the equivalence conditions of the measurement effects (II.5)
have the form

$\displaystyle\forall x\in[X],O\in\mathcal{O},w\in[W],\forall j\in[W_{w}]:$
$\displaystyle
q_{v}=\sum_{k,y}\beta^{v}_{j}(k,y)((\Gamma_{x})_{O,U^{y}_{k}}+(\Gamma_{x})_{O,{U^{y}_{k}}^{\dagger}}),$
$\displaystyle
n_{w}=\sum_{k,y}\beta^{v}_{j}(k,y)((\Gamma_{x})_{U^{y}_{k},O}+(\Gamma_{x})_{{U^{y}_{k}}^{\dagger},O})\,,$
(11)

where $q_{v},n_{w}\in\mathbb{C}$, and we define

$\begin{split}&\left.(\Gamma_{x})_{O,U^{y}_{K-1}}+(\Gamma_{x})_{O,{U^{y}_{K-1}}^{\dagger}}\right.\\\
=&\left.2(2-K)(\Gamma_{x})_{O,\mathbb{I}}-\sum^{K-2}_{k=0}\left((\Gamma_{x})_{O,U^{y}_{k}}+(\Gamma_{x})_{O,{U^{y}_{k}}^{\dagger}}\right)\right.\end{split}$
(12)

and

$\begin{split}&\left.(\Gamma_{x})_{U^{y}_{K-1},O}+(\Gamma_{x})_{{U^{y}_{K-1}}^{\dagger},O}\right.\\\
=&\left.2(2-K)(\Gamma_{x})_{\mathbb{I},O}-\sum^{K-2}_{k=0}\left((\Gamma_{x})_{U^{y}_{k},O}+(\Gamma_{x})_{{U^{y}_{k}}^{\dagger},O}\right)\right.\end{split}$
(13)

for all $O\in\mathcal{O}$ and $x\in[X]$.

In a given contextuality scenario, the set of behaviours $\mathbf{p}$ for
which one can find a set of moment matrices $\\{\Gamma_{x}\\}_{x}\geq 0$ such
that

$\frac{1}{2}+\frac{1}{4}\big{[}(\Gamma_{x})_{\mathbb{I},U^{y}_{k}}+(\Gamma_{x})_{\mathbb{I},{U^{y}_{k}}^{\dagger}}\big{]}=p(k|x,y)~{}~{}\forall
x,y,k,$ (14)

satisfying all the above constraints, is called $\mathcal{Q}_{1}$ (referring
to the first level of the hierarchy), and it is clear that
$\mathcal{Q}\subseteq\mathcal{Q}_{1}$. To demonstrate the ease of
implementation and high efficiency of this unitary-based relaxation, we
provide a code tutorial in appendix B.

For bounding the set $Q^{\Pi}$, we resort to the standard formulation of the
SDP relaxations and consider the list of operators
$\mathcal{O}=\\{\mathbb{I},\\{\Pi^{k}_{y}\\}^{Y-1,K-2}_{y=0,k=0}\\}$, where
$\Pi^{y}_{k}$ are projectors. From this, apart from the trivial constraint
$(\Gamma_{x})_{\mathbb{I},\mathbb{I}}=1$ for all $x$, we obtain
$(\Gamma_{x})_{\Pi^{y}_{k},\Pi^{y}_{l}}=\delta_{kl}(\Gamma_{x})_{\mathbb{I},\Pi^{y}_{k}}$
for all $x$, $y$, $k$ and $l$. Taking into consideration the constraints
emerging from operational equivalences, for all contextuality scenarios
(similarly to $\mathcal{Q}_{1}$) one can define the set
$\mathcal{Q}_{1}^{\Pi}$ containing $\mathcal{Q}^{\Pi}$.

##  IV Applications

###  IV.1 Tight bounds on the quantum set

The primary application of the SDP hierarchy is finding numerical proofs for
the maximal quantum value $S_{Q}$ of any success metric $S$. This is possible
when the value $S_{\mathcal{Q}_{L}}$, obtained from internal maximisation
techniques [9, 22], matches that of the upper bound obtained from the $l$-th
level of the hierarchy, i.e., $S_{\mathcal{Q}_{L}}=S_{\mathcal{Q}_{l}}$ (up to
machine precision).

As a first example, we apply the hierarchy to the simplest non-trivial single
parameter family of contextuality scenarios [23],
$(4,2,2,\mathcal{OE}_{P}(\alpha),\emptyset)$. Let the preparation setting $x$
be composed of two bits $x=(x_{0},x_{1})\in\\{0,1\\}^{2}$. We consider a
family of operational equivalence conditions of the form
$\frac{1}{2}P_{00}+\frac{1}{2}P_{11}\simeq\alpha P_{01}+(1-\alpha)P_{10}$,
characterised by the coefficient $\alpha\in[0,1]$. Now consider the success
metric $S(\mathbf{p})=\frac{1}{8}\sum_{x_{0},x_{1},y}p(x_{y}|x_{0},x_{1},y)$.
While the first level of the SDP relaxation $\mathcal{Q}^{\Pi}_{1}$ of the set
retrieves non-trivial upper bounds
$S_{\mathcal{Q}^{\Pi}_{1}}<S_{\mathcal{C}}$, the bounds obtained from the
second level of the relaxation $\mathcal{Q}^{\Pi}_{2}$ saturate those obtained
by internal maximisation, thus we find
$S_{Q}=S_{\mathcal{Q}_{L}}=S_{\mathcal{Q}^{\Pi}_{2}}$.

Figure 2:  The maximal of the success probability of $(2,2)$-porac task for
the simplest contextuality scenario
$(4,2,2,\mathcal{OE}_{P}(\alpha),\emptyset)$ with operational equivalence
conditions of the form $\frac{1}{2}P_{00}+\frac{1}{2}P_{11}\simeq\alpha
P_{01}+(1-\alpha)P_{10}$ characterised by the convex coefficient
$\alpha\in[0,1]$. Notice the range of $\alpha$ for which
$S_{\mathcal{Q}}>S_{\mathcal{NC}}$, $S_{\mathcal{Q}}>S_{\mathcal{Q}}^{\Psi}$,
this constitutes a proof of Proposition 7.

Moreover, for this case we employ a SDP relaxation $\mathcal{Q}^{\Psi}_{1}$,
based directly on the NPA hierarchy [20] to bound the set
$\mathcal{Q}^{\Psi}$. Remarkably, for a range of the scenario parameter
$\alpha$, we find that pure states aren’t enough to violate the noncontextual
bound, i.e., $S_{\mathcal{Q}^{\Psi}}\leq
S_{\mathcal{Q}^{\Psi}_{1}}<S_{\mathcal{NC}}<S_{\mathcal{Q}_{L}}$, which
constitutes a numerical proof of Proposition 7 (see Fig. 2).

Next, we consider a cryptographically appealing family of preparation
noncontextuality inequalities, referred to as $(n,2)$-parity oblivious random
access codes (porac) introduced in [7], where
$S_{\mathcal{NC}}=\frac{1}{2}(1+\frac{1}{n})$. The first levels of both
relaxations, $\mathcal{Q}^{\Pi}_{1}$ and $\mathcal{Q}_{1}$, saturate the known
optimal quantum bounds for $n\in\\{2,\ldots,7\\}$, i.e.,
$S_{\mathcal{Q}}=S_{\mathcal{Q}^{\Pi}_{1}}=S_{\mathcal{Q}_{1}}=\frac{1}{2}(1+\frac{1}{\sqrt{n}})$
[8, 14].

Moving to tests of universal contextuality, we consider the scenario
$T=(6,3,2,\mathcal{U}_{P},\mathcal{U}_{M})$ defined by the operational
equivalences
$\frac{1}{2}(P_{0}+P_{1})\simeq\frac{1}{2}(P_{2}+P_{3})\simeq\frac{1}{2}(P_{4}+P_{5})$,
and
$\frac{1}{3}([0|M_{0}]+[0|M_{1}]+[0|M_{2}])\simeq\frac{1}{3}([1|M_{0}]+[1|M_{1}]+[1|M_{2}])$.
Here the noncontextual polytope has six distinct non-trivial facets up to
relabelling symmetries [19], each corresponding to a distinct noncontextuality
inequality (Table 1). While the optimal violation of the first inequality has
been established experimentally [6], the general relaxation yields tight
bounds on maximum quantum violation for all other facet inequalities.
Moreover, we retrieve optimal states and measurements that saturate these
bounds in Table 1 (see Fig. 6).

$S(\mathbf{p})$ | $S_{\mathcal{C}}$ | $S_{\mathcal{NC}}$ | $S_{\mathcal{Q}_{L}}$ | $S_{\mathcal{Q}_{1}}$
---|---|---|---|---
$p_{00}+p_{12}+p_{24}$ | $3$ | $2.5$ | $3$ | $3$
$p_{00}+p_{11}+p_{24}$ | $3$ | $2.5$ | $2.8660254$ | $2.8660254$
$p_{00}-p_{02}-2p_{02}-2p_{11}+2p_{12}+2p_{24}$ | $4.5$ | $3$ | $3.9209518$ | $3.9209518$
$2p_{00}-p_{11}+2p_{12}$ | $3.5$ | $3$ | $3.3660254$ | $3.3660254$
$p_{00}-p_{04}+p_{11}+p_{12}+2p_{24}$ | $5$ | $4$ | $4.6889010$ | $4.6889010$
$p_{00}-p_{04}+2p_{11}+2p_{24}$ | $5$ | $4$ | $4.6457513$ | $4.6457513$

Table 1:  Optimal values for $\mathcal{C}$, $\mathcal{NC}$, and $\mathcal{Q}$
for all facet inequalities [12] in the universal contextuality scenario
$T=(6,3,2,\mathcal{U}_{P},\mathcal{U}_{M})$, where $p_{yx}=p(0|x,y)$. The
values $S_{\mathcal{Q}_{L}}$ and $S_{\mathcal{Q}_{1}}$ are equal in each case,
up to machine precision, providing a numerical proof of the optimal quantum
value, $S_{\mathcal{Q}}$.

Next, we considered universal noncontextuality inequalities obtained from
$n$-cycle Kochen–Specker graphs [19, 24, 25]. In this case also, the
relaxation retrieves tight quantum bounds
$S_{\mathcal{Q}}=3+\frac{n\cos{\frac{\pi}{n}}}{1+\cos{\frac{\pi}{n}}}$ for
$n\in\\{5,7,9,11\\}$ (see Table 2).

$n$ | $S_{\mathcal{C}}$ | $S_{\mathcal{NC}}$ | $S_{\mathcal{Q}_{L}}$ | $S_{\mathcal{Q}_{1}}$
---|---|---|---|---
$5$ | $3$ | $5$ | $5.2360679$ | $5.2360679$
$7$ | $3$ | $6$ | $6.3176672$ | $6.3176672$
$9$ | $4.5$ | $7$ | $7.3600895$ | $7.3600895$
$11$ | $3.5$ | $8$ | $7.3600895$ | $7.3600895$
Table 2:  Optimal quantum value for generalised noncontextuality inequalities
based on $n$-cycle KS graphs.

Finally, we considered a class of novel universal noncontextuality
inequalities based on $(n,2)$-poracs. In addition to the preparation
equivalence conditions that ensue from the parity oblivious conditions, we
introduce measurement equivalences parameterised by $n$, taking the form
$\frac{1}{n}\sum^{n-1}_{i=0}[0|M^{i}]\simeq\frac{1}{n}\sum^{n-1}_{i=0}[1|M^{i}].$
It is fairly easy to see that the noncontextual bounds on the success metric
associated with $(n,2)$-porac remains unaltered (see Lemma 2). However, the
quantum bound is further restricted. Yet again, the first level of the general
SDP relaxation $\mathcal{Q}_{1}$ yields optimal quantum bounds for
$n\in\\{2,\ldots,7\\}$ (see Table 3).

$n$ | $S_{\mathcal{C}}$ | $S_{\mathcal{NC}}$ | $S_{\mathcal{Q}_{L}}$ | $S_{\mathcal{Q}_{1}}$
---|---|---|---|---
$2$ | $3/4$ | $3/4$ | $0.75$ | $0.75$
$3$ | $3/4$ | $2/3$ | $0.75$ | $0.75$
$4$ | $3/4$ | $5/8$ | $0.7165063$ | $0.7165063$
$5$ | $3/4$ | $3/5$ | $0.7041241$ | $0.7041241$
$6$ | $3/4$ | $7/12$ | $0.6863389$ | $0.6863389$
$7$ | $3/4$ | $4/7$ | $0.6767766$ | $0.6767766$
Table 3:  Optimal contextual $S_{\mathcal{C}}$, noncontextual
$S_{\mathcal{NC}}$, and quantum $S_{\mathcal{Q}}$ values for the
$(n,2)$-mporac task.

###  IV.2 Monogamy of preparation contextuality

A new feature that we find using the SDP hierarchy is that of monogamy of
preparation contextuality. Consider a prepare-and-measure scenario with two
measuring parties, Bob and Charlie, whose actions are space-like separated.
The preparation party, Alice, shares a preparation according to her setting
$x$ between Bob and Charlie. The observed statistics in such a case is
described by $p_{BC}(k_{B},k_{C}|x,y_{B},y_{C})$, where $y_{B}$ ($y_{C}$) and
$k_{B}$ ($k_{C}$) are the measurement settings and outcomes of Bob (Charlie),
respectively. Apart from the operational equivalences of preparations and
measurements, space-like separation implies no-signalling between Bob and
Charlie [15], that is,

$\begin{split}&\left.p_{B}(k_{B}|x,y_{B},y_{C})=p_{B}(k_{B}|x,y_{B},y^{\prime}_{C})~{}~{}\forall
k_{B},x,y_{B},y_{C},y^{\prime}_{C}\right.\\\
&\left.p_{C}(k_{C}|x,y_{B},y_{C})=p_{C}(k_{C}|x,y^{\prime}_{B},y_{C})~{}~{}\forall
k_{C},x,y_{B},y^{\prime}_{B},y_{C},\right.\end{split}$ (15)

where $p_{B}$ and $p_{C}$ are the marginal distributions of Bob and Charlie,
respectively.

We consider this tripartite version of the ($n$,$2$)-porac game: here, Alice’s
input is three bits, $x=x_{0}x_{1}x_{2}$, and she is not allowed to send any
information about the parity of any pair of her bits, as well as about
$x_{0}\oplus x_{1}\oplus x_{2}$, which is reflected in operational
equivalences of her preparations. Specifically, assuming uniform distribution
of $x$, this parity obliviousness implies

$\frac{1}{2}(P_{00x_{2}}+P_{11x_{2}})=\frac{1}{2}(P_{01x_{2}}+P_{10x_{2}})~{}~{}\forall
x_{2},$ (16)

and similarly for the other pairs of bits. Also, no information about
$x_{0}\oplus x_{1}\oplus x_{2}$ implies

$\frac{1}{4}(P_{000}+P_{011}+P_{101}+P_{110})=\frac{1}{4}(P_{001}+P_{010}+P_{100}+P_{111}).$
(17)

The two measuring parties, Bob and Charlie, are both aiming to maximise their
average success probability $S_{B}$ and $S_{C}$, respectively, expressed by

$S_{Z}=\frac{1}{16}\sum_{x,y_{Z}}p_{Z}(x_{y_{Z}}|x,y_{Z}),$ (18)

where $Z$ denotes either $B$ or $C$, and $p_{Z}$ is the respective marginal
probability distribution. We find that, say, Charlie’s success probability is
bounded by that of Bob’s, i.e., their success probabilities satisfy certain
monogamy relations. For any behaviour in $\mathcal{C}$ also satisfying no-
signalling, we obtain the relations $S_{B}+S_{C}\leq_{\text{NS}}\frac{3}{2}$
for the $(3,2)$-porac (see Fig. 3).

Quantum behaviours in this setup, $\mathbf{p}\in\mathcal{Q}$, are described by
$p_{BC}(k_{B},k_{C}|x,y_{B},y_{C})=\tr[\rho_{x}(M^{y_{B}}_{k_{B}}\otimes
N^{y_{C}}_{k_{C}})]$, where $\\{M^{y_{B}}_{k_{B}}\\}$ and
$\\{N^{y_{C}}_{k_{C}}\\}$ are the measurement operators of Bob and Charlie,
respectively, and one might assume without loss of generality that they are
projectors, in light of Proposition 3. In order to obtain monogamy relations
in the quantum case, we employ our semidefinite relaxation techniques to bound
$\mathcal{Q}^{\Pi}$, and implement the level $\mathcal{Q}_{1+BC}$, built from
monomials of projectors of Bob, Charlie, and products of Bob’s and Charlie’s
projectors, $M^{y_{B}}_{k_{B}}N^{y_{C}}_{k_{C}}$ (but not employing monomials
corresponding to products of different operators of Bob or Charlie only, e.g.
$M^{y_{B}}_{k_{B}}M^{y^{\prime}_{B}}_{k^{\prime}_{B}}$). This gives us the
monogamy relation $S_{B}+S_{C}\leq_{\mathcal{Q}^{\Pi}_{1+BC}}1.392$. For
further details on the form of these monogamy relations, see Fig. 3, where we
plot the maximum attainable $S_{C}$ given a fixed $S_{B}$, at the level
$\mathcal{Q}_{1+BC}$.

Figure 3: Monogamy relations expressed as bounds on the success probability
$S_{C}$ of Charlie, given the success probability $S_{B}$ of Bob. For
contextual behaviours $\mathbf{p}\in\mathcal{C}$, the upper and lower bounds
agree (as computing the value is a simple linear program), and give the black
line on the figure. For the quantum set $\mathcal{Q}$, we obtain upper bounds
from the $\mathcal{Q}_{1+BC}$ level of the SDP hierarchy, and lower bounds
from see-saw optimisation ($\mathcal{Q}_{L}$).

###  IV.3 Semi-device-independent quantum key distribution

The above monogamy relations imply the potential application of preparation
contextuality to quantum key distribution. In particular, we might replace the
trusted party Charlie with a malicious eavesdropper Eve, who is trying to read
certain messages $x$ encoded into the preparations of Alice, $\rho_{x}$,
intended to Bob. In a particularly paranoid scenario, we might assume that Eve
is responsible for the manufacturing of the devices of Alice and Bob, and
therefore she has perfect knowledge of the states $\rho_{x}$ that Alice is
able to prepare, as well as of the measurements $M^{y}_{b}$ that Bob is able
to perform. However, we assume that the devices behave in the same way every
round (i.i.d. assumption [26]), and that while running the porac protocol,
Alice and Bob have free will and can choose their settings $x$ and $y$
independently of Eve (free will assumption [27]).

The protocol for extracting a secure key between Alice and Bob is as follows:
they play many rounds of the (3,2)-porac game, in each round uniformly
randomly choosing their settings $x$ and $y$. After accumulating statistics
from many rounds, Bob announces his input setting $y$ for each round via a
classical public channel (that can be read but not modified by Eve). After
learning these values, Alice only keeps her bit $a=x_{y}$ and discards the
other two. At the same time, Eve measures her part of the quantum state
(individually in each round, assuming no quantum memory of Eve [26]), and
produces a classical output $e$. The resulting tripartite correlation is of
the form $p_{ABE|XY}(a,b,e|x,y)=\delta_{a,x_{y}}\tr[\rho_{x}(M^{y}_{b}\otimes
E_{e})]$. Averaging over all the setting choices, the parties end up with the
tripartite probability distribution

$p_{ABE}(a,b,e)=\sum_{xy}p_{XY}(x,y)p_{ABE|XY}(a,b,e|x,y),$ (19)

and we will assume the uniform distribution $p_{XY}(x,y)=\frac{1}{16}$ for all
$x$, $y$.

According to the seminal result by Csiszár and Körner [28], a lower bound on
the extractable key between Alice and Bob from the above distribution is

$r\geq I(A:B)-I(A:E)=H(E|A)-H(B|A),$ (20)

where $I(A:B)$ is the mutual information of $A$ and $B$, $H(B|A)$ is the
conditional Shannon entropy, and these quantities are computed from the
bipartite marginal distributions. Note that $H(E|A)\geq
H_{\text{min}}(E|A)=-\log S_{E}$, where $S_{E}$ is the guessing probability of
Eve. In order to bound $H(B|A)$, we assume that independently of the settings
$x$ and $y$, Bob’s output is $b=x_{y}$ with probability $S_{B}$ and $b\neq
x_{y}$ with probability $1-S_{B}$ (this holds in the case of the optimal
quantum success probability, or assuming a noisy scenario with uniform noise,
e.g. employing the noisy states
$\tilde{\rho}_{x}=\eta\rho_{x}+(1-\eta)\frac{\mathbb{I}}{d}$, where $\rho_{x}$
are the optimal states and $d$ is the dimension). Under these assumptions,
$H(B|A)=-h(S_{B})$, where $h$ is the binary entropy, and we obtain a bound on
the key rate in terms of the success probabilities of Eve and Bob:

$r\geq-\log S_{E}-h(S_{B}).$ (21)

Note that for success probabilities greater than $\frac{1}{2}$ (the trivial
lower bound), both $-\log S_{E}$ and $h(S_{B})$ are monotonically decreasing
functions of the success probabilities. Therefore, in order to obtain a lower
bound on the key rate in terms of Bob’s success probability $S_{B}$, it is
enough to upper bound $S_{E}$ in terms of $S_{B}$, which can be done using our
semidefinite relaxation techniques, analogously to the monogamy relations
obtained in section IV.2. We applied our techniques on the level $Q_{1+BE}$,
and found that for a nontrivial region of $S_{B}$ below the optimal success
probability, it is possible to extract a secure key from the observed
behaviour (see Fig. 4). Therefore, we have demonstrated that preparation
contextuality leads to secure semi-device-independent quantum cryptographic
protocols. We note that in Ref. [29] the authors study quantum key
distribution based on the monogamy of the Klyachko–Can–Binicioglu–Shumovsky-
type contextuality, and in Ref. [30] the authors propose a quantum key
distribution protocol based on generalised measurement contextuality. However,
up to our knowledge, our proposed protocol is the first demonstration of the
potential of preparation contextuality for semi-device-independent quantum key
distribution.

Figure 4: Lower bound on the key rate as a function of Bob’s success
probability in a (3,2)-porac-based key distribution scenario, computed at the
level $\mathcal{Q}_{1+BE}$ of the SDP hierarchy. We see that for success
probabilities $S_{B}$ close to the optimal one, Alice and Bob are able to
extract a secure key.

##  V Summary

In this work, we study the behaviours emerging from operational theories in
contextuality scenarios defined by operational equivalences of preparations
and measurements. We give a rigorous definition of contextuality scenarios,
and establish generic features of the relations of the behaviour sets that
arise from different operational theories, with a specific emphasis on the
quantum set, $\mathcal{Q}$, and its natural subsets, $\mathcal{Q}^{\Pi}$ and
$\mathcal{Q}^{\Psi}$.

For these quantum sets, we also develop semidefinite programming hierarchies
that outer approximate the set of quantum correlations by upper bounding
linear functionals defined on them. Using a novel unitary parametrisation, we
are able to efficiently tackle the cases where projective measurements are not
sufficient for optimal performance. Thus our relaxations allow us to upper
bound the quantum set in all generalised contextuality scenarios, with
arbitrary preparation and measurement equivalences. We find that our hierarchy
provides tight bounds already at low levels. This methodolgy also allows us to
bound functionals that are relevant for applications, specifically, to derive
monogamy relations for preparation contextuality, and lower bound secure key
rates for semi-device-independent quantum key distribution.

## Note added

See the related work by Tavakoli et. al appearing on the arxiv the same day as
this manuscript.

##  VI Acknowledgements

The authors thank Piotr Mironowicz for the first co-implementation of the
relaxation, and Miguel Navascués for the idea in Lemma 1. We thank Debashis
Saha, Nikolai Miklin, Ana Belén Sainz and John H. Selby for fruitful
discussions. AC acknowledges financial support by FNP grants First
TEAM/2016-1/5,and NCN grant SHENG 2018/30/Q/ST2/00625. VJW acknowledges
support from the Foundation for Polish Science (IRAP project, ICTQT, contract
no. 2018/MAB/5, co-financed by EU within Smart Growth Operational Programme).
MF acknowledges funding from the Government of Spain (FIS2020-TRANQI and
Severo Ochoa CEX2019-000910-S), Fundació Cellex, Fundació Mir-Puig,
Generalitat de Catalunya (CERCA, AGAUR SGR 1381) and the ERC AdG CERQUTE. The
numerical optimization was carried out using Ncpol2sdpa [21], YALMIP [31] and
SDPT3 [32]. AC acknowledges Tool for creative support.

## References

  * Clarke  _et al._ [1956] S. Clarke, G. W. von Leibniz, I. Newton, and H. G. Alexander,  _The Leibniz-Clarke Correspondence: Together With Extracts from Newton’s Principia and Opticks_ (Manchester University Press, 1956).
  * Spekkens [2019] R. W. Spekkens, The ontological identity of empirical indiscernibles: Leibniz’s methodological principle and its significance in the work of Einstein, arXiv:1909.04628 (2019).
  * Spekkens [2005] R. W. Spekkens, Contextuality for preparations, transformations, and unsharp measurements, Phys. Rev. A 71, 052108 (2005).
  * Schmid  _et al._ [2019] D. Schmid, J. Selby, E. Wolfe, R. Kunjwal, and R. W. Spekkens, The characterization of noncontextuality in the framework of generalized probabilistic theories, arXiv:1911.10386 (2019).
  * Schmid  _et al._ [2020] D. Schmid, J. H. Selby, M. F. Pusey, and R. W. Spekkens, A structure theorem for generalized-noncontextual ontological models, arXiv:2005.07161 (2020).
  * Mazurek  _et al._ [2016] M. D. Mazurek, M. F. Pusey, R. Kunjwal, K. J. Resch, and R. W. Spekkens, An experimental test of noncontextuality without unphysical idealizations, Nat. Commun. 7, 11780 (2016).
  * Spekkens  _et al._ [2009] R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner, and G. J. Pryde, Preparation contextuality powers parity-oblivious multiplexing, Phys. Rev. Lett. 102, 010401 (2009).
  * Chailloux  _et al._ [2016] A. Chailloux, I. Kerenidis, S. Kundu, and J. Sikora, Optimal bounds for parity-oblivious random access codes, New J. Phys. 18, 045003 (2016).
  * Ambainis  _et al._ [2019] A. Ambainis, M. Banik, A. Chaturvedi, D. Kravchenko, and A. Rai, Parity oblivious d-level random access codes and class of noncontextuality inequalities, Quantum Inf. Process. 18, 111 (2019).
  * Saha and Chaturvedi [2019] D. Saha and A. Chaturvedi, Preparation contextuality as an essential feature underlying quantum communication advantage, Phys. Rev. A 100, 022108 (2019).
  * Saha  _et al._ [2019] D. Saha, P. Horodecki, and M. Pawłowski, State independent contextuality advances one-way communication, New J. Phys. 21, 093057 (2019).
  * Schmid and Spekkens [2018] D. Schmid and R. W. Spekkens, Contextual advantage for state discrimination, Phys. Rev. X 8, 011015 (2018).
  * Emeriau  _et al._ [2020] P.-E. Emeriau, M. Howard, and S. Mansfield, Quantum advantage in information retrieval, arXiv:2007.15643 (2020).
  * Ghorai and Pan [2018] S. Ghorai and A. Pan, Optimal quantum preparation contextuality in an n-bit parity-oblivious multiplexing task, Phys. Rev. A 98, 032110 (2018).
  * Brunner  _et al._ [2014] N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner, Bell nonlocality, Rev. Mod. Phys. 86, 419 (2014).
  * Banik  _et al._ [2015] M. Banik, S. S. Bhattacharya, A. Mukherjee, A. Roy, A. Ambainis, and A. Rai, Limited preparation contextuality in quantum theory and its relation to the Cirel’son bound, Phys. Rev. A 92, 030103 (2015).
  * Chaturvedi and Saha [2019] A. Chaturvedi and D. Saha, Quantum prescriptions are more ontologically distinct than they are operationally distinguishable, arXiv:1909.07293 (2019).
  * Boyd and Vandenberghe [2004] S. Boyd and L. Vandenberghe,  _Convex Optimization_ (Cambridge University Press, 2004).
  * Xu  _et al._ [2016] Z.-P. Xu, D. Saha, H.-Y. Su, M. Pawłowski, and J.-L. Chen, Reformulating noncontextuality inequalities in an operational approach, Phys. Rev. A 94, 062103 (2016).
  * Navascués  _et al._ [2008] M. Navascués, S. Pironio, and A. Acín, A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations, New J. Phys. 10, 073013 (2008).
  * Wittek [2015] P. Wittek, Algorithm 950: Ncpol2sdpa—sparse semidefinite programming relaxations for polynomial optimization problems of noncommuting variables, ACM Trans. Math. Softw. 41, 1 (2015).
  * Mironowicz [2015] P. Mironowicz,  _Applications of semi-definite optimization in quantum information protocols_ , Ph.D. thesis, Gdansk University of Technology (2015).
  * Pusey [2018] M. F. Pusey, Robust preparation noncontextuality inequalities in the simplest scenario, Phys. Rev. A 98, 022112 (2018).
  * Liang  _et al._ [2011] Y.-C. Liang, R. W. Spekkens, and H. M. Wiseman, Specker’s parable of the overprotective seer: A road to contextuality, nonlocality and complementarity, Phys. Rep. 506, 1 (2011).
  * Araújo  _et al._ [2013] M. Araújo, M. T. Quintino, C. Budroni, M. T. Cunha, and A. Cabello, All noncontextuality inequalities for the $n$-cycle scenario, Phys. Rev. A 88, 022118 (2013).
  * Arnon-Friedman [2018] R. Arnon-Friedman,  _Reductions to IID in Device-independent Quantum Information Processing_ , Ph.D. thesis, ETH Zürich (2018).
  * Acín  _et al._ [2007] A. Acín, N. Brunner, N. Gisin, S. Massar, S. Pironio, and V. Scarani, Device-independent security of quantum cryptography against collective attacks, Phys. Rev. Lett. 98, 230501 (2007).
  * Csiszár and Körner [1978] I. Csiszár and J. Körner, Broadcast channels with confidential messages, IEEE Trans. Inf. Theory 24, 339 (1978).
  * Singh  _et al._ [2017] J. Singh, K. Bharti, and Arvind, Quantum key distribution protocol based on contextuality monogamy, Phys. Rev. A 95, 062333 (2017).
  * Troupe and Farinholt [2015] J. E. Troupe and J. M. Farinholt, A contextuality based quantum key distribution protocol, arXiv:1512.02256 (2015).
  * Löfberg [2004] J. Löfberg, YALMIP : A toolbox for modeling and optimization in MATLAB, in  _In Proceedings of the CACSD Conference_ (Taipei, Taiwan, 2004).
  * Toh  _et al._ [1999] K.-C. Toh, M. J. Todd, and R. H. Tütüncü, Sdpt3—a matlab software package for semidefinite programming, version 1.3, Optim. Methods Softw. 11, 545 (1999).

##  Appendix A Proofs

In this section we recall the statements from the main text and provide their
proofs.

######  Proposition 1.

For all contextuality scenarios the set of quantum behaviours $\mathcal{Q}$ is
convex.

###### Proof.

Let us consider two behaviours, $\mathbf{p},\tilde{\mathbf{p}}\in\mathcal{Q}$,
given by $p(k|x,y)=\tr(\rho_{x}M^{y}_{k})$ and
$\tilde{p}(k|x,y)=\tr(\tilde{\rho}_{x}\tilde{M}^{y}_{k})$, where $\rho_{x}$
and $M^{y}_{k}$ are quantum states and measurements, respectively, on a
Hilbert space $\mathcal{H}$, and $\tilde{\rho}_{x}$ and $\tilde{M}^{y}_{k}$
are quantum states and measurements, respectively, on a Hilbert space
$\tilde{\mathcal{H}}$. Furthermore, $\rho_{x}$ and $\tilde{\rho_{x}}$ satisfy
operational equivalences of the form (II.5), and $M^{y}_{k}$ and
$\tilde{M}^{y}_{k}$ satisfy operational equivalences of the form (II.5).

Consider an arbitrary convex combination,
$\hat{\mathbf{p}}=\lambda\mathbf{p}+(1-\lambda)\tilde{\mathbf{p}}$, where
$\lambda\in[0,1]$, i.e.,

$\hat{p}(k|x,y)=\lambda p(k|xy)+(1-\lambda)\tilde{p}(k|x,y)~{}~{}\forall
x,y,k.$ (22)

We show that $\hat{\mathbf{p}}\in\mathcal{Q}$ by providing explicit states and
measurements, such that $\hat{p}(k|x,y)=\tr(\hat{\rho}_{x}\hat{M}^{y}_{k})$.
In particular, consider the states

$\hat{\rho}_{x}=\lambda\rho_{x}\oplus(1-\lambda)\tilde{\rho}_{x}\in\mathcal{B}_{+}(\mathcal{H}\oplus\tilde{\mathcal{H}}),$
(23)

and the measurement operators

$\hat{M}^{y}_{k}=M^{y}_{k}\oplus\tilde{M}^{y}_{k}\in\mathcal{B}_{+}(\mathcal{H}\oplus\tilde{\mathcal{H}}).$
(24)

It is straightforward to verify that these constitute valid quantum states and
measurements on $\mathcal{H}\oplus\tilde{\mathcal{H}}$, satisfy the same
operational equivalence constraints as in Eqs. (II.5) and (II.5), and that
indeed $\hat{p}(k|xy)=\tr(\hat{\rho}_{x}\hat{M}^{y}_{k})$. This concludes the
proof that $\mathcal{Q}$ is a convex set.

∎

######  Proposition 2.

For all contextuality scenarios the subset of quantum behaviours
$\mathcal{Q}^{\Pi}$ is convex.

###### Proof.

The proof is identical to the proof of the previous proposition. Notice that
if $(M^{y}_{k})^{2}=M^{y}_{k}$ and $(\tilde{M}^{y}_{k})^{2}=\tilde{M}^{y}_{k}$
for all $y$ and $k$, then it also holds that
$(\hat{M}^{y}_{k})^{2}=\hat{M}^{y}_{k}$ for all $y$ and $k$. ∎

######  Proposition 3.

For all contextuality scenarios with only trivial equivalences of measurement
effects $T=(X,Y,Z,\mathcal{OE}_{P},\emptyset)$, projective measurements are
sufficent to recover the quantum set, i.e., $\mathcal{Q}=\mathcal{Q}^{\Pi}$.

###### Proof.

Given a quantum behaviour, $\mathbf{p}\in\mathcal{Q}$, there necessarily exist
density operators $\rho_{x}$ for $x\in[X]$ satisfying the constraints
$\mathcal{OE}_{P}$ and POVMs $\\{M^{y}_{k}\\}_{k\in[K]}$ for $y\in[Y]$ on a
finite dimensional Hilbert space $\mathcal{H}$ such that
$p(k|x,y)=\tr(\rho_{x}M^{y}_{k})$. As a consequence of Naimark’s theorem we
may find unitary operators $U^{y}$ on $\mathbb{C}^{K}\otimes\mathcal{H}$ such
that

$\tr(\ket{0}\bra{0}\otimes\rho_{x}U^{y}\ket{k}\bra{k}\otimes\mathbb{I}{U^{y}}^{\dagger})=\tr(\rho_{x}M^{y}_{k}).$
(25)

∎

######  Proposition 4.

For all contextuality scenarios with only trivial equivalences of
preparations, $T=(X,Y,Z,\emptyset,\mathcal{OE}_{M})$, all behaviours are
noncontextual, i.e., $\mathcal{NC}=\mathcal{Q}=\mathcal{C}$.

###### Proof.

Given a behaviour $\bm{p}^{C}\in\mathcal{C}$, consider the quantum strategy
for the scenario $(X,Y,K,\mathcal{O},\mathcal{OE}_{M})$ in which
$\rho_{x}=\ket{x}\bra{x}$ where $\\{\ket{x}\\}_{x\in[X]}$ is a orthonormal
basis of $\mathbb{C}^{X}$ and
$M^{y}_{k}=\sum_{x\in[X]}p^{C}(k|x,y)\ket{x}\bra{x}$. Since each $0\leq
p^{C}(k|x,y)\leq 1$ we have that $0\leq M^{y}_{k}\leq\mathbb{I}$, and since
$\sum_{k\in[K]}p^{C}(k|x,y)=1$ we find $\sum_{k\in[K]}M^{y}_{k}=\mathbb{I}$
for all $x\in[X]$ and $y\in[Y]$.

Given any operational equivalence

$\sum_{k\in[K],y\in[Y]}p_{j}(k,y|\omega)[k|M^{y}]=\sum_{k\in[K],y\in[Y]}p_{j}(k,y|\omega^{\prime})[k|M^{y}]$
(26)

in the set $\mathcal{OE}_{M}$, we find

$\displaystyle\sum_{k\in[K],y\in[Y]}p_{j}(k,y|\omega)M^{y}_{k}$
$\displaystyle=\sum_{k\in[K],y\in[Y],x\in[X]}p_{j}(k,y|\omega)p^{O}(k|x,y)\ket{x}\bra{x}$
(27)
$\displaystyle=\sum_{k\in[K],y\in[Y],x\in[X]}p_{j}(k,y|\omega^{\prime})p^{O}(k|x,y)\ket{x}\bra{x}$
$\displaystyle=\sum_{k\in[K],y\in[Y]}p_{j}(k,y|\omega^{\prime})M^{y}_{k}\,.$

Finally, $\Tr\left(M^{y}_{k}\ket{x}\bra{x}\right)=p^{C}(k|x,y)$ and therefore
$\mathcal{Q}=\mathcal{C}$. The equality $\mathcal{NC}=\mathcal{Q}$ follows due
to the existence of Beltrametti-Bugajski $\psi$-complete ontological model [3,
17]. ∎

######  Proposition 5.

For all contextuality scenarios with three or fewer preparation procedures,
$T=(X\leq 3,Y,Z,\mathcal{OE}_{P},\mathcal{OE}_{M})$, all behaviours are
noncontextual, i.e., $\mathcal{NC}=\mathcal{Q}=\mathcal{C}$.

###### Proof.

Up to relabelling, there is only one non-trivial family of sets
$\mathcal{OE}_{P}$ of operational preparation equivalences when $X=3$, namely,

$P_{2}=qP_{0}+(1-q)P_{1}$

for some $q\in[0,1]$. Given a behaviour $\bm{p}^{C}\in\mathcal{C}$, one can
verify that the density operators $\rho_{0}=\ket{0}\bra{0}$,
$\rho_{1}=\ket{1}\bra{1}$ and $\rho_{2}=q\rho_{0}+(1-q)\rho_{1}$ and the
operators $M^{y}_{k}=p^{C}(k|0,y)\ket{0}\bra{0}+p^{C}(k|1,y)\ket{1}\bra{1}$
satisfy $Tr(\rho_{x}M^{y}_{k})=p^{C}(k|x,y)$, $0\leq M^{y}_{k}\leq\mathbb{I}$,
and $\sum_{k\in[K]}M^{y}_{k}=\mathbb{I}$, in addition to any operational
equivalences in the set $\mathcal{OE}_{M}$. We have shown
$\mathcal{Q}=\mathcal{C}$. Now as a $\psi$-complete ontological model for any
three pure preparations is preparation noncontextual [17] the desired thesis
follows. ∎

######  Proposition 6.

In general, for contextuality scenarios with non-trivial equivalences of
measurement effects, projective measurements cannot produce all quantum
contextual behaviours, i.e., $\mathcal{Q}^{\Pi}\subsetneq\mathcal{Q}$.

###### Proof.

To prove the desired thesis we shall employ the contextuality scenario
$\\{2,2,3,\mathcal{OE}_{P},\mathcal{OE}_{M}\\}$, we further invoke the
$(2,3)$-mporac task, a generalization of $(2,2)$-mporac task, wherein Alice
receives two trits $a_{0},a_{1}\in[3]$, and is required to keep the parity
trit $a_{0}+a_{1}\mod{3}$ secret. Additionally, Bob has two three outcome
measurements $\\{M^{y}_{k}\\}^{1,2}_{Y=0,K=0}$ which satisfy the following
equivalence conditions,

$\frac{1}{2}[0|M_{0}]+\frac{1}{2}[0|M_{1}]\simeq\frac{1}{2}[1|M_{0}]+\frac{1}{2}[1|M_{1}]\simeq\frac{1}{2}[2|M_{0}]+\frac{1}{2}[2|M_{1}]$
(28)

First, we shall demonstrate that the operational equivalences (28) do not
allow for any projective measurements, rendering the set of quantum contextual
boxes obtained when the individual quantum measurements are projective
$\mathbb{Q}^{\Pi}$ to be $\emptyset$. It is straigtforward to that the
operational equivalences (28) necessitate the following constraints on quantum
measurement effects,

$\frac{1}{2}\left(\begin{array}[]{ll}M^{0}_{0}+M^{1}_{0}\\\
M^{0}_{1}+M^{1}_{1}\\\
M^{0}_{2}+M^{1}_{2}\end{array}\right)\equiv\left(\begin{array}[]{ll}\frac{\mathbb{I}}{3}\\\
\frac{\mathbb{I}}{3}\\\ \frac{\mathbb{I}}{3}\end{array}\right)$ (29)

Let us assume that each $M^{y}_{k}$ is a projector, specifically,
$(M^{y}_{k})^{2}=M^{y}_{k}$. Now from the equation (29) we have
$M^{1}_{0}=\frac{2\mathbb{I}}{3}-M^{0}_{0}$, which leads us to,

$\displaystyle(M^{1}_{0})^{2}$
$\displaystyle=\frac{4\mathbb{I}}{9}-\frac{4M^{0}_{0}}{3}+(M^{0}_{0})^{2},$
(30) $\displaystyle=\frac{4\mathbb{I}}{9}-\frac{M^{0}_{0}}{3},$

where the second equality follows from the projectivity assumption
$(M^{0}_{0})^{2}=M^{0}_{0}$. Whereas the assumption
$(M^{1}_{0})^{2}=M^{1}_{0}$ implies
$\frac{2\mathbb{I}}{3}-M^{0}_{0}=\frac{4\mathbb{I}}{9}-\frac{M^{0}_{0}}{3}$
which yields $M^{0}_{0}=\frac{\mathbb{I}}{3}$, which is not a projection, and
therefore contradicts our projectivity assumption. The relaxation for the set
$\mathcal{Q}^{\Pi}$ when applied to this scenario either returns an error, or
a value $\frac{1}{3}$ depending on the solver. The maximal noncontextual the
success probability of this $(2,3)$-mporac is $S_{\mathcal{NC}}=0.5$ Finally,
the states and POVMs depicted in Fig. 5 achieve a success probability of
$S_{\mathcal{Q}}\approx 0.5257834$, which leads us to the desired thesis.

Figure 5:  Quantum protocol for $(2,3)$-mporac that attains
$S_{\mathcal{Q}}=0.5257834>S_{\mathcal{NC}}=0.5>S_{\mathcal{Q}^{\Pi}}=\frac{1}{3}$.
This constitutes the proof of Proposition 6

.

∎

######  Proposition 7.

In general, for contextuality scenarios with non-trivial equivalences of
preparations, pure states cannot produce all quantum contextual behaviours,
i.e., $\mathcal{Q}^{\Psi}\subsetneq\mathcal{Q}$.

###### Proof.

In the $(2,2)$-porac, consider, operational equivalence of the form
$P_{a_{0}=1,a_{1}=1}\equiv\frac{1}{2}P_{a_{0}=0,a_{1}=1}+\frac{1}{2}P_{a_{0}=1,a_{1}=0}$.
Now if we demand that the involved preparations are pure quantum states, it is
straightforward to see that the constraints implied by the operational
equivalence condition can only be satisfied when the three quantum states are
identical, which leads to the upper bound on the performance of pure states in
this task, $S_{Q}^{\psi}=0.75$. Now, the non-contextual bound, quantum lower
bound, and the upper bound obtained via the first level of our hierarchy are
indentical $S_{N}C=S_{Q_{L}}=S_{Q_{1}}=0.8750$, which proves the desired
thesis. We implemented a separate hierarchy of semi-definite programs to bound
the preparation contextual correlations obtained from the pure states, the
resulting upper-bounds from the first level of hierarchy are plotted in Fig.
2. ∎

######  Lemma 1.

Any operator $0\leq M\leq\mathbb{I}$ on a finite dimensional Hilbert space
$\mathcal{H}$ can be written as
$M=\frac{\mathbb{I}}{2}+\frac{U+U^{\dagger}}{4}$, where $U$ is a unitary
operator on $\mathcal{H}$.

###### Proof.

Every such operator $M$ can be written as its spectral decomposition,

$M=\sum_{j}\lambda_{j}\outerproduct{j}{j},$ (31)

where $\\{\ket{j}\\}_{j=0}^{\dim\mathcal{H}-1}$ is an orthonormal basis on
$\mathcal{H}$ (the eigenbasis of $M$), and $0\leq\lambda_{j}\leq 1$ for all
$j$. Then, consider the unitary operator

$U=\sum_{j}\mathrm{e}^{\mathrm{i}\alpha_{j}}\outerproduct{j}{j},$ (32)

such that $\lambda_{j}=\frac{1}{2}(1+\cos\alpha_{j})$ and
$\\{\ket{j}\\}_{j=0}^{\dim\mathcal{H}-1}$ is the eigenbasis of $M$. Notice
that such set of $\alpha_{j}$ can always be found for any set of $\lambda_{j}$
satisfying $0\leq\lambda_{j}\leq 1$. Therefore, it holds that

$M=\sum_{j}\frac{1}{2}(1+\cos\alpha_{j})\outerproduct{j}{j}=\sum_{j}\Big{[}\frac{1}{2}+\frac{1}{4}(\mathrm{e}^{\mathrm{i}\alpha_{j}}+\mathrm{e}^{-\mathrm{i}\alpha_{j}})\Big{]}\outerproduct{j}{j}=\frac{\mathbb{I}}{2}+\frac{U+U^{\dagger}}{4}.$
(33)

∎

######  Lemma 2.

The maximal noncontextual success probability of $(n,2)$-mporac tasks remains
the same as the noncontextual success probability of $(n,2)$-porac tasks such
that $S_{NC}=\frac{1}{2}(1+\frac{1}{n})$.

###### Proof.

As the $(n,2)$-mporac tasks have more constraints than $(n,2)$-porac, so
straight off we have $S_{\mathcal{NC}}\leq\frac{1}{2}(1+\frac{1}{n})$. All we
need to prove is that $\frac{1}{2}(1+\frac{1}{n})$ is a viable success
probability with the additional operational equivalences of measurement
effects. Let us consider a binary ontic state space such that the ontic state
$\lambda\in\\{0,1\\}$. The epistemic states for this scenario are simply
enconding the first bit of Alice such that $\mu(\lambda=a_{0}|P_{x})=1$. The
response schemes are of the form $\xi(k=\lambda|M^{y=0},\lambda)=1$, and
$\xi(k=\lambda|M^{y\neq 0},\lambda)=\frac{n-2}{2(n-1)}$. It is straightforward
to check these response schemes are non-contextual, and achieve the desired
success probability $S_{NC}=\frac{1}{2}(1+\frac{1}{n})$. ∎

##  Appendix B Tutorial code

As a demonstration of the ease of implementation of the relaxations presented
in this work, we provide a basic verbose code for the universal contextuality
scenario $(X=6,Y=3,K=2,\mathcal{U}_{P},\mathcal{U}_{M})$, where we have the
following operational equivalences,

$\displaystyle\frac{1}{2}(P_{0}+P_{1})\simeq\frac{1}{2}(P_{2}$
$\displaystyle+P_{3})\simeq\frac{1}{2}(P_{4}+P_{5}),$ (34)
$\displaystyle\frac{1}{3}([0|M_{0}]+[0|M_{1}]+[0|M_{2}])$
$\displaystyle\simeq\frac{1}{3}([1|M_{0}]+[1|M_{1}]+[1|M_{2}]).$ (35)

Here we’ll be employing Matlab in conjunction with a standard optimization
toolbox YALMIP, and SDPT3 as our SDP solver.

For this scenario we will employ the operator list
$\mathcal{O}=\\{\mathbb{I},\\{U^{y}_{k},{U^{y}_{k}}^{\dagger}\\}^{Y-1,K-2}_{y=0,k=0}\\}$.
We begin by declaring the specifications of the prepare-and-measure
experiment, total number of operators, empty arrays for constraints, a
probability cell for storing observed behaviour, an empty array to for the
results, and $X$ SDP variables,

⬇

6; % six settings for the preparation device

Y = 3; % three settings for the measurement device

K = 2; % binary outcomes

O = 2*Y*(K-1)+1; % total number of operators in our list

conP = []; % an empty list for constraints on the moment matrix level

conM = []; % an empty list for constraints on the substrate level

Prob = cell(X,Y,K-1); % a cell for probabilities

S = []; % an empty list for upper bounds

G = cell(X,1); % cell for X moment matrices

It is a feature of our formulation that one can easily segregate constraints
on abstract moment matrices, from those that depend specifically on the
operators in the operator list. The former includes the following constraints
that ensue from positive semidefiniteness of the quantum states, and
equivalence conditions of preparations (34),

⬇

x = 0:X-1

G{x+1}=sdpvar(O,O,'hermitian','complex'); % declaration of our SDP variables

conP = [conP;G{x+1} $\geq$ 0]; % semi-definite constraints

end

conP = [conP; G{1} + G{2} == G{3} + G{4}; G{1} + G{2} == G{5} + G{6}]; %
preparation equivalences

Now let us now collect constraints that are specific to the operator list we
are employing. First, we create an indexing function which returns the
position of the operator in each moment matrix given the operator specifiers,

⬇

= @(y, k, u) 2*(K-1)*y + 2*k + u + 2; % function to return the position of the
operators

where $U^{y,u=0}_{k}=U^{y}_{k}$, and $U^{y,u=1}_{k}={U^{y}_{k}}^{\dagger}$.
Let us now specify how the operators
$\\{{U^{y}_{k}}^{\dagger}\\}^{Y-1,K-2}_{y=0,k=0}$ are related to
$\\{{U^{y}_{k}}\\}^{Y-1,K-2}_{y=0,k=0}$, along with constraints that ensue for
unitarity of operators in our list,

⬇

j = 1:O

for x = 0:X-1

for y = 0:Y-1

for k = 0:K-2

conM = [conM; G{x+1}(j,idx(y,k,0)) == G{x+1}(idx(y,k,1),j)];

conM = [conM; G{x+1}(idx(y,k,0),j) == G{x+1}(j,idx(y,k,1))];

end

end

conM = [conM; G{x+1}(j,j) == 1]; % unitarity constraints

end

end

We can now collect observed data
$p(k|x,y)=\frac{\mathbb{I}}{4}+\frac{1}{4}(\tr{\rho_{x}U^{k}_{y}}+\tr{\rho_{x}U^{k}_{y}})$,

⬇

x = 0:X-1

for y = 0:Y-1

for k = 0:K-2

Prob{x+1,y+1,k+1} = 0.5 + 0.25 * (G{x+1}(1, idx(y,k,0)) + G{x+1}(1,
idx(y,k,1)));

end

end

end

The measurement equivalences (35) amount to additional addtional constraints
on the unitary operators,

$\sum^{Y-1}_{y=0}(U^{k}_{0}+{U^{k}_{0}}^{\dagger})=0$ (36)

which can be enforced in the following way, specific to our operator list,

⬇

x = 0:X-1

for j = 1:O

sum1 = 0; sum2 = 0;

for y = 0:Y-1

for k = 0:K-2

sum1 = sum1 + G{x+1}(j,idx(y,k,0)) + G{x+1}(j,idx(y,k,1));

sum2 = sum2 + G{x+1}(idx(y,k,0),j) + G{x+1}(idx(y,k,1),j);

end

end

conM = [conM; sum1 == 0; sum2 == 0]; % measurement equivalences

end

end

Now we are all set to retrieve quantum bounds on facet inequalities in Table 1
and in [4],

⬇

= real(Prob{1,1,1} + Prob{3,2,1} + Prob{5,3,1});

diagnostics = optimize([conP;conM], -S1, sdpsettings('solver', 'sdpt3'));

S = [S;value(S1)];

%-------------------------------------------------------------------------------

S2 = real(Prob{1,1,1} + Prob{2,2,1} + Prob{5,3,1});

diagnostics = optimize([conP;conM], -S2, sdpsettings('solver', 'sdpt3'));

S = [S;value(S2)];

%-------------------------------------------------------------------------------

S3 = real(Prob{1,1,1} - Prob{3,1,1} -2 * Prob{5,1,1} -2 * Prob{2,2,1} + 2 *
Prob{3,2,1} + 2 * Prob{5,3,1});

diagnostics = optimize([conP;conM], -S3, sdpsettings('solver', 'sdpt3'));

S = [S;value(S3)];

%-------------------------------------------------------------------------------

S4 = real(2* Prob{1,1,1} - Prob{2,2,1} +2* Prob{3,2,1});

diagnostics = optimize([conP;conM], -S4, sdpsettings('solver', 'sdpt3'));

S = [S;value(S4)];

%-------------------------------------------------------------------------------

S5 = real(Prob{1,1,1} - Prob{5,1,1} + Prob{2,2,1} + Prob{3,2,1} + 2 *
Prob{5,3,1});

diagnostics = optimize([conP;conM], -S5, sdpsettings('solver', 'sdpt3'));

S = [S;value(S5)];

%-------------------------------------------------------------------------------

S6 = real(Prob{1,1,1} - Prob{5,1,1} + 2*Prob{2,2,1} + 2 * Prob{5,3,1});

diagnostics = optimize([conP;conM], -S6, sdpsettings('solver', 'sdpt3'));

S = [S;value(S6)];

%-------------------------------------------------------------------------------

S7 = real(Prob{1,1,1} - Prob{4,1,1} -2 * Prob{5,1,1} -2 * Prob{2,2,1} + 2 *
Prob{3,2,1} + 2 * Prob{5,3,1});

diagnostics = optimize([conP;conM], -S7, sdpsettings('solver', 'sdpt3'));

S = [S;value(S7)];

where the first six expressions correspond to the facet inequalities of the
noncontextual polytope in this scenario (see Table 1), while the seventh
expression from equation $(26)$ in [4] is the third facet inequality with a
typing error. And we are done, we can display the results by,

⬇

mat long;

disp(S)

3.000000002229091

2.866025404069207

3.920951868572950

3.366025406135015

4.688901059948105

4.645751312070173

3.464101523755184

##  Appendix C Optimal states and measurements

Figure 6:  Quantum protocols that attain maximal quantum values for all facet
inequalities in Table 1 in the contextuality scenario
$T=\\{6,3,2,\mathcal{U}_{P},\mathcal{U}_{M}\\}$.