Hypergraph framework for irreducible noncontextuality
inequalities from logical proofs of the Kochen-Specker
theorem
Ravi Kunjwal
1,2
1
Perimeter Institute for Theoretical Physics,
31 Caroline Street North, Waterloo, Ontario, Canada, N2L 2Y5,
2
Centre for Quantum Information and Communication,
´
Ecole polytechnique de Bruxelles, CP 165, Universit
´
e libre de Bruxelles, 1050
Brussels, Belgium.
January 8, 2020
Kochen-Specker (KS) theorem reveals the
inconsistency between quantum theory and
any putative underlying model of it satisfying
the constraint of KS-noncontextuality. A logi-
cal proof of the KS theorem is one that relies
only on the compatibility relations amongst a
set of projectors (a KS set) to witness this
inconsistency. These compatibility relations
can be represented by a hypergraph, referred
to as a contextuality scenario. Here we con-
sider contextuality scenarios that we term KS-
uncolourable, e.g., those which appear in logi-
cal proofs of the KS theorem. We introduce a
hypergraph framework to obtain noise-robust
witnesses of contextuality from such scenarios.
Our approach builds on the results
of R. Kunjwal and R. W. Spekkens,
Phys. Rev. Lett. 115, 110403 (2015), by
providing new insights into the relationship
between the structure of a contextuality
scenario and the associated noise-robust
noncontextuality inequalities that witness
contextuality. The present work also forms
a necessary counterpart to the framework
presented in R. Kunjwal, Quantum 3, 184
(2019), which only applies to KS-colourable
contextuality scenarios, i.e., those which do
not admit logical proofs of the KS theorem
but do admit statistical proofs.
We rely on a single hypergraph invariant, de-
fined in R. Kunjwal, Quantum 3, 184 (2019),
that appears in our contextuality witnesses,
namely, the weighted max-predictability. The
present work can also be viewed as a study of
this invariant. Significantly, unlike the case of
R. Kunjwal, Quantum 3, 184 (2019), none of
the graph invariants from the graph-theoretic
framework for KS-contextuality due to Ca-
bello, Severini, and Winter (the “CSW frame-
work”, Phys. Rev. Lett. 112, 040401 (2014))
Ravi Kunjwal: quaintum.research@gmail.com
are relevant for our noise-robust noncontextu-
ality inequalities.
Contents
1 Introduction 2
2 Definitions 3
2.1 Operational theories . . . . . . . . . . 3
2.2 Ontological models . . . . . . . . . . . 4
2.3 Operational equivalences and Noncon-
textuality . . . . . . . . . . . . . . . . 4
2.3.1 Operational equivalences . . . . 4
2.3.2 Context . . . . . . . . . . . . . 4
2.3.3 Noncontextuality . . . . . . . . 4
2.4 Contextuality scenarios and probabilis-
tic models on them . . . . . . . . . . . 5
3 A family of KS-uncolourable scenarios:
the mapping 2Reg(·) 7
3.1 KS-uncolourability under 2Reg(·) . . . 7
3.2 From graphs to hypergraphs under
2Reg(·) . . . . . . . . . . . . . . . . . 8
Complete bipartite graphs un-
der 2Reg(·) . . . . . . . . . . . 8
4 Uniform contextuality scenarios, their
parameters, and KS-uncolourability 10
4.1 Conditions on the parameters of a
contextuality scenario for its KS-
uncolourability . . . . . . . . . . . . . 11
4.1.1 2-regular contextuality scenarios 11
4.1.2 d-uniform and 2-regular contex-
tuality scenarios of type 2Reg(G) 11
4.1.3 d-uniform contextuality scenarios 11
4.2 The Kochen-Specker (1967) construction 12
5 Contextuality scenarios and extremal
probabilistic models on them 12
6 Noise-robust noncontextuality inequali-
ties from a hypergraph invariant 14
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 1
arXiv:1805.02083v3 [quant-ph] 7 Jan 2020
6.1 Operational equivalences . . . . . . . . 14
6.2 Minimally Indeterministic Sets of Con-
texts (MISCs) . . . . . . . . . . . . . . 17
6.2.1 Noise-robust noncontextu-
ality inequalities for any
KS-uncolourable contextuality
scenario . . . . . . . . . . . . . 17
6.2.2 Sufficient condition for a set of
contexts to be a MISC is not
necessary . . . . . . . . . . . . 18
6.2.3 2Reg(K
3,3
) . . . . . . . . . . . 18
6.2.4 2Reg(K
1,7
) . . . . . . . . . . . 21
6.2.5 2Reg(K
1,n
) with n(> 1) odd . 21
6.2.6 2Reg(K
m,n
), for odd mn > 1 . 22
7 Discussion and future work 25
Acknowledgement 26
Appendices 26
A Note on matching scenarios 26
B Can the noise-robust noncontextuality
inequalities of Eq. (26) be saturated? 27
References 28
1 Introduction
The Kochen-Specker (KS) theorem [1] stands out as a
fundamental insight into the nature of quantum mea-
surements, formalizing the fact that these measure-
ments cannot always be understood as merely reveal-
ing pre-existing values of physical quantities. How-
ever, the relevance of the KS theorem for real-world
physics with finite-precision measurements has been
a subject of intense controversy in the past [2–5]. Re-
cent work [6–11] has taken the first steps towards
turning the insight of the Kochen-Specker theorem
into operational constraints — or noncontextuality in-
equalities — that are robust to noise and therefore ex-
perimentally testable. These inequalities do not pre-
sume the structure of quantum measurements — in
particular, that they are projective — in their deriva-
tion, relying only on operational constraints that can
be verified in an experiment and make sense, in partic-
ular, for nonprojective measurements in quantum the-
ory.
1
They are grounded in the generalized framework
1
Note that, strictly speaking, the traditional assumption of
KS-noncontextuality [1, 12] can be applied to arbitrary mea-
surements if one doesn’t care to justify outcome determinism
from noncontextuality `a la Ref. [13], but even so, it fails to
make sense as a notion of classicality for nonprojective mea-
surements in quantum theory, e.g., for trivial POVMs. See
Section I and Appendix A of Ref. [14] for a discussion of this
pathology of KS-noncontextuality as a notion of classicality.
Also see Refs. [15, 16] for a more in-depth discussion of these
issues, particularly the status of Fine’s theorem [17] in the case
of noncontextuality.
for contextuality proposed by Spekkens [13]. This
framework is motivated by a methodological princi-
ple underlying the Kochen-Specker theorem: namely,
noncontextuality as an application of the principle of
ontological identity of operational indiscernables, or
as Spekkens sometimes calls it, Leibnizianity [18, 19].
Recent developments in this operational approach
to noncontextuality `a la Spekkens have led to a
plethora of noise-robust noncontextuality inequalities.
We know examples of these for geometric KS con-
structions such as the 18 ray construction due to Ca-
bello, Estebaranz, and Garc´ıa-Alcaine (CEGA) [6, 20]
as well as algebraic constructions due to Peres and
Mermin [9, 21, 22]. We also have novel examples that
have no analogue in the traditional Kochen-Specker
paradigm, such as the fair coin flip inequality [7],
the robust noncontextuality inequalities due to Pusey
[8] for the simplest nontrivial scenario admitting con-
textuality that is possible in the Spekkens approach,
and the algorithmic approach to handling prepare-
and-measure experiments with specified operational
equivalences [11].
In this paper, which builds upon the conceptual
ideas outlined in Ref. [6], we provide a hypergraph
framework for obtaining noise-robust noncontextual-
ity inequalities for any Kochen-Specker construction
that is KS-uncolourable, i.e., logical proofs [10] of the
Kochen-Specker theorem in the style of Ref. [1]. The
case of statistical proofs of the Kochen-Specker the-
orem — such as the argument due to Klyachko et
al. [23] and the general graph-theoretic framework
of Ref. [24] due to Cabello, Severini, and Winter
(CSW) — has already been formalized within the
Spekkens framework [13] in two previous contribu-
tions: Ref. [10] provides the conceptual argument
leading to this formalization while Ref. [14] provides
a hypergraph-theoretic framework that obtains noise-
robust noncontextuality inequalities from arbitrary
statistical proofs of the KS theorem by going be-
yond the CSW framework [24]. The approach we
develop in this paper allows one to identify the phys-
ical quantities that one can expect to be constrained
by the assumption of noncontextuality (and why) in
KS-uncolourable contextuality scenarios. This is in
contrast to the approach adopted in Refs. [6, 9, 11]
which require explicit enumeration of all the vertices
of the polytope of probability assignments possible on
the scenario and/or performing quantifier elimination.
To circumvent this requirement, we rely on a charac-
terization of extremal probabilistic models on contex-
tuality scenarios proved in Ref. [25] and a mapping
from graphs to hypergraphs (for a family of contextu-
ality scenarios) that we will introduce in this paper.
The structure of the paper is as follows: In Sec-
tion 2, we recall some definitions that will be used
throughout the paper. In Section 3, we define a map-
ping from graphs to hypergraphs that can be used
to generate KS-uncolourable hypergraphs; we obtain
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 2
many known KS-uncolourable hypergraphs as exam-
ples. Section 4 defines a parameterization of contex-
tuality scenarios that is used to obtain a characteriza-
tion of KS-uncolourability for them. Section 5 recalls
a theorem on extremal probabilistic models on con-
textuality scenarios, proved in Ref. [25], that will be
crucial to obtaining our noncontextuality inequalities.
In Section 6, we outline our general framework which
is applicable to any KS-uncolourable contextuality sc-
neario. In particular, Eq. (26) provides the general
form of noise-robust noncontextuality inequalities we
obtain. We then use the results developed so far to ob-
tain irreducible noncontextuality inequalities for some
families of KS-uncolourable contextuality scenarios:
in contrast to the inequality of Ref. [6], these inequal-
ities cannot be reduced to any simpler ones. We prove
a general theorem characterizing these inequalities for
a whole family of KS-uncolourable contextuality sce-
narios. Table 1 summarizes features of this family of
contextuality scenarios that determine the structure
of irreducible noncontextuality inequalities. Section 7
concludes with a summary of the framework and open
questions that merit further research.
2 Definitions
2.1 Operational theories
We will be concerned with prepare-and-measure ex-
periments in our tests of noncontextuality: that is,
we imagine a preparation device as a source of a sys-
tem that is subjected (following its preparation) to
a measurement procedure carried out by a measure-
ment device (see Fig. 1). The preparation device has
many possible source settings S ∈ S, each S specify-
ing a particular ensemble of preparation procedures
labelled by (classical) source outcomes s ∈ V
S
, where
V
S
is the set of source outcomes for source setting S.
We call [s|S] a source event. Hence, each prepara-
tion procedure is denoted by P
[s|S]
, corresponding to
the source event [s|S]: that is, the system is prepared
according to P
[s|S]
with probability p(s|S) ∈ [0, 1],
where
P
s∈V
S
p(s|S) = 1, for every choice of setting
S ∈ S. The ensemble of preparation procedures as-
sociated with the source setting S is then given by
{P
[s|S]
, p(s|S)}
s∈V
S
.
Similarly, the measurement device has many possi-
ble measurement settings M ∈ M, each M specifying
a particular measurement procedure with many possi-
ble measurement outcomes m ∈ V
M
, where V
M
is the
set of values the measurement device can output when
the measurement setting is M and a system prepared
by some source is an input to the measurement device.
We will use [m|M] to denote the measurement event
that the outcome m was witnessed for measurement
setting M.
The joint probability of a particular outcome m for
measurement setting M and a particular outcome s
Measurement
Source
Figure 1: A schematic of the prepare-and-measure experi-
ment: the source setting S ∈ S produces a source outcome
s ∈ V
S
and a system prepared according to preparation P
[s|S]
that is then subjected to the measurement device with mea-
surement setting M ∈ M which then outputs a measure-
ment outcome m ∈ V
M
. The joint probability of source
and measurement outcomes is given by p(m, s|M, S). The
source outcome s occurs with probability p(s|S) and set-
ting S prepares the ensemble {P
[s|S]
, p(s|S)}
s∈V
S
. Time
goes up: we assume that future settings/outcomes do not
influence past settings/outcomes, so that p(m, s|M, S) =
p(m|M, S, s)p(s|M, S) = p(m|M, S, s)p(s|S).
for source setting S when the input to the measure-
ment device is a system prepared according to pro-
cedure P
[s|S]
is given by p(m, s|M, S) ∈ [0, 1], where
P
m,s
p(m, s|M, S) = 1. One can view this joint prob-
ability as composed of two pieces:
p(m, s|M, S) = p(m|M, S, s)p(s|S),
where p(m|M, S, s) is the conditional probability of
outcome m for measurement M when the system is
prepared according to procedure P
[s|S]
and p(s|S) is
the conditional probability that the system is indeed
prepared according to P
[s|S]
for the source (setting)
S.
An operational theory is therefore a specification
of the triple (S, M, p), where S is the set of source
settings in the operational theory, M is the set of
measurement settings, and p : V
M
× V
S
× M × S →
[0, 1] is a function that specifies the joint probabil-
ity p(m, s|M, S) that a given source setting S ∈ S
and measurement setting M ∈ M produce respective
outcomes s ∈ V
S
and m ∈ V
M
when the system pre-
pared by the preparation device is fed to the measure-
ment device, and where
P
m,s
p(m, s|M, S) = 1 for all
M ∈ M, S ∈ S.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 3
2.2 Ontological models
An ontological model of an operational theory seeks to
provide an explanatory framework for its predictions,
grounding them in intrinsic properties of physical sys-
tems. All such properties of a system are presumed
to be encoded in its ontic state λ ∈ Λ, where Λ is the
set of all possible ontic states of the system. A source
event [s|S] prepares the system in ontic state λ with
probability µ(λ|S, s) ∈ [0, 1], where
P
λ
µ(λ|S, s) = 1.
On measuring the system in ontic state λ, the mea-
surement M produces outcome m with probability
ξ(m|M, λ) ∈ [0, 1], where
P
m
ξ(m|M, λ) = 1 for all
λ ∈ Λ. We then have:
p(m|M, S, s) =
X
λ∈Λ
ξ(m|M, λ)µ(λ|S, s). (1)
We can use Bayes’ theorem to write µ(s|S, λ) =
µ(s,λ|S)
µ(λ|S)
. Noting that µ(s, λ|S) = µ(λ|S, s)p(s|S), we
have
µ(s|S, λ) =
µ(λ|S, s)p(s|S)
µ(λ|S)
, or
µ(λ|S, s) =
µ(s|S, λ)µ(λ|S)
p(s|S)
. (2)
Substituting this in Eq. (1), we have
p(m, s|M, S) =
X
λ∈Λ
ξ(m|M, λ)µ(s|S, λ)µ(λ|S), (3)
which describes how the operational joint probabili-
ties of the prepare-and-measure experiment must be
reproduced by the ontological model. Here ξ(m|M, λ)
is the predictive probability that a particular outcome
m will occur for a given measurement setting M when
the input ontic state is λ while µ(s|S, λ) is the retrod-
ictive probability that a particular outcome s occurred
for a given source setting S which produced the ontic
state λ. µ(λ|S) is the probability that λ was sampled
by the source setting S at all, ignoring its outcomes
s ∈ V
S
.
2.3 Operational equivalences and Noncontex-
tuality
2.3.1 Operational equivalences
Two source events [s|S] and [s
0
|S
0
] are said to be op-
erationally equivalent, denoted [s|S] ' [s
0
|S
0
], if:
∀[m|M] : p(m, s|M, S) = p(m, s
0
|M, S
0
),
where M ∈ M, m ∈ V
M
. (4)
Two source settings S and S
0
are said to be opera-
tionally equivalent, denoted [>|S] ' [>|S
0
], if:
∀[m|M] :
X
s∈V
S
p(m, s|M, S) =
X
s
0
∈V
S
0
p(m, s
0
|M, S
0
),
where M ∈ M, m ∈ V
M
. (5)
The symbol “>” denotes coarse-graining over all out-
comes, i.e., the [>|S] is the source event that at least
one outcome in V
S
occurred for source setting S. In
this paper, we will only make use of such coarse-
grained operational equivalences between source set-
tings, that is, ones where we sum over the classical
outcomes of the sources.
Two measurement events [m|M] and [m
0
|M
0
] are
said to be operationally equivalent, denoted [m|M ] '
[m
0
|M
0
], if:
∀[s|S] : p(m, s|M, S) = p(m
0
, s|M
0
, S),
where S ∈ S, s ∈ V
S
. (6)
Note that, because of normalization, any two
coarse-grained measurement settings M and
M
0
are always operationally equivalent, i.e.,
P
m∈V
M
p(m, s|M, S) =
P
m
0
∈V
M
0
p(m
0
, s|M
0
, S) =
p(s|S) for all [s|S]. It’s only in the case of sources that
the operational equivalence after coarse-graining is
nontrivial, i.e., it needs to be verified experimentally.
2.3.2 Context
Any distinction between operationally equivalent ex-
perimental procedures — preparations or measure-
ments — is called a context.
2.3.3 Noncontextuality
We define the notion of noncontextuality following the
proposal by Spekkens [13], wherein the assumption of
noncontextuality requires operationally equivalent ex-
perimental procedures to be represented identically in
the ontological model. That is, differences of context
between operationally equivalent experimental proce-
dures should be as irrelevant in the ontological model
as they are in the operational theory. Indeed, this
indifference to variations in context – that is, non-
contextuality – in the ontological model is meant to
account for the indifference to variations in context –
that is, operational equivalence – that holds in the op-
erational theory. Our goal is to put this hypothesis of
noncontextuality to experimental test by figuring out
operational constraints – noncontextuality inequali-
ties – that it imposes on the operational statistics.
Thus, the assumption of preparation noncontextu-
ality applied to operationally equivalent source events,
[s|S] ' [s
0
|S
0
], reads
µ(λ|S, s) = µ(λ|S
0
, s
0
) ∀λ ∈ Λ. (7)
Applied to the operational equivalence [>|S] ' [>|S
0
],
preparation noncontextuality reads
∀λ ∈ Λ :
X
s∈V
S
p(s|S)µ(λ|S, s)
=
X
s
0
∈V
S
0
p(s
0
|S
0
)µ(λ|S
0
, s
0
), or (8)
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 4
µ(λ|S) = µ(λ|S
0
) ∀λ ∈ Λ, (9)
where
µ(λ|S) ≡
X
s∈V
S
µ(s, λ|S) =
X
s∈V
S
p(s|S)µ(λ|S, s),
and similarly
µ(λ|S
0
) ≡
X
s
0
∈V
S
0
µ(s
0
, λ|S
0
) =
X
s
0
∈V
S
0
p(s
0
|S
0
)µ(λ|S
0
, s
0
).
We will only make use of this type of preparation
noncontextuality in this paper.
The assumption of measurement noncontextual-
ity applied to operationally equivalent measurement
events [m|M] ' [m
0
|M
0
] reads
ξ(m|M, λ) = ξ(m
0
|M
0
, λ) ∀λ ∈ Λ. (10)
2.4 Contextuality scenarios and probabilistic
models on them
In keeping with the definitions of Ref. [25], we intro-
duce the following notions:
• Contextuality scenario: A contextuality scenario
is a hypergraph H where the nodes of the hy-
pergraph w ∈ W (H) denote measurement out-
comes and hyperedges denote measurements f ∈
F (H) ⊆ 2
W (H)
such that
S
f∈F (H)
= W (H). We
will assume the set of nodes W (H) is finite and,
therefore, so is the set of hyperedges F (H).
A node shared between multiple hyperedges rep-
resents a measurement outcome with multiple
possible measurement contexts in which it can
occur. This is the notion of a (measurement) con-
text that is used in logical proofs of the Kochen-
Specker theorem relying on KS-uncolourability
[1, 20]. We will be concerned with this notion
of measurement context in this paper.
2
• n-hypercycle: An n-hypercycle is a collection of
n nodes, {w
i
}
n
i=1
, in a hypergraph H ≡ (W, F )
such that for all i ∈ {1, 2, . . . , n}, {w
i
, w
i+1
} ⊆ f
for some f ∈ F , but no other subsets of {w
i
}
n
i=1
appear in a hyperedge of H. Note that we have
assumed addition modulo n, i.e., n+1 = 1, while
labelling the nodes.
Note that every n-hypercycle in a hypergraph is
also an n-cycle, where by “n-cycle” we refer to a
collection of n nodes, {w
i
}
n
i=1
, such that for all
i ∈ {1, 2, . . . , n}, {w
i
, w
i+1
} ⊆ f for some f ∈
F . On the other hand, not every n-cycle in a
hypergraph is an n-hypercycle.
2
Spekkens contextuality [13] encompasses the measurement
contexts relevant in the Kochen-Specker paradigm but does not
restrict itself to them (see, e.g., [7]). In particular, it allows for
a notion of preparation contexts which has been previously used
in Ref. [6] – the conceptual precursor to the present work – and
which we will use in this paper.
When the hypergraph H is a graph, i.e., every
hyperedge f ∈ F contains exactly two nodes
from W , then every n-cycle of H is also an n-
hypercycle.
3
• Probabilistic model: A probabilistic model on a
contextuality scenario is an assignment of proba-
bilities to the nodes of a hypergraph, p : W (H) →
[0, 1], such that the hyperedges are normalized,
i.e.,
P
w∈f
p(w) = 1 for all f ∈ F (H). We de-
note the set of such general probabilistic models
on H by G(H).
Viewed operationally, any probabilistic model on
the contextuality scenario specifies the probabili-
ties of measurement outcomes when the measure-
ments are implemented on some preparation in
an operational theory. A given operational the-
ory may only allow a certain subset of all possible
probabilistic models on a contextuality scenario
when the measurements in the scenario are im-
plemented on a preparation possible in the op-
erational theory. Indeed, that is the premise of
Ref. [25], where possible probabilistic models on
a given contextuality scenario are classified as
classical, quantum, or general probabilistic mod-
els. The full set of possible probabilistic models
on the contextuality scenario, corresponding to
a polytope, constitutes the set of general proba-
bilistic models.
We will be interested in the polytope of general
probabilistic models in this paper. In particu-
lar, we do not seek to classify probabilistic mod-
els on a contextuality scenario `a la Acin, Fritz,
Leverrier, and Sainz (AFLS) [25]. Instead, we
will be interested in properties of these proba-
bilistic models that become crucial only in the
operational approach `a la Spekkens [13], having
no analogue in the AFLS framework. This is to
be expected since the AFLS framework is a for-
malization of the Kochen-Specker paradigm and
we seek to ask questions that necessitate a re-
formulation and extension of this paradigm `a la
Spekkens. For the case of statistical proofs of the
Kochen-Specker theorem, this has been achieved
in Refs. [10, 14]. This paper seeks to achieve this
3
Note that we are not necessarily imagining that H it-
self is isomorphic to an n-cycle graph. H can be any ar-
bitrary hypergraph and the question is if it admits sub-
hypergraphs that are n-hypercycles. The n-hypercycles
that are contained in H are distinct from (and, in gen-
eral, fewer in number than) the n-cycles contained in
it. For example, consider the 6-vertex hypergraph H =
{{1, 2, 3}, {3, 4, 5}, {5, 6, 1}}. This hypergraph contains the fol-
lowing n-cycles: {{1, 2}, {2, 3}, {1, 3}}, {{3, 4}, {4, 5}, {3, 5}},
{{5, 6}, {6, 1}, {1, 5}}, and {{1, 3}, {3, 5}, {1, 5}}. However,
only one of these n-cycles is an n-hypercycle, namely,
{{1, 3}, {3, 5}, {1, 5}}, since its vertices are not all contained
in a single hyperedge. When the hypergraph is a graph, e.g.,
H
0
= {{1, 3}, {3, 5}, {1, 5}}, then all its n-cycles are also n-
hypercycles.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 5
for logical proofs of the Kochen-Specker theorem,
based on the ideas conceptualized in Ref. [6]. Our
goal here is to provide technical tools concerning
the sorts of hypergraph properties – distinct from
the ones discussed in, for example, Refs. [24, 25]
– that are relevant for the noise-robust noncon-
textuality inequalities we derive in the opera-
tional approach `a la Spekkens. These hypergraph
properties are easily captured in a new hyper-
graph invariant that we defined in Ref. [14] —
the weighted max-predictability β(Γ, q) for a con-
textuality scenario Γ with hyperedges weighted
by probabilities according to the distribution q
— and which we will define in due course in
this paper. We will use β(Γ, q) to obtain noise-
robust noncontextuality inequalities arising from
any contextuality scenario Γ yielding a logical
proof of the KS theorem.
Note that the probability assigned to a mea-
surement outcome (or node) by any probabilis-
tic model on the hypergraph does not vary with
the measurement context (or hyperedge) that the
measurement outcome may be considered a part
of: operationally, this means that the operational
theories that lead to various probabilistic models
on contextuality scenarios exhibit nontrivial op-
erational equivalences between measurement out-
comes of different measurements. These oper-
ational equivalences take the form of the same
node being shared between two (or more) hy-
peredges and are represented in their entirety by
the structure of the hypergraph denoting the con-
textuality scenario. The assumption of measure-
ment noncontextuality – as we have defined it –
will be applied to these operational equivalences
implicit in the contextuality scenario.
• Kochen-Specker (KS) uncolourable scenario: A
KS-uncolourable scenario is a contextuality sce-
nario which does not admit a probabilistic model
that is deterministic, i.e., p : W (H) → {0, 1},
even though it may admit indeterministic prob-
abilistic models.
4
4
For readers familiar with the notion of “strong contextu-
ality” in the sheaf-theoretic approach of Abramsky and Bran-
denburger [26], we note that KS-uncolourability is a property
of the contextuality scenario itself rather than (as in the case of
“strong contextuality”) of a particular probabilistic model on it.
In this sense, KS-uncolourability is distinct from strong contex-
tuality. However, the two notions are related in the sense that
KS-uncolourability of a contextuality scenario implies strong
contextuality for all probabilistic models on it. Strong con-
textuality is the property of a probabilistic model: namely,
that the probabilistic model does not admit a convex decom-
position that has in its support a deterministic model(s). Ex-
tremal probabilistic models on a KS-colourable contextuality
scenario that are indeterministic are, by definition, strongly
contextual. On the other hand, every probabilistic model on
a KS-uncolourable contextuality scenario (extremal or not) is
strongly contextual.
A contextuality scenario which does admit de-
terministic probabilistic models is called KS-
colourable.
• Kochen-Specker (KS) set: A KS set is a set of
rank 1 projectors, {Π
w
}
w∈W (H)
, on some Hilbert
space H that can be associated with the nodes
W (H) of a KS-uncolourable scenario such that
P
w∈f
Π
w
= I for all f ∈ F (H) and Π
w
Π
w
0
=
δ
w,w
0
Π
w
for any w, w
0
∈ f . Here I is the identity
operator on H.
Each KS set corresponds to an infinity of possible
probabilistic models on a KS-uncolourable con-
textuality scenario, each given by p(w) = TrρΠ
w
for all w ∈ W (H), for some density operator ρ
on H.
• (Induced) Subscenario: Given a contextuality
scenario H with nodes W (H) and contexts F (H),
the subscenario H
S
induced by a subset of nodes
S ⊆ W (H) is given by: W (H
S
) ≡ S and
F (H
S
) ≡ {f ∩ S|f ∈ F (H)}.
That is, H
S
is constructed by dropping all the
nodes in W (H)\S and restricting the hyperedges
in F (H) to their intersection with the nodes in
S.
Remark on probabilistic models on H
S
: Note
that an induced subscenario H
S
admits a valid
probabilistic model only if f ∩ S 6= ∅ for all
contexts f ∈ F (H) because otherwise the set of
hyperedges in H
S
will include empty sets which
cannot be normalized, rendering a probabilistic
model impossible on H
S
(that is, G(H
S
) = ∅).
In the language of hypergraph theory, S must be
a transversal (or “hitting set”) of H.
• Extension of a probabilistic model on an induced
subscenario (H
S
) to the parent contextuality sce-
nario (H): Every probabilistic model on H
S
, say
p
S
, can be extended to a probabilistic model p
on H as follows: p(w) = p
S
(w) ∀w ∈ S and
p(w) = 0 otherwise. p is said to be an extension
of p
S
from H
S
to H.
5
We now recall Theorem 2.5.3 of Ref. [25], a charac-
terization of extremal probabilistic models on a con-
textuality scenario, that we will use:
Theorem 1. (Theorem 2.5.3 in [25])
p ∈ G(H) is extremal if and only if it is the exten-
sion of a unique probabilistic model p
S
on an induced
subscenario H
S
(that is, G(H
S
) = {p
S
}) to the prob-
abilistic model p on H.
Hence, there is a one-to-one correspondence be-
tween extremal probabilistic models on H and in-
duced subscenarios of H with unique probabilistic
5
Note that the definition of an induced subscenario (H
S
)
and the extension of a probabilistic model from H
S
to H is
adopted from Ref. [25], specifically Definition 2.5.1 in Ref. [25].
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 6
models. Indeed, as noted in [25], this means that
each extremal probabilistic model p ∈ G(H) is in
one-to-one correspondence with the set of vertices as-
signed nonzero probability by the extremal probabilis-
tic model, i.e. S
p
≡ {w ∈ W (H)|p(w) 6= 0}.
6
3 A family of KS-uncolourable scenar-
ios: the mapping 2Reg(·)
We now consider a particular mapping, which we call
2Reg(·), that often converts a graph to a contextuality
scenario that is KS-uncolourable.
7
We will see that
many known examples of KS-uncolourable scenarios
arise in this way. The mapping 2Reg(·) is defined in
the following manner:
• Input Graph: G = (V, E), where V =
{v
1
, v
2
, . . . , v
|V |
} and E = {e
1
, e
2
, . . . , e
|E|
} ⊆
{{v
i
, v
j
}|i, j ∈ {1, . . . , n}, i 6= j}.
• Output Hypergraph: 2Reg(G) ≡ H = (W, F ),
where
– each node w
k
∈ W (k = 1, . . . , |W |) is de-
fined by a pair of edges in E that share a ver-
tex, i.e., for every pair {e
i
, e
j
} ⊆ E (where
i 6= j) such that e
i
∩e
j
6= ∅, there is a corre-
sponding node w
k
∈ W . The cardinality of
W , |W|, is therefore equal to the number of
distinct pairs of edges in E such that each
pair shares a vertex (in V ).
– For every edge e
i
∈ E, we define a corre-
sponding hyperedge f
i
∈ F such that the
nodes in f
i
correspond precisely to the pairs
of edges {{e
i
, e
j
}|e
i
∩ e
j
6= ∅, j 6= i and j ∈
{1, . . . , n}}. We have |F | = |E|.
A key property of such a hypergraph, H, generated
via 2Reg(G) is that each node w
k
(corresponding to
a pair {e
i
, e
j
}, say) in W appears in exactly two hy-
peredges (f
i
, f
j
∈ F ) of the hypergraph H. That is,
2Reg(G) is a 2-regular hypergraph for any graph G.
This is simply because every node in H is essentially
defined by the intersection of two hyperedges in H.
8
6
This fact seems to be closely related to the later work
of Abramsky et al.[27], where the combinatorial structure of
no-signalling polytopes is characterized in entirely possibilis-
tic terms. In particular, characterization of the face lattice of
the polytope G(H) of probabilistic models on H (as done in
Ref. [27], albeit within a different formalism) implies a charac-
terization of the vertices of this polytope (as done in Ref. [25]).
The proof of Theorem 2.5.3 in Ref. [25] provides direct evidence
of this connection.
7
“2Reg” refers to the fact that contextuality scenarios ob-
tained under this mapping are such that every node of the
scenario has degree 2, i.e., it appears in two hyperedges or con-
texts, hence the scenario is 2-regular.
8
Note that if G contains (at least) an edge disjoint from
the rest of G, the mapping 2Reg(·) results in a set of hyper-
11
12
32
33
23
21
22
31 13
2Reg(.)
1 2 3
1 2 3
2Reg(K
3,3
)
K
3,3
Figure 2: The bipartite graph K
3,3
under the mapping
2Reg(·).
To see how this mapping works consider an
example: the complete bipartite graph K
3,3
with vertices V = {1, 2, 3,
¯
1,
¯
2,
¯
3} and edges
E = {(1
¯
1), (1
¯
2), (1
¯
3), (2
¯
1), (2
¯
2), (2
¯
3), (3
¯
1), (3
¯
2), (3
¯
3)}
transforms under 2Reg(·) to the CEGA hypergraph
[20] which, given a realization with 18 rays in R
4
,
provides a proof of the KS theorem in 4 dimensions.
See Fig. 2. We will see how this mapping works in
a forthcoming section on complete bipartite graphs
under 2Reg(·).
3.1 KS-uncolourability under 2Reg(·)
Theorem 2. Given a graph G = (V, E), the con-
textuality scenario 2Reg(G) is KS-uncolourable if and
only if |E| is odd.
Proof. |E| is odd ⇒ 2Reg(G) is KS-uncolourable:
We have |E| normalization equations for any KS-
noncontextual assignment of {0, 1} probabilities to
the nodes of the hypergraph 2Reg(G), since 2Reg(G)
has |E| contexts and the {0, 1}-valued assignments
to the nodes in each context should add up to 1; on
adding all the normalization equations together, we
note that since each {0, 1}-valued assignment to a
node appears in two different equations we have an
even number on the left-hand-side (LHS) of the re-
sulting equation and an odd number (= |E|) on the
right-hand-side (RHS), hence there is no {0, 1}-valued
solution to the normalization equations and 2Reg(G)
is KS-uncolourable.
To prove the converse, we show that |E| is even ⇒
2Reg(G) is KS-colourable: Note that 2Reg(G) con-
sists of a set of |E| contexts such that every pair
of them with a non-empty intersection shares ex-
actly one node. Let’s call these contexts C
1
, C
2
,
C
3
,. . . ,C
|E|
, labelled such that C
i
and C
i+1
(addi-
tion modulo |E|, so |E| + 1 = 1) share a node for all
edges where (at least) one of them (corresponding to the dis-
joint edge) is empty. Strictly speaking, this is not a hypergraph
since it has an empty hyperedge and thus 2Reg(·) will not re-
sult in a contextuality scenario. Therefore, such graphs G will
not be of interest to us. Henceforth, we will only consider G
for which 2Reg(G) is a contextuality scenario.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 7
i ∈ {1, 2, . . . , |E|}. Consider now the even hypercycle
of size |E| given by the contexts
C
1
− C
2
− C
3
− · · · − C
|E|
− C
1
and assign the probability 1 to node defined by the
intersection of C
1
and C
2
(denoted C
1
− C
2
), proba-
bility 0 to node defined by the intersection of C
2
and
C
3
(denoted C
2
− C
3
), 1 to node defined by intersec-
tion of C
3
and C
4
(denoted C
3
− C
4
),. . . , and so on,
alternating assignments of 1 and 0, up to assigning
probability 0 to the node denoted C
|E|
−C
1
.
9
The in-
duced subscenario consisting of singleton hyperedges
(that is, hyperedges with a single node each)
{{C
1
− C
2
}, {C
3
− C
4
}, . . . , {C
|E|−1
− C
|E|
}}
then admits a unique probabilistic model which ex-
tends to a deterministic extremal probabilistic model
on 2Reg(G). This is easy to see because the induced
subscenario assigns probability 1 to
|E|
2
nodes and
each of those nodes appears in two contexts, thus en-
suring that all the contexts are properly normalized
in the extension of the unique probabilistic model to
2Reg(G). Hence, 2Reg(G) is KS-colourable whenever
|E| is even.
3.2 From graphs to hypergraphs under 2Reg(·)
We will now prove some facts about the behaviour of
some special classes of graphs under 2Reg(·).
Lemma 1. All n-cycle (n ≥ 3) graphs are invariant
under 2Reg(·).
Proof. Given the n-cycle graph
{e
12
≡ {v
1
, v
2
}, e
23
≡ {v
2
, v
3
}, . . . , e
n1
≡ {v
n
, v
1
}},
the hypergraph under 2Reg(·) is given by
{E
12
≡ {w
1
≡ (e
12
, e
n1
), w
2
≡ (e
12
, e
23
)},
E
23
≡ {w
2
≡ (e
12
, e
23
), w
3
≡ (e
23
, e
34
)}, . . . ,
E
n1
≡ {w
n
≡ (e
n−1,n
, e
n1
), w
1
≡ (e
12
, e
n1
)}},
which is the n-hypercycle isomorphic to the starting
n-cycle graph. From Theorem 2, an n-hypercycle is
KS-uncolourable if and only if n is odd. Note, in
particular, that a triangle (or 3-cycle) graph goes to
a 3-hypercycle. See Fig. 3.
Lemma 2. Any n-vertex complete graph K
n
is
mapped under 2Reg(·) to a hypergraph with
n
C
2
=
n(n−1)
2
hyperedges with 2(n − 2) nodes per hyperedge
and
n
C
2
(n − 2) =
n(n−1)(n−2)
2
nodes in all.
9
Note that “C
i
− C
i+1
” denotes the node that appears in
both contexts, C
i
and C
i+1
.
2Reg(.)
2Reg(.)
Figure 3: n-cycles map to n-hypercycles and triangle maps
to a 3-hypercycle under 2Reg(·).
Proof.
K
n
≡ {e
12
, . . . , e
1n
, e
23
, . . . , e
2n
, . . . , e
n−1,n
},
where e
ij
≡ {v
i
, v
j
} denotes the edge connecting
vertices v
i
and v
j
, where i, j ∈ {1, 2, . . . , n} and
i 6= j. The hyperedges of 2Reg(K
n
) are now de-
fined by E
ij
≡ {{(e
ij
, e
ik
)|k 6= i, j}
n
k=1
, {(e
ij
, e
kj
)|k 6=
i, j}
n
k=1
}, where i, j ∈ {1, . . . , n} and i 6= j. Hence,
2Reg(K
n
) is a hypergraph with
n(n−1)
2
hyperedges
with 2(n − 2) nodes per hyperedge, each node (e.g.,
(e
ij
, e
ik
)) appearing in two hyperedges (e.g., E
ij
and
E
ik
). The total number of nodes in the hypergraph
is
n(n−1)(n−2)
2
. From Theorem 2, 2Reg(K
n
) is KS-
uncolourable if and only if
n
C
2
is odd.
Complete bipartite graphs under 2Reg(·)
Having looked at the behaviour of n-cycle graphs and
complete graphs K
n
under 2Reg(·), let us now see how
the family of complete bipartite graphs, K
m,n
, can
lead to KS-uncolorable scenarios and how this par-
ticular representation in terms of complete bipartite
graphs helps us better understand the common ideas
underlying constructions of many KS-uncolorable sce-
narios. A contextuality scenario 2Reg(K
m,n
) can be
obtained from any complete bipartite graph K
m,n
in
the following steps:
1. K
m,n
is given by a set of vertices V =
{v
1
, v
2
, . . . , v
m
, t
1
, t
2
, . . . , t
n
} and edges E =
{e
ij
≡ {v
i
, t
j
}|i ∈ {1, 2, . . . , m}, j ∈
{1, 2, . . . , n}}.
2. Edges of K
m,n
become edges of
2Reg(K
m,n
), so the contextuality scenario
we construct will have mn hyperedges,
{f
11
, f
12
, . . . , f
1n
, . . . , f
m1
, . . . , f
mn
}.
3. Every pair of edges that share a node in K
m,n
defines a node in 2Reg(K
m,n
), e.g.,
{(e
11
, e
12
), . . . , (e
11
, e
1m
), (e
11
, e
21
), . . . , (e
11
, e
n1
)}
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 8
1
11
12
13
2Reg(.)
1 2 3
K
1,3
2Reg(K
1,3
)
Figure 4: K
1,3
under 2Reg(·).
1
11
12 13 14
15
2Reg(.)
1 2 3 4 5
K
1,5
2Reg(K
1,5
)
Figure 5: K
1,5
under 2Reg(·). Here we denote the hyper-
edges by lines rather than loops for simplicity. Each hyper-
edge contains 4 nodes and we have 5 hyperedges.
are all the (m−1)+(n−1) nodes in the hyperedge
f
11
of 2Reg(K
m,n
). Hence, every hyperedge of
2Reg(K
m,n
) has (m − 1) + (n − 1) nodes.
4. Since every node appears in two hyperedges of
2Reg(K
m,n
), 2Reg(K
m,n
) has
mn((m−1)+(n−1))
2
nodes.
5. Hence: 2Reg(K
m,n
) is a contextuality scenario
with
mn((m−1)+(n−1))
2
nodes carved up into mn
hyperedges with (m−1)+(n−1) nodes per hyper-
edge and each node appearing in two hyperedges.
Lemma 3. 2Reg(K
m,n
) is a KS-uncolourable contex-
tuality scenario if and only if mn (> 1) is odd.
Proof. This follows from Theorem 2 since mn is the
number of contexts in 2Reg(K
m,n
).
Examples of known KS-uncolourable contextuality
scenarios that are of the type 2Reg(K
m,n
):
1. The 3-hypercycle (or “triangle”) contextuality
scenario from K
1,3
: 2Reg(K
1,3
). This is the sim-
plest KS-uncolourable scenario. It does not ad-
mit a KS set. See Fig. 4
2. 2Reg(K
1,5
) in Ref. [31]. No KS set has been
found for this scenario. The assignments in
Ref. [31] are subnormalized (that is, the projec-
tors in a basis do not add up to identity) and do
not satisfy the definition of a KS set. See Fig. 5.
3. The seven-context KS construction (21 rays in 6
dimensions): 2Reg(K
1,7
) [32]. See Fig. 6.
4. The CEGA contextuality scenario (18 rays in 4
dimensions): 2Reg(K
3,3
) [20]. See Fig. 2.
Theorem 3. 2Reg(G) is a 3-hypercycle if and only if
G is
1. the claw graph, i.e., bipartite graph K
1,3
, or
2. the 3-cycle or triangle graph, i.e. a graph iso-
morphic to {{v
1
, v
2
}, {v
2
, v
3
}, {v
3
, v
1
}}.
Proof. The proof is just by explicitly exhausting all
possible 3-edge graphs and verifying whether they
lead to a 3-hypercycle.
For 2Reg(G) to be a 3-hypercycle, G must have
three edges, say {e
1
, e
2
, e
3
}. Further, since each node
2Reg(G) is defined by a pair of edges in {e
1
, e
2
, e
3
},
and since there are only three distinct pairs of edges in
{e
1
, e
2
, e
3
}, it must be the case that the intersection
of each pair of edges corresponds to a vertex in G.
However, not every vertex in G needs to be in the
intersection of two edges.
A vertex in G can be of degree 1, 2, or 3. The
fact that every pair of edges in G must have a non-
empty intersection means that there exists at least
one vertex of degree 2 in G given by e
1
∩ e
2
or e
2
∩ e
3
or e
3
∩ e
1
. Let us denote the edges sharing this vertex
by {e
i
, e
j
} (i 6= j ∈ {1, 2, 3}), so that the vertex is
e
i
∩ e
j
. We thus know that G has at least 3 vertices.
The only option for the remaining edge, denoted e
k
(k 6= i, j ∈ {1, 2, 3}), in G – for 2Reg(G) to be a
3-hypercyle – is then to attach to the vertex e
i
∩ e
j
,
thus producing a claw graph K
1,3
with 4 vertices and 3
edges, or to attach to the two degree 1 vertices of edges
e
i
, e
j
, thus forming a 3-cycle or triangle graph.
Corollary 1. The mapping 2Reg(·) is not invertible.
Proof. This follows from Theorem 3. There does
not exist an inverse mapping that, when applied to
2Reg(G) would yield G: in general, 2Reg(·) is a many-
to-one mapping, hence non-invertible. The example
of Theorem 3 illustrates this.
Theorem 4. 2Reg(G) is a k-hypercycle, k ≥ 4, if
and only if G is a k-cycle.
10
Proof. Since 2Reg(G) is a k-hypercycle, G must have
k edges, say {e
1
, e
2
, . . . , e
k
}. Since the nodes of
2Reg(G) are defined by pairs of edges in G with non-
empty intersection, there must be k such pairs in
{e
1
, e
2
, . . . , e
k
}. The intersection of each such pair is
a vertex of G, hence G has at least k vertices. The de-
gree of any vertex of G cannot be more than 2: for any
vertex of degree 3 or more in G one would have the
presence of a 3-hypercycle in 2Reg(G) (which could
not then be a k-hypercycle, k ≥ 4) from Theorem
3. Hence, G is a graph with k edges and at least k
vertices such that k pairs of edges have a non-empty
intersection and each vertex of G is of degree no more
than 2. These constraints fix G to be a k-cycle: any
10
Plus superfluous vertices of degree 0, but these can be safely
ignored.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 9
11
12 13
14 15 16
17
1
2Reg(.)
1 2 3 4 5 6 7
2Reg(K
1,7
)
K
1,7
Figure 6: K
1,7
under 2Reg(·).
change to the k-cycle can only be done by adding ver-
tices of degree 0, but no edges can be added. We can
safely ignore such superfluous vertices (of degree 0)
since they do not change anything about 2Reg(G).
Combining the above with Lemma 1, we have our
result.
The contextuality scenario 2Reg(G) obtained from
a graph G can be viewed as a matching scenario of
another graph L(G), the line graph of G, in the sense
of Ref. [25]. We comment on this connection in Ap-
pendix A. In the next section we define some param-
eters to characterize arbitrary contextuality scenarios
in a systematic manner before we present our general
approach to obtaining noise-robust noncontextuality
inequalities from KS-uncolourable scenarios.
4 Uniform contextuality scenar-
ios, their parameters, and KS-
uncolourability
Before we can talk about noise-robust noncontextual-
ity inequalities obtained from KS-uncolourable con-
textuality scenarios, we need a way to detect KS-
uncolourability of a given scenario. We now define
some parameters that we will use in our discussion of
KS-uncolourability and then provide some (sufficient)
conditions for KS-uncolourability of a contextuality
scenario. In the process, we also answer some open
questions that were posed in Ref. [33]. The conditions
we obtain are enough for the contextuality scenarios
we consider in this paper but the question of identify-
ing conditions that are both necessary and sufficient
for KS-uncolourability of a contextuality scenario re-
mains open, despite some previous research hinting at
ways in which this might be done [34, 35].
Consider a contextuality scenario, H = (W, F ),
where W is its set of nodes and F its set of hyper-
edges. Further, the scenario is such that there are d
nodes in each hyperedge (that is, the hypergraph is
d-uniform), |F | hyperedges, and |W | nodes in all. Let
m be the number of nodes that appear in more than
one hyperedge. We then have the following relations:
m ≤ |W | ≤ d|F |. (11)
More precisely,
d|F | =
D
X
k=1
kn
k
,
|W | =
D
X
k=1
n
k
,
m =
D
X
k=2
n
k
= |W | − n
1
, (12)
where n
k
is the number of nodes which each appear
in k distinct hyperedges (i.e., there exist n
k
nodes
of degree k) and D is the largest number of distinct
hyperedges any node can appear in (i.e., there exists
a node which appears in D distinct hyperedges but
no node that appears in D + 1 distinct hyperedges or,
equivalently, D is the degree of a node of maximum
degree in the hypergraph). Note that
d|F |
2
=
n
1
2
+ n
2
+
D
X
k=3
kn
k
2
. (13)
We therefore have
m ≤
d|F |
2
(14)
for any contextuality scenario.
In Ref. [33], an algorithmic way to enumerate KS-
uncolourable hypergraphs which admit KS sets was
presented. The observations noted in Ref. [33] as a
result of this algorithmic enumeration led to some
conjectures, some of which we now answer by sim-
ply noting constraints between the parameters defined
above.
An open question in Sec. 5(i) of Ref. [33] was:
Is it true for arbitrary d that m ≤
d|F |
2
(for KS-
uncolourable hypergraphs which admit KS sets)? We
have just answered this question in the affirmative
(see Eq. (14)) for all d-uniform contextuality scenar-
ios, not just those which are KS-uncolourable and ad-
mit KS sets. Further,
n
1
= 0 ⇔ m = |W | ⇒ |W | ≤
d|F |
2
, (15)
that is, if every node in a contextuality scenario ap-
pears in at least 2 distinct hyperedges, then m =
|W | ≤
d|F |
2
. More precisely,
|W | ≤
d|F |
2
⇔ n
1
≤
D
X
k=3
(k − 2)n
k
= n
3
+ 2n
4
+ 3n
5
+ · · · + (D − 2)n
D
.
This characterizes all the contextuality scenarios
for which |W | ≤
d|F |
2
. Hence, for any n
1
> 0, we
must have enough nodes with degree greater than 2
for the relation |W | ≤
d|F |
2
to hold. An open prob-
lem in Sec. 5(ii) of Ref. [33] asks: Given a fixed d,
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 10
at what value of |W | does the inequality |W | ≤
d|F |
2
cease to hold? We have shown that |W | >
d|F |
2
iff
n
1
>
P
D
k=3
(k − 2)n
k
. That is, roughly speaking, the
inequality |W | ≤
d|F |
2
ceases to hold when there are
way too many nodes of degree 1 than there are nodes
of degree 3 or higher.
Indeed, the only known exception to |W | ≤
d|F |
2
that Ref. [33] finds is the construction due to Kochen
and Specker [1] (henceforth called the “KS67 con-
struction”) with |W | = 192, d = 3, |F | = 118, so
that
d|F |
2
= 177 and we have |W | >
d|F |
2
. However,
it is still the case that m = 117 <
d|F |
2
= 177 (strict
inequality because some of the nodes appear in more
than 2 hyperedges). Note that in this case n
1
= 75
which is way greater than n
3
+ 7n
9
= 45.
4.1 Conditions on the parameters of a contex-
tuality scenario for its KS-uncolourability
We have d|F | =
P
D
k=1
kn
k
, |W | =
P
D
i=1
n
k
, and
m = |W | − n
1
for any d-uniform contextuality sce-
nario. We want to find conditions that rule out the
existence of a {0, 1}-valued solution for the system of
|F | normalization equations in |W | variables with d
variables in each equation.
4.1.1 2-regular contextuality scenarios
From Theorem 2 we know that any 2-regular contex-
tuality scenario is KS-uncolourable if and only if it
has an odd number of contexts.
4.1.2 d-uniform and 2-regular contextuality scenarios
of type 2Reg(G)
For d-uniform and 2-regular contextuality scenarios
(every node of degree 2) we have m = |W | =
d|F |
2
.
There are |F | normalization equations in
d|F |
2
vari-
ables, each variable appearing in two equations.
For any graph G, 2Reg(G) is a 2-regular contex-
tuality scenario and 2Reg(G) is KS-uncolourable if
and only if |F | is odd (Theorem 2). If we further
require 2Reg(G) to be a d-uniform contextuality sce-
nario, then d must be even for any 2Reg(G) if |F | is
odd.
11
Hence, KS-uncolourability holds for those (and
only those) d-uniform 2Reg(G) contextuality sce-
narios which have even d and odd |F |: any KS
set satisfying such KS-uncolourability can there-
fore only be constructed on an even-dimensional
Hilbert space.
All proofs of the Kochen-Specker theorem relying
on d-uniform contextuality scenarios of type 2Reg(G)
11
For |W | =
d|F |
2
to be an integer.
must therefore require an even-dimensional Hilbert
space. In other words, it is impossible to realize KS
sets for these scenarios in odd dimensions.
4.1.3 d-uniform contextuality scenarios
For more general d-uniform hypergraphs — that is,
not necessarily restricted to those of the type 2Reg(G)
— we have: |F | equations with |W | variables, n
k
of them appearing in exactly k equations (for all
k ∈ {1, 2, . . . , D}), and each equation a sum of d vari-
ables adding up to 1. Such a hypergraph is said to
be KS-uncolourable when these equations do not ad-
mit a {0, 1}-valued solution. We now give some suf-
ficient conditions for KS-uncolourability of these hy-
pergraphs.
Let us denote by W
k
the set of nodes such that each
node in the set appears in k equations (contexts), i.e.,
W
k
= {w
(k)
j
|j ∈ {1, . . . , n
k
}}, where k ∈ {1, . . . , D}.
The cardinality of the set W
k
is n
k
. On adding up
the |F| equations, we have:
D
X
k=1
k
n
k
X
j=1
p(w
(k)
j
)
= |F |, (16)
where p(w
(k)
j
) ∈ {0, 1} denotes the value assigned to
node w
(k)
j
.
Lemma 4.
P
D
k=1
k
P
n
k
j=1
p(w
(k)
j
)
, where p(w
(k)
j
) ∈
{0, 1}, is an even number if and only if an even num-
ber of nodes of each odd degree k (such that n
k
> 0)
are assigned the value 1, i.e.,
n
k
X
j=1
p(w
(k)
j
)
is an even number for all odd k with n
k
> 0.
Proof. This should be clear from noting that
D
X
k=1
k
n
k
X
j=1
p(w
(k)
j
)
(17)
=
X
k even
k
n
k
X
j=1
p(w
(k)
j
)
+
X
k odd
k
n
k
X
j=1
p(w
(k)
j
)
.
The even k part of the sum is even simply because all
the terms in the sum over k are even. The odd k part
of the sum over k is even if and only if in each term
P
n
k
j=1
p(w
(k)
j
) in the sum is even, i.e.,
n
k
X
j=1
p(w
(k)
j
)
is an even number for all odd k with n
k
> 0.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 11
Lemma 5. A KS contradiction arises if one of
the following holds:
1. |F | is odd and
P
n
k
j=1
p(w
(k)
j
) is an even num-
ber for all odd k with n
k
> 0.
2. |F | is even and there exists an odd k with
n
k
> 0 such that
P
n
k
j=1
p(w
(k)
j
) is an odd
number.
Proof. This is trivially the case because an even num-
ber 6= an odd number.
4.2 The Kochen-Specker (1967) construction
In terms of the parameters we have defined, the KS-
uncolourability of the KS67 construction can be seen
from the following:
• d = 3, n
1
= 75(= 192 − 117), n
2
= 90, n
3
= 24,
n
9
= 3, and n
k
= 0 for all other k.
• |W | = n
1
+ n
2
+ n
3
+ n
9
= 192.
• m = n
2
+ n
3
+ n
9
= 90 + 24 + 3 = 117.
• d|F | = n
1
+2n
2
+3n
3
+9n
9
= 75+180+72+27 =
354, hence |F | = 354/3 = 118.
• m = |W |−n
1
= 117 < |W | = 192, m < d|F |/2 =
177 but |W | > d|F |/2 = 177.
• d = 3, |F | = 118, |W | = 192, m = 117.
On adding up the 118 normalization constraints on
KS67, we have:
75
X
j=1
p(w
(1)
j
) + 2
90
X
j=1
p(w
(2)
j
)
+ 3
24
X
j=1
p(w
(3)
j
) + 9
3
X
j=1
p(w
(9)
j
)
= 118. (18)
We know that one of the normalization equations is
3
X
j=1
p(w
(9)
j
) = 1,
hence there exists an odd k = 9 (with n
k
= n
9
= 3 >
0) such that
P
3
j=1
p(w
(9)
j
) = 1, an odd number. Since
|F | = 118 is even, we have a KS contradiction for this
hypergraph from Lemma 5.
5 Contextuality scenarios and ex-
tremal probabilistic models on them
Once we know that a contextuality scenario is KS-
uncolourable, what can we say about the structure of
extremal probabilistic models on it? If the extremal
probabilistic models on a contextuality scenario ad-
mit a “nice” characterization, then this can be used
in obtaining noise-robust noncontextuality inequali-
ties. In this section, we consider contextuality scenar-
ios of type 2Reg(·) and extremal probabilistic models
on them. Later we will use this characterization for
obtaining noise-robust noncontextuality inequalities.
Note that since 2Reg(G) are matching scenarios in
the sense of Ref. [25], our characterization of extremal
probabilistic models presented below is already known
from graph-theoretic methods used in Ref. [25]. All
we have done below is to provide an alternative self-
contained proof that proceeds directly from Theorem
1 instead of relying on known results from graph the-
ory. This is partly motivated by a need to explore
in more generality (than done in Ref. [25]) the conse-
quences of Theorem 1, many of which we will later use
in obtaining noise-robust noncontextuality inequali-
ties.
Theorem 5. Each extremal probabilistic model on
2Reg(G) for any graph G is an extension of the
unique probabilistic model on an induced subscenario
consisting of some set of disjoint odd k-hypercycles,
k ∈ {3, 5, . . . }, and/or some set of singleton contexts.
Hence, each extremal probabilistic model on 2Reg(G)
assigns probabilities from {0,
1
2
, 1} to the nodes of
2Reg(G).
Proof. We know that each extremal probabilistic
model p on H ≡ 2Reg(G) is in one-to-one correspon-
dence with the set of nodes to which it assigns nonzero
probability: S
p
≡ {w ∈ W (H)|p(w) 6= 0}.
For any graph G, every node in H(= 2Reg(G)) ap-
pears in two contexts. Hence, in any induced subsce-
nario H
S
p
defined by a subset of nodes of H given by
S
p
(for extremal probabilistic model p on H), none of
the nodes can appear in more than two contexts and
none of them can be assigned probability zero. This
leaves two possibilities for nodes in H
S
p
: either a node
appears in one context or it appears in two contexts.
Let us denote by q
S
p
the restriction of extremal
probabilistic model p on H to the unique probabilistic
model q
S
p
on H
S
p
: q
S
p
(w) = p(w) > 0 for all w ∈ S
p
(and p(w) = 0 for all w ∈ W \S
p
).
Consider the set of nodes S
(1)
p
⊆ S
p
such that
each of these nodes appears in exactly one context in
H
S
p
and the subhypergraph H
1
obtained from H
S
p
by deleting all nodes in S
p
\S
(1)
p
and all hyperedges
f ∈ F (H
S
p
) such that f ∩ S
(1)
p
= ∅. H
1
is then a
hypergraph consisting of |S
(1)
p
| nodes, each contained
in its own singleton hyperedge, hence H
1
admits the
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 12
unique probabilistic model q
S
(1)
p
assigning probability
1 to each node: q
S
(1)
p
(w) = p(w) = 1 for all w ∈ S
(1)
p
.
That is, H
1
is a union of (disjoint) singleton contexts.
Now consider the remaining set of nodes S
(2)
p
⊆ S
p
(where S
(2)
p
≡ S
p
\S
(1)
p
) such that each node appears
in exactly two contexts in H
S
p
and the subhypergraph
H
2
obtained from H
S
p
by deleting all nodes in S
(1)
p
and all hyperedges f ∈ F (H
S
p
) such that f ∩S
(2)
p
= ∅.
We will now show that H
2
is a union of disjoint odd
k-hypercycles, k ≥ 3: for H
2
, the number of nodes of
degree 2 is n
2
= |S
(2)
p
|, and the restriction of extremal
probabilistic model p > 0 on H to nodes in H
2
, de-
fined by q
S
(2)
p
(w) = p(w) for all w ∈ S
(2)
p
, is also
extremal on H
2
(otherwise p > 0 on H can’t be ex-
tremal). Now, the existence of a probabilistic model
q
S
(2)
p
> 0 on H
2
that is extremal ⇔ q
S
(2)
p
> 0 on H
2
is unique (from Theorem 1) ⇒ |F (H
2
)| ≥ |W (H
2
)|
(where W (H
2
) = S
(2)
p
). From n
2
(H
2
) = |W (H
2
)|,
it follows that
P
f∈F (H
2
)
d(f) = 2|W (H
2
)|, where
d(f) > 1 for all f ∈ F (H
2
) (because d(f) = 1 for
any f ∈ F(H
2
) would be in conflict with the require-
ment that n
2
(H
2
) = |W (H
2
)| and q
S
(2)
p
> 0 on H
2
).
Now:
min
d(f):f ∈F (H
2
)
X
f∈F (H
2
)
d(f)
= 2|F (H
2
)|,
achieved at d(f) = 2 for all f ∈ F (H
2
). Hence,
X
f∈F (H
2
)
d(f) ≥ 2|F (H
2
)|.
But since
P
f∈F (H
2
)
d(f) = 2|W (H
2
)| and |W (H
2
)| ≤
|F (H
2
)|, we have that
X
f∈F (H
2
)
d(f) ≤ 2|F (H
2
)|.
Overall,
2|F (H
2
)| ≤
X
f∈F (H
2
)
d(f) ≤ 2|F (H
2
)|,
which means that
P
f∈F (H
2
)
d(f) = 2|F (H
2
)|. We
therefore have: |F (H
2
)| = |W(H
2
)| and d(f) = 2 for
all f ∈ F (H
2
). This gives us the following character-
ization of H
2
:
n
2
(H
2
) = |W (H
2
)|, |F(H
2
)| = |W (H
2
)|, and
d(f) = 2 for all f ∈ F (H
2
)
⇔
H
2
is a union of disjoint k-hypercycles (k ≥ 3).
This follows from noting that, firstly, H
2
is a 2-
uniform hypergraph (that is, d(f) = 2 for all f ∈
F (H
2
)), hence really a graph. Secondly, a k-cycle
(k ≥ 3) is defined as a connected graph where each
vertex is of degree 2 and the number of edges is equal
to the number of vertices. Hence, a graph where each
vertex is of degree 2 and the number of edges is equal
to the number of vertices is a union of disjoint k-
cycles. H
2
is just such a (hyper)graph.
Together with the fact that H
2
admits the unique
probabilistic model q
S
(2)
p
> 0, this means that the k-
hypercycles in the disjoint union have, in fact, odd
k ≥ 3. This is because even k-hypercycles admit
non-unique deterministic extremal probabilistic mod-
els which allow for assignment of probability 0 to some
nodes. That is,
n
2
(H
2
) = |W (H
2
)|, |F(H
2
)| = |W (H
2
)|, d(f) = 2 for
all f ∈ F(H
2
), and H
2
admits a unique probabilistic
model
⇔
H
2
is a union of disjoint odd k-hypercycles (k ≥ 3).
This in turn implies that the unique probabilistic
model q
S
(2)
p
> 0 is in fact given by q
S
(2)
p
(w) =
1
2
for
all w ∈ S
(2)
p
.
Hence: every extremal probabilistic model p on
H = 2Reg(G) is given by the induced subscenario H
S
p
consisting of a disjoint union of H
1
and H
2
, the for-
mer a set of singleton contexts and the latter a union
of disjoint odd k-hypercycles. Overall, p(w) = 1 for
all w ∈ S
(1)
p
, p(w) =
1
2
for all w ∈ S
(2)
p
, and p(w) = 0
for all w ∈ W \S
p
(where S
p
= S
(1)
p
t S
(2)
p
).
Combining Theorems 3, 4, and 5, we have that we
only need to look for the presence of K
1,3
and k-cycles
(k ≥ 3) in any graph G in order to ascertain all the ex-
tremal probabilistic models on the scenario 2Reg(G).
Corollary 2. G contains a subgraph K
1,3
or an odd
k-cycle (k ≥ 3) if and only if the indeterministic ex-
tremal probabilistic models on 2Reg(G) correspond to
k-hypercycle extremal probabilistic models, k ≥ 3.
Theorem 6. Every scenario 2Reg(K
m,n
) constructed
from bipartite graph K
m,n
(with mn > 1 odd) contain-
ing a bipartite subgraph K
1,k
or K
k,1
, where k(≤ m, n)
is odd, admits extremal probabilistic model(s) cor-
responding to induced subscenarios obtained from a
union of the k-hypercycle with some singletons.
Proof. Taking the complement of K
m,n
, once sub-
graph K
1,k
or K
k,1
is removed, we denote the result-
ing graph as G(K
m,n
\K
1,k
) or G(K
m,n
\K
k,1
), respec-
tively. Since both G(K
m,n
\K
1,k
) and G(K
m,n
\K
k,1
)
have mn − k (an even number) of edges, from
Theorem 2 we have that 2Reg(G(K
m,n
\K
1,k
)) and
2Reg(G(K
m,n
\K
k,1
)) are KS-colourable and therefore
admit extremal probabilistic models induced entirely
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 13
by singletons.
12
Now consider an induced subscenario
of 2Reg(G(K
m,n
\K
1,k
)) or 2Reg(G(K
m,n
\K
k,1
))
that consists entirely of singletons so that the
number of hyperedges in 2Reg(G(K
m,n
\K
1,k
)) or
2Reg(G(K
m,n
\K
k,1
)) is twice the number of single-
tons in this induced subscenario.
13
Extending this
induced subscenario by adding a k-hypercycle (dis-
joint from the subscenario) leads to an induced sub-
scenario of 2Reg(K
m,n
), namely, one that is a union
of a k-hypercycle with the singletons. (See Fig. 7 for
an illustration in the case of K
3,3
.)
6 Noise-robust noncontextuality in-
equalities from a hypergraph invariant
We are finally in a position to use the understand-
ing developed so far to obtain noise-robust noncontex-
tuality inequalities for KS-uncolourable contextuality
scenarios. The noise-robust noncontextuality inequal-
ities reported in Ref. [6] and the more fine-grained
ones for the case of the 18 ray scenario [20] reported
in Ref. [36] will be seen to be special cases of our in-
equalities. We begin with an outline of the general
framework within which our noise-robust noncontex-
tuality inequalities will be obtained. In particular, we
will introduce a hypergraph invariant and make pre-
cise the role that it plays in our inequalities. This
framework is applicable to any KS-uncolourable con-
textuality scenario and we will study some well-known
examples of such scenarios. This is in contrast to the
framework of Ref. [14] which is only applicable to con-
textuality scenarios that are KS-colourable and also
satisfy the property that all probabilistic models on
them obey consistent exclusivity `a la AFLS [25].
12
Note that when k = n, G(K
m,n
\K
1,k=n
)=K
m−1,n
, and
when k = m, G(K
m,n
\K
k=m,1
)=K
m,n−1
. That is, the sub-
graphs are complete bipartite graphs in these cases, but not
otherwise.
13
This factor of two arises because the contextuality scenarios
are 2-regular, i.e., every vertex appears in two hyperedges.
1 2 3
1 2 3
1 2
1 2 3
11
12
32
33
23
21
22
31 13
11
12
23
21
22
13
3
1 2 3
32
33
31
(11)-(21)
(22)-(23)
(12)-(13)
(31)-(32)
(31)-(33)
(32)-(33)
(a)
(b)
(c)
2Reg(.) 2Reg(.) 2Reg(.)
Figure 7: (a) K
3,3
and its two subgraphs, K
2,3
and K
1,3
,
(b) the contextuality scenarios obtained under the mapping
2Reg(·), and (c) the induced subscenarios corresponding to
extremal probabilistic models on the respective contextuality
scenarios, 2Reg(K
2,3
), 2Reg(K
1,3
), and 2Reg(K
3,3
). The
induced subscenario corresponding to an extremal probabilis-
tic model on 2Reg(K
3,3
) is a disjoint union of induced sub-
scenarios corresponding to 2Reg(K
2,3
) and 2Reg(K
1,3
).
6.1 Operational equivalences
In keeping with the treatment in Ref. [6], we asso-
ciate with each KS-uncolourable scenario two kinds
of hypergraphs: one corresponding to the operational
equivalences presumed between measurement events
and another corresponding to operational equiva-
lences presumed between source events.
14
Assuming the contextuality scenario consists of
n (measurement) contexts with d nodes each,
we consider n measurement settings M
i
, i ∈
{1, 2, . . . , n} ≡ [n], each with d possible outcomes,
m
i
∈ {1, 2, . . . , d} ≡ [d]. We assume opera-
tional equivalences between the measurement out-
comes [m
i
|M
i
] that are reflected in the contextu-
ality scenario. These are of the type: [m
i
|M
i
] '
[m
j
|M
j
], for some pairs {i, j} ⊂ {1, 2, . . . , d}. The as-
sumption of measurement noncontextuality then says:
ξ(m
i
|M
i
, λ) = ξ(m
j
|M
j
, λ) ∀λ ∈ Λ.
We also consider source settings S
i
, i ∈ [n], each
with d possible outcomes s
i
∈ [d], such that the follow-
ing operational equivalences hold among the sources:
∀[m|M] :
d
X
s
i
=1
p(m, s
i
|M, S
i
) =
d
X
s
j
=1
p(m, s
j
|M, S
j
),
for all i, j ∈ [n]. (19)
That is,
[>|S
1
] ' [>|S
2
] ' · · · ' [>|S
n
]. (20)
14
We are assuming that in any experimental test of noncon-
textuality, these operational equivalences have been established
[7].
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 14
[1|M
1
]
[2|M
1
]
[3|M
1
]
[4|M
1
]
[1|M
2
]
[2|M
2
]
[3|M
2
]
[4|M
2
]
[1|M
3
]
[2|M
3
]
[3|M
3
]
[4|M
3
]
[1|M
4
][2|M
4
]
[3|M
4
][4|M
4
]
[1|M
5
]
[2|M
5
]
[3|M
5
]
[1|M
6
]
[2|M
6
]
[3|M
6
]
[4|M
6
]
[1|M
7
]
[2|M
7
]
[3|M
7
]
[4|M
7
]
[1|M
8
]
[2|M
8
]
[3|M
8
]
[4|M
8
]
[1|M
9
]
[2|M
9
]
[3|M
9
]
[4|M
9
]
[4|M
5
]
:
Figure 8: Operational equivalences between measurements
(top) and operational equivalences between sources (bot-
tom).
Given that
p(m, s|M, S) =
X
λ∈Λ
ξ(m|M, λ)µ(s|S, λ)µ(λ|S),
the assumption of preparation noncontextuality then
says:
µ(λ|S
1
) = µ(λ|S
2
) = · · · = µ(λ|S
n
) ≡ ν(λ) ∀λ ∈ Λ.
(21)
Here,
µ(λ|S
i
) ≡
d
X
s
i
=1
µ(λ|S
i
, s
i
)p(s
i
|S
i
), for all i ∈ [n].
(22)
We recall the measurement events and source events
hypergraphs for the example of Ref. [6] in Fig. 8,
where n = 9 and d = 4. The noncontextual-
ity inequality of Ref. [6] that follows from the op-
erational equivalences for sources and measurements
then reads:
A ≡
1
9
9
X
i=1
1
4
4
X
m
i
=1
p(m
i
|M
i
, S
i
, s
i
= m
i
)
≤ max
λ∈Λ
1
9
9
X
i=1
ζ(M
i
, λ) =
5
6
, (23)
where ζ(M
i
, λ) ≡ max
m
i
ξ(m
i
|M
i
, λ) for all i ∈
{1, 2, . . . , 9}, so that
1
9
P
9
i=1
ζ(M
i
, λ) is the average
max-probability for a given λ ∈ Λ. Hence, the
noncontextuality inequality bounds A by the maxi-
mum average max-probability of the measurements
M
i
possible in any ontological model. Noting that
p(s
i
= m
i
|S
i
) =
1
4
for all m
i
∈ [4] for the scenario of
Ref. [6], we can rewrite the quantity A as:
A =
1
9
9
X
i=1
4
X
s
i
=1
p(m
i
= s
i
, s
i
|M
i
, S
i
)
≡
1
9
9
X
i=1
4
X
x=1
p(m
i
= x, s
i
= x|M
i
, S
i
). (24)
In the general case of n measurement procedures with
d outcomes each, the expression for A reads
A ≡
1
n
n
X
i=1
d
X
x=1
p(m
i
= x, s
i
= x|M
i
, S
i
). (25)
Furthermore, we need not even restrict ourselves to
a uniform average of the source-measurement corre-
lation over the source and measurement settings and
allow instead a weighted average given by some prob-
ability distribution q ≡ {q
i
}
n
i=1
, where q
i
≥ 0 for all i
and
P
i
q
i
= 1. The quantity A then becomes the
source-measurement correlation quantity Corr that
was previously defined in Ref. [14] and can be upper
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 15
bounded as follows (following Ref. [6]):
Corr
=
n
X
i=1
q
i
d
X
x=1
p(m
i
= x, s
i
= x|M
i
, S
i
),
=
n
X
i=1
q
i
d
X
x=1
X
λ∈Λ
ξ(m
i
= x|M
i
, λ)µ(s
i
= x|S
i
, λ)µ(λ|S
i
),
≤
n
X
i=1
q
i
d
X
s
i
=1
X
λ∈Λ
max
m
i
∈[d]
ξ(m
i
|M
i
, λ)µ(s
i
|S
i
, λ)µ(λ|S
i
),
=
X
λ∈Λ
n
X
i=1
q
i
ζ(M
i
, λ)
d
X
s
i
=1
µ(s
i
|S
i
, λ)µ(λ|S
i
),
=
X
λ∈Λ
n
X
i=1
q
i
ζ(M
i
, λ)µ(λ|S
i
)
!
,
=
X
λ∈Λ
n
X
i=1
q
i
ζ(M
i
, λ)
!
ν(λ),
(using preparation noncontextuality)
≤ max
λ∈Λ
n
X
i=1
q
i
ζ(M
i
, λ)
(using convexity)
≡ β(Γ, q) < 1 (for some choices of q)
(using measurement noncontextuality and
KS-uncolourability). (26)
Here, β(Γ, q) is the weighted max-predictability for a
contextuality scenario Γ, first defined in Ref. [14] as
β(Γ, q) ≡ max
λ∈Λ
ind
n
X
i=1
q
i
ζ(M
i
, λ), (27)
where Λ
ind
is the set of ontic states which all assign
indeterministic extremal probabilistic models on Γ,
i.e., extremal probabilistic models with probabilities
valued in the interval (0, 1) for at least one measure-
ment context in the contextuality scenario. In this pa-
per, the contextuality scenario Γ is KS-uncolourable,
hence the qualifier that the maximization in the defi-
nition of β(Γ, q) is taken over only the ontic states that
assign indeterministic extremal probabilistic models
to measurement events in Γ (that is, Λ
ind
) is unnec-
essary: all ontic states assigning probabilities to the
measurement events of a KS-uncolourable Γ must nec-
essarily correspond to indeterministic extremal prob-
abilistic models (i.e., Λ = Λ
ind
). Note also that
β(Γ, q) need not always be strictly less than 1 for
KS-uncolourable Γ: this can happen, for example, if
q is supported only on those contexts (if they exist)
which are all assigned {0, 1}-valued probabilities (i.e.,
they are deterministic) by some extremal probabilis-
tic model on Γ. On the other hand, we know that
there always exists a choice of q such that β(Γ, q) < 1
simply because of the KS-uncolourability of Γ, e.g.,
any choice where q is supported on all the contexts of
Γ — such as q being a uniform probability distribu-
tion over the measurement contexts — so that there
is no extremal probabilistic model that makes all the
contexts deterministic.
In the following sections, we will show how bounds
on Corr when q is supported on certain (sub)sets of
contexts (which we will call minimally indeterministic
sets of contexts, or MISCs, below) can be obtained
from conceptual arguments instead of a brute-force
computational approach. We will show that for such
MISCs (instead of all the contexts in a contextuality
scenario), we can obtain noncontextuality inequalities
of the type:
Corr
q
≡
c
X
i=1
q
r
i
d
X
x=1
p(m
r
i
= x, s
r
i
= x|M
r
i
, S
r
i
)
≤ β(Γ, q) < 1, (28)
where c (< n) is the number of contexts in a MISC,
each context denoting a measurement setting M
r
i
,
where q
r
i
> 0 for all i ∈ {1, 2, . . . , c},
P
c
i=1
q
r
i
= 1,
and r
i
∈ {1, 2, . . . , n} are all distinct.
15
If the contextuality scenario Γ were KS-colourable,
then we would have max
λ∈Λ
P
n
i=1
q
i
ζ(M
i
, λ) = 1 for
any choice of q (corresponding to any set of c con-
texts); however, since Γ is KS-uncolourable, there nec-
essarily exist one or more sets of c contexts (for some
c) such that max
λ∈Λ
P
n
i=1
q
i
ζ(M
i
, λ) < 1 when q is
supported on such sets. Note that while in the for-
mer case β(Γ, q) is undefined, in the latter case we
have β(Γ, q) = max
λ∈Λ
P
n
i=1
q
i
ζ(M
i
, λ). The MISCs
we define below are examples of such sets of c con-
texts for which β(Γ, q) < 1. Finding a MISC and
computing its β(Γ, q) value yields a noise-robust non-
contextuality inequality in our framework.
We will be interested in finding all the irreducible
MISCs (or as we define them later, “irrMISCs”) in a
KS-uncolourable contextuality scenario: finding them
and evaluating their β(Γ, q) values amounts to identi-
fying a minimal set of independent noncontextuality
inequalities for that scenario; from these, all the other
MISC inequalities can be obtained by coarse-graining.
15
Note that this inequality follows from the assumptions of
preparation and measurement noncontextuality, as in Eq. (26),
hence it is a noise-robust “noncontextuality inequality”. Un-
like the noise-robust noncontextuality inequalities of Ref. [14],
however, the noncontextuality inequalities in this paper are
not (in any sense) “generalizations” of KS-noncontextuality
inequalities `a la CSW [24]. The set of probabilistic models
on a KS-uncolourable contextuality scenario that satisfy KS-
noncontextuality is empty, i.e., the set of “classical models” in
the terminology of Ref. [25] is empy for such scenarios. Hence,
any probabilistic model on such a scenario is KS-contextual and
no meaningful constraint from KS-noncontextuality on proba-
bilistic models can be written down. This is also reflected in
the fact that our inequalities here do not invoke any of the
traditional graph invariants used in Ref. [24].
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 16
6.2 Minimally Indeterministic Sets of Contexts
(MISCs)
We now consider assignments of probabilistic mod-
els to a contextuality scenario specified by an on-
tic state λ ∈ Λ according to the response functions
ξ(m
i
|M
i
, λ) ∈ [0, 1]. A deterministic context is one
where all the measurement outcomes are assigned
{0, 1}-valued probabilities, i.e., ξ(m
i
|M
i
, λ) ∈ {0, 1}
for all m
i
, M
i
. An indeterministic context is one
which is not deterministic, i.e., it only allows prob-
ability assignments in [0, 1) to the measurement out-
comes. The max-probability for a deterministic con-
text is 1 while for an indeterministic context it is less
than 1.
Minimally Indeterministic Set of Con-
texts (MISC) of size c: A set of c contexts
such that no more than c − 1 of them can be
made deterministic by any (extremal) probabilis-
tic model on the (parent) contextuality scenario,
i.e., β(Γ, q) < 1 when q is supported entirely on
such a set of c contexts.
Intuitively, a MISC is a subset of contexts that
does not admit a KS-noncontextual assignment of
outcomes arising from a restriction of any probabilis-
tic model on the parent contextuality scenario (of
which the MISC is a subset) to just the MISC. By
a “restriction” of a probabilistic model to a MISC, we
mean the set of probabilities assigned to measurement
events in a MISC by the probabilistic model on the
parent contextuality scenario. Any proper subset of
a MISC might, however, admit a KS-noncontextual
assignment of outcomes arising in this way.
16
6.2.1 Noise-robust noncontextuality inequalities for
any KS-uncolourable contextuality scenario
Simple noncontextuality inequalities can be obtained
from a KS-uncolourable contextuality scenario by
identifying the following type of MISCs:
For a KS-uncolourable contextuality scenario
(with, say, n contexts), every extremal probabilis-
tic model will make some of the contexts indeter-
ministic. Let k be the smallest number of such
16
Mansfield and Barbosa [28] have previously considered a
notion of (partial) extendability of an empirical model (prob-
abilistic model, in our terminology) on a measurement cover
(i.e., a joint measurability structure [29] which yields a contex-
tuality scenario [30]) to an empirical model on another measure-
ment cover such that the down-closure of the first measurement
cover is contained in the down-closure of the second. While this
notion bears a superficial similarity to the relation between a
proper subset of a MISC and the MISC itself, as we have de-
scribed it, it may be an interesting avenue for further research
to look into rigorously formalizing the counterpart of MISCs in
the sheaf-theoretic approach [26], possibly via Ref. [28].
indeterministic contexts present in any extremal
probabilistic model on the KS-uncolourable con-
textuality scenario. Then any set of n − k + 1
contexts (out of all the n) constitutes a MISC,
i.e., β(Γ, q) < 1 when q is supported entirely over
this set of contexts.
From Theorem 1, for a KS-uncolourable contextu-
ality scenario, every extremal probabilistic model is
in one-to-one correspondence with an induced sub-
scenario admitting a unique probabilistic model. KS-
uncolourability means that any induced subscenario
with a unique probabilistic model would necessarily
contain hyperedges that are non-singleton (i.e., con-
taining more than one node) with their nodes assigned
probabilities less than 1. Ignoring the singleton hy-
peredges in such an induced subscenario (i.e., those
containing exactly one node), all the remaining hy-
peredges are indeterministic. We refer to the subsce-
nario consisting of these remaining (indeterministic)
hyperedges and the nodes they contain as an induced
indeterministic subscenario. k is then the number
of contexts in the smallest (in terms of the number
of contexts) induced indeterministic subscenario ob-
tained from an induced subscenario with a unique
probabilistic model. Now note that the hypergraph
with the least number of contexts (and containing no
singleton contexts) admitting a unique probabilistic
model is a 3-hypercycle. Hence, a 3-hypercycle is the
smallest induced indeterministic subscenario possible
and we have
Sufficient condition for a set of contexts
to be a MISC: For any KS-uncolourable con-
textuality scenario it will be the case that k ≥ 3
and any set of n − 2 contexts in the scenario will
form a MISC, i.e., β(Γ, q) < 1 when q is supported
on any set of n − 2 contexts.
For an example, see Fig. 7(c), second column, for
an induced indeterministic subscenario of the 18 ray
hypergraph [20] and the third column for the induced
subscenario of which the induced indeterministic sub-
scenario is a part.
Given that k is the size of the smallest induced in-
deterministic subscenario, we have a noncontextual-
ity inequality whenever q is supported on any set of
n − k + 1 contexts (which constitute a MISC):
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 17
Corr
q
≡
n−k+1
X
i=1
q
r
i
d
X
x=1
p(m
r
i
= x, s
r
i
= x|M
r
i
, S
r
i
)
≤ max
λ∈Λ
n−k+1
X
i=1
q
r
i
ζ(M
r
i
, λ)
≡ β(Γ, q). (29)
If we take q
r
i
=
1
n−k+1
for all i ∈ {1, 2, . . . , n − k + 1},
we have the following noncontextuality inequality for
a MISC consisting of n − k + 1 contexts:
Corr
q
≡
1
n − k + 1
n−k+1
X
i=1
d
X
x=1
p(m
r
i
= x, s
r
i
= x|M
r
i
, S
r
i
)
≤ max
λ∈Λ
1
n − k + 1
n−k+1
X
i=1
ζ(M
r
i
, λ) ≡ β(Γ, q)
≤
n − k
n − k + 1
+
p
max
(n − k + 1)
= 1 −
1 − p
max
n − k + 1
, (30)
where p
max
∈
1
d
, 1
is the largest max-probability
associated with any indeterministic context included
in the MISC. This max-probability corresponds to an
extremal probabilistic model that makes all but one of
the contexts in the MISC deterministic. In the case of
the 18 ray scenario, for example, k = 3 and any set of
n−k+1 = 9−3+1 = 7 contexts forms a MISC and we
have p
max
=
1
2
, so that the upper bound in the above
inequality given by
13
14
. (See Fig. 7, third column: the
six deterministic contexts together with any one of
the three indeterministic contexts form such a seven-
context MISC.)
6.2.2 Sufficient condition for a set of contexts to be a
MISC is not necessary
While the sufficient condition outlined above for a set
of contexts in a contextuality scenario to be a MISC
works for any KS-uncolourable contextuality scenario
and yields noncontextuality inequalities, it is not a
necessary condition. It is possible to identify smaller
MISCs depending on the particular contextuality sce-
nario and the probabilistic models on it.
Consider, for example, all the scenarios of the type
2Reg(G) that we have discussed. In these scenarios,
each node appears in two contexts and therefore de-
terministic contexts appear in pairs in any extremal
probabilistic model on these scenarios: this is because
the deterministic contexts in any extremal probabilis-
tic model are determined by singleton hyperedges in
the induced subscenario and the node in a single-
ton hyperedge (assigned probability 1) appears in two
contexts in the full contextuality scenario (see Fig. 7,
third column, for example). It then becomes possi-
ble to reduce the MISCs of size n − k + 1 that we
have identified above to MISCs of size
n−k
2
+ 1 simply
by taking the given MISC and omitting one of each
pair of deterministic contexts that share a node in the
given MISC. For example, see Fig. 7(c), third column,
where three deterministic contexts together with an
indeterministic context form a four-context MISC.
Since a MISC may thus contain smaller MISCs, we
define the notion of an “irreducible MISC”:
Irreducible MISC (irrMISC): A MISC
which does not contain another MISC as a proper
subset.
Therefore, an irrMISC is such that for its every
proper subset there exists an extremal probabilistic
model in which this proper subset is deterministic. As
we noted, the MISCs of size n−k+1 we have identified
above can be reduced to MISCs of size
n−k
2
+ 1 in
2Reg(·) scenarios. Are these MISCs of size
n−k
2
+ 1
irreducible? Not necessarily.
In general, it is possible to identify proper subsets
of MISCs which are irreducible MISCs. Let us see how
this plays out for some scenarios we will consider in
detail here: 2Reg(K
3,3
), 2Reg(K
1,7
), and the general
case of 2Reg(K
1,n
) (odd n > 1). For concreteness,
we will assume in the following subsections that q is a
uniform distribution over all the contexts in a MISC,
although our identification of MISCs does not rely on
this choice.
After illustrating the underlying ideas via these ex-
plicit examples, we will conclude with a general theo-
rem characterizing irrMISCs in contextuality scenar-
ios of type 2Reg(K
m,n
) (with odd mn > 1).
6.2.3 2Reg(K
3,3
)
Denoting the edges of K
3,3
(and the corresponding
hyperedges of 2Reg(K
3,3
)) by
{(1
¯
1), (1
¯
2), (1
¯
3), (2
¯
1), (2
¯
2), (2
¯
3), (3
¯
1), (3
¯
2), (3
¯
3)},
we can identify the following six 3-hypercycles in
2Reg(K
3,3
) (See Fig. 13):
(1
¯
1) − (1
¯
2) − (1
¯
3) − (1
¯
1)
(2
¯
1) − (2
¯
2) − (2
¯
3) − (2
¯
1)
(3
¯
1) − (3
¯
2) − (3
¯
3) − (3
¯
1)
(1
¯
1) − (2
¯
1) − (3
¯
1) − (1
¯
1)
(1
¯
2) − (2
¯
2) − (3
¯
2) − (1
¯
2)
(1
¯
3) − (2
¯
3) − (3
¯
3) − (1
¯
3). (31)
It is easy to show that each of these 3-hypercycles
forms a part of multiple induced subscenarios corre-
sponding to extremal probabilistic models. For ex-
ample, see Fig. 13 for the induced subscenarios (and
corresponding extremal probabilistic models) where
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 18
the 3-hypercycle (3
¯
1) − (3
¯
2) − (3
¯
3) − (3
¯
1) appears.
Since a 3-hypercycle is the smallest hypergraph with
a unique probabilistic model that isn’t deterministic,
we can build a 7-context MISC by taking any one of
the edges in (3
¯
1) − (3
¯
2) − (3
¯
3) − (3
¯
1) and the remain-
ing six edges (out of nine). This gives three distinct
MISCs for the 3-hypercycle (3
¯
1) − (3
¯
2) − (3
¯
3) − (3
¯
1):
MISC
1
(7) ≡ {(3
¯
1), (2
¯
1), (2
¯
2), (2
¯
3), (1
¯
1), (1
¯
2), (1
¯
3)},
MISC
2
(7) ≡ {(3
¯
2), (2
¯
1), (2
¯
2), (2
¯
3), (1
¯
1), (1
¯
2), (1
¯
3)},
MISC
3
(7) ≡ {(3
¯
3), (2
¯
1), (2
¯
2), (2
¯
3), (1
¯
1), (1
¯
2), (1
¯
3)}.
(32)
The noncontextuality inequality corresponding to
each 7-context MISC (MISC
j
(7), j = 1, 2, 3) is given
by
Corr
MISC
j
(7)
≡
1
7
X
i∈MISC
j
(7)
4
X
x=1
p(m
i
= x, s
i
= x|M
i
, S
i
)
≤ max
λ∈Λ
1
7
X
i∈MISC
j
(7)
ζ(M
i
, λ) ≡ β(Γ, q)
=
1
7
6 +
1
2
=
13
14
. (33)
More generally, from the fact that the contextuality
scenario admits 3-hypercycles, we have that the aver-
age predictability is constrained for any set of c ≥ 7
contexts (out of 9) since at most 6 of them can be
made deterministic but not the remaining ones by any
extremal probabilistic model. Then for any choice of
c contexts such that c = 7, 8, 9, we have noncontex-
tuality inequalities with Corr
MISC
j
(c)
constrained by
13/14, 7/8, and 5/6 respectively.
The 7-context MISCs can be further reduced to
4-context MISCs by eliminating one of each pair
of contexts from the remaining deterministic edges,
{(2
¯
1), (2
¯
2), (2
¯
3), (1
¯
1), (1
¯
2), (1
¯
3)}, in the MISC. For
each MISC
j
(7), for instance, these pairs of determin-
istic contexts can be:
{(2
¯
1) − (2
¯
2), (2
¯
3) − (1
¯
3), (1
¯
1) − (1
¯
2)},
{(2
¯
1) − (1
¯
1), (2
¯
3) − (1
¯
3), (2
¯
2) − (1
¯
2)},
{(2
¯
1) − (1
¯
1), (2
¯
3) − (2
¯
2), (1
¯
3) − (1
¯
2)},
{(2
¯
1) − (2
¯
3), (2
¯
2) − (1
¯
2), (1
¯
1) − (1
¯
3)}. (34)
Picking a context from each of the 3 pairs of deter-
ministic contexts and a context from the 3-hypercycle
(3
¯
1) − (3
¯
2) − (3
¯
3) − (3
¯
1), we need to check if such
a set of 4 contexts forms a MISC: by verifying that
it does not appear as a subset of the deterministic
set of 6 contexts fixed by any of the remaining 3-
hypercycles. An example of such a set of 4 contexts is
{(3
¯
1), (2
¯
1), (1
¯
2), (1
¯
3)} which is a MISC(4). It is not a
subset of any of the deterministic sets of contexts in-
duced by 3-hypercycle extremal probabilistic models,
namely:
{(2
¯
1), (2
¯
2), (2
¯
3), (3
¯
1), (3
¯
2), (3
¯
3)}
induced by (1
¯
1) − (1
¯
2) − (1
¯
3) − (1
¯
1),
{(1
¯
1), (1
¯
2), (1
¯
3), (3
¯
1), (3
¯
2), (3
¯
3)}
induced by (2
¯
1) − (2
¯
2) − (2
¯
3) − (2
¯
1),
{(1
¯
1), (1
¯
2), (1
¯
3), (2
¯
1), (2
¯
2), (2
¯
3)}
induced by (3
¯
1) − (3
¯
2) − (3
¯
3) − (3
¯
1),
{(1
¯
2), (2
¯
2), (3
¯
2), (1
¯
3), (2
¯
3), (3
¯
3)}
induced by (1
¯
1) − (2
¯
1) − (3
¯
1) − (1
¯
1),
{(1
¯
1), (2
¯
1), (3
¯
1), (1
¯
3), (2
¯
3), (3
¯
3)}
induced by (1
¯
2) − (2
¯
2) − (3
¯
2) − (1
¯
2),
{(1
¯
1), (2
¯
1), (3
¯
1), (1
¯
2), (2
¯
2), (3
¯
2)}
induced by (1
¯
3) − (2
¯
3) − (3
¯
3) − (1
¯
3). (35)
In all, there are 9 such MISC(4) and they are irre-
ducible, i.e., no proper subset of these 9 MISCs forms
a MISC. This is easy to verify, for example, for the
MISC(4) {(3
¯
1), (2
¯
1), (1
¯
2), (1
¯
3)}: every proper subset
of this MISC(4) appears in one of the six determinis-
tic sets of contexts. These irrMISCs are depicted in
Fig. 9 and listed below:
{(1
¯
1), (2
¯
1), (3
¯
2), (3
¯
3)}
{(1
¯
1), (3
¯
1), (2
¯
2), (2
¯
3)}
{(1
¯
2), (2
¯
2), (3
¯
1), (3
¯
3)}
{(1
¯
2), (3
¯
2), (2
¯
1), (2
¯
3)}
{(1
¯
3), (2
¯
3), (3
¯
1), (3
¯
2)}
{(1
¯
3), (3
¯
3), (2
¯
1), (2
¯
2)}
{(2
¯
1), (3
¯
1), (1
¯
2), (1
¯
3)}
{(2
¯
2), (3
¯
2), (1
¯
1), (1
¯
3)}
{(2
¯
3), (3
¯
3), (1
¯
1), (1
¯
2)}. (36)
Each of these irrMISC(4)s (with uniform q) corre-
sponds to a noncontextuality inequality:
Corr
irrMISC(4)
≡
1
4
X
i∈irrMISC(4)
4
X
x=1
p(m
i
= x, s
i
= x|M
i
, S
i
)
≤ max
λ∈Λ
1
4
X
i∈irrMISC(4)
ζ(M
i
, λ)
≤
1
4
3 +
1
2
=
7
8
. (37)
Are there any still smaller MISCs, say MISC(3),
in this contextuality scenario? Indeed, such MISCs
exist and they correspond precisely to the perfect
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 19
{(11),(12),(23),(33)} {(11),(13),(22),(32)} {(12),(13),(21),(31)}
{(12),(32),(21),(23)} {(13),(33),(21),(22)}
{(11),(31),(22),(23)}
{(11),(21)(32),(33)} {(12),(22),(31),(33)} {(13),(23)(31),(32)}
1 2 3
1 2 3
Figure 9: All irrMISC(4) for the 2Reg(K
3,3
) scenario.
matchings of the graph K
3,3
. Each of the six ver-
tices of K
3,3
is an origin of a 3-hypercycle (corre-
sponding to 2Reg(K
1,3
); see Fig. 13) in the contex-
tuality scenario 2Reg(K
3,3
). Hence, a perfect match-
ing – namely, a set of disjoint edges such that they
cover all the six vertices of the graph – ensures that
the three hyperedges corresponding to these edges in
the perfect matching cannot all be made determinis-
tic by any 3-hypercycle extremal probabilistic model
on 2Reg(K
3,3
). This is because at least one of the
three hyperedges, e.g. {(1
¯
1), (2
¯
2), (3
¯
3)}, will be inde-
terministic (forming a part of a 3-hypercycle) in these
extremal probabilistic models. Indeed, these three hy-
peredges can’t be made deterministic by any extremal
probabilistic model at all, since all extremal prob-
abilistic models on 2Reg(K
3,3
) are induced by odd
hypercycles and the remaining extremal probabilistic
models must therefore contain at least a 5-hypercycle.
A 5-hypercycle extremal probabilistic model would
make 4 contexts deterministic, but these 4 contexts
will come in pairs that each share a deterministic
node assigned probability 1. This means a maximum
of 2 independent deterministic contexts in any other
extremal probabilistic models besides those induced
by 3-hypercycles: hence these extremal probabilistic
models cannot make more than two of the three con-
texts in a perfect matching deterministic (since the
three contexts share no nodes in 2Reg(K
3,3
)). There
are six perfect matchings of K
3,3
, hence 6 instances
of MISC(3), all of which are in fact irreducible:
{(1
¯
1), (2
¯
2), (3
¯
3)}
{(1
¯
1), (2
¯
3), (3
¯
2)}
{(2
¯
2), (1
¯
3), (3
¯
1)}
{(3
¯
3), (1
¯
2), (2
¯
1)}
{(1
¯
3), (2
¯
1), (3
¯
2)}
{(3
¯
1), (1
¯
2), (2
¯
3)}. (38)
See Fig. 10. Each of these irrMISC(3)s yields a non-
contextuality inequality (again, assuming uniform q
1 2 3
1 2 3
{(11),(22),(33)} {(11),(23),(32)} {(13),(22),(31)}
{(12),(21),(33)} {(13),(21),(32)} {(12),(23),(31)}
Figure 10: All irrMISC(3) for the 2Reg(K
3,3
) scenario.
here):
Corr
irrMISC(3)
≡
1
3
X
i∈irrMISC(3)
4
X
x=1
p(m
i
= x, s
i
= x|M
i
, S
i
)
≤ max
λ∈Λ
1
3
X
i∈irrMISC(3)
ζ(M
i
, λ)
≤
1
3
2 +
1
2
=
5
6
. (39)
The noncontextuality inequality of Ref. [6] can
then be obtained by coarse-graining these ir-
rMISC(3) inequalities, say the ones correspond-
ing to irrMISCs {(1
¯
1), (2
¯
3), (3
¯
2)}, {(2
¯
2), (1
¯
3), (3
¯
1)}
and {(3
¯
3), (1
¯
2), (2
¯
1)} or the ones corresponding to
irrMISCs {(1
¯
1), (2
¯
2), (3
¯
3)}, {(1
¯
3), (2
¯
1), (3
¯
2)}, and
{(3
¯
1), (1
¯
2), (2
¯
3)}, to yield:
A ≡
1
9
3
X
i,j=1
4
X
x=1
p(m
(i
¯
j)
= x, s
(i
¯
j)
= x|M
(i
¯
j)
, S
(i
¯
j)
)
≤ max
λ∈Λ
1
9
3
X
i,j=1
ζ(M
(i
¯
j)
, λ)
≤
1
9
6 + 3.
1
2
=
5
6
. (40)
Note that the upper bounds on the average corre-
lation corresponding to irrMISC(3)s and irrMISC(4)s
were first obtained in Ref. [36] via an implementation
of Fourier-Motzkin elimination.
17
On the other hand, our derivation hinges on a con-
ceptual insight – based on the mapping 2Reg(·) and
Theorem 1 – that clarifies why we expect the aver-
age source-measurement correlation of particular sets
17
See [36] for details of that numerical approach. It consists
of writing down all the positivity and normalization constraints
on the average correlation for each context and then eliminat-
ing the ontological variables via Fourier-Motzkin elimination
to eventually yield operational noise-robust noncontextuality
inequalities.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 20
of contexts (rather than arbitrary sets of contexts)
in these noncontextuality inequalities to be bounded
away from 1. It boils down to identifying MISCs
and irrMISCs in a contextuality scenario. Indeed, as
we now show, our understanding lets us obtain pre-
viously undiscovered noncontextuality inequalities in
other KS-uncolourable contextuality scenarios.
6.2.4 2Reg(K
1,7
)
We denote the edges of K
1,7
(and the corresponding
contexts in 2Reg(K
1,7
)) by
{(1
¯
1), (1
¯
2), (1
¯
3), (1
¯
4), (1
¯
5), (1
¯
6), (1
¯
7)}.
Since every edge is connected to every other edge
in K
1,7
and vertex 1 is the origin of all hypercy-
cles, we have that each choice of a set of 3 con-
texts in 2Reg(K
1,7
) will form a 3-hypercycle. Ex-
tremal probabilistic models induced by subscenarios
containing these 3-hypercycles can make at most all
the remaining 4 contexts deterministic. Indeed, tak-
ing out 3 edges from K
1,7
yields K
1,4
as a remnant
and 2Reg(K
1,4
) admits only deterministic extremal
probabilistic models.
Each MISC of size c would require a set of c contexts
such that no more than c − 1 of them can be made
deterministic in any extremal probabilistic model on
2Reg(K
1,7
). We know that every choice of a set of
4 contexts in 2Reg(K
1,7
) can be made deterministic
by some extremal probabilistic model since every such
choice is in one-to-one correspondence with a choice
of a 3-hypercycle (consisting of the remaining 3 con-
texts) inducing such an extremal probabilistic model
on 2Reg(K
1,7
): we have
7
C
4
=
7
C
3
= 35 such choices.
Hence a set of contexts of size ≤ 4 can never form
a MISC: there will always exist an extremal proba-
bilistic model which will make all of the contexts in
the set deterministic. All irrMISCs are therefore of
size c = 5 in 2Reg(K
1,7
) and every set of 5 contexts
(n − k + 1 = 7 − 3 + 1 = 5) forms an irrMISC(5). See
Fig. 11.
The noise-robust noncontextuality inequalities for
2Reg(K
1,7
) then correspond to average source-
measurement correlation (assuming uniform q) for:
1. irrMISC(5)s:
Corr
irrMISC(5)
≡
1
5
X
j∈irrMISC(5)
6
X
x=1
p(m
j
= x, s
j
= x|M
j
, S
j
)
≤ max
λ∈Λ
1
5
X
j∈irrMISC(5)
ζ(M
j
, λ)
=
1
5
4 +
1
2
=
9
10
. (41)
There are
7
C
5
= 21 such inequalities.
1
1 2 3 4 5 6 7
1 1 1 1
1 1 1 1
1 1
1
1 1
111
1 1 1 1
1 2 3 4 5 6 7
1
1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 2 3 4 5 6 7
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1
2
3
4
5
6
7
1 2 3 4 5 6 71 2 3 4 5 6 71 2 3 4 5 6 7
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7 1 2 3 4 5 6 7
Figure 11: All irrMISC(5) for the 2Reg(K
1,7
) scenario.
2. Each irrMISC(5) and 1 indeterministic context:
Corr
MISC(6)
≡
1
6
6
X
j=1
6
X
x=1
ζ(m
r
j
= x, s
r
j
= x|M
r
j
, S
r
j
)
≤ max
λ∈Λ
1
6
6
X
j=1
ζ(M
r
j
, λ)
=
1
6
4 + 2.
1
2
=
5
6
. (42)
for every subset of 6 distinct contexts
{r
1
, r
2
, r
3
, r
4
, r
5
, r
6
} ⊂ {(1
¯
1), (1
¯
2), . . . , (1
¯
7)}.
There are
7
C
6
= 7 such inequalities.
3. All the contexts (or each irrMISC(5) and 2 inde-
terministic contexts):
Corr
MISC(7)
≡
1
7
7
X
i=1
6
X
x=1
p(m
i
= x, s
i
= x|M
i
, S
i
)
≤ max
λ∈Λ
1
7
7
X
i=1
ζ(M
i
, λ)
=
1
7
4 + 3.
1
2
=
11
14
. (43)
There is one such inequality.
6.2.5 2Reg(K
1,n
) with n(> 1) odd
We denote the edges of K
1,n
(and the corresponding
contexts in 2Reg(K
1,n
)) by
{(1
¯
1), (1
¯
2), . . . , (1¯n)}.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 21
Since every edge is connected to every other edge in
K
1,n
, each triple of contexts in 2Reg(K
1,n
) will form a
3-hypercycle. Extremal probabilistic models induced
by subscenarios containing these 3-hypercycles can at
most make the remaining n−3 contexts deterministic.
Indeed, taking out 3 edges from K
1,n
yields K
1,n−3
as
a remnant and 2Reg(K
1,n−3
) does admit determinis-
tic extremal probabilistic models (from Theorem 2,
since n − 3 is even for any odd n > 1.)
Each MISC of size c would require a set of c contexts
such that no more than c − 1 of them can be made
deterministic in any extremal probabilistic model on
2Reg(K
1,n
). We know that every choice of a set of
n − 3 contexts in 2Reg(K
1,n
) can be made determin-
istic by some extremal probabilistic model since ev-
ery such choice is in one-to-one correspondence with
a choice of a 3-hypercycle (consisting of the remain-
ing 3 contexts) inducing such an extremal probabilis-
tic model on 2Reg(K
1,n
):
n
C
n−3
=
n
C
3
=
n!
3!(n−3)!
.
Hence a set of contexts of size ≤ n−3 can never form a
MISC: there will always exist an extremal probabilis-
tic model which will make all of the contexts in the set
deterministic. All irrMISCs are therefore of size n − 2
in 2Reg(K
1,n
) and every set of n−2 contexts forms an
irrMISC(n − 2). Clearly, the sufficient condition for
a set of contexts to be a MISC that we identified in
Sec. 6.2.1 is also necessary for contextuality scenarios
of the type 2Reg(K
1,n
) for odd n ≥ 3.
The noncontextuality inequalities for 2Reg(K
1,n
)
then correspond to average source-measurement cor-
relation for
1. irrMISC(n − 2)s:
Corr
irrMISC(n−2)
≡
1
n − 2
X
j∈irrMISC(n−2)
n−1
X
x=1
p(m
j
= x, s
j
= x|M
j
, S
j
)
≤ max
λ∈Λ
1
n − 2
X
j∈irrMISC(n−2)
ζ(M
j
, λ)
=
1
n − 2
n − 3 +
1
2
= 1 −
1
2(n − 2)
. (44)
There are
n
C
n−2
=
n!
2!(n−2)!
=
n(n−1)
2
such in-
equalities.
2. Each irrMISC(n − 2) and 1 indeterministic con-
text:
Corr
MISC(n−1)
≡
1
n − 1
n−1
X
j=1
n−1
X
x=1
p(m
r
j
= x, s
r
j
= x|M
r
j
, S
r
j
)
≤ max
λ∈Λ
1
n − 1
n−1
X
j=1
ζ(M
r
j
, λ)
=
1
n − 1
n − 3 + 2.
1
2
= 1 −
1
n − 1
. (45)
for every subset of n − 1 distinct contexts
{r
1
, r
2
, . . . , r
n−1
} ⊂ {(1
¯
1), (1
¯
2), . . . , (1¯n)}. There
are
n
C
n−1
= n such inequalities.
3. All the contexts (or each irrMISC(n − 2) and 2
indeterministic contexts):
Corr
MISC(n)
≡
1
n
n
X
i=1
n−1
X
x=1
p(m
i
= x, s
i
= x|M
i
, S
i
)
≤ max
λ∈Λ
1
n
n
X
i=1
ζ(M
i
, λ)
=
1
n
n − 3 + 3.
1
2
= 1 −
3
2n
. (46)
There is one such inequality.
18
6.2.6 2Reg(K
m,n
), for odd mn > 1
We now extend the derivation of irrMISC non-
contextuality inequalities above to the case of all
KS-uncolourable 2-regular scenarios, 2Reg(K
m,n
),
obtained from arbitrary complete bipartite graphs
K
m,n
. These are just those K
m,n
with odd mn > 1
(from Theorem 2): K
3,3
and K
1,n
(odd n > 1) are spe-
cial cases of these, so the recipe for noncontextuality
inequalities obtained here will recover the noncontex-
tuality inequalities we have already obtained.
Obtaining these noncontextuality inequalities en-
tails two things: identifying all the irrMISCs in the
contextuality scenario and calculating their upper
bounds due to noncontextuality, i.e., β(Γ, q). Since
these are 2-regular scenarios, calculating the upper
bounds is easy (due to Theorem 5).
Before we proceed with the general result, we need
the following definitions:
18
Note that the contextuality scenario 2Reg(K
1,5
) appeared
in Ref. [31], where a subnormalized assignment of quantum
projectors to this scenario in C
6
was presented. This set of
projectors, however, is not a KS set because of the subnormal-
ization.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 22
Edge cover: An edge cover of a graph is a set of its
edges such that every vertex of the graph belongs to
at least one of the edges in this set. For example, K
3,3
has an edge cover {{1,
¯
1}, {1,
¯
2}, {2,
¯
2}, {2,
¯
3}, {3,
¯
3}}.
Minimum edge cover: An edge cover of the smallest
possible size for a graph is called its minimum edge
cover. Size of an edge cover is given by the number of
edges it contains. For example, K
3,3
has a minimum
edge cover {{1,
¯
1}, {2,
¯
2}, {3,
¯
3}}.
Minimal edge cover: An edge cover such that no
proper subset of it is an edge cover is called a minimal
edge cover. Every minimum edge cover is minimal,
but not conversely. For example, K
3,3
has a minimal
edge cover {{1,
¯
1}, {1,
¯
2}, {2,
¯
3}, {3,
¯
3}}.
Below, we prove some properties of minimal edge
covers of K
m,n
before moving on to a characterization
of irrMISCs in K
m,n
.
Theorem 7. Any minimal edge cover of K
m,n
partitions the vertices of K
m,n
into a disjoint
union of κ connected subgraphs, where κ ∈
{1, 2, . . . , min{m, n}}, and we have for the number of
edges, N, in the minimal edge cover, N = m + n − κ.
Hence, we have
max{m, n} ≤ N ≤ m + n − 1.
When either m = 1 or n = 1, we have that K
m,n
is its own only minimal (hence also minimum) edge
cover so that κ = 1. For m, n ≥ 2, the total number
of minimum edge covers of K
m,n
is
max{m, n}!
|m − n|!
(min{m, n})
|m−n|
,
and the total number of minimal (not necessarily min-
imum) edge covers of K
m,n
(m, n ≥ 2) is
m+n−2
X
N=max{m,n}
(number of minimal edge covers of size N).
(47)
Proof. For a given K
m,n
, let’s call the set of m vertices
S
m
and the set of n vertices S
n
. The size, N, of an
edge cover of K
m,n
must satisfy
N =
X
v∈S
m
deg(v) =
X
v∈S
n
deg(v), (48)
where v denotes a vertex of K
m,n
and deg(v) denotes
the degree of the vertex, i.e., the number of edges in
which it appears.
Note that two vertices connected by an edge in a
minimal edge cover cannot both have degree > 1: if an
edge cover has a pair of degree 2 vertices connected
by an edge, then the edge cover cannot be minimal
since the said connecting edge can be dropped while
maintaining the edge cover property. (See Fig. 12.)
This means that a minimal edge cover of K
m,n
is such
that any vertex of degree 2 or more is only connected
Figure 12: Why two vertices connected by an edge in a mini-
mal edge cover of a bipartite graph cannot both have degree
greater than 1.
to degree 1 vertices, hence the minimal edge cover is
a disjoint union of connected bipartite subgraphs of
type K
1,b
or K
a,1
, where a ≤ m, b ≤ n. Denoting
the set of vertices of each subgraph by V
i
, we have
that number of edges in such a subgraph is |V
i
| − 1.
Thus, the total number of edges in a minimal edge
cover, N =
P
κ
i=1
|V
i
| − κ = m + n − κ, where κ is
the number of disjoint subgraphs whose union yields
the minimal edge cover. Clearly, 1 ≤ κ ≤ min{m, n},
where κ = 1 corresponds to the case of any K
m,n
graph with m = 1 or n = 1 since it is its own minimal
edge cover and we have N = m+n − 1. For any other
K
m,n
(with m, n ≥ 2), we have that κ ≥ 2 and the
maximum size of a minimal edge cover is m + n − 2:
this is achieved when a vertex v
min
∈ S
min{m,n}
is
connected to all but one (say, v
max
) of the vertices in
S
max{m,n}
. The remaining vertex v
max
∈ S
max{m,n}
is then connected to all vertices of S
min{m,n}
except
v
min
∈ S
min{m,n}
. We then have N = m + n − 2.
The total number of minimum edge covers can
be computed as follows: every vertex in S
min{m,n}
is connected one-to-one via an edge to a vertex in
S
max{m,n}
and there are
max{m,n}!
|m−n|!
possible ways to
do this. For each such way, each of the remaining
|m − n| vertices in S
max{m,n}
can be connected via an
edge to one of the min{m, n} vertices of S
min{m,n}
,
so there are (min{m, n})
|m−n|
possible configurations
for the remaining edges. This yields a total of
max{m,n}!
|m−n|!
(min{m, n})
|m−n|
minimum edge covers for
K
m,n
.
We leave the general case as an open question:
What is the number of minimal-but-not-minimum
edge covers for an arbitrary complete bipartite graph
K
m,n
, where m, n ≥ 2?
Theorem 8. A set of contexts in 2Reg(K
m,n
), odd
mn > 1, forms a MISC if and only if
1. for m = 1 or n = 1: the number of contexts in
the set is at least mn − 2.
2. for m ≥ 3 and n ≥ 3: the corresponding set of
edges in K
m,n
is an edge cover of K
m,n
.
Proof. Case 1, i.e., m = 1 or n = 1 (and odd mn >
1):
In this case, we have that every choice of 3 edges in
K
m,n
is a claw and therefore induces a 3-hypercycle
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 23
1
3
1 2 3
2
1 2 3
1 2 3
1
1 2 3
2
1 2 3
3
321
(a)
(b)
Figure 13: (a) All the six 3-hypercycles in the scenario
2Reg(K
3,3
), (b) Examples of extremal probabilistic models
corresponding to a particular 3-hypercycle.
extremal probabilistic model on 2Reg(K
m,n
) that
renders all the remaining (mn − 3) contexts in
2Reg(K
m,n
) deterministic. To form a MISC, then,
requires at least mn − 3 + 1 = mn − 2 contexts. (See
Fig. 11 for a K
1,7
example.)
Case 2, i.e., m ≥ 3 and n ≥ 3 (and odd mn > 1):
Every MISC of 2Reg(K
m,n
) corresponds to an edge
cover of K
m,n
: We show this by proving the contra-
positive. If a set of edges is not an edge cover of
K
m,n
, then there exists a vertex in K
m,n
(not covered
by the set of edges) that can support a claw (subgraph
K
1,3
of K
m,n
) which corresponds to a 3-hypercycle in
2Reg(K
m,n
), odd mn > 1. All the contexts in the
corresponding set of contexts can then be made de-
terministic relative to an extremal probabilistic model
induced by this 3-hypercycle (cf. Theorems 5 and 6),
hence the set cannot be a MISC. (See Fig. 7.)
Every edge cover of K
m,n
corresponds to a MISC
of 2Reg(K
m,n
): If a set of edges forms an edge cover
of K
m,n
, then there does not exist any vertex in K
m,n
that can support a claw disjoint from the set of edges.
Hence, it is not possible to find a 3-hypercycle ex-
tremal probabilistic model on 2Reg(K
m,n
) that makes
all the contexts in the set deterministic: at least one
of the contexts must belong to a 3-hypercycle in any
extremal probabilistic model induced by such a hy-
percycle. The set of contexts must therefore be a
MISC.
19
(See Fig. 13)
19
Recall that we need to restrict ourselves to 3-hypercycle ex-
tremal probabilistic models to identify MISCs in 2Reg(K
m,n
)
scenarios: any bigger odd hypercycles would make even fewer
contexts deterministic than a 3-hypercycle extremal probabilis-
tic model and lead us to an artificially lower bound on the
noncontextuality inequality; we have to give a noncontextual
model as much leeway as mathematically possible to reproduce
perfect predictability and thus find an upper bound that can-
not be exceeded by any noncontextual ontological model, not
merely those using extremal probabilistic models induced by 5
or higher odd hypercycles.
K
33
K
34
K
35
K
44
K
55
Minimum edge covers
Minimal-but-not-minimum edge covers
Figure 14: Representative minimal edge covers of various
complete bipartite graphs, both minimum and non-minimum.
Theorem 9. A set of contexts is an irrMISC for
2Reg(K
m,n
), odd mn > 1, if and only if
1. for m = 1 or n = 1: the number of contexts in
the set is exactly mn − 2.
2. for m ≥ 3 and n ≥ 3: the corresponding set of
edges in K
m,n
is a minimal edge cover of K
m,n
,
i.e., an edge cover such that none of its proper
subsets is an edge cover.
Proof. This just follows from noting the definition of
an irrMISC and Theorem 8: an irrMISC is a MISC
that does not contain another MISC as a proper sub-
set.
Hence, a minimum edge cover always corresponds
to an irrMISC, but not conversely. The 3-context
irrMISCs of 2Reg(K
3,3
) form minimum edge covers
(of size 3) but the 4-context irrMISCs of 2Reg(K
3,3
)
don’t form minimum edge covers. Thus, the small-
est irrMISCs correspond to minimum edge covers,
which for K
m,n
(odd mn > 1) are of size max{m, n}
(cf. Theorem 7). See Figs. 9 and 10.
When m = n, the smallest irrMISCs correspond
to the perfect matchings
20
of K
m,m
and thus there
are m! such irrMISCs. Recall that for K
3,3
, there
are 6 such irrMISCs. The other irrMISCs are min-
imal edge covers that are not minimum. The num-
ber of these minimal-but-not-minimum edge covers
is 9 for K
3,3
: every minimal-but-not-minimum edge
cover of K
3,3
should contain at least one vertex of
degree 2 because no vertex can be degree 3 if the
edge cover is minimal and the edge cover would be
a minimum edge cover if all vertices are degree 1;
20
A perfect matching of a graph is a set of mutually disjoint
edges that cover all vertices of the graph.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 24
there are three possible choices for a degree 2 ver-
tex among {1, 2, 3} and for each such choice there are
three possible choices of pairs of vertices connected to
it given by {{
¯
1,
¯
2}, {
¯
2,
¯
3}, {
¯
1,
¯
3}; choosing these fixes
a minimal-but-not-minimum edge cover and we there-
fore have 3 × 3 = 9 irrMISCs arising from these edge
covers. Note that no larger irrMISCs exist for K
3,3
since N ≤ m + n − 2 = 4. In Fig. 14, we illustrate
minimum and minimal-but-not-minimum edge covers
for some classes of complete bipartite graphs.
In Table 1, we summarize facts about irrMISCs in
various contextuality scenarios that we have consid-
ered in this section.
7 Discussion and future work
To summarize, we have presented a framework for
noise-robust noncontextuality inequalities that are in-
spired by logical proofs of the Kochen-Specker theo-
rem. We have identified special sets of these inequal-
ities, corresponding to irreducible minimally indeter-
ministic sets of contexts (or irrMISCs), that are in-
dependent of each other and can generate any other
noise-robust noncontextuality inequality correspond-
ing to a minimally indeterministic set of contexts
(MISC) or even any other (non-MISC) set of contexts.
The basic building blocks of any noise-robust noncon-
textuality inequality obtained in this framework are
the noise-robust noncontextuality inequalities for ir-
rMISCs. Along the way, we also obtained a param-
eterization of contextuality scenarios and identified
ways to detect their KS-uncolourability.
Note that the contextuality scenarios we have con-
sidered within this framework are all required to be
KS-uncolourable and this is the only restriction on
them.
21
In particular, we do not insist that they ad-
mit a realization with KS sets of projectors in quan-
tum theory. When they do admit such a realiza-
tion, we have that quantum theory can violate any
noise-robust noncontextuality inequality by achieving
Corr
q
= 1 in the ideal noiseless limit. When they
don’t admit realization with KS sets then it remains
an open question whether noise-robust noncontextu-
ality inequalities of type Corr
q
≤ β(Γ, q) might still
admit a quantum violation using nonprojective posi-
tive operator-valued measures (POVMs).
We conclude with some directions for future work
building on this framework.
1. Sufficiency of the noise-robust noncontextuality
21
The case of KS-colourable contextuality scenarios that fit
within a generalization of the CSW framework [24] was con-
sidered in Ref. [14]. These KS-colourable scenarios satisfy the
property that the set of probabilistic models satisfying con-
sistent exclusivity on them coincides with the set of general
probabilistic models on them. The case of KS-colourable con-
textuality scenarios where this property fails – and which are
therefore outside the purview of Refs. [14, 24] – will be taken
up in future work.
inequalities from irrMISCs:
A crucial open question is whether the sat-
isfaction of noncontextuality inequalities `a la
Eq. (26) for the set of all irrMISCs of a given
KS-uncolourable contextuality scenario is suffi-
cient to guarantee the existence of a noncontex-
tual ontological model in this scenario. In princi-
ple, one could check this in a brute-force manner
for some scenario by using the algorithmic ap-
proach of Ref. [11] but, ideally, one would like an
analytical proof of sufficiency (or otherwise) that
applies to arbitrary KS-uncolourable contextual-
ity scenarios.
A weaker open question is whether it’s possible
to saturate any noncontextuality inequality of the
form in Eq. (26) in a noncontextual ontological
model. We do not have an answer to this but we
provide a possible approach to constructing such
models in Appendix B.
2. POVM realizations when no KS sets exist:
Do there exist KS-uncolourable contextuality
scenarios that do not admit KS sets but allow
for a realization with POVMs in such a way that
a noise-robust noncontextuality inequality can be
violated? If so, construct some examples and de-
termine the optimal POVM realization for them.
Note that since POVMs can realize arbitrary
joint measurability structures in quantum theory
[29], it is conceivable that some such realizations
could work for violating noise-robust noncontex-
tuality inequalities of the type obtained in this
paper even when the KS-uncolourable contextu-
ality scenario concerned does not admit a real-
ization with KS sets.
3. Lower-dimensional POVM realizations when KS
sets exist:
For KS-uncolourable contextuality scenarios that
do admit KS sets, find a realization with POVMs
that works on a Hilbert space of lower dimen-
sion than the KS set realization and still vio-
lates a noise-robust noncontextuality inequality.
Is it possible, for example, to realize the 18 ray
scenario [20] (Fig. 2) with four-outcome qubit
POVMs such that an irrMISC noncontextuality
inequality is violated?
4. Other KS constructions and extremal probabilis-
tic models on their contextuality scenarios:
We have only considered KS-uncolourable con-
textuality scenarios of type 2Reg(K
m,n
) in de-
tail in this paper. It would be interesting to an-
alyze the original Kochen-Specker construction
[1] and others that do not fall within the fam-
ily of contextuality scenarios we have considered
here. In particular, the parameterization of KS-
uncolourable scenarios in Section 4 should be
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 25
Scenario Number of irrMISCs Bounds on Corr
for uniform q
2Reg(K
3,3
) 15: 6 3-context and 9 4-context irrMISCs (Figs. 9,10) Eqs. (37), (39)
2Reg(K
1,7
) 21: All 5-context (Fig. 11) Eq. (41)
2Reg(K
1,n
) (with odd n > 1)
n(n−1)
2
: All (n − 2)-context Eq. (44)
Table 1: Summary of irrMISCs for a familar of 2-regular contextuality scenarios. A general characterization of irrMISCs for
contextuality scenarios of type 2Reg(K
m,n
) (with odd mn > 1), of which all the examples above are instances, can be found
in Theorem 9.
useful in attempting such analyses. Note that
our analysis in this paper relied heavily on the
characterization of extremal probabilistic mod-
els on 2Reg(K
m,n
) contextuality scenarios given
by Theorem 5. More generally, it relied on the
characterization of extremal probabilistic mod-
els on arbitrary contextuality scenarios given by
AFLS [25] (see Theorem 1). The characteriza-
tion of Theorem 1 will be useful in attempting
to study contextuality scenarios that do not fall
under the purview of Theorem 5. Indeed, it
would be worthwhile to obtain a characteriza-
tion of contextuality scenarios that admit unique
probabilistic models since these are the ones that
induce extremal probabilistic models on any con-
textuality scenario following Theorem 1.
5. Applications to quantum information protocols:
Given that the framework we have proposed
leverages KS-uncolourability to provide noise-
robust operational signatures of contextuality,
there is good reason to expect that it might
be relevant for quantum information tasks. In
particular, it could be used to study the ques-
tion of how logical proofs of the KS theorem
can be leveraged to provide advantages in (pos-
sibly some variant of) state discrimination `a la
Ref. [37] (which does not use contextuality aris-
ing from Kochen-Specker proofs). In particu-
lar, the task of maximizing the average source-
measurement correlation (the quantity Corr
q
)
could possibly be related to minimum error state
discrimination as follows: for any d-uniform con-
textuality scenario with n contexts, we consider n
ensembles of states (each denoted by source set-
ting S
i
) such that the average preparation pro-
cedures associated with them ([>|S
i
]) are all op-
erationally equivalent and we apply the assump-
tion of preparation noncontextuality relative to
this operational equivalence. Our task then is
to discriminate between elements of each ensem-
ble under an additional constraint on the set of
allowed measurements, namely, that they sat-
isfy the operational equivalences required for KS-
uncolourability and we apply measurement non-
contextuality relative to these operational equiv-
alences. Maximizing Corr
q
then corresponds to
maximizing the average success probability of
discrimination given by Corr
q
for the set of en-
sembles in the support of probability distribution
q (defined over the set of n contexts). If the value
of Corr
q
exceeds the bound from our noise-robust
noncontextuality inequality, we then have that
the operational theory allows a greater success
probability for minimum error state discrimina-
tion than a theory which admits a noncontextual
ontological model.
Note also that the possibility of realizing vio-
lations of our noise-robust noncontextuality in-
equalities using POVMs on lower-dimensional
systems (than the ones on which KS sets exist)
also makes it interesting to study this problem
from such a perspective.
Acknowledgement
I would like to thank Anirudh Krishna, Rob Spekkens,
Tom´aˇs Gonda, Tobias Fritz, Andreas Winter, Giulio
Chiribella, Matt Pusey, and Nuriya Nurgalieva for
discussions and feedback at various stages during the
writing of this paper. Thanks are also due to two
anonymous reviewers for a critical reading of the pa-
per, in particular Reviewer 1 for pointing out possible
connections with the sheaf-theoretic literature on con-
textuality. This research was supported by Perime-
ter Institute for Theoretical Physics. Research at
Perimeter Institute is supported by the Government
of Canada through the Department of Innovation, Sci-
ence, and Economic Development Canada and by the
Province of Ontario through the Ministry of Research,
Innovation and Science.
Appendices
A Note on matching scenarios
Here we elaborate on the connection between the con-
textuality scenario 2Reg(G) obtained from a graph G
and the matching scenario of L(G), the line graph of
G, cf. Ref. [25].
The line graph L(G) of a graph G is obtained by
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 26
representing each edge of G as a vertex of L(G) and
for each pair of edges in G that have a non-empty
intersection we connect the corresponding vertices in
L(G) by an edge.
Following Ref. [25], we then have:
Theorem 10. 2Reg(G) = Mat(L(G)), i.e., the
construction of a contextuality scenario from a
graph G under the mapping 2Reg(·) is equivalent
to the construction of a matching scenario obtained
from the line graph of G, namely, L(G). Also,
Dual(2Reg(G)) = L(G), that is, the dual graph of
2Reg(G) is the line graph of G.
A matching scenario Mat(L(G)) is constructed as
follows: every edge of L(G) is represented by a ver-
tex of Mat(L(G)) and each hyperedge of Mat(L(G))
contains those vertices of Mat(L(G)) which represent
edges of L(G) that have a non-empty intersection. We
leave it as an exercise for the reader to verify that the
composition of the two mappings L(.) and Mat(.) ap-
plied to G in that order as Mat ◦ L(G) is the same as
the mapping 2Reg(G) for any G.
Hence, 2Reg(G) is a matching scenario of L(G).
Matching scenarios were discussed in [25]. Indeed,
the following lemma shows how matching scenarios
obtained corresponding to complete graphs discussed
in Ref. [25] arise from bipartite graphs under the map-
ping 2Reg(·).
Lemma 6. L(K
1,n
) is the complete graph K
n
.
2Reg(K
1,n
) = Mat(L(K
1,n
)) is therefore the match-
ing scenario Mat
n
of AFLS [25].
We refer the reader to Sec. 9.4 of Ref. [25] for
further details on matching scenarios. We mention
the connection to matching scenarios of L(G) here
only for completeness and, as such, they are not dis-
cussed in much detail in the main text. We infer
properties of 2Reg(G) directly from G instead of con-
sidering an intermediate graph L(G), since G has a
much more compact representation than L(G) and
the edge-hyperedge correspondence between G and
2Reg(G) can be exploited to understand the struc-
ture of 2Reg(G) and possible probabilistic models on
it. This in turn let us obtain our noncontextuality
inequalities for such scenarios.
B Can the noise-robust noncontextu-
ality inequalities of Eq. (26) be satu-
rated?
It remains an open question whether all noise-robust
noncontextuality inequalities of the form in Eq. (26)
can be saturated by a noncontextual ontological
model. We will, however, describe below a procedure
for constructing a noncontextual ontological model
saturating these inequalities when certain conditions
are satisfied. (Specifically, Eq. (52) below.)
22
For each noise-robust noncontextuality inequality
obtained from a KS-uncolourable contextuality sce-
nario, given by
Corr
q
≡
n
X
i=1
q
i
d
X
x=1
p(m
i
= x, s
i
= x|M
i
, S
i
)
≤ β(Γ, q), (49)
we can sometimes construct a straightforward non-
contextual ontological model that saturates it as long
as some conditions are satisfied. If it exists, such a
model would obviously also satisfy (if not saturate)
any other noise-robust noncontextuality inequality.
To see how this straightforward construction works,
we first write Corr
q
in terms of an ontological model
as
Corr
q
=
n
X
i=1
q
i
d
X
x=1
X
λ∈Λ
ξ(m
i
= x|M
i
, λ)µ(s
i
= x|S
i
, λ)µ(λ|S
i
),
=
n
X
i=1
q
i
d
X
x=1
X
λ∈Λ
ξ(m
i
= x|M
i
, λ)µ(s
i
= x|S
i
, λ)ν(λ),
(using preparation noncontextuality,
µ(λ|S
i
) = ν(λ) ∀λ, i). (50)
We note the following constraint (independent of
noncontextuality) on the ontological representation of
preparations that needs to hold in the model:
µ(s
i
|S
i
, λ)ν(λ) = µ(λ|S
i
, s
i
)p(s
i
|S
i
). (51)
This constraint implies the following phenomenologi-
cal constraint on the ontological model:
∀[s
i
|S
i
] :
X
λ∈Λ
µ(s
i
|S
i
, λ)ν(λ) = p(s
i
|S
i
). (52)
The first step in constructing the model is to choose
µ(s
i
|S
i
, λ) = δ
s
i
,y
, where y is such that
max
m
i
ξ(m
i
|M
i
, λ) = ξ(m
i
= y|M
i
, λ) ≡ ζ(M
i
, λ).
We do this for every S
i
, i ∈ {1, 2, . . . , n}, so that we
now have
Corr
q
=
X
λ∈Λ
n
X
i=1
q
i
ζ(M
i
, λ)
!
ν(λ). (53)
22
We do not know of concrete examples where these condi-
tions might be satisfied but we consider it worthwhile to men-
tion how a noncontextual model could be constructed, should
the reader be interested in investigating the feasibility of our
proposal for particular cases. Of course, a better solution would
be to come up with a different recipe for a construction that
works for any inequality of the form in Eq. (26).
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 27
Note that in all this, the response functions satisfy
the assumption of measurement noncontextuality.
Let us denote by Λ
detP
the following set of λ ∈ Λ:
Λ
detP
≡ {λ ∈ Λ
µ(s
i
|S
i
, λ) = 1 for some [s
i
|S
i
]},
(54)
where s
i
∈ [d], i ∈ [n] for any [s
i
|S
i
].
Next, we choose ν(λ) in such a way that the in-
equality is saturated: in particular, we take ν(λ) to
be supported entirely over the set
Λ
max
≡ {λ ∈ Λ
n
X
i=1
q
i
ζ(M
i
, λ) = β(Γ, q)},
so that ν(λ) = 0 for all λ ∈ Λ\Λ
max
. Recalling the
constraint of Eq. (52), that
∀[s
i
|S
i
] :
X
λ∈Λ
µ(s
i
|S
i
, λ)ν(λ) = p(s
i
|S
i
), (55)
we have that our choice of µ(s
i
|S
i
, λ) and ν(λ) above
should satisfy the property that
Λ
detP
∩ Λ
max
6= ∅, (56)
since otherwise we cannot satisfy the constraint of
Eq. (52). If there exist no λ that lie in Λ
detP
∩ Λ
max
,
then we cannot proceed with our construction of the
noncontextual ontological model. If Eq. (56) is sat-
isfied, then our choices of µ(s
i
|S
i
, λ) and ν(λ) must
further satisfy the constraint of Eq. (52). Again, if
this cannot be done, our construction cannot proceed.
Assuming we have satisfied the constraint of
Eq. (52) while choosing µ(s
i
|S
i
, λ) and ν(λ) as pre-
scribed above, we then have
Corr
q
= β(Γ, q) (57)
and the noise-robust noncontextuality inequality is
thus saturated.
23
References
[1] S. Kochen and E. P. Specker, “The Problem
of Hidden Variables in Quantum Mechanics”, J.
Math. Mech. 17, 59 (1967). Also available at JS-
TOR.
[2] D. A. Meyer, “Finite Precision Measurement Nul-
lifies the Kochen-Specker Theorem”, Phys. Rev.
Lett. 83, 3751 (1999).
[3] A. Kent, “Noncontextual Hidden Variables and
Physical Measurements”, Phys. Rev. Lett. 83,
3755 (1999).
23
What we haven’t shown above is a concrete example of a
scenario where a noncontextual ontological model following our
prescription can actually be constructed and, to that extent,
we haven’t contributed much to proving saturation. We have
merely suggested a possible route towards it.
[4] R. Clifton and A. Kent, “Simulating quantum
mechanics by non-contextual hidden variables”,
Proc. R. Soc. Lond. A: Vol. 456, 2101-2114 (2000).
[5] J. Barrett and A. Kent, “Non-contextuality, finite
precision measurement and the Kochen-Specker
theorem”, Stud. Hist. Philos. Mod. Phys. 35, 151
(2004).
[6] R. Kunjwal and R. W. Spekkens, “From the
Kochen-Specker Theorem to Noncontextuality In-
equalities without Assuming Determinism”, Phys.
Rev. Lett. 115, 110403 (2015).
[7] M. D. Mazurek, M. F. Pusey, R. Kunjwal, K. J.
Resch, R. W. Spekkens, “An experimental test
of noncontextuality without unphysical idealiza-
tions”, Nat. Commun. 7, 11780 (2016).
[8] M. F. Pusey, “Robust preparation noncontextu-
ality inequalities in the simplest scenario”, Phys.
Rev. A 98, 022112 (2018).
[9] A. Krishna, R. W. Spekkens, and E. Wolfe, “De-
riving robust noncontextuality inequalities from
algebraic proofs of the Kochen-Specker theorem:
the Peres-Mermin square”, New J. Phys 19,
123031 (2017).
[10] R. Kunjwal and R. W. Spekkens, “From sta-
tistical proofs of the Kochen-Specker theorem
to noise-robust noncontextuality inequalities”,
Phys. Rev. A 97, 052110 (2018).
[11] D. Schmid, R. W. Spekkens, and E. Wolfe,
“All the noncontextuality inequalities for arbi-
trary prepare-and-measure experiments with re-
spect to any fixed set of operational equivalences”,
Phys. Rev. A 97, 062103 (2018).
[12] R. Kunjwal, “Contextuality beyond the Kochen-
Specker theorem”, arXiv:1612.07250 [quant-ph]
(2016).
[13] R. W. Spekkens, “Contextuality for prepara-
tions, transformations, and unsharp measure-
ments”, Phys. Rev. A 71, 052108 (2005).
[14] R. Kunjwal, “Beyond the Cabello-Severini-
Winter framework: Making sense of contextuality
without sharpness of measurements”, Quantum 3,
184 (2019).
[15] R. W. Spekkens, “The Status of Determinism
in Proofs of the Impossibility of a Noncontextual
Model of Quantum Theory”, Found. Phys. 44,
1125-1155 (2014).
[16] R. Kunjwal, “Fine’s theorem, noncontextuality,
and correlations in Specker’s scenario”, Phys. Rev.
A 91, 022108 (2015).
[17] A. Fine, “Hidden Variables, Joint Probability,
and the Bell Inequalities”, Phys. Rev. Lett. 48,
291 (1982).
[18] R. W. Spekkens, “Leibniz’s principle of the iden-
tity of indiscernibles as a foundational principle
for quantum theory”, Information-Theoretic In-
terpretations of Quantum Mechanics (2016), Uni-
versity of Western Ontario, available at https:
//www.youtube.com/watch?v=HWOkjisIxc4.
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 28
[19] R. W. Spekkens, “The ontological identity of
empirical indiscernibles: Leibniz’s methodological
principle and its significance in the work of Ein-
stein”, arXiv:1909.04628 [physics.hist-ph] (2019).
[20] A. Cabello, Adan, J. Estebaranz, and G. Garcia-
Alcaine, “Bell-Kochen-Specker theorem: A proof
with 18 vectors,” Phys. Lett. A 212, 183 (1996).
[21] A. Peres, “Two simple proofs of the Kochen-
Specker theorem”, J. Phys. A 24, L175 (1991).
[22] N. D. Mermin, “Hidden variables and the two
theorems of John Bell”, Rev. Mod. Phys. 65, 803
(1993).
[23] A. A. Klyachko, M. A. Can, S. Binicio˘glu, and
A. S. Shumovsky, “Simple Test for Hidden Vari-
ables in Spin-1 Systems”, Phys. Rev. Lett. 101,
020403 (2008).
[24] A. Cabello, S. Severini, and A. Winter, “Graph-
Theoretic Approach to Quantum Correlations”,
Phys. Rev. Lett. 112, 040401 (2014).
[25] A. Ac´ın, T. Fritz, A. Leverrier, and A. B. Sainz,
A Combinatorial Approach to Nonlocality and
Contextuality, Comm. Math. Phys. 334(2), 533-
628 (2015).
[26] S. Abramsky and A. Brandenburger, “The sheaf-
theoretic structure of non-locality and contextual-
ity”, New J. Phys. 13, 113036 (2011).
[27] S. Abramsky, R. S. Barbosa, K. Kishida, R. Lal,
and S. Mansfield, “Possibilities determine the
combinatorial structure of probability polytopes”,
Journal of Mathematical Psychology, Volume 74,
Pages 58-65 (2016).
[28] S. Mansfield and R. S. Barbosa, “Extendabil-
ity in the sheaf-theoretic approach: Construc-
tion of Bell models from Kochen-Specker models”,
arXiv:1402.4827 [quant-ph] (2014).
[29] R. Kunjwal, C. Heunen, and T. Fritz, “Quantum
realization of arbitrary joint measurability struc-
tures”, Phys. Rev. A 89, 052126 (2014).
[30] T. Gonda, R. Kunjwal, D. Schmid, E. Wolfe, and
A. B. Sainz, “Almost Quantum Correlations are
Inconsistent with Specker’s Principle”, Quantum
2, 87 (2018).
[31] A. Cabello, “Twin inequality for fully contex-
tual quantum correlations”, Phys. Rev. A 87,
010104(R) (2013).
[32] P. Lisonˇek, P. Badziag, J. R. Portillo, and A. Ca-
bello, “Kochen-Specker set with seven contexts”,
Phys. Rev. A 89, 042101 (2014).
[33] M. Pavicic, J-P. Merlet, B. McKay, and
N. D. Megill, “Kochen-Specker vectors”, J. Phys.
A: Math. Gen. 38 1577 (2005).
[34] S. Mansfield, “The Mathematical Structure of
Non-locality and Contextuality”, PhD thesis, Uni-
versity of Oxford (2013).
[35] G. Car`u, “Towards a complete cohomology
invariant for non-locality and contextuality”,
arXiv:1807.04203 [quant-ph] (2018).
[36] A. Krishna, “Experimentally Testable Noncon-
textuality Inequalities Via Fourier-Motzkin Elim-
ination”, M.Sc. Thesis, University of Waterloo
(2015).
[37] D. Schmid and R. W. Spekkens, “Contextual Ad-
vantage for State Discrimination”, Phys. Rev. X
8, 011015 (2018).
Accepted in Quantum 2019-12-31, click title to verify. Published under CC-BY 4.0. 29