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