# Gadget structures in proofs of the Kochen-Specker theorem

Ravishankar Ramanathan  Laboratoire d’Information Quantique, Université Libre
de Bruxelles, Belgium  Monika Rosicka  Institute of Theoretical Physics and
Astrophysics and the National Quantum Information Centre, Faculty of
Mathematics, Physics and Informatics, University of Gdansk, 80-308 Gdansk,
Poland.  Karol Horodecki  Institute of Informatics and the National Quantum
Information Centre, Faculty of Mathematics, Physics and Informatics,
University of Gdansk, 80-309 Gdansk, Poland.  Stefano Pironio  Laboratoire
d’Information Quantique, Université Libre de Bruxelles, Belgium  Michał
Horodecki  Institute of Theoretical Physics and Astrophysics and the National
Quantum Information Centre, Faculty of Mathematics, Physics and Informatics,
University of Gdansk, 80-308 Gdansk, Poland.  Paweł Horodecki  Faculty of
Applied Physics and Mathematics and the National Quantum Information Centre,
Gdansk University of Technology, 80-233 Gdansk, Poland.

###### Abstract

The Kochen-Specker theorem is a fundamental result in quantum foundations that
has spawned massive interest since its inception. We show that within every
Kochen-Specker graph, there exist interesting subgraphs which we term
$01$-gadgets, that capture the essential contradiction necessary to prove the
Kochen-Specker theorem, i.e,. every Kochen-Specker graph contains a
$01$-gadget and from every $01$-gadget one can construct a proof of the
Kochen-Specker theorem. Moreover, we show that the $01$-gadgets form a
fundamental primitive that can be used to formulate state-independent and
state-dependent statistical Kochen-Specker arguments as well as to give simple
constructive proofs of an “extended” Kochen-Specker theorem first considered
by Pitowsky in Pitowsky .

##  I Introduction

According to the quantum formalism, a projective measurement $M$ is described
by a set $M=\\{V_{\\_}1,\ldots,V_{\\_}m\\}$ of projectors $V_{\\_}i$ that are
orthogonal, $V_{\\_}iV_{\\_}j=\delta_{\\_}{ij}V_{\\_}i$, and sum to the
identity, $\sum_{\\_}iV_{\\_}i=I$. Each $V_{\\_}i$ corresponds to a possible
outcome $i$ of the measurement $M$ and determines the probability of this
outcome when measuring a state $|\psi\rangle$ through the formula
$\text{Pr}_{\\_}{\psi}(i\mid M)=\langle\psi|V_{\\_}i|\psi\rangle$.

If two physically distinct measurements $M=\\{V_{\\_}1,\ldots,V_{\\_}m\\}$ and
$M^{\prime}=\\{V^{\prime}_{\\_}1,\ldots,V^{\prime}_{\\_}{m^{\prime}}\\}$ share
a common projector, i.e., $V_{\\_}i=V^{\prime}_{\\_}{i^{\prime}}=V$ for some
outcome $i$ of $M$ and $i^{\prime}$ of $M^{\prime}$, it then follows that

$\text{Pr}_{\\_}{\psi}(i\mid M)=\text{Pr}_{\\_}{\psi}(i^{\prime}\mid
M^{\prime})=\langle\psi|V|\psi\rangle\,.$ (1)

In other words, though quantum measurements are defined by _sets_ of
projectors, the outcome probabilities of these measurements are determined by
the _individual_ projectors alone, independently of the broader set – or the
_context_ – to which they belong. We say that the probability assignment is
_non-contextual_.

The Kocken-Specker (KS) theorem KS  is a cornerstone result in the foundations
of quantum mechanics, establishing that, in Hilbert spaces of dimension
greater than two, it is not possible to find a _deterministic_ outcome
assignment that is non-contextual. Deterministic means that all outcome
probabilities should take only the values $0$ or $1$. Non-contextual means, as
above, that these probabilities are not directly assigned to the measurements
themselves, but to the individual projectors from which they are composed,
independently of the context to which the projectors belong. More formally,
the KS theorem establishes that it is not possible to find a rule $f$ such
that

$\text{Pr}_{\\_}{f}(i\mid M)=\text{Pr}_{\\_}{f}(i^{\prime}\mid
M^{\prime})=f(V)\in\\{0,1\\}\,,$ (2)

which would provide a deterministic analogue of a quantum state.

The most common way to prove the KS theorem involves a set
$\mathcal{S}=\\{V_{\\_}1,\ldots,V_{\\_}n\\}$ of rank-one projectors. We can
represent these projectors by the vectors (strictly speaking, the rays) onto
which they project and thus view $\mathcal{S}$ as a set of vectors
$\mathcal{S}=\\{|v_{\\_}1\rangle,\ldots,|v_{\\_}n\rangle\\}\subset\mathbb{C}^{d}$.
Consider an assignment $f:\mathcal{S}\rightarrow\\{0,1\\}$ that associates to
each $|v_{\\_}i\rangle$ in $\mathcal{S}$ a probability
$f(|v_{\\_}i\rangle)\in\\{0,1\\}$. To interpret the $f(|v_{\\_}i\rangle)$ as
valid measurement outcome probabilities, they should satisfy the two following
conditions:

(3)

The first condition is required because if a set of vectors are mutually
orthogonal, they may be part of the same measurement, but then their
corresponding probabilities must sum at most to 1. The second condition
follows from the fact that if $d$ vectors are mutually orthogonal in
$\mathbb{C}^{d}$, they form a complete basis, and then their corresponding
probabilities must exactly sum to one. Note that the first condition implies
in particular that any two vectors $|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$
in $\mathcal{S}$ that are orthogonal cannot both be assigned the value 1 by
$f$.

We call any assignment $f:\mathcal{S}\rightarrow\\{0,1\\}$ satisfying the
above two conditions, a $\\{0,1\\}$-coloring of $\mathcal{S}$. The Kocken-
Specker theorem states that if $d\geq 3$, there exist sets of vectors that are
not $\\{0,1\\}$-colorable, thus establishing the impossibility of a non-
contextual deterministic outcome assignment. We call such
$\\{0,1\\}$-uncolorable sets, KS sets. In their original proof, Kochen and
Specker describe a set $\mathcal{S}$ of 117 vectors in $\mathbb{C}^{d}$
dimension $d=3$ KS . The minimal KS set contains 18 vectors in dimension $d=4$
CEG96 ; Cab08 .

In this paper, we identify within KS sets interesting subsets which we term
$01$-gadgets. Such $01$-gadgets are $\\{0,1\\}$-colorable and thus do not
represent by themselves KS sets. However, they do not admit arbitrary
$\\{0,1\\}$-coloring: in any $\\{0,1\\}$-coloring of a $01$-gadget, there
exist two non-orthogonal vectors $|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$
that cannot both be assigned the color 1. We show that such $01$-gadgets form
the essence of the KS contradiction, in the sense that every KS set contains a
$01$-gadget and from every $01$-gadget one can construct a KS set.

Besides being useful in the construction of KS sets, we show that $01$-gadgets
also form a fundamental primitive in constructing statistical KS arguments à
la Clifton Clifton93  and state-independent non-contextuality inequalities as
introduced in YO12 . Moreover, we show that an “extended” Kochen-Specker
theorem considered by Pitowsky Pitowsky  and Abbott et al. ACS15 ; ACCS12  can
be easily proven using an extension of the notion of $01$-gadgets. We give
simple constructive proofs of these different results.

Certain $01$-gadgets have already been studied previously in the literature,
as they possess other interesting properties. In particular, $01$-gadgets were
also used in Arends09  to show that the problem of checking whether certain
families of graphs (which represent natural candidates for KS sets) are
$\\{0,1\\}$-colorable is NP-complete, a result which we refine in the present
paper.

This paper is organized as follows. In section II, we introduce some notation
and elementary concepts, in particular the representation of KS sets as
graphs. In section III, we define the notion of $01$-gadgets and establish
their relation to KS sets. In section IV, we give several constructions of
$01$-gadgets and associated KS sets. In section V, we show how $01$-gadgets
can be used to construct statistical KS arguments. In section VI, we also show
a simple constructive proof of the extended Kochen-Specker theorem of Pitowsky
Pitowsky  and Abbott et al. ACCS12  using a notion of extended $01$-gadgets
which we introduce. In section VII, we show that $01$-gadgets can be used to
establish the NP-completeness of $\\{0,1\\}$-coloring of the family of graphs
relevant for KS proofs. We finish by a general discussion and conclusion in
section IX.

##  II Preliminaries

Much of the reasoning involving KS sets is usually carried out using a graph
representation of KS sets defined below. We thus start by reminding some basic
graph-theoretic definitions.

#### Graphs.

Throughout the paper, we will deal with simple undirected finite graphs $G$,
i.e., finite graphs without loops, multi-edges or directed edges. We denote
$V(G)$ the vertices of $G$ and $E(G)$ the edges of $G$. If two vertices
$v_{\\_}1,v_{\\_}2$ are connected by an edge, we say that they are adjacent,
and write $v_{\\_}1\sim v_{\\_}2$.

A subgraph $H$ of $G$ (denoted $H<G$) is a graph formed from a subset of
vertices and edges of $G$, i.e., $V(H)\subseteq V(G)$ and $E(H)\subseteq
E(G)$. An induced subgraph $K$ of $G$ (denoted $K\lhd G$) is a subgraph that
includes all the edges in $G$ whose endpoints belong to the vertex subset
$V(K)\subseteq V(G)$, i.e., $E(K)\subseteq E(G)$ with $(v_{\\_}1,v_{\\_}2)\in
E(K)$ iff $(v_{\\_}1,v_{\\_}2)\in E(G)$ for all $v_{\\_}1,v_{\\_}2\in V(K)$.

A clique in the graph $G$ is a subset of vertices $Q\subset V(G)$ such that
every pair of vertices in $Q$ is connected by an edge, i.e., $\forall
v_{\\_}1,v_{\\_}2\in Q$ we have $v_{\\_}1\sim v_{\\_}2$. A maximal clique in
$G$ is a clique that is not a subset of a larger clique in $G$. A maximum
clique in $G$ is a clique that is of maximum size in $G$. The clique number
$\omega(G)$ of $G$ is the cardinality of a maximum clique in $G$.

#### Orthogonality graphs.

The use of graphs in the context of the KS theorem comes from the fact that it
is convenient to represent the orthogonality relations in a KS set
$\mathcal{S}$ by a graph $G_{\\_}\mathcal{S}$, known as its orthogonality
graph CSW10 ; CSW14 . In such a graph, each vector $|v_{\\_}i\rangle$ in
$\mathcal{S}$ is represented by a vertex $v_{\\_}i$ of $G_{\\_}{\mathcal{S}}$
and two vertices $v_{\\_}1,v_{\\_}2$ of $G_{\\_}{\mathcal{S}}$ are connected
by an edge if the associated vectors $|v_{\\_}1\rangle,|v_{\\_}2\rangle$ are
orthogonal, i.e. $v_{\\_}1\sim v_{\\_}2$ if $\langle
v_{\\_}1|v_{\\_}2\rangle=0$ (for instance the graph in Fig. 1 is the
orthogonality graph of the set of vectors given by eq. (III)).

It follows that in an orthogonality graph $G_{\\_}{\mathcal{S}}$, a clique
corresponds to a set of mutually orthogonal vectors in $\mathcal{S}$. If
$\mathcal{S}\subset\mathbb{C}^{d}$ contains a basis set of $d$ orthogonal
vectors, then the maximum clique in $G_{\\_}{\mathcal{S}}$ is of size
$\omega(G_{\\_}{\mathcal{S}})=d$.

#### Coloring of graphs.

The problem of $\\{0,1\\}$-coloring $\mathcal{S}$ thus translates into the
problem of coloring the vertices of its orthogonality graph
$G_{\\_}\mathcal{S}$ such that vertices connected by an edge cannot both be
assigned the color 1 and maximum cliques have exactly one vertex of color 1.
Formally, we say that an arbitrary graph $G$ is $\\{0,1\\}$-colorable if there
exists an assignment $f:V(G)\rightarrow\\{0,1\\}$ such that

(4)

The KS theorem is then equivalent to the statement that there exist for any
$d\geq 3$, finite sets of vectors $\mathcal{S}\subset\mathbb{C}^{d}$ (the KS
sets) such that their orthogonality graph $G_{\\_}{\mathcal{S}}$ is not
$\\{0,1\\}$-colorable. Deciding if a given graph $G$ admits a
$\\{0,1\\}$-coloring is NP-complete Arends09 . Note that any graph $G$ that is
not $\\{0,1\\}$-colorable must contain at least two cliques of maximum size
$\omega(G)$. Indeed, if a graph $G$ contains a single clique of maximum size
it always admits a $\\{0,1\\}$-coloring consisting in assigning the value 0 to
all its vertices, except for one vertex in the maximum clique that is assigned
the value 1.

#### Orthogonal representations.

For a given graph $G$, an orthogonal representation $\mathcal{S}$ of $G$ in
dimension $d$ is a set of non-zero vectors
$\mathcal{S}=\\{|v_{\\_}i\rangle\\}$ in $\mathbb{C}^{d}$ obeying the
orthogonality conditions imposed by the edges of the graph, i.e.,
$v_{\\_}1\sim v_{\\_}2\Rightarrow\langle v_{\\_}1|v_{\\_}2\rangle=0$ Lovasz87
. We denote by $d(G)$ the minimum dimension of an orthogonal representation of
$G$ and we say that $G$ has dimension $d(G)$. Obviously, $d(G)\geq\omega(G)$.
A _faithful_ orthogonal representation of $G$ is given by a set of vectors
$\mathcal{S}=\\{|v_{\\_}i\rangle\\}$ that in addition obey the condition that
non-adjacent vertices are assigned non-orthogonal vectors, i.e., $v_{\\_}1\sim
v_{\\_}2\Leftrightarrow\langle v_{\\_}1|v_{\\_}2\rangle=0$ and that distinct
vertices are assigned different vectors, i.e., $v_{\\_}1\neq
v_{\\_}2\Leftrightarrow|v_{\\_}1\rangle\neq|v_{\\_}2\rangle$. We denote by
$d^{*}(G)$ the minimum dimension of such a faithful orthogonal representation
of $G$ and we say that $G$ has faithful dimension $d^{*}(G)$.

Given a graph $G$ of dimension $d(G)$, the orthogonality graph
$G_{\\_}\mathcal{S}$ of the minimal orthogonal representation $\mathcal{S}$ of
$G$ has faithful dimension $d^{*}(G_{\\_}\mathcal{S})=d(G)$. The graph
$G_{\\_}\mathcal{S}$ can be seen as obtained from $G$ by adding edges (between
vertices that are non-adjacent in $G$, but corresponding to vectors in
$\mathcal{S}$ that are nevertheless orthogonal) and by identifying certain
vertices (those that correspond to identical vectors in $\mathcal{S}$). We say
that $G_{\\_}\mathcal{S}$ is the faithful version of $G$.

#### KS graphs.

While the non-$\\{0,1\\}$-colorability of a set $S$ translates into the
non-$\\{0,1\\}$-colorability of its orthogonality graph $G_{\\_}\mathcal{S}$,
the non-$\\{0,1\\}$-colorability of an arbitrary graph $G$ translates into the
non-$\\{0,1\\}$-colorability of one of its orthogonal representations only if
this representation has the minimal dimension $d(G)=\omega(G)$. Indeed, it is
only under this condition that the requirement that $\sum_{\\_}{v\in
Q_{\\_}{\max}}f(v)=1$ in the definition of the $\\{0,1\\}$-coloring of the
graph $G$ gives rise to the corresponding requirement that $\sum_{\\_}{v\in
Q_{\\_}{\max}}f(|v\rangle)=1$ for its orthogonal representation (if the
dimension $d$ is larger than $\omega(G)=|Q_{\\_}{\max}|$, the
$|Q_{\\_}{\max}|<d$ mutually orthogonal vectors $\\{|v\rangle:v\in
Q_{\\_}{\max}\\}$ in $\mathbb{C}^{d}$ do not form a basis).

If a graph $G$ is not $\\{0,1\\}$-colorable and has dimension
$d(G)=\omega(G)$, it thus follows that its minimal orthogonal representation
$\mathcal{S}$ forms a KS set. If in addition $d^{*}(G)=\omega(G)$, we say that
$G$ is a KS graph (this last condition can always be obtained by considering
the faithful version of $G$, i.e., the orthogonality graph
$G_{\\_}\mathcal{S}$ of its minimal orthogonal representation $\mathcal{S}$).

The problem of finding KS sets can thus be reduced to the problem of finding
KS graphs. But as we have noticed above, deciding if a graph is
$\\{0,1\\}$-colorable is NP-complete. In addition, while finding an orthogonal
representation for a given graph can be expressed as finding a solution to a
system of polynomial equations, efficient numerical methods for finding such
representations are still lacking. Thus, finding KS sets in arbitrary
dimensions is a difficult problem towards which a huge amount of effort has
been expended CA96 . In particular, “records” of minimal Kochen-Specker
systems in different dimensions have been studied CEG96 , the minimal KS
system in dimension four is the $18$-vector system due to Cabello et al. CEG96
; Cab08  while lower bounds on the size of minimal KS systems in other
dimensions have also been established.

##  III $01$-gadgets and the Kochen-Specker theorem

We now introduce the notion of $01$-gadgets that play a crucial role in
constructions of KS sets.

######  Definition 1.

A $01$-gadget in dimension $d$ is a $\\{0,1\\}$-colorable set
$\mathcal{S}_{\\_}\text{gad}\subset\mathbb{C}^{d}$ of vectors containing two
distinguished vectors $|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$ that are non-
orthogonal, but for which $f(|v_{\\_}1\rangle)+f(|v_{\\_}2\rangle)\leq 1$ in
every $\\{0,1\\}$-coloring $f$ of $\mathcal{S}_{\\_}\text{gad}$.

In other words, while a $01$-gadget $\mathcal{S}_{\\_}\text{gad}$ admits a
$\\{0,1\\}$-coloring, in any such coloring the two distinguished non-
orthogonal vertices cannot both be assigned the value $1$ (as if they were
actually orthogonal). We can give an equivalent, alternative definition of a
gadget as a graph.

######  Definition 2.

A $01$-gadget in dimension $d$ is a $\\{0,1\\}$-colorable graph
$G_{\\_}\text{gad}$ with faithful dimension
$d^{*}(G_{\\_}\text{gad})=\omega(G_{\\_}\text{gad})=d$ and with two
distinguished non-adjacent vertices $v_{\\_}1\nsim v_{\\_}2$ such that
$f(v_{\\_}1)+f(v_{\\_}2)\leq 1$ in every $\\{0,1\\}$-coloring $f$ of
$G_{\\_}\text{gad}$.

In the following when we refer to a $01$-gadget, we freely alternate between
the equivalent set or graph definitions.

An example of a $01$-gadget in dimension 3 is given by the following set of 8
vectors in $\mathbb{C}^{3}$:

$\displaystyle|u_{\\_}1\rangle=\frac{1}{\sqrt{3}}(-1,1,1),\;\;|u_{\\_}2\rangle=\frac{1}{\sqrt{2}}(1,1,0),$
$\displaystyle|u_{\\_}3\rangle=\frac{1}{\sqrt{2}}(0,1,-1),|u_{\\_}4\rangle=(0,0,1),$
$\displaystyle|u_{\\_}5\rangle=(1,0,0),\;\;|u_{\\_}6\rangle=\frac{1}{\sqrt{2}}(1,-1,0),$
$\displaystyle|u_{\\_}7\rangle=\frac{1}{\sqrt{2}}(0,1,1),\;\;|u_{\\_}8\rangle=\frac{1}{\sqrt{3}}(1,1,1),$
(5)

where the two distinguished vectors are $|v_{\\_}1\rangle=|u_{\\_}1\rangle$
and $|v_{\\_}2\rangle=|u_{\\_}8\rangle$. Its orthogonality graph is
represented in Fig. 1. It is easily seen from this graph representation that
the vertices $u_{\\_}1$ and $u_{\\_}8$ cannot both be assigned the value 1, as
this then necessarily leads to the adjacent vertices $u_{\\_}4$ and $u_{\\_}5$
to be both assigned the value 1, in contradiction with the
$\\{0,1\\}$-coloring rules. This graph was identified by Clifton, following
work by Stairs Clifton93 ; Stairs , and used by him to construct statistical
proofs of the Kochen-Specker theorem. We will refer to it as the Clifton
gadget $G_{\\_}{\text{Clif}}$. The Clifton gadget and similar gadgets were
termed “definite prediction sets” in CA96 .

Figure 1: The $8$-vertex “Clifton” graph that was used by Kochen and Specker
in their construction of the $117$ vector KS set. The two distinguished
vertices are $u_{\\_}1$ and $u_{\\_}8$.

We identify the role played by 01-gadgets in the construction of Kochen-
Specker sets via the following theorem.

######  Theorem 1.

For any Kochen-Specker graph $G_{\\_}\text{KS}$, there exists a subgraph
$G_{\\_}{\text{gad}}<G_{\\_}{\text{KS}}$ with
$\omega(G_{\\_}\text{gad})=\omega(G_{\\_}\text{KS})$ that is a $01$-gadget.
Moreover, given a $01$-gadget $G_{\\_}{\text{gad}}$, one can construct a KS
graph $G_{\\_}\text{KS}$ with
$\omega(G_{\\_}\text{KS})=\omega(G_{\\_}{\text{gad}})$.

The demonstration of our theorem is constructive, it allows to build a
$01$-gadget from a KS graph and conversely. The $01$-gadget in the original
$117$-vector proof by Kochen-Specker is the Clifton graph in Fig. 1. A
$16$-vertex $01$-gadget in dimension 4 that is an induced subgraph of the
$18$-vertex KS graph introduced in CEG96  is represented in Fig. 2.

Figure 2: A $16$ vertex coloring gadget (also a $101$-gadget) that is a
subgraph of the $18$ vertex Kochen-Specker graph in dimension $d=4$ found by
Cabello et al. CEG96 . The $9$ edge colors denote $9$ cliques in the graph,
with the maximum clique being of size $\omega(G)=4$. The distinguished
vertices $u_{\\_}1,u_{\\_}6$ are denoted by black circles.

###### Proof.

We start by showing the first part of the Theorem: that one can construct a
$01$-gadget $G_{\\_}{\text{gad}}$ from any KS graph $G_{\\_}\text{KS}$. Given
$G_{\\_}\text{KS}$, which by definition is not $\\{0,1\\}$-colorable, we first
construct, by deleting vertices one at a time, an induced subgraph
$G_{\\_}{\text{crit}}$ that is vertex-critical. By vertex-critical, we mean
that $(i)$ $G_{\\_}{\text{crit}}$ is not $\\{0,1\\}$-colorable, but $(ii)$ any
subgraph obtained from it by deleting a supplementary vertex does admit a
$\\{0,1\\}$-coloring. Observe that in the process of constructing
$G_{\\_}{\text{crit}}$ we are able to preserve the maximum clique size, i.e.,
$\omega(G_{\\_}{\text{crit}})=\omega(G_{\\_}{\text{KS}})$. This is because we
are able to delete vertices from all but two maximum cliques, simply because
at least two maximum cliques must exist in a graph that is not
$\\{0,1\\}$-colorable. Observe also that $G_{\\_}{\text{crit}}$ is itself a KS
graph, since the faithful orthogonal representation of $G_{\\_}\text{KS}$ in
dimension $d=\omega(G_{\\_}{\text{ KS}})$ provides an orthogonal
representation of $G_{\\_}\text{crit}$ in the same dimension.

We consider three cases: $(i)$ there exists a vertex in $G_{\\_}{\text{crit}}$
that belongs to a single maximum clique, $(ii)$ all vertices in
$G_{\\_}{\text{crit}}$ belong to at least two maximum cliques, and there
exists a vertex that belong to exactly two maximum cliques; $(iii)$, all
vertices in $G_{\\_}{\text{crit}}$ belong to at least three maximum cliques.
In the first two cases, which happens to be the case encountered in all known
KS graphs, we will be able to prove that the $01$-gadget appears as an induced
subgraph while in the third case, the $01$-gadget appears as a subgraph that
may not necessarily be induced.

In case $(i)$, let $v$ be one of the vertices having the property that it
belongs to a single maximum clique. We denote this clique $Q_{\\_}1\subset
G_{\\_}{\mathcal{S}}^{\text{crit}}$. Deleting $v$ leads to a graph
$G_{\\_}{\text{crit}}\setminus v$ that is $\\{0,1\\}$-colorable by definition.
However, observe that in any coloring $f$ of $G_{\\_}{\text{crit}}\setminus
v$, all the vertices in $Q_{\\_}1\setminus v$ are assigned the value $0$ by
$f$. This is because, if one of these vertices were assigned value $1$, then
one could obtain a valid coloring of $G_{\\_}{\text{crit}}$ from $f$ by
defining $f(v)=0$. Choose a vertex $v_{\\_}1\in Q_{\\_}1\setminus v$ and any
other non-adjacent vertex $v_{\\_}2\in G_{\\_}{\text{crit}}\setminus v$. Then
$G_{\\_}{\text{crit}}\setminus v$ is the required $01$-gadget with
$v_{\\_}1,v_{\\_}2$ playing the role of the distinguished vertices.

In case $(ii)$, let $v$ be one of the vertices having the property that it
belongs to exactly two maximum cliques, which we denote
$Q_{\\_}1,Q_{\\_}2\subset G_{\\_}{\text{crit}}$. Again, deleting $v$ leads to
a graph $G_{\\_}{\text{crit}}\setminus v$ that is $\\{0,1\\}$-colorable.
However, in any coloring $f$ of $G_{\\_}{\text{crit}}\setminus v$, it cannot
be that a value $f(v_{\\_}1)=1$ and a value $f(v_{\\_}2)=1$ are simultaneously
assigned to a vertex $v_{\\_}1\in Q_{\\_}1\setminus v$ and a vertex
$v_{\\_}2\in Q_{\\_}2\setminus v$. This is again because if there was such a
coloring $f$, then one could obtain a valid coloring for
$G_{\\_}{\text{crit}}$ by defining $f(v)=0$, in contradiction with the
criticality of $G_{\\_}{\text{crit}}$. Choose $v_{\\_}1\in Q_{\\_}1\setminus
v$ and $v_{\\_}2\in Q_{\\_}2\setminus v$ such that $v_{\\_}1$ and $v_{\\_}2$
are not adjacent. Two such vertices must exist. Indeed, if all vertices
$Q_{\\_}1\setminus v$ where adjacent to all vertices of $Q_{\\_}2\setminus v$,
then the maximum clique size would be strictly greater than
$\omega(G_{\\_}\text{crit})$. Therefore, we have that
$G_{\\_}{\text{crit}}\setminus v$ is the required $01$-gadget with
$v_{\\_}1,v_{\\_}2$ the distinguished vertices.

Finally, we consider the case $(iii)$ where each vertex in
$G_{\\_}{\text{crit}}$ belongs to at least three maximum cliques. In this
case, we cannot proceed as above where we remove a certain vertex $v$ and pick
vertices from two maximal cliques containing $v$, because we can no longer
guarantee that these two vertices cannot simultaneously be assigned the value
1 (we can only guarantee that a certain $t$-uple of vertices, each one picked
from the $t$ maximum cliques to which $v$ belongs, cannot all simultaneously
be assigned the value 1). Instead, we proceed as follows. We start by deleting
edges of $G_{\\_}{\text{crit}}$ one at a time, to construct a new graph
$G^{\prime}_{\\_}{\text{crit}}$ that is edge-critical. By edge-critical, we
mean, similarly to the construction above, that
$G^{\prime}_{\\_}{\text{crit}}$ is not $\\{0,1\\}$-colorable, but any graph
obtained from it by deleting a supplementary edge (and thus also by deleting a
supplementary vertex) does admit a $\\{0,1\\}$-coloring. As above, we are able
to preserve the maximum clique size in the process, i.e.,
$\omega(G^{\prime}_{\\_}{\text{crit}})=\omega(G_{\\_}{\text{crit}})=\omega(G_{\\_}\text{KS}))$
and $G^{\prime}_{\\_}{\text{crit}}$ is still a KS graph admitting an
orthogonal representation in dimension
$d=\omega(G^{\prime}_{\\_}{\text{crit}})$.

If the resulting graph $G^{\prime}_{\\_}{\text{crit}}$ is as in the cases
$(i)$ and $(ii)$ above, we proceed as before to construct a $01$-gadget from a
graph $G^{\prime}_{\\_}{\text{crit}}\setminus v$, with the caveat that
choosing two non-adjacent vertices $v_{\\_}1$ and $v_{\\_}2$ in
$G^{\prime}_{\\_}{\text{crit}}$ does not necessarily guarantee that they are
non-orthogonal in the natural representation induced by the one of
$G_{\\_}\text{KS}$. This is because we have been removing edges from
$G_{\\_}\text{crit}$ to construct $G^{\prime}_{\\_}\text{crit}$. However, we
can always choose two vertices $v_{\\_}1$ and $v_{\\_}2$ that were non-
adjacent in the original graph $G_{\\_}\text{KS}$ and thus that correspond to
non-orthogonal vectors. Again, this is because otherwise the maximum clique
size of $G_{\\_}\text{KS}$ would be greater than $\omega(G_{\\_}\text{KS})$.
The $01$-gadget construction can then be completed by taking the faithful
version of $G^{\prime}_{\\_}{\text{crit}}\setminus v$.

If the resulting graph $G^{\prime}_{\\_}{\text{crit}}$ is not as in the cases
$(i)$ and $(ii)$ above, we proceed as follows. Let $v$ be an arbitrary vertex
of $G^{\prime}_{\\_}{\text{crit}}$. By assumption, this vertex belong to at
least two maximun cliques $Q_{\\_}1,Q_{\\_}2$ (and actually even at least a
third one). Delete all the edges $(v,v^{\prime})$ from $Q_{\\_}1$ where
$v^{\prime}\in Q_{\\_}1$ to form $G^{\prime}_{\\_}{\text{crit}}\setminus
E(Q_{\\_}1)$ which is $\\{0,1\\}$-colorable by definition. In any such
coloring $f$, either $f(v)=0$ or $f(v)=1$. In the first case, we must
necessarily have that $f(v^{\prime})=0$ for all $v^{\prime}\in
Q_{\\_}1\setminus v$, since otherwise the coloring $f$ would also define a
valid coloring for $G^{\prime}_{\\_}{\text{crit}}$. In the second case, we
have $f(v^{\prime\prime})=0$ for all $v^{\prime\prime}\in Q_{\\_}2\setminus v$
by definition of a coloring. We thus conclude that it cannot be simultaneously
the case that $f(v^{\prime})=f(v^{\prime\prime})=1$ for $v^{\prime}\in
Q_{\\_}1\setminus v$ and $v^{\prime\prime}\in Q_{\\_}2\setminus v$. Choose
$v_{\\_}1\in Q_{\\_}1$ and $v_{\\_}2\in Q_{\\_}2$ non-adjacent in
$G_{\\_}\text{KS}$, which is always possible by the same argument as given
before. The faithful version of the graph
$G^{\prime}_{\\_}{\text{crit}}\setminus E(Q_{\\_}1)$ forms the required
$01$-gadget with $v_{\\_}1,v_{\\_}2$ being the distinguished vertices.

We now proceed to prove the second part of the statement. Starting from a
gadget graph we give a construction of a KS graph. The construction
generalizes the original Kochen-Specker construction of KS  to arbitrary
dimensions and arbitrary repeating gadget units. Given $G_{\\_}{\text{gad}}$,
we know that there exists a faithful orthogonal representation
$\\{|v_{\\_}i\rangle\\}_{\\_}{i=1}^{n}$ in a Hilbert space of dimension
$d=\omega(G_{\\_}{\text{gad}})$ with $n=|V(G_{\\_}{\text{gad}})|$. Let
$v_{\\_}1,v_{\\_}2$ denote the distinguished vertices, and let
$|v_{\\_}2^{\perp}\rangle$ denote a vector orthogonal to $|v_{\\_}2\rangle$
that lies in the plane $\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$,
spanned by the vectors $|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$, with
$\theta=\arccos{|\langle v_{\\_}1|v_{\\_}2^{\perp}\rangle|}>0$ by definition
of a $01$-gadget. We consider the following cases: $(i)$ $\frac{\pi}{2\theta}$
is rational and can be written as $\frac{p}{q}$ with $q$ an odd integer,
$(ii)$ $\frac{\pi}{2\theta}$ is rational and is given by $\frac{p}{q}$ with
$q$ an even integer, or alternatively, $\frac{\pi}{2\theta}$ is irrational.

_Case $(i)$: $\frac{\pi}{2\theta}$ is rational and is given by $\frac{p}{q}$
with $q$ an odd integer._ Recall that $|v_{\\_}2^{\perp}\rangle$ is orthogonal
to $|v_{\\_}2\rangle$ in the plane
$\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$. In the subspace orthogonal
to $\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$, choose a basis consisting
of $d-2$ mutually orthogonal vectors
$|w_{\\_}1\rangle,\dots,|w_{\\_}{d-2}\rangle$. Denoting
$G^{\prime}_{\\_}{\text{gad}}$ as the orthogonality graph of the entire set of
these vectors
$\\{|v_{\\_}i\rangle\\}_{\\_}{i=1}^{n}\bigcup\\{|v_{\\_}2^{\perp}\rangle,|w_{\\_}1\rangle,\dots,|w_{\\_}{d-2}\rangle\\}$,
we obtain a gadget graph that can be used as a building block in a Kochen-
Specker type construction. In particular, the crucial property of
$G^{\prime}_{\\_}{\text{gad}}$ is that in any $\\{0,1\\}$-coloring $f$,
$f(v_{\\_}1)=1\Rightarrow f(v_{\\_}2^{\perp})=1$. This can be seen as follows:
$f(v_{\\_}1)=1$ implies, by the $\\{0,1\\}$-coloring rules, that
$f(w_{\\_}i)=0$ for all $i\in[d-2]$. Moreover, by the gadget property, we have
$f(v_{\\_}2)=0$, and this imposes $f(v_{\\_}2^{\perp})=1$ to satisfy the
requirement that exactly one of the vertices in the maximum clique
$(v_{\\_}2,v_{\\_}2^{\perp},w_{\\_}1,\dots,w_{\\_}{d-2})$ is assigned value
$1$.

As in the original KS construction of KS , we construct a chain of $p+1$
copies $G^{\prime(i)}_{\\_}{\text{gad}}$ $(i=0,1,\ldots,p\\}$ of
$G^{\prime}_{\\_}{\text{gad}}$ so that $p\theta=q\frac{\pi}{2}$ is an odd
integral multiple of $\frac{\pi}{2}$. These copies are obtained from the
realization of $G^{\prime}_{\\_}{\text{gad}}$ by successive applications of a
unitary $\mathcal{U}$, i.e.,
$|v_{\\_}j^{(i)}\rangle=\mathcal{U}^{i}|v_{\\_}j\rangle$ for $i=0,1,\ldots,p$
and $j=1,\ldots,n$ and similarly for the other vectors in
$G^{\prime}_{\\_}{\text{gad}}$. This unitary operator $\mathcal{U}$ is defined
as

$\displaystyle\mathcal{U}=|v_{\\_}2^{\perp}\rangle\langle
v_{\\_}1|-|v_{\\_}2\rangle\langle v_{\\_}1^{\perp}|+{\bf 1}_{\\_}W,$ (6)

where $|v_{\\_}1^{\perp}\rangle$ denotes the vector orthogonal to
$|v_{\\_}1\rangle$ in the plane
$\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$ and where ${\bf 1}_{\\_}W$
denotes the identity on the subspace orthogonal to
$\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$. Writing
$|v_{\\_}2^{\perp}\rangle=\alpha|v_{\\_}1\rangle+\beta|v_{\\_}1^{\perp}\rangle$
for some $\alpha,\beta\in\mathbb{C}$, we see that applying once $\mathcal{U}$
to the faithful realization of $G^{\prime}_{\\_}{\text{gad}}$ gives

$\displaystyle\mathcal{U}|v_{\\_}1\rangle=|v_{\\_}2^{\perp}\rangle,$
$\displaystyle\mathcal{U}|v_{\\_}2^{\perp}\rangle=\alpha|v_{\\_}2^{\perp}\rangle-\beta|v_{\\_}2\rangle.$
(7)

We have evidently $|\langle
v_{\\_}2^{\perp}|\mathcal{U}|v_{\\_}2^{\perp}\rangle|=|\langle
v_{\\_}1|v_{\\_}2^{\perp}\rangle|$ and that

$\displaystyle\arccos|\langle
v_{\\_}1|\mathcal{U}|v_{\\_}2^{\perp}\rangle|=2\arccos|\langle
v_{\\_}1|v_{\\_}2^{\perp}\rangle|=2\theta.$ (8)

We thus have that under successive applications of $\mathcal{U}$,
$|v_{\\_}1^{(0)}\rangle\rightarrow|v_{\\_}1^{(1)}\rangle=|v_{\\_}2^{\perp,(0)}\rangle$,
$|v_{\\_}2^{\perp,(0)}\rangle\rightarrow|v_{\\_}2^{\perp,(1)}\rangle$,
$|v_{\\_}1^{(1)}\rangle\rightarrow|v_{\\_}1^{(2)}\rangle=|v_{\\_}2^{\perp,(1)}\rangle$,
$|v_{\\_}2^{\perp,(1)}\rangle\rightarrow|v_{\\_}2^{\perp,(2)}\rangle$, and so
on, with $|v_{\\_}1^{(p)}\rangle\perp|v_{\\_}1^{(0)}\rangle$. Furthermore, in
any $\\{0,1\\}$-coloring $f$ of the graph union
$\bigcup_{\\_}{i}G^{\prime(i)}_{\\_}{\text{gad}}$,
$f(v_{\\_}1^{(0)})=1\Rightarrow f(v_{\\_}1^{(p)})=1$. A similar construction
of $d-1$ copies of $\bigcup_{\\_}{i}G^{\prime(i)}_{\\_}{\text{gad}}$ gives
rise to a graph with a clique formed by the vertices
$v_{\\_}1^{(0)},v_{\\_}1^{(p)}$ and the $d-2$ vectors that complete the basis.
The resulting graph is a Kochen-Specker graph since in any
$\\{0,1\\}$-coloring, if any of the vertices in this maximal clique is
assigned value $1$ then so are all of them, giving rise to a contradiction. We
thus obtain a finite system of vectors given by the union of the vector sets
in each of the graphs, that gives rise to a proof of the Kochen-Specker
theorem in dimension $\omega(G_{\\_}{\text{gad}})$.

_Case $(ii)$: $\frac{\pi}{2\theta}$ is rational and is given by $\frac{p}{q}$
with $q$ an even integer, or alternatively, $\frac{\pi}{2\theta}$ is
irrational._

In this case, we construct from $G_{\\_}{\text{gad}}$ a larger gadget
$\tilde{G}_{\\_}{\text{gad}}$ with the property that the angle
$\tilde{\theta}$ between the distinguished vectors obeys
$\frac{\pi}{2\tilde{\theta}}=\frac{\tilde{p}}{\tilde{q}}\in\mathbb{Q}$, with
$\tilde{q}$ an odd integer. As in the previous case, we let
$|v_{\\_}2^{\perp}\rangle$ be the vector orthogonal to $|v_{\\_}2\rangle$ in
the plane $\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$, and
$|v_{\\_}1^{\perp}\rangle$ be the vector orthogonal to $|v_{\\_}1\rangle$ in
this plane, so that
$|v_{\\_}2^{\perp}\rangle=\alpha|v_{\\_}1\rangle+\beta|v_{\\_}1^{\perp}\rangle$,
for some $\alpha,\beta\in\mathbb{C}$. We also consider a basis
$\\{|w_{\\_}1\rangle,\dots,|w_{\\_}{d-2}\rangle\\}$ for the subspace
orthogonal to $\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$ and denote
$G^{\prime}_{\\_}{\text{gad}}$ as the orthogonality graph of the set of
vectors
$\\{|v_{\\_}i\rangle\\}_{\\_}{i=1}^{n}\bigcup\\{|v_{\\_}2^{\perp}\rangle,|w_{\\_}1\rangle,\dots,|w_{\\_}{d-2}\rangle\\}$.

Let $\mathcal{U}$ denote a unitary operator transforming $|v_{\\_}1\rangle$ to
$|v_{\\_}2^{\perp}\rangle$, i.e., $\mathcal{U}$ is of the form

$\displaystyle\mathcal{U}$ $\displaystyle=$
$\displaystyle|v_{\\_}2^{\perp}\rangle\langle
v_{\\_}1|-|v^{\prime}_{\\_}2\rangle\langle v_{\\_}1^{\perp}|+$ (9)
$\displaystyle+|w^{\prime}_{\\_}1\rangle\langle
w_{\\_}1|+\dots+|w^{\prime}_{\\_}{d-2}\rangle\langle w_{\\_}{d-2}|$

with $|v^{\prime}_{\\_}2\rangle$,
$|w^{\prime}_{\\_}1\rangle,\ldots,|w^{\prime}_{\\_}{d-2}\rangle$ orthogonal to
$|v_{\\_}2^{\perp}\rangle$ and orthogonal to each other. Applying
$\mathcal{U}$ to the orthogonal representation of the gadget gives that

$\displaystyle\mathcal{U}|v_{\\_}1\rangle$ $\displaystyle=$
$\displaystyle|v_{\\_}2^{\perp}\rangle,$
$\displaystyle\mathcal{U}|v_{\\_}2^{\perp}\rangle$ $\displaystyle=$
$\displaystyle\alpha|v_{\\_}2^{\perp}\rangle-\beta|v^{\prime}_{\\_}2\rangle$
(10)

Let $\tilde{\theta}=\arccos|\langle
v_{\\_}1|\mathcal{U}|v_{\\_}2^{\perp}\rangle|$. We choose
$|v^{\prime}_{\\_}2\rangle$ and thereby $\mathcal{U}$ such that
$\frac{\pi}{2\tilde{\theta}}=\frac{\tilde{p}}{\tilde{q}}\in\mathbb{Q}$ with
$\tilde{q}$ an odd integer. Now construct $G^{\prime}_{\\_}{\text{gad}}$ as
the orthogonality graph of the set of vectors

$\displaystyle\\{|v_{\\_}i\rangle\\}_{\\_}{i=1}^{n}\bigcup\\{|v_{\\_}2^{\perp}\rangle,|w_{\\_}1\rangle,\dots,|w_{\\_}{d-2}\rangle\\}\bigcup$
$\displaystyle\\{\mathcal{U}|v_{\\_}i\rangle\\}_{\\_}{i=2}^{n}\bigcup\\{\mathcal{U}|v_{\\_}2^{\perp}\rangle,|w^{\prime}_{\\_}1\rangle,\dots,|w^{\prime}_{\\_}{d-2}\rangle\\}.$
(11)

We have thus concatenated two gadgets to form the new gadget
$G^{\prime}_{\\_}{\text{gad}}$ with the property that if
$f(|v_{\\_}1\rangle)=1$ then also $f(|v_{\\_}2^{\perp}\rangle)=1$ and
consequently also $f(\mathcal{U}|v_{\\_}2^{\perp}\rangle)=1$. We are now in
the same position as in the previous case i.e., we may construct a chain of
$\tilde{p}+1$ copies $G^{\prime(i)}_{\\_}{\text{gad}}$ of
$G^{\prime}_{\\_}{\text{gad}}$ and follow the steps as in the previous case to
construct the entire KS set in dimension $\omega(G_{\\_}{\text{gad}})$.

In both cases, we thus obtain a construction of a Kochen-Specker set in
dimension $\omega(G_{\\_}{\text{gad}})$, completing the proof.
$\sqcap$$\sqcup$

We remark that the above Theorem does not guarantee that the $01$-gadgets
appear as induced subgraphs in KS graphs; this is the case only when at least
one vertex in the $\\{0,1\\}$-critical subgraph of the KS graph belongs to at
most two maximum cliques.

##  IV Other 01-gadgets and KS sets constructions

In this section, we make some interesting observations about $01$-gadgets and
provide new constructions of $01$-gadgets that will be used in the next
sections.

######  Lemma 1.

For any $d\geq 3$, there exists a $01$-gadget in dimension $d$ consisting of
$5+d$ vertices.

###### Proof.

For $d=3$, a 8-vertex $01$-gadget is simply given by the Clifton gadget
$G_{\\_}{\text{Clif}}$. In higher dimensions, a new $01$-gadget
$G^{\prime}_{\\_}{\text{Clif}}$ can be obtained by adding $d-3$ vertices to
$G_{\\_}{\text{Clif}}$ with edges joining the additional vertices to each
other and to each of the $8$ vertices in $G_{\\_}{\text{Clif}}$. Clearly, a
faithful representation of $G^{\prime}_{\\_}{\text{Clif}}$ can be obtained by
supplementing the $3$-dimensional representation of $G_{\\_}{\text{Clif}}$
with $d-3$ mutually orthogonal vectors in the complementary subspace. The
construction preserves the property that a $\\{0,1\\}$-coloring of
$G^{\prime}_{\\_}{\text{Clif}}$ exists and that the two distinguished vertices
$v_{\\_}1,v_{\\_}2$ of $G_{\\_}{\text{Clif}}$, now viewed as vertices of
$G^{\prime}_{\\_}{\text{Clif}}$, cannot both be assigned the value $1$ in any
$\\{0,1\\}$ coloring.  $\sqcap$$\sqcup$

The $8$-vertex Clifton gadget $G_{\\_}{\text{Clif}}$ was shown to be the
minimal $01$-gadget in dimension 3 Arends09 . This result was obtained by an
exhaustive search over all non-isomorphic square-free graphs of up to $7$
vertices. It is an open question to prove if the simple construction in Lemma
1 gives the minimal $01$-gadgets in dimension $d>3$ or whether even smaller
gadgets exist in these higher dimensions.

In the Clifton gadget $G_{\\_}{\text{Clif}}$ the overlap between the two
distinguised vertices is $|\langle v_{\\_}1|v_{\\_}2\rangle|=1/3$. The
following Lemma shows that one can reduce this overlap at the expense of
increasing the dimension by one.

######  Lemma 2.

Let $G$ be a $01$-gadget in dimension $d$ with distinguished vectors
$|u_{\\_}1\rangle,|u_{\\_}2\rangle$. Then there exists a $01$-gadget
$G^{\prime}$ in dimension $d+1$ with distinguished vertices
$|v_{\\_}1\rangle,|v_{\\_}2\rangle$ for any choice of the overlap $0<|\langle
v_{\\_}1|v_{\\_}2\rangle|\leq|\langle u_{\\_}1|u_{\\_}2\rangle|$.

###### Proof.

Let $\\{|u_{\\_}i\rangle\\}_{\\_}{i=1}^{n}\subset\mathbb{C}^{d}$ be the set of
$n$ vectors forming the gadget $G$. We define $G^{\prime}$ as the set of $n+1$
vectors $\\{|v_{\\_}i\rangle\\}_{\\_}{i=0}^{n}$ in $\mathbb{C}^{d+1}$ defined
as follows. For given $|u_{\\_}i\rangle\in\mathbb{C}^{d}$, let
$|\tilde{u}_{\\_}i\rangle\in\mathbb{C}^{d+1}$ be the vector obtained by
padding a $0$ to the end of $|u_{\\_}i\rangle$. Define the vectors
$|v_{\\_}i\rangle$ as

$|v_{\\_}i\rangle:=\left\\{\begin{array}[]{lr}(0,\dots,0,1)^{T},&\text{for
}i=0\\\
\mathcal{N}\left(|\tilde{u}_{\\_}1\rangle+x(0,\dots,0,1)^{T}\right),&\text{for
}i=1\\\ |\tilde{u}_{\\_}i\rangle&\text{for }i=2,\dots,n\end{array}\right.$

with a free parameter $x\in\mathbb{R}$ and corresponding normalization factor
$\mathcal{N}$. Now, notice that the orthogonality relations between the set of
vectors $|v_{\\_}1\rangle,\dots,|v_{\\_}{n}\rangle$ is the same as the
orthogonality relations between the set of vectors
$|u_{\\_}1\rangle,\dots,|u_{\\_}{n}\rangle$. The only additional orthogonality
relations in $G^{\prime}$ involve $|v_{\\_}0\rangle$, which is orthogonal to
all other vectors but $|v_{\\_}1\rangle$. By this property, it follows that if
$f(|v_{\\_}0\rangle)=0$ in a coloring of $G^{\prime}$, then the coloring of
the remaining vectors $|v_{\\_}1\rangle,\dots,|v_{\\_}{n}\rangle$ is
constrained exactly as for $|u_{\\_}1\rangle,\dots,|u_{\\_}{n|}\rangle$ in
$G$. In particular, we cannot have simultaneously
$f(|v_{\\_}1\rangle)=f(|v_{\\_}2\rangle)=1$. Now simply observe that if
$f(|v_{\\_}2\rangle)=1$, we must have necessarily have $f(|v_{\\_}0\rangle)=0$
since $|v_{\\_}0\rangle\perp|v_{\\_}2\rangle$ and thus $|v_{\\_}1\rangle$
cannot also satisfy $f(|v_{\\_}1\rangle)=1$. In other words, $G^{\prime}$ is a
$01$-gadget with $|v_{\\_}1\rangle,|v_{\\_}2\rangle$ playing the role of the
distinguished vertices. Finally, we see that by varying the free parameter
$x\in\mathbb{R}$, we get any overlap $0<|\langle
v_{\\_}1|v_{\\_}2\rangle|\leq|\langle u_{\\_}1|u_{\\_}2\rangle|$ between the
distinguished vertices.  $\sqcap$$\sqcup$

We now show the following.

######  Theorem 2.

Let $|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$ be any two distinct non-
orthogonal vectors in $\mathbb{C}^{d}$ with $d\geq 3$. Then there exists a
01-gadget in dimension $d$ with $|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$
being the two distinguished vertices.

While the existence of such a construction can be anticipated from the Kochen-
Specker construction from Theorem 1, we give a construction with much fewer
vectors based on the $43$-vertex graph of Fig. 3.

###### Proof.

The construction is based on the $43$-vertex graph $G$ of Fig. 3. We first
show the construction for $\mathbb{C}^{3}$, and then straightforwardly extend
it to $\mathbb{C}^{d}$ for $d>3$. Suppose thus that we are given
$|v_{\\_}1\rangle,|v_{\\_}2\rangle\in\mathbb{C}^{3}$. We consider two cases:
(i) $0<|\langle v_{\\_}1|v_{\\_}2\rangle|\leq\frac{1}{\sqrt{2}}$ and (ii)
$\frac{1}{\sqrt{2}}<|\langle v_{\\_}1|v_{\\_}2\rangle|\leq 1$.

Case (i): $0<|\langle v_{\\_}1|v_{\\_}2\rangle|\leq\frac{1}{\sqrt{2}}$.
Suppose without loss of generality that $|v_{\\_}1\rangle=(1,0,0)^{T}$ and
$|v_{\\_}{2}\rangle=\frac{1}{\sqrt{1+x^{2}}}(x,1,0)^{T}$ with $0<x\leq 1$. In
this case, the induced subgraph $G_{\\_}{\text{ind}}$ of $G$ consisting of the
vertex set $V(G_{\\_}{\text{ind}})=\\{1,\dots,22\\}$ and
$E(G_{\\_}{\text{ind}})=\\{(u_{\\_}i,u_{\\_}j):1\leq i,j\leq
22,(u_{\\_}i,u_{\\_}j)\in E(G)\\}$ will suffice to construct the gadget with
$u_{\\_}1$ and $u_{\\_}{22}$ the two distinguished vertices, corresponding to
$|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$. First, it is easily verified from
the graph that in any $\\{0,1\\}$-coloring $f$, $f(u_{\\_}1)$ and
$f(u_{\\_}{22})$ cannot both be assigned the value 1. It thus only remains to
provide an orthogonal representation of the graph $G_{\\_}{\text{ind}}$. Such
a representation is given by the following set of (non-normalized) vectors:

$\displaystyle|u_{\\_}1\rangle=(1,0,0)^{T};\;\;|u_{\\_}2\rangle=(0,1,-1)^{T};\;\;|u_{\\_}3\rangle=(0,1,0)^{T};$
$\displaystyle|u_{\\_}4\rangle=(0,y,1)^{T};\;\;|u_{\\_}5\rangle=(2x,1,1)^{T};\;\;|u_{\\_}6\rangle=(-1,0,2x)^{T};$
$\displaystyle|u_{\\_}7\rangle=(-2x,0,-1)^{T};\;\;|u_{\\_}8\rangle=(x,1,-2x^{2})^{T};$
$\displaystyle|u_{\\_}9\rangle=(2x^{3},2x^{2},1+x^{2})^{T};$
$\displaystyle|u_{\\_}{10}\rangle=(-(1+x^{2}),0,2x^{3})^{T};$
$\displaystyle|u_{\\_}{11}\rangle=(2x^{3},0,1+x^{2})^{T};$
$\displaystyle|u_{\\_}{12}\rangle=(x(1+x^{2}),1+x^{2},-2x^{4})^{T};$
$\displaystyle|u_{\\_}{13}\rangle=(2x^{5},2x^{4},(1+x^{2})^{2})^{T};$
$\displaystyle|u_{\\_}{14}\rangle=(-(1+x^{2})^{2},0,2x^{5})^{T};$
$\displaystyle|u_{\\_}{15}\rangle=(2x^{5},0,(1+x^{2})^{2})^{T};$
$\displaystyle|u_{\\_}{16}\rangle=(x(1+x^{2})^{2},(1+x^{2})^{2},-2x^{6})^{T};$
$\displaystyle|u_{\\_}{17}\rangle=(2x^{7},2x^{6},(1+x^{2})^{3})^{T};$
$\displaystyle|u_{\\_}{18}\rangle=(-x(1+y^{2}),-1,y)^{T};$
$\displaystyle|u_{\\_}{19}\rangle=(1,-x,-x)^{T};\;\;|u_{\\_}{20}\rangle=(1,-x,0)^{T};$
$\displaystyle|u_{\\_}{21}\rangle=(1,-x,xy)^{T};\;\;|u_{\\_}{22}\rangle=(x,1,0)^{T};$
(12)

with

$\displaystyle
y=\frac{(1+x^{2})^{3}+\sqrt{(1+x^{2})^{6}-16x^{14}(1+x^{2})}}{4x^{8}}\,.$ (13)

It is easily verified that this set of vectors satisfy all the orthogonality
relations encoded by the induced subgraph $G_{\\_}{\text{ind}}$ we are
considering.

Case (ii): $\frac{1}{\sqrt{2}}<|\langle v_{\\_}1|v_{\\_}2\rangle|\leq 1$.
Suppose without loss of generality that $|v_{\\_}1\rangle=(1,0,0)^{T}$ and
$|v_{\\_}{2}\rangle=(1+x,1-x,0)^{T}/\sqrt{2+2x^{2}}$ with $0<x\leq 1$. In this
case, we consider the entire $43$-vertex graph $G$ from Fig. 3, with
$u_{\\_}1$ and $u_{\\_}{42}$ the two distinguished vertices, corresponding to
$|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$. Again, it is easily seen that in
any $\\{0,1\\}$-coloring $f$, $f(u_{\\_}1)$ and $f(u_{\\_}{42})$ cannot both
be assigned the value 1. It thus only remains to provide an orthogonal
representation of the graph $G$.

The graph $G$ can be seen as being composed from $(i)$ the induced subgraph
$G_{\\_}{\text{ind}}$ with vertices $u_{\\_}1,\ldots,u_{\\_}{22}$ considered
above, $(ii)$ an isomorphic subgraph $G^{\prime}_{\\_}{\text{ind}}$ with
vertices
$u^{\prime}_{\\_}1=u_{\\_}{20},u^{\prime}_{\\_}2=u_{\\_}{23},\ldots,u^{\prime}_{\\_}{22}=u_{\\_}{42}$,
$(iii)$ the vertex $u_{\\_}{43}$ connected to $u_{\\_}1$, $u_{\\_}{20}$,
$u_{\\_}{22}$, $u_{\\_}{42}$.

The first 22 vectors $u_{\\_}1,\ldots,u_{\\_}{22}$ of $G_{\\_}{\text{ind}}$
are chosen as above with $x=1$ and $y=2+\sqrt{2}$. The 22 vectors
$u^{\prime}_{\\_}1,\ldots,u^{\prime}_{\\_}{22}$ of
$G^{\prime}_{\\_}{\text{ind}}$ are also obtained from the above solution, but
with $0<x\leq 1$ a free parameter, and after applying first a unitary $U$ that
maps $(1,0,0)$ to $(1,-1,0)/\sqrt{2}$ and $(0,1,0)$ to $(1,1,0)\sqrt{2}$ and
leave invariant $(0,0,1)$. We thus have
$|u_{\\_}1\rangle=|v_{\\_}1\rangle=(1,0,0)^{T}$ and
$|u_{\\_}{42}\rangle=|v_{\\_}2\rangle=(1+x,1-x,0)^{T}/\sqrt{2+2x^{2}}$ as
assumed.

By construction, the orthogonality relations of the subgraphs
$G_{\\_}{\text{ind}}$ and $G^{\prime}_{\\_}{\text{ind}}$ are satisfied. We
also have that the vectors common to the two subgraphs are indeed identical,
namely $|u_{\\_}{20}\rangle=(1,-1,0)^{T}$ and
$|u_{\\_}{22}\rangle=(1,1,0)^{T}$. Furthemore, choosing
$|u_{\\_}{43}\rangle=(0,0,1)^{T}$, we also have that $|u_{\\_}{43}\rangle$ is
orthogonal to $|u_{\\_}1\rangle,|u_{\\_}{20}\rangle,|u_{\\_}{22}\rangle$, and
$|u_{\\_}{42}\rangle$ as required.

This completes the construction of the gadget for $\mathbb{C}^{3}$. Now, one
may simply consider the same set of vectors as being embedded in any
$\mathbb{C}^{d}$ (with additional vectors $(0,0,0,1,0,\dots,0)^{T}$,
$(0,0,0,0,1,0,\dots,0)^{T}$ etc.) to construct a gadget in this dimension.
$\sqcap$$\sqcup$

Figure 3: The 43 vertex $01$-gadget used in the proof of Theorem 2.

Theorem 2 allows to construct new KS graphs than the one given in the proof of
Theorem 1. Some of such constructions in dimension 3 are shown in Fig. 4. A
crucial role in these is played by the repeating unit $G_{\\_}0$ shown in Fig.
4 (a). This unit is given by a set of basis vectors
$\\{|u_{\\_}1\rangle,|u_{\\_}2\rangle,|u_{\\_}3\rangle\\}$ all connected via
appropriate $01$-gadgets to a central vector $|v_{\\_}1\rangle$. In any
$\\{0,1\\}$-coloring $f$ of $G_{\\_}0$, one of the three basis vectors must be
assigned the value $1$, so that we necessarily have $f(|v_{\\_}1\rangle)=0$.
In other words, $G_{\\_}0$ is a graph in which a particular vector necessarily
takes value $0$ in any $\\{0,1\\}$-coloring. Note that this property is also
shown by the graph in Fig. 3

Note that from $G_{\\_}0$, one can also construct an orthogonality graph
$G_{\\_}1$ in which a particular vector necessarily takes values 1 in any
$\\{0,1\\}$-coloring. Indeed, consider two copies of $G_{\\_}0$ with the
respective central vectors $|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$
orthogonal to each other, so that $f(|v_{\\_}1\rangle)=f(|v_{\\_}2\rangle)=0$.
Then, in any $\\{0,1\\}$-coloring of the resulting graph $G_{\\_}1$, the third
basis vector $|v_{\\_}3\rangle\perp|v_{\\_}1\rangle,|v_{\\_}2\rangle$
necessarily obeys $f(|v_{\\_}3\rangle)=1$.

Figure 4: Graphs with the dashed edges denoting $01$-gadgets. (a) In any
$\\{0,1\\}$-coloring of the graph $G_{\\_}0$, the central vertex is
necessarily assigned value $0$. (b) Three copies of $G_{\\_}0$ with the
central vertices forming a basis in $\mathbb{C}^{3}$ so that the resulting
graph $G_{\\_}{KS1}$ forms a Kochen-Specker proof. (c) Another proof of the KS
theorem $G_{\\_}{KS2}$ is obtained by connecting every pair of vectors in two
bases by a $01$-gadget.

In Fig. 4 (b), a KS proof in $\mathbb{C}^{3}$ is based on the unit $G_{\\_}0$,
repeated three times with a basis set of central vectors
$|v_{\\_}1\rangle,|v_{\\_}2\rangle,|v_{\\_}3\rangle$. By the property of
$G_{\\_}0$ in any $\\{0,1\\}$-coloring, all these three basis vectors are
assigned value $0$ leading to a KS contradiction. In Fig. 4 (c), the
construction is based on two basis sets
$\\{|u_{\\_}1\rangle,|u_{\\_}2\rangle,|u_{\\_}3\rangle\\}$ and
$\\{|v_{\\_}1\rangle,|v_{\\_}2\rangle,|v_{\\_}3\rangle\\}$ with an appropriate
$01$-gadget connecting every pair $|u_{\\_}i\rangle,|v_{\\_}j\rangle$ for
$i,j=1,2,3$. So that assigning value $1$ to any of the vectors in one basis,
necessarily implies that all of the vectors in the other basis are assigned
value $0$, leading to a contradiction. Furthermore, the construction can be
readily extended to derive KS graphs using any frustrated graph.

##  V Statistical KS arguments based on $01$-gadgets

The KS theorem can be seen as a proof that no non-contextual deterministic
hidden-variable interpretation of quantum theory is possible. In a
deterministic hidden-variable model, we aim to reproduce the quantum
probabilities

$\text{Pr}_{\\_}{\psi}(i|M)=\sum_{\\_}\lambda
q_{\\_}{\psi}(\lambda)f_{\\_}\lambda(i|M)$ (14)

in term of hidden-variables $\lambda$, where a distribution
$q_{\\_}{\psi}(\lambda)$ over the hidden-variables is associated to each
quantum state $|\psi\rangle$, and where for each $\lambda$, the model predicts
with certainty that one of the outcomes $i$ will occur for each measurement
$M$, i.e., the hidden measurement outcome probabilities $f_{\\_}\lambda(i|M)$
satisfy $f_{\\_}\lambda(i|M)\in\\{0,1\\}$. Furthermore, the model is non-
contextual if, as in the quantum case, the probabilistic assignment to the
outcome $i$ of the (projective) measurement $M$, only depends on the
corresponding projector $V_{\\_}i$, independently of the wider context
provided by the full description of the measurement
$M=\\{V_{\\_}1,V_{\\_}2,\ldots,V_{\\_}n\\}$. In other words in a non-
contextual deterministic hidden-variable, we aim to write for every projector
$V$:

$\langle\psi|V|\psi\rangle=\sum_{\\_}\lambda
q_{\\_}{\psi}(\lambda)f_{\\_}\lambda(V)\,,$ (15)

where $f_{\\_}\lambda(V)\in\\{0,1\\}$. Obviously, we should also require for
consistency that $\sum_{\\_}{i\in\mathcal{O}}f(V_{\\_}i)\leq 1$ for any set
$\mathcal{O}$ of mutually orthogonal projectors, with equality when the
projectors in $\mathcal{O}$ sum to the identity.

No-go theorems against such models, i.e., “proofs of contextuality” , are
usually obtained by considering a finite set
$\mathcal{S}=\\{|v_{\\_}1\rangle,\ldots,|v_{\\_}n\rangle\\}\subset\mathbb{C}^{d}$
of rank-one projectors $V_{\\_}i$, represented as vectors through
$V_{\\_}i=|v_{\\_}i\rangle\langle v_{\\_}i|$. Specializing to this case, a
non-contextual hidden variable model should satisfy for each
$|v_{\\_}i\rangle$ in $\mathcal{S}$ and each $|\psi\rangle$ in
$\mathbb{C}^{d}$,

$|\langle\psi|v_{\\_}i\rangle|^{2}=\sum_{\\_}\lambda
q_{\\_}{\psi}(\lambda)f_{\\_}\lambda(|v_{\\_}i\rangle)\,,$ (16)

where the $f_{\\_}\lambda:\mathcal{S}\rightarrow\\{0,1\\}$ are
$\\{0,1\\}$-colorings of $\mathcal{S}$.

At least three types of no-go theorems, from strongest to weakest, against
such non-contextual hidden-variable models can be constructed.

The first types correspond to Kochen-Specker theorems. They establish that for
certain sets $\mathcal{S}$, it is not possible to consistently define
$\\{0,1\\}$-colorings $f_{\\_}\lambda$ of $\mathcal{S}$, even before
attempting to use them to reproduce the quantum probabilities. This is what we
have discussed until now.

In the second type of proofs, a $\\{0,1\\}$-coloring of $\mathcal{S}$ is not
excluded. But it can be shown that for any such coloring $f_{\\_}\lambda$ of
$\mathcal{S}$, a certain inequality
$\sum_{\\_}ic_{\\_}if_{\\_}\lambda(|v_{\\_}i\rangle)\leq c_{\\_}0$ must
necessarily be satisfied, while in the quantum case, it happens that
$\sum_{\\_}ic_{\\_}i|v_{\\_}i\rangle\langle v_{\\_}i|>c_{\\_}0\mathbb{I}$. In
other words, though it is possible to find a $\\{0,1\\}$ assignment
$f_{\\_}\lambda(|v_{\\_}i\rangle)$ to each projector $|v_{\\_}i\rangle\langle
v_{\\_}i|$ in $\mathcal{S}$ that is compatible with the orthogonality
relations among such projectors, any such assignment fails to reproduce some
more complex relation of the type $\sum_{\\_}ic_{\\_}i|v_{\\_}i\rangle\langle
v_{\\_}i|>c_{\\_}0\mathbb{I}$ satisfied by these projectors. This immediately
implies a contradiction with eq. (16), since in the quantum case we have for
any $|\psi\rangle$,
$\sum_{\\_}ic_{\\_}i|\langle\psi|v_{\\_}i\rangle|^{2}>c_{\\_}0$, while
according to a non-contextual hidden variable model, we would have
$\sum_{\\_}ic_{\\_}i|\langle\psi|v_{\\_}i\rangle|^{2}=\sum_{\\_}\lambda
q_{\\_}{\psi}(\lambda)\left[\sum_{\\_}ic_{\\_}if_{\\_}\lambda(|v_{\\_}i\rangle)\right]\leq\sum_{\\_}\lambda
q_{\\_}{|\psi\rangle}(\lambda)c_{\\_}0\leq c_{\\_}0$. Such no-go theorems are
referred to as “statistical state-independent” KS arguments and were
introduced by Yu and Oh YO12 .

Finally, for certain sets $\mathcal{S}$, it is possible to find valid
$\\{0,1\\}$-colorings that do not lead to any type of contradictions of the
second type above. However, it is not possible to take mixtures of such
colorings, as in eq. (16), to reproduce the predictions of certain quantum
states $|\psi\rangle$. Such no-go theorems are referred to as “statistical
state-dependent” KS arguments and were introduced by Clifton in Clifton93 .

While we have seen in the previous section how proofs of the KS theorem can be
constructed using $01$-gadgets, in this section we show how to use them to
build statistical state-independent and state-dependent KS arguments

###  V.1 State-independent KS arguments

In YO12 , Yu and Oh introduced a set of 13 vectors in $\mathbb{C}^{3}$ that
provides a state-independent proof of contextuality, despite not being a KS
set. We show how using Theorem 2, it is possible to construct other state-
independent proofs of contextuality based on $01$-gadgets. To do this, we make
use of the following lemma.

######  Lemma 3.

Let $|u_{\\_}i\rangle$, for $i=1,\dots,d+1$ be the unit vectors denoting the
vertices of a $d$-dimensional simplex embedded in $\mathbb{R}^{d}$. Then

$\displaystyle\sum_{\\_}{i=1}^{d+1}|u_{\\_}i\rangle\langle
u_{\\_}i|=\frac{d+1}{d}\mathbb{I}.$ (17)

###### Proof.

Since $|u_{\\_}i\rangle$ form the vertices of the $d$-simplex, we have
$\langle u_{\\_}i|u_{\\_}j\rangle=-\frac{1}{d}$ for any $i\neq
j\in\\{1,\dots,d+1\\}$. It then follows

$\displaystyle\left(\sum_{\\_}{i=1}^{d+1}\langle
u_{\\_}i|\right)\left(\sum_{\\_}{j=1}^{d+1}|u_{\\_}i\rangle\right)=(d+1)+d(d+1)\left(-\frac{1}{d}\right)=0,$

so that

$\displaystyle O:=\sum_{\\_}{i=1}^{d+1}|u_{\\_}i\rangle\langle
u_{\\_}i|=-\sum_{\\_}{i\neq j=1}^{d+1}|u_{\\_}i\rangle\langle u_{\\_}j|$ (18)

This then implies that

$\displaystyle O^{2}=O-\frac{1}{d}\sum_{\\_}{i\neq
j=1}^{d+1}|u_{\\_}i\rangle\langle u_{\\_}j|=\frac{d+1}{d}O.$ (19)

Moreover, $O$ is invertible, since
$\text{span}(\\{|u_{\\_}i\rangle\\}_{\\_}{i=1}^{d+1})=\mathbb{R}^{d}$ so that
we obtain $O=\frac{d+1}{d}\mathbb{I}$.  $\sqcap$$\sqcup$

Now, state-independent KS arguments for $\mathbb{C}^{d}$ are straightforwardly
constructed as follows. For every pair of vectors
$|u_{\\_}i\rangle,|u_{\\_}j\rangle$ of the $d$-simplex, consider a $01$-gadget
$\mathcal{S}_{\\_}{ij}$ with $|u_{\\_}i\rangle$, $|u_{\\_}j\rangle$ the
distinguished vertices. Since $|u_{\\_}i\rangle$ and $|u_{\\_}j\rangle$ are
non-orthogonals, such gadgets exists, as implied by Theorem 2. The resulting
set of vectors $\mathcal{S}=\cup_{\\_}{ij}\mathcal{S}_{\\_}{ij}$ exhibits
state-independent contextuality. Indeed, by the property of the $01$-gadgets,
only one of the vectors $|u_{\\_}i\rangle$ for $i=1,\dots,d+1$ can be assigned
the value $1$ in any $\\{0,1\\}$-coloring of $\mathcal{S}$. It thus follows
that

$\displaystyle\sum_{\\_}{i=1}^{d+1}f(|u_{\\_}i\rangle)\leq 1,.$ (20)

On the other hand, from Lemma 3, every state $|\psi\rangle$ from
$\mathbb{C}^{d}$ achieves the value
$\sum_{\\_}{i=1}^{d+1}|\langle\psi|u_{\\_}i\rangle|^{2}=\frac{d+1}{d}>1$.

While we have used the $d+1$ vertices of a $d$-simplex in the construction
above, we observe that any set $\\{|u_{\\_}i\rangle\\}$ of vectors in
$\mathbb{C}^{d}$ such that $\sum_{\\_}{i}|\langle\psi|u_{\\_}i\rangle|^{2}>1$
for all $|\psi\rangle\in\mathbb{C}^{d}$ can be utilized in the construction,
although such a set clearly needs to contain at least $d+1$ vectors.

###  V.2 State-dependent KS arguments

The relation between state-dependent KS arguments and 01-gadgets is even more
direct than in the above construction. Actually, the first state-dependent KS
argument introduced by Clifton in Clifton93  was precisely based on the set of
vectors (III) forming the Clifton gadget $G_{\\_}\text{gad}$. His argument was
as follows. In every non-contextual hidden-variable model attempting to
replicate the quantum probabilities associated to the projectors of the
Clifton gadget, we should have
$|\langle\psi|u_{\\_}1\rangle|^{2}+|\langle\psi|u_{\\_}8\rangle|^{2}=\sum_{\\_}\lambda
q_{\\_}\psi(\lambda)\left(f_{\\_}\lambda(|u_{\\_}1\rangle)+f_{\\_}\lambda(|u_{\\_}8\rangle)\right)\leq
1$, by the gadget property. However, if we take
$|\psi\rangle=|u_{\\_}1\rangle$, we find that according to the quantum
predictions $|\langle u_{\\_}1|u_{\\_}1\rangle|^{2}+|\langle
u_{\\_}1|u_{\\_}8\rangle|^{2}=1+|\langle u_{\\_}1|u_{\\_}8\rangle|^{2}>1$
since $|\langle u_{\\_}1|u_{\\_}8\rangle|^{2}>0$ as $|u_{\\_}1\rangle$ and
$|u_{\\_}8\rangle$ are non-orthogonal. Other state-dependent proofs based on
inequalities have since been developed, with the smallest involving five
vectors KCBS08 .

Obviously, the argument used by Clifton for the particular set of vectors he
introduced, immediately carries over to any $01$-gadget. Thus every
$01$-gadget serves as a proof of state-dependent contextuality.

Note that it was realized in CDLP14  that a class of graphs, known as perfect
graphs, define a class of graphs that cannot serve as proofs of (even state-
dependent) contextuality. That is, for any orthogonal representation
$\\{|v_{\\_}j\rangle\\}\subset\mathbb{C}^{d}$ of a perfect graph and for any
pure state $|\psi\rangle\in\mathbb{C}^{d}$, the outcome probabilities
$|\langle\psi|v_{\\_}j\rangle|^{2}$ admit a non-contextual hidden variable
model of the form (16). Since a non-contextual hidden variable model is not
possible for a $01$-gadget, we deduce that no perfect graph is a $01$-gadget.
Perfect graphs are a well-known class of graphs which by the strong perfect
graph theorem CRST06  can be characterized as those graphs that do not contain
odd cycles and anti-cycles of length greater than three as induced subgraphs.

Finally, remark that the argument due to Clifton presented above works not
only for the state $|\psi\rangle=|u_{\\_}1\rangle$, but for any state
$|\psi\rangle\in\mathbb{C}^{3}$ which obeys
$|\langle\psi|u_{\\_}1\rangle|^{2}+|\langle\psi|u_{\\_}8\rangle|^{2}>1$. More
generally, we now present a $01$-gadget which serves to prove state-dependent
contextuality for all but a measure zero set of states in $\mathbb{C}^{3}$.

This construction is based on the gadget $G$ of Fig. 3 with the 43 vector
orthogonal representation presented in the proof of Theorem 2. Note that if we
take $x=1$ in this representation, then the two distinguished vectors
$|u_{\\_}1\rangle$ and $|u_{\\_}{42}\rangle$ actually coincide and are both
equal to $(1,0,0)$ (i.e., the two distinguished vertices $u_{\\_}1$ and
$u_{\\_}{42}$ should actually be identified). Therefore in any
$\\{0,1\\}$-coloring $f$ of $G$,
$2f(|u_{\\_}1\rangle)=f(|u_{\\_}1\rangle)+f(|u_{\\_}{42}\rangle)\leq 1$, i.e.
the vector $|v_{\\_}1\rangle$ is assigned value $0$. This implies that $G$
witnesses state-dependent contextuality of all states in $\mathbb{C}^{3}$ but
for a measure zero set of states $|\psi\rangle$ that are orthogonal to
$|v_{\\_}1\rangle=(1,0,0)$.

The construction that we just described is based on 42 vectors. It is actually
possible to find a slightly smaller construction based on the following 40
vectors:

$\displaystyle|u_{\\_}1\rangle=(1,-1,0)^{T};\;\;|u_{\\_}2\rangle=(1,1,1)^{T};$
$\displaystyle|u_{\\_}3\rangle=(1,1,0)^{T};\;\;|u_{\\_}4\rangle=(1,1,b)^{T};$
$\displaystyle|u_{\\_}5\rangle=(-2,1,1)^{T};\;\;|u_{\\_}6\rangle=(1,-1,3)^{T};$
$\displaystyle|u_{\\_}7\rangle=(3,-3,-2)^{T};\;\;|u_{\\_}8\rangle=(2,0,3)^{T};$
$\displaystyle|u_{\\_}9\rangle=(-3,0,2)^{T};\;\;|u_{\\_}{10}\rangle=(-2,2,-3)^{T};$
$\displaystyle|u_{\\_}{11}\rangle=(3,-3,-4)^{T};\;\;|u_{\\_}{12}\rangle=(4,0,3)^{T};$
$\displaystyle|u_{\\_}{13}\rangle=(-3,0,4)^{T};\;\;|u_{\\_}{14}\rangle=(-4,4,-3)^{T};$
$\displaystyle|u_{\\_}{15}\rangle=(3,-3,-8)^{T};\;\;|u_{\\_}{16}\rangle=(8,0,3)^{T};$
$\displaystyle|u_{\\_}{17}\rangle=(-3,0,8)^{T};\;\;|u_{\\_}{18}\rangle=(-8,4+\sqrt{7},-3)^{T};$
$\displaystyle|u_{\\_}{19}\rangle=(0,1,-1)^{T};|u_{\\_}{20}\rangle=(0,1,0)^{T};$
$\displaystyle|u_{\\_}{21}\rangle=(0,-3+8b,-16-3b)^{T};\;\;|u_{\\_}{22}\rangle=(1,0,0)^{T};$
$\displaystyle|u_{\\_}{23}\rangle=(1,0,-1)^{T};\;\;|u_{\\_}{24}\rangle=(2-\sqrt{2},0,1)^{T};$
$\displaystyle|u_{\\_}{25}\rangle=(1,-2,1)^{T};\;\;|u_{\\_}{26}\rangle=(0,1,2)^{T};$
$\displaystyle|u_{\\_}{27}\rangle=(0,2,-1)^{T};\;\;|u_{\\_}{28}\rangle=(1,-1,-2)^{T};$
$\displaystyle|u_{\\_}{29}\rangle=(1,-1,1)^{T};\;\;|u_{\\_}{30}\rangle=(0,1,1)^{T};$
$\displaystyle|u_{\\_}{31}\rangle=(0,1,-1)^{T};\;\;|u_{\\_}{32}\rangle=(-1,1,1)^{T};$
$\displaystyle|u_{\\_}{33}\rangle=(-1,1,-2)^{T};\;\;|u_{\\_}{34}\rangle=(0,2,1)^{T};$
$\displaystyle|u_{\\_}{35}\rangle=(0,1,-2)^{T};\;\;|u_{\\_}{36}\rangle=(2,-2,-1)^{T};$
$\displaystyle|u_{\\_}{37}\rangle=(1,-1,4)^{T};\;\;|u_{\\_}{38}\rangle=(-2-\sqrt{2},6-\sqrt{2},2)^{T};$
$\displaystyle|u_{\\_}{39}\rangle=|u_{\\_}2\rangle;\;\;|u_{\\_}{40}\rangle=|u_{\\_}3\rangle;\;\;|u_{\\_}{41}\rangle=(1,1,-2+\sqrt{2})^{T};$
$\displaystyle|u_{\\_}{42}\rangle=|u_{\\_}1\rangle;|u_{\\_}{43}\rangle=(0,0,1)^{T};$

with $b=\frac{-4+\sqrt{7}}{3}$, and where we have the following identities
$|u_{\\_}{1}\rangle=|u_{\\_}{42}\rangle$,
$|u_{\\_}2\rangle=|u_{\\_}{39}\rangle$,
$|u_{\\_}3\rangle=|u_{\\_}{40}\rangle$. It can be verified that the graph in
Fig. 3 where we identify the vertices $u_{\\_}{1}$ and $u_{\\_}{42}$,
$u_{\\_}2$ and $u_{\\_}{39}$, $u_{\\_}3$ and $u_{\\_}{40}$, is the
orthogonality graph of these 40 vectors. These 40 vectors thus form a
$01$-gadget, where as above the vector $|u_{\\_}1\rangle=(1,-1,0)$ can only be
assigned the value $0$, implying that it can serve as a state-dependent
contextuality proof for any vector in $\mathbb{C}^{3}$ that is not orthogonal
to $(1,-1,0)$. We leave it as an open question whether this set of $40$
vectors is the minimal set with this property.

##  VI Proofs of the extended Kochen-Specker theorem using $01$-gadgets

In this section, we consider a stronger variant of the KS theorem due to
Pitowsky Pitowsky  and Hrushovski and Pitowsky HP03 . While the KS theorem is
concerned with $\\{0,1\\}$-colorings where all projectors (or vectors) in a
given set $S$ must be assigned a value in $\\{0,1\\}$, we consider here more
general assignments where any real value in $[0,1]$ is allowed to the members
of $S$. Specifically, given a set of vectors
$\mathcal{S}=\\{|v_{\\_}1\rangle,\ldots,|v_{\\_}n\rangle\\}\subset\mathbb{C}^{d}$,
we say that $f:\mathcal{S}\rightarrow[0,1]$ is a $[0,1]$-assignment if $f$
satisfies the same rules (3) as it does for $\\{0,1\\}$-colorings. Both
$\\{0,1\\}$-colorings and $[0,1]$-assignments can be interpreted as assigning
a probability to the projectors corresponding to each of the elements of $S$.
But while the assignment is constrained to be deterministic in the case of
$\\{0,1\\}$-colorings since these probabilities can only take the values $0$
or $1$, the probabilistic assignment may be completely general (hence non-
deterministic) for $[0,1]$-assignments. In particular, for any given quantum
state $|\psi\rangle$, the Born rule
$f(|v_{\\_}i\rangle)=|\langle\psi|v_{\\_}i\rangle|^{2}$ defines a valid
$[0,1]$-assignment.

Hrushovski and Pitowsky HP03 , following earlier work by Pitowsky in Pitowsky
, proved the following theorem, which they call the “logical indeterminacy
principle”.

######  Theorem 3 (HP03 ).

Let $|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$ be two non-orthogonal vectors in
$\mathbb{C}^{d}$ with $d\geq 3$. Then there is a finite set of vectors
$S\subset\mathbb{C}^{d}$ with $|v_{\\_}1\rangle,|v_{\\_}2\rangle\in S$ such
that for any $[0,1]$-assignment, it holds that
$f(|v_{\\_}1\rangle),f(|v_{\\_}2\rangle)\in\\{0,1\\}$ if and only if
$f(|v_{\\_}1\rangle)=f(|v_{\\_}2\rangle)=0$.

Thus for any two non-orthogonal vectors $|v_{\\_}1\rangle$ and
$|v_{\\_}2\rangle$, at least one of the probabilities associated to the
vectors $|v_{\\_}1\rangle$ or $|v_{\\_}2\rangle$ must be strictly between zero
and one, unless they are both equal to zero. A corollary of this result,
observed in ACCS12 ; ACS14 ; ACS14-2  is that if $f(|v_{\\_}1\rangle)=1$ (this
should, for instance, necessarily be the case if we attempt to reproduce the
quantum probabilities for measurements performed on the state
$|\psi\rangle=|v_{\\_}1\rangle$), then $f(|v_{\\_}2\rangle)\neq 0,1$, showing
that one can localise the “value-indefiniteness” of quantum observables that
the KS theorem implies. Theorem 3 therefore provides a stronger variant of the
KS theorem, and we will refer to it as the _extended KS theorem_.

The proof of Theorem 3 given in HP03  was obtained as a corollary of Gleason’s
theorem Gleason . A more explicit constructive proof was given by Abbott,
Calude and Svozil ACCS12 ; ACS14 , where they also noted that significantly
none of the known KS sets serves to prove Theorem 3. Note that an earlier
proof of the extended KS theorem was also given in Pitowsky . All these
existing proofs of the extended KS theorem involve complicated constructions
with no systematic procedure for obtaining the requisite sets of vectors. In
this subsection, we will provide a simple systematic method for obtaining in a
constructive way these extended KS sets.

In order to prove the extended KS theorem, we need gadgets of a special kind,
which are defined as usual $01$-gadgets apart from the fact that the condition
that the two distinguished vertices cannot both be assigned the value $1$ in
any $\\{0,1\\}$-colorings should also hold for any $[0,1]$-assignments. That
is, we simply replace ‘$\\{0,1\\}$-coloring’ by ‘$[0,1]$-assignment’ and
$f(|v_{\\_}1\rangle)+f(|v_{\\_}2\rangle)\leq 1$ by
$f(|v_{\\_}1\rangle)+f(|v_{\\_}2\rangle)<2$ in Definition 1, and similarly for
Definition 2. We call such new gadgets ‘extended $01$-gadgets’. It is easily
verified that the Clifton gadget in Fig. 1 and the $16$-vertex gadget in Fig.
2 obey this additional restriction.

Our first aim will be to construct such extended $01$-gadgets for any two
given non-orthogonal vectors
$|v_{\\_}1\rangle,|v_{\\_}2\rangle\in\mathbb{C}^{d}$ for $d\geq 3$. This is
the content of the following Theorem, which generalizes Theorem 2.

######  Theorem 4.

Let $|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$ be any two distinct non-
orthogonal vectors in $\mathbb{C}^{d}$ with $d\geq 3$. Then there exists an
extended 01-gadget in dimension $d$ with $|v_{\\_}1\rangle$ and
$|v_{\\_}2\rangle$ being the two distinguished vertices.

###### Proof.

We begin with the construction for $d=3$ and generalize it to higher
dimensions naturally. The construction is an iterative procedure based on the
Clifton gadget $G_{\\_}{\text{Clif}}$ given in Fig. 1.

Firstly, as stated previously, it is readily seen that $G_{\\_}{\text{Clif}}$
is actually an extended $01$-gadget with $u_{\\_}1,u_{\\_}8$ the two
distinguished vertices, i.e., any $[0,1]$-assignment
$f:V(G_{\\_}{\text{Clif}})\rightarrow[0,1]$ cannot be such that
$f(u_{\\_}1)=f(u_{\\_}8)=1$. Further, it is known that the $\mathbb{R}^{3}$
realization of $G_{\\_}{\text{Clif}}$ given by (III) achieves the (minimal
possible) separation of $\theta_{\\_}1=\arccos{|\langle
u_{\\_}1|u_{\\_}8\rangle|}=\arccos{1/3}$ between the two end vertices Stanford
.

We now describe a nesting procedure that at each step decreases the angle
between the vectors corresponding to the two outer vertices. The procedure
works as follows. Replace the edge $(u_{\\_}4,u_{\\_}5)$ in
$G_{\\_}{\text{Clif}}$ by $G^{\prime}_{\\_}{\text{Clif}}$, a copy of
$G_{\\_}{\text{Clif}}$ where we identify $u^{\prime}_{\\_}1=u_{\\_}4$ and
$u^{\prime}_{\\_}8=u_{\\_}5$. The new graph thus obtained has $14$ vertices
and $21$ edges. The operation has the property that in any $[0,1]$-assignment
$f$, an assignment of value $1$ to the two outer vertices of the new graph
(i.e. $u_{\\_}1,u_{\\_}8$) leads to a similar assignment to the two outer
vertices of the inner copy of $G_{\\_}{\text{Clif}}$ (i.e.
$u^{\prime}_{\\_}1,u^{\prime}_{\\_}8$) thereby giving rise to a contradiction.
In other words, the newly constructed graph is once again an extended
$01$-gadget. This procedure can be repeated an arbitrary number of times, as
illustrated in Fig. 5, leading to an extended $01$-gadget formed from $k$
nested Clifford graphs
$G_{\\_}{\text{Clif}}^{1},G_{\\_}{\text{Clif}}^{2},G_{\\_}{\text{Clif}}^{2},\ldots,G_{\\_}{\text{Clif}}^{k}$
where $G_{\\_}{\text{Clif}}^{1}$ corresponds to the most inner graph and
$G_{\\_}{\text{Clif}}^{k}$ to the most outer graph. We now show that the total
graph at the $k$-th iteration is an orthogonality graph where the overlap
$|\langle u_{\\_}1^{(k)}|u_{\\_}8^{(k)}\rangle|$ between the two outer
vertices $u_{\\_}1^{k},u_{\\_}8^{k}$ can be chosen to take any value in
$[0,\frac{k}{k+2}]$, thus spanning any possible value in $[0,1[$ for $k$
sufficiently large. Setting $|v_{\\_}1\rangle=|u_{\\_}1^{(k)}\rangle$ and
$|v_{\\_}2\rangle=|u_{\\_}8^{(k)}\rangle$ with $k$ depending on the overlap of
the given vectors $|\langle v_{\\_}1|v_{\\_}2\rangle|$, then gives the
required gadget and proves the Theorem.

Suppose that at the $k$-th step of the iteration, the vectors representing the
two outer vertices of the “inner” gadget from the $k-1$-th step are

$\displaystyle|u_{\\_}4^{(k)}\rangle=|u_{\\_}1^{(k-1)}\rangle=(1,0,0),$
$\displaystyle|u_{\\_}5^{(k)}\rangle=|u_{\\_}8^{(k-1)}\rangle=\frac{1}{\sqrt{1+x_{\\_}k^{2}}}(x_{\\_}k,1,0),$
(21)

without loss of generality, so that the overlap between these vectors is
$|\langle
u_{\\_}4^{(k)}|u_{\\_}5^{(k)}\rangle|=\frac{x_{\\_}k}{\sqrt{1+x_{\\_}k^{2}}}$,
where for simplicity of the construction we take
$x_{\\_}k\in\mathbb{R}^{+}_{\\_}0$. The remaining vectors then in general have
the following (non-normalized) orthogonal representation in $\mathbb{R}^{3}$

$\displaystyle|u_{\\_}8^{(k)}\rangle=(a_{\\_}k,b_{\\_}k,c_{\\_}k),\;\;|u_{\\_}6^{(k)}\rangle=(0,-c_{\\_}k,b_{\\_}k),$
$\displaystyle|u_{\\_}7^{(k)}\rangle=(c_{\\_}k,-c_{\\_}kx_{\\_}k,-a_{\\_}k+b_{\\_}kx_{\\_}k),\;\;|u_{\\_}2^{(k)}\rangle=(0,b_{\\_}k,c_{\\_}k),\;\;$
$\displaystyle|u_{\\_}3^{(k)}\rangle=(-a_{\\_}k+b_{\\_}kx_{\\_}k,a_{\\_}kx_{\\_}k-b_{\\_}kx_{\\_}k^{2},-c_{\\_}k-c_{\\_}kx_{\\_}k^{2}),$
$\displaystyle|u_{\\_}1\rangle=(-b_{\\_}kc_{\\_}k-a_{\\_}kc_{\\_}kx_{\\_}k,-a_{\\_}kc_{\\_}k+b_{\\_}kc_{\\_}kx_{\\_}k,a_{\\_}kb_{\\_}k-b_{\\_}k^{2}x_{\\_}k),$

with $a_{\\_}k,b_{\\_}k,c_{\\_}k\in\mathbb{R}$. This gives an overlap of

$\displaystyle|\langle
u_{\\_}1^{(k)}|u_{\\_}8^{(k)}\rangle|=\frac{|-a_{\\_}kc_{\\_}k(b_{\\_}k+a_{\\_}kx_{\\_}k)|}{\sqrt{(a_{\\_}k^{2}+b_{\\_}k^{2}+c_{\\_}k^{2})(c_{\\_}k^{2}(b_{\\_}k+a_{\\_}kx_{\\_}k)^{2}+b_{\\_}k^{2}(a_{\\_}k-b_{\\_}kx_{\\_}k)^{2}+(a_{\\_}kc_{\\_}k-b_{\\_}kc_{\\_}kx_{\\_}k)^{2})}}.$
(23)

A direct optimization of this expression with respect to the parameters
$a_{\\_}k,b_{\\_}k,c_{\\_}k$ gives the choice $b_{\\_}k=1$, $c_{\\_}k=1$,
$a_{\\_}k=x_{\\_}k+\sqrt{1+x_{\\_}k^{2}}$. So that the overlap between the two
outer vertices at the $k$-th step of the iteration is given by

$\displaystyle|\langle
u_{\\_}1^{(k)}|u_{\\_}8^{(k)}\rangle|=\frac{1}{3+4x_{\\_}k(x_{\\_}k-\sqrt{1+x_{\\_}k^{2}})}=:\frac{x_{\\_}{k+1}}{\sqrt{1+x_{\\_}{k+1}^{2}}}.$
(24)

With the initial overlap for $k=1$ of $1/3$ and corresponding initial $x$
values of $x_{\\_}1=0$ and $x_{\\_}2=\frac{1}{2\sqrt{2}}$, we can now evaluate
the expression for the overlap for any $k>1$. We find that the overlap at the
$k$-th step is $\frac{k}{k+2}$. This is readily seen by an inductive argument.
The base claim is clear, suppose that at the $k$-th step the overlap is given
by $\frac{x_{\\_}{k+1}}{\sqrt{1+x_{\\_}{k+1}^{2}}}=\frac{k}{k+2}$, i.e.,
$x_{\\_}{k+1}=\frac{k}{2\sqrt{k+1}}$. Substituting in Eq.24, we obtain
$\frac{x_{\\_}{k+2}}{\sqrt{1+x_{\\_}{k+2}^{2}}}=\frac{k+1}{k+3}=\frac{(k+1)}{(k+1)+2}$.
Moreover, we see that choosing $b_{\\_}k=1,c_{\\_}k=1$, the overlap expression
(23) is a continuous function of $a_{\\_}k$ for any fixed $x_{\\_}k$ with the
minimum value of $0$ achieved at $a_{\\_}k=0$. Thus, every intermediate
overlap in $[0,\frac{k}{k+2}]$ between the two outer vectors is also
achievable by appropriate choice of $a_{\\_}k$ for the fixed value of
$x_{\\_}k,b_{\\_}k,c_{\\_}k$. This completes the construction of the gadget
for $\mathbb{C}^{3}$ (possibly by taking its faithful version in the graph
representation).

Now, one may simply consider the same set of vectors as being embedded in any
$\mathbb{C}^{d}$ (with additional vectors$(0,0,0,1,0,\dots,0)^{T}$,
$(0,0,0,0,1,0,\dots,0)^{T}$ etc.) to construct a gadget in this dimension.
$\sqcap$$\sqcup$

In fact, the construction above is not unique. We give an alternative set of
vectors that also serves to prove Theorem 4. The construction is shown in Fig.
6. Suppose we are given two distinct non-orthogonal vectors
$|v_{\\_}1\rangle=(1,0,0)^{T}$, $|v_{\\_}2\rangle=(x,\sqrt{1-x^{2}},0)^{T}$,
with $0<x<1$. We begin by adding the following set of vectors with a parameter
$y\in\mathbb{R}$:

$\displaystyle|v_{\\_}3\rangle=(0,x,-\sqrt{1-x^{2}})^{T};$
$\displaystyle|v_{\\_}4\rangle=(-(1-x^{2}),x\sqrt{1-x^{2}},x^{2})^{T};$
$\displaystyle|v_{\\_}5\rangle=(x,(1-x^{2})\sqrt{1-x^{2}},x(1-x^{2}))^{T};$
$\displaystyle|v_{\\_}6\rangle=(0,y,\sqrt{1-y^{2}})^{T};$
$\displaystyle|v_{\\_}7\rangle=(-\sqrt{(1-x^{2})(1-y^{2})},x\sqrt{1-y^{2}},xy)^{T};$
$\displaystyle|v_{\\_}8\rangle=(x,(1-y^{2})\sqrt{1-x^{2}},y\sqrt{(1-x^{2})(1-y^{2})})^{T};$
$\displaystyle|v_{\\_}9\rangle=(0,1,0)^{T};\;\;|v_{\\_}{10}\rangle=(-\sqrt{1-x^{2}},x,0)^{T}.$
(25)

The remaining vectors are obtained using a repeating unit consisting of four
vectors:

$\displaystyle|v_{\\_}{7+4t}\rangle=(-(1-x^{2}),0,x^{2(t-1)})^{T};$
$\displaystyle|v_{\\_}{8+4t}\rangle=(x^{2(t-1)},0,1-x^{2})^{T};$
$\displaystyle|v_{\\_}{9+4t}\rangle=(-x(1-x^{2}),-(1-x^{2})\sqrt{1-x^{2}},x^{2t-1})^{T};$
$\displaystyle|v_{\\_}{10+4t}\rangle=(x^{2t},x^{2t-1}\sqrt{1-x^{2}},1-x^{2})^{T};$
(26)

repeated $t$ times for an integer $t\geq 1$ depending on $x$. Choosing the
parameter $y$ as

$\displaystyle
y=\sqrt{\frac{(1-x^{2})^{2}+2x^{4t-2}-\sqrt{(1-x^{2})((1-x^{2})^{3}-4x^{4t})}}{2(1-x^{2})(1-x^{2}+x^{4t-2})}},$

we find that $y\in\mathbb{R}$, for $t$ satisfying $(1-x^{2})^{3}\geq 4x^{4t}$.
We see that as $t$ increases this inequality can be satisfied for larger
values of $x$, and for any $0<x<1$ as $t\rightarrow\infty$. From the
orthogonality graph of this set of vectors $S$ shown in Fig. 6, it is clear
that there cannot be any assignement $f:S\rightarrow[0,1]$ such that
$f(|v_{\\_}1\rangle)=f(|v_{\\_}2\rangle)=1$, giving an extended $01$-gadget.

While the construction in Theorem 4 and that in the previous paragraph work
for any two distinct vectors, given two such vectors it is of great interest
to find the minimal extended $01$-gadget with these vectors as the
distinguished vertices. While this question is the foundational analog for
extended KS systems of the question of finding minimal KS sets, it is also of
practical interest in obtaining Hardy paradoxes with optimal values of the
non-zero probability, and extracting randomness from the gadgets R17 .

We now show how the extended $01$-gadgets can be used to construct proofs of
the extended KS Theorem 3.

Figure 5: An iterative construction of an extended $01$-gadget for which the
two distinguished vertices $u_{\\_}1$ and $u_{\\_}8$ are such that in the
limit of large number of iterations $k$, $|\langle
u_{\\_}1^{(k)}|u_{\\_}8^{(k)}\rangle|\in[0,1[$.

Figure 6: An alternative construction of an extended $01$-gadget for which the
two distinguished vertices $v_{\\_}1$ and $v_{\\_}2$ are such that in the
limit of large number $t$ of the repeating unit of four vectors, $|\langle
v_{\\_}1|v_{\\_}2\rangle|$ can take any value in $[0,1[$.

###### Proof.

(Theorem 3) We present the construction for $d=3$, the proof for higher
dimensions will follow in an analogous fashion. The idea is encapsulated by
Fig. 7. Suppose we are given two distinct non-orthogonal vectors
$|v_{\\_}1\rangle$ and $|v_{\\_}2\rangle$ in $\mathbb{C}^{d}$. We begin by
constructing an appropriate extended $01$-gadget $G_{\\_}{v_{\\_}1,v_{\\_}2}$,
depending on $|\langle v_{\\_}1|v_{\\_}2\rangle|$, with the corresponding
$v_{\\_}1,v_{\\_}2$ being the distinguished vertices.

Let $|v_{\\_}3\rangle=|v_{\\_}1\rangle\times|v_{\\_}2\rangle$ denote the
vector orthogonal to the plane
$\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$ spanned by $|v_{\\_}1\rangle$
and $|v_{\\_}2\rangle$, where $\times$ denotes the cross product of the
vectors. Let $|v_{\\_}4\rangle$ be the vector in the plane
$\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$ orthogonal to
$|v_{\\_}1\rangle$, and $|v_{\\_}5\rangle$ denote the vector in this plane
orthogonal to $|v_{\\_}2\rangle$, so that
$\\{|v_{\\_}1\rangle,|v_{\\_}3\rangle,|v_{\\_}4\rangle\\}$,
$\\{|v_{\\_}2\rangle,|v_{\\_}3\rangle,|v_{\\_}5\rangle\\}$ form orthogonal
bases in $\mathbb{C}^{3}$. We construct appropriate extended $01$-gadgets
$G_{\\_}{v_{\\_}1,v_{\\_}5}$ and $G_{\\_}{v_{\\_}2,v_{\\_}4}$ depending on
$|\langle v_{\\_}1|v_{\\_}5\rangle|$ and $|\langle v_{\\_}2|v_{\\_}4\rangle|$.
In $G_{\\_}{v_{\\_}1,v_{\\_}5}$ the vertices $v_{\\_}1,v_{\\_}5$ corresponding
to the vectors $|v_{\\_}1\rangle,|v_{\\_}5\rangle$ play the role of the
distinguished vertices and similarly in $G_{\\_}{v_{\\_}2,v_{\\_}4}$. Let
$G_{\\_}{\text{Pit}}$ denote the orthogonality graph of the entire set of
vectors
${G_{\\_}{v_{\\_}1,v_{\\_}2}}\bigcup{G_{\\_}{v_{\\_}1,v_{\\_}5}}\bigcup{G_{\\_}{v_{\\_}2,v_{\\_}4}}\bigcup|v_{\\_}3\rangle$.

We have that in any assignment $f:V(G_{\\_}{\text{Pit}})\rightarrow[0,1]$ for
which $f(v_{\\_}1),f(v_{\\_}2)\in\\{0,1\\}$, if $f(v_{\\_}1)=1,f(v_{\\_}2)=1$,
then we obtain a contradiction by the property of the extended $01$-gadget
$G_{\\_}{v_{\\_}1,v_{\\_}2}$. On the other hand, if
$f(v_{\\_}1)=1,f(v_{\\_}2)=0$, then since
$|v_{\\_}1\rangle\perp|v_{\\_}3\rangle$ we have $f(v_{\\_}3)=0$, and by the
property of the extended $01$-gadget $G_{\\_}{v_{\\_}1,v_{\\_}5}$ we have
$f(v_{\\_}5)=0$. This gives a contradiction since $v_{\\_}2,v_{\\_}3,v_{\\_}5$
form a maximum clique. Similarly, if $f(v_{\\_}1)=0,f(v_{\\_}2)=1$, then since
$|v_{\\_}2\rangle\perp|v_{\\_}3\rangle$ we have $f(v_{\\_}3)=0$, and by the
property of the extended $01$-gadget $G_{\\_}{v_{\\_}2,v_{\\_}4}$ we have
$f(v_{\\_}4)=0$. This also gives a contradiction since
$v_{\\_}1,v_{\\_}3,v_{\\_}4$ form a maximum clique. Therefore, we have any
assignment $f:V(G_{\\_}{\text{Pit}})\rightarrow[0,1]$ which obeys
$f(v_{\\_}1),f(v_{\\_}2)\in\\{0,1\\}$ also must necessarily obey
$f(v_{\\_}1)=f(v_{\\_}2)=0$. This completes the proof.

Figure 7: A constructive proof of the extended Kochen-Specker theorem 3 using
the extended $01$-gadgets. Given vectors
$|v_{\\_}1\rangle,|v_{\\_}2\rangle\in\mathbb{C}^{d}$, we obtain vector
$|v_{\\_}3\rangle\perp\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$ and two
other vectors $|v_{\\_}4\rangle,|v_{\\_}5\rangle$ in the plane
$\text{span}(|v_{\\_}1\rangle,|v_{\\_}2\rangle)$ with the orthogonality
relations indicated in the left figure. Dashed edges between two vertices
indicate an extended $01$-gadget from Theorem 4 with the two vertices being
distinguished.

$\sqcap$$\sqcup$

###  VI.1 Discussion

Intuitively, with respect to any $\\{0,1\\}$ coloring, a $01$-gadget behaves
like a ”virtual edge” between its two special vertices, with this edge also
obeying the rule that at most one of its incident vertices may be assigned the
color $1$. Moreover, in Theorem 2 we have shown that $01$-gadgets may be
constructed with any two non-orthogonal vectors as the special vertices.
Starting from a given set of vectors, this allows us to connect any two non-
orthogonal vectors by an appropriate $01$-gadget, which imposes additional
constraints on the $\\{0,1\\}$-colorings of the resulting set of vectors. By
appropriately adding such virtual edges, we are eventually able to obtain a
set of vectors that gives a Kochen-Specker contradiction. Moreover, it turns
out that the statistical proofs of the Kochen-Specker theorem can also be
interpreted in the same manner. For instance, the famous Yu-Oh graph of YO12
can be interpreted as six $01$-gadgets connecting the vectors
$(1,1,1)^{T},(1,1,-1)^{T},(1,-1,1)^{T}$ and $(-1,1,1)^{T}$. These four vectors
thus form a ”virtual clique”, with the property that in any
$\\{0,1\\}$-coloring of the Yu-Oh set, the sum of the values attributed to
these four vectors cannot exceed one. On the other hand, any quantum state has
overlap with these four vectors summing to $4/3$ providing a statistical
contradiction. Similar considerations also apply to the extended Kochen-
Specker theorem of Pitowsky by means of extended $01$-gadgets.

##  VII Computational complexity of $\\{0,1\\}$-colorings

Clearly, complete graphs of size $d+1$ cannot be faithfully realized in
$\mathbb{C}^{d}$, but there also exist certain other graphs that cannot be
faithfully realized in $\mathbb{C}^{d}$. The well-known example is the four-
cycle (square) graph in $\mathbb{C}^{3}$, this can be seen by the following
simple argument. Suppose a pair of vertices in opposite corners of the square
is assigned without loss of generality the vectors $|0\rangle$ and
$\alpha|0\rangle+\beta|1\rangle$, with $\alpha,\beta\in\mathbb{C}$. Since
these vectors span a plane and the remaining pair of vertices are both
required to be orthogonal to this plane, these latter vectors are both equal
up to a phase to $|2\rangle$, contradicting the requirement of faithfulness.
There exist analogous graphs that are not faithfully realizable in higher
dimensions, some of which are shown in Fig. 8.

Figure 8: Examples of forbidden subgraphs in dimensions $3,4$ and $5$. Graph
(i) is the square graph which is not faithfully realizable in $\mathbb{C}^{3}$
as explained in the text. Graph (iv) is the graph from C11  which was verified
to be not faithfully realizable in dimension three despite being square-free.
Graph (ii) is not faithfully realizable in $\mathbb{C}^{4}$, which can be seen
as arising from the fact that the induced square subgraph is not faithfully
realizable in $\mathbb{C}^{3}$ and the additional vertex being adjacent to all
vertices of the square, the vector corresponding to this vertex occupies an
orthogonal subspace to that spanned by the square. Graph (iii) is similarly
not realizable in $\mathbb{C}^{5}$ this time owing to the presence of two
vertices (which themselves cannot be represented by identical vectors) that
are adjacent to all the vertices of the square. It is clear that the
construction can be extended to higher dimensions.

In searching for Kochen-Specker vector systems in $\mathbb{C}^{d}$, it is
therefore crucial to reduce the size of the search by restricting to non-
isomorphic graphs which do not contain these forbidden graphs as subgraphs.
Indeed, searching over non-isomorphic square-free graphs lead to the proof
that the smallest Kochen-Specker vector system in $\mathbb{C}^{3}$ is of size
at least $18$ Arends09 .

Let us denote the set of forbidden graphs in $\mathbb{C}^{d}$ as
$\\{G_{\\_}{\text{fbd}}\\}$. We show, following the proof by Arends et al.
Arends09 ; AOW11  for the square-free case, that the problem of checking
$\\{0,1\\}$-colorability of $\\{G_{\\_}{\text{fbd}}\\}$-free graphs is NP-
complete. Here, by a $\\{G_{\\_}{\text{fbd}}\\}$-free graph we mean a graph
that does not contain any of the forbidden graphs as subgraphs.

######  Theorem 5 (see also Arends09 ).

Checking $\\{0,1\\}$-colorability of $\\{G_{\\_}{\text{fbd}}\\}$-free graphs
is NP-complete.

The proof is based on a reduction to the well-known graph coloring problem
that uses $01$-gadgets in a crucial manner. Let us first recall the usual
notion of coloring of a graph used in the proof. A proper coloring $c$ of a
graph $G$ is an assignment of one among $n$ colors to each of the vertices of
the graph $c:V(G)\rightarrow[n]$ ($[n]:=\\{1,\dots,n\\}$) such that no pair of
adjacent vertices are assigned the same color. If such a coloring exists, we
say that $G$ is $n$-colorable.

###### Proof.

The proof generalizes and simplifies that for the analogous question of
$\\{0,1\\}$-colorability of square-free graphs in Arends09 , with the
difference being that we directly use the constructions of $01$-gadgets from
the previous sections. Firstly, we know that checking $\\{0,1\\}$-colorability
of a $\\{G_{\\_}{\text{fbd}}\\}$-free graph is in NP because the problem of
checking an arbitrary graph for $\\{0,1\\}$-colorability is in NP Arends09 .
Suppose we are given a graph $G$. The idea is to construct a new graph $H$
which is $\\{G_{\\_}{\text{fbd}}\\}$-free such that the problem of
$\omega(G)$-colorability of $G$ is equivalent to the problem of
$\\{0,1\\}$-colorability of $H$. Provided the construction is achievable in
polynomial time, this gives a reduction from the $\\{0,1\\}$-colorability
problem to the $\omega(G)$-colorability problem (for $\omega(G)\geq 3$) which
is known to be NP-complete CLRS01 .

The construction goes as follows. Replace every vertex $v\in V(G)$ by a clique
of size $\omega(G)$ in $H$ and label the corresponding vertices $v_{\\_}i\in
V(H)$ for $i\in[\omega(G)]$. For every edge $(u,v)\in E(G)$, connect the
corresponding vertices $(u_{\\_}i,v_{\\_}i)$ by a $01$-gadget
$\Gamma_{\\_}{(u_{\\_}i,v_{\\_}i)}$ in $H$. The exact form of the gadget
$\Gamma_{\\_}{(u_{\\_}i,v_{\\_}i)}$ is left unspecified at the moment, for the
polynomial time reduction it is only important that it is finite (i.e.,
$|V(\Gamma_{\\_}{(u_{\\_}i,v_{\\_}i)})|$ and
$|E(\Gamma_{\\_}{(u_{\\_}i,v_{\\_}i)})|$ are finite), so that
$|V(H)|\leq\omega(G)(|V(\Gamma_{\\_}{(u_{\\_}i,v_{\\_}i)})|_{\\_}{max}-1)|V(G)|$
and
$|E(H)|\leq\omega(G)|V(G)|+|E(\Gamma_{\\_}{(u_{\\_}i,v_{\\_}i)})|_{\\_}{max}|E(G)|$,
i.e., $|V(H)|=O(|V(G)|)$ and $|E(H)|=O(|E(G)|+|V(G)|)$.

We first verify that $H$ is $\\{G_{\\_}{\text{fbd}}\\}$-free. We do this by
showing that $H$ is in fact faithfully realizable in dimension $\omega(G)$ and
consequently free of the forbidden subgraphs for that dimension. For the
vertices $v\in V(G)$, the actual representation of the vertices $v_{\\_}i\in
V(H)$ is chosen independent of the exact structure of the graph, i.e., for any
$G$ with $|V(G)|=n$, we choose a fixed faithful orthogonal representation
$\\{|v_{\\_}i\rangle\\}$ for $v\in V(G)$ and $i\in[\omega(G)]$. Indeed, to
show the realizability of the rest of $H$, it suffices to show the
realizability of the vertices $v_{\\_}1$ for $v\in V(G)$, since the
representation for the remaining vertices $v_{\\_}i$ for $i\geq 2$ can be
readily obtained by a cyclic permutation
$\Pi_{\\_}i:|j\rangle\mapsto|j+i\rangle$ with the sum taken modulo
$\omega(G)$. The structure of the graph is then incorporated by means of an
appropriate choice of the gadgets $\Gamma_{\\_}{(u_{\\_}i,v_{\\_}i)}$. The
crucial idea behind the construction is that there exist finite sized gadgets
(with faithful representations) for any two distinct vertices as shown in
Prop. 4. So that for any edge $(u,v)\in E(G)$, we use a gadget
$\Gamma(u_{\\_}1,v_{\\_}1)$ from Prop. 4 (the same gadget is used for the
other pairs $(u_{\\_}i,v_{\\_}i)$) corresponding to the required overlap
$|\langle u_{\\_}1|v_{\\_}1\rangle|$. Now, since the representation is
faithful, we do not have different vertices represented by the same vector. As
such, the construction from Prop. 4 yields a finite sized gadget for any pair
of vertices $(u_{\\_}i,v_{\\_}1)$.

The proof that checking $\\{0,1\\}$-colorability of the
$\\{G_{\\_}{\text{fbd}}\\}$-free graph $H$ is equivalent to checking the
$\omega(G)$-colorability of $G$ (which is $NP$-complete) follows along
analogous lines to the proof in Arends09  and we present it here for
completeness. Firstly, we show that $H$ is $\\{0,1\\}$-colorable if $G$ is
$\omega(G)$-colorable. Consider the intermediate situation when we form a
graph $G^{\prime}$ by replacing every vertex $v\in V(G)$ by a clique of size
$\omega(G)$ and labeling the corresponding vertices $v_{\\_}i\in
V(G^{\prime})$ for $i\in[\omega(G)]$. For every edge $(u,v)\in E(G)$, connect
the corresponding vertices $(u_{\\_}i,v_{\\_}i)$ by an edge in $G^{\prime}$.
The strategy is to show that if $G$ is $\omega(G)$-colorable, then
$G^{\prime}$ admits a valid $\\{0,1\\}$-assignment. Suppose $G$ is
$\omega(G)$-colorable, and $c:V(G)\rightarrow[\omega(G)]$ is an optimal
coloring. We define the $\\{0,1\\}$-coloring of $G^{\prime}$ by

$c^{\prime}(v_{\\_}i)=\left\\{\begin{array}[]{lr}1,&\text{for }i=c(v)\\\
0,&\text{else}\end{array}\right.$

The fact that this is a valid $\\{0,1\\}$-coloring of $G^{\prime}$ follows the
proof of Lemma 1 in Arends09 . We now derive the $\\{0,1\\}$-coloring of $H$
from that of $G^{\prime}$ by seeing that each of the gadgets in Prop. 4 can be
$\\{0,1\\}$-colored in all three cases, when the distinguished vertices
$u_{\\_}i,v_{\\_}i$ have the assignments: (i) $f(u_{\\_}i)=0,f(v_{\\_}i)=0$,
(ii) $f(u_{\\_}i)=0,f(v_{\\_}i)=1$, and $f(u_{\\_}i)=1,f(v_{\\_}i)=0$. This is
done by checking that such a valid $\\{0,1\\}$-coloring exists for the Clifton
gadget in Fig. 1 in each of the three cases. The $\\{0,1\\}$-coloring can be
extended to the entire gadget iteratively by following the procedure shown in
the proof of Prop. 4. This gives a valid $\\{0,1\\}$-coloring of $H$.

We now show that a valid $\\{0,1\\}$-coloring of $H$ also implies that $G$ is
$\omega(G)$-colorable. Let $f:V(H)\rightarrow\\{0,1\\}$ be a valid $\\{0,1\\}$
assignment of $H$. For every $v\in V(G)$, by the fact that we have a valid
$\\{0,1\\}$-coloring, exactly one of the vertices $v_{\\_}i\in V(H)$ is
assigned value $1$, i.e., $f(v_{\\_}i)=1$. One can then define a
$\omega(G)$-coloring $c:V(G)\rightarrow[\omega(G)]$ by $c(v)=i\leftrightarrow
c(v_{\\_}i)=1$ for every $v\in V(G)$. It is clear that this is a valid
coloring since if $(u,v)\in E(G)$ we have by the property of the gadget that
at most one of $u_{\\_}i,v_{\\_}i$ is assigned value $1$, i.e., either
$f(u_{\\_}i)=0$ or $f(v_{\\_}i)=0$. Thus, the $\\{0,1\\}$-colorability of the
$\\{G_{\\_}{\text{fbd}}\\}$-free graph $H$ is equivalent to the
$\omega(G)$-colorability of $G$. From CLRS01 , we know that for $\omega(G)\geq
3$, this problem is NP-complete, which finishes the proof.  $\sqcap$$\sqcup$

It is also interesting to examine the complexity of identifying $01$-gadgets.
In this case, it appears to be necessary to enumerate all
$\\{0,1\\}$-colorings of a given graph and to check $O(n^{2})$ vertices to
identify the possible distinguished vertices. Note that for a graph with $n$
vertices there are $2^{n}$ possible $\\{0,1\\}$-colorings so that it is not
apparent whether even a polynomially checkable certificate exists for this
problem. Peeters in P96  gave a polynomial time reduction preserving graph
planarity of the problem of testing $\xi(G)\leq 3$ to the problem of testing
whether the chromatic number $\chi(G)$ is less than or equal to $3$, which is
a well-known NP-complete problem, so that it is hard to check whether
$d(G)\leq 3$ already for the case of planar graphs.

##  VIII Randomness from $01$-gadgets

In this section, we give a brief outline of how $01$-gadgets may be linked to
device-independent randomness certification. Namely, when two parties Alice
and Bob perform locally the measurements from the Clifton gadget on their half
of a maximally entangled state (in $\mathbb{C}^{3}\otimes\mathbb{C}^{3}$), we
will show that some specific outcome of their joint measurements has
probability bounded from above and below (and this holds in all no-signaling
theories). This can be inserted into a fully device-independent protocol as
given in PRL-rand , the details are deferred to a separate paper R17 . To show
how the Clifton gadget can be used for randomness amplification we first
consider a non-contextual assignment of probabilities to its vertices $v$
satisfying

$\sum_{\\_}{v\in\text{clique}}p_{\\_}v\leq 1,\quad\sum_{\\_}{v\in\text{maximum
clique}}p_{\\_}v=1$ (27)

This is the same requirement as Eq.(3), but we now assign not necessarily
zeros and ones, but probabilities (i.e., values in $[0,1]$ rather than in
$\\{0,1\\}$). Recall that such an assignment was also considered in our
discussion of the extended Kochen-Specker theorem in Section VI. Now, since
the gadgets are $\\{0,1\\}$ colorable, such an assignment of zeros and ones is
possible, although in the $\\{0,1\\}$ assignment, it is not possible to assign
$1$’s to both vertices $1$ and $8$. Here, we will first show, that even if we
assign probabilities, we still cannot have $p_{\\_}1=p_{\\_}8=1$, and we will
provide a quantitative bound for this. Indeed, let us write Eq.(27) explicitly
for the cliques in question from the Clifton gadget in Fig. 1:

$\displaystyle p_{\\_}1+p_{\\_}2\leq 1,\quad p_{\\_}1+p_{\\_}6\leq 1,\quad
p_{\\_}4+p_{\\_}5\leq 1,$ $\displaystyle\quad p_{\\_}7+p_{\\_}8\leq 1,\quad
p_{\\_}3+p_{\\_}2\leq 1$ (28)

for non-maximal cliques and

$p_{\\_}2+p_{\\_}3+p_{\\_}4=1,\quad p_{\\_}5+p_{\\_}6+p_{\\_}7=1$ (29)

for the two maximum cliques. We sum up all the inequalities (VIII), and get

$2p_{\\_}1+p_{\\_}2+p_{\\_}3+p_{\\_}4+p_{\\_}5+p_{\\_}6+p_{\\_}7+2p_{\\_}8\leq
5.$ (30)

Using (29) we then obtain

$p_{\\_}1+p_{\\_}8\leq\frac{3}{2}.$ (31)

To exploit this feature for randomness amplification, we consider a maximally
entangled state shared by two parties. The parties will measure observables
composed of the projectors given by the quantum representation (if the clique
is not maximal, one simply adds a third orthogonal projector to obtain a
complete measurement). Recall here that a set of eight projectors
$P_{\\_}v=|u_{\\_}v\rangle\langle u_{\\_}v|$ that is compatible with the
Clifton graph is given in Eq.(III). Projectors of Alice will be denoted
$A_{\\_}v$ and those of Bob $B_{\\_}v$, and the probability of obtaining
outcome $v$, while measuring observable containing $v$, will be denoted by
$p(A_{\\_}v=1)$. We correspondingly denote by $p(A_{\\_}v=0)$ the probability
that the outcome $v$ was not obtained. Clearly
$p(A_{\\_}v=1)+p(A_{\\_}v=0)=1$. Now, we shall show using no-signaling (which
will impose non-contextuality), that the probability
$p(A_{\\_}1=1,B_{\\_}8=1)$ is bounded from above. To see this, we apply
Eq.(31) to Alice’s observables and get

$\displaystyle p(A_{\\_}1=1)+p(A_{\\_}8=1)\leq\frac{3}{2}$ (32)

From the correlations in the maximally entangled state, we have that

$p(A_{\\_}8=1)=p(B_{\\_}8=1)$ (33)

giving

$p(A_{\\_}1=1)+p(B_{\\_}8=1)\leq\frac{3}{2}.$ (34)

Now, from no-signaling we have

$\displaystyle
p(A_{\\_}1=1)=p(A_{\\_}1=1,B_{\\_}8=0)+p(A_{\\_}1=1,B_{\\_}8=1),$
$\displaystyle
p(B_{\\_}8=1)=p(A_{\\_}1=0,B_{\\_}8=1)+p(A_{\\_}1=1,B_{\\_}8=1).$

Summing these and applying (34) we get

$\displaystyle p(A_{\\_}1=1,B_{\\_}8=0)+p(A_{\\_}1=1,B_{\\_}8=1)+$
$\displaystyle
p(A_{\\_}1=0,B_{\\_}8=1)+p(A_{\\_}1=1,B_{\\_}8=1)\leq\frac{3}{2}$ (36)

and hence

$p(A_{\\_}1=1,B_{\\_}8=1)\leq\frac{3}{4}.$ (37)

Thus we have obtained, that the probability of the event
$(A_{\\_}1,B_{\\_}8)=(1,1)$ is bounded from above. We have also the lower
bound

$p(A_{\\_}1=1,B_{\\_}8=1)=\frac{1}{3}|\langle
u_{\\_}1|u_{\\_}8\rangle|^{2}\geq\frac{1}{27}.$ (38)

Thus

$\frac{1}{27}\leq p(A_{\\_}1=1,B_{\\_}8=1)\leq\frac{3}{4}$ (39)

Therefore, the outcome $(A_{\\_}1,B_{\\_}8)=(1,1)$ has randomness, which can
be used in a randomness amplification scheme employing the protocol of PRL-
rand . The lower bound is $\frac{1}{27}$ in noiseless conditions, and assuming
we have exactly measured the specified projectors. In a real experiment, this
value may be different, but if the noise is low enough it should be close to
$\frac{1}{27}$. Also the upper bound, relies on perfect correlations, which in
a real experiment may be imperfect. Thus in noisy conditions, we will have
less stringent lower and upper bounds, though these are certifiable by
statistics from the experiment. Note that crucially we have not used
explicitly Bell inequalities, nor even the KS paradox. We have simply made use
of the perfect correlations between the parties and the local $01$-gadget
structure of Alice and Bob’s observables.

##  IX Conclusion and Open Questions

In this paper, we have shown that there exist interesting subgraphs of the
Kochen-Specker graphs that we termed $01$-gadgets that encapsulate the main
contradiction necessary to prove the Kochen-Specker theorem. Furthermore, we
gave simple constructive proofs of statistical KS arguments and state-
independent non-contextuality inequalities for any $d\geq 3$ using these
gadgets. An extended notion of $01$-gadgets also helped to provide simple
constructive proofs of the extended Kochen-Specker theorem Pitowsky . The
gadgets enable a proof of the NP-completeness of checking
$\\{0,1\\}$-colorability of graphs free from the forbidden subgraphs from
Hilbert spaces of any dimension. Practically, the gadgets open up a highly
important application of contextuality to practical device-independent
randomness generation, which we study in a companion paper R17  where we
provide an explicit device-independent protocol for randomness amplification
based on BRGH+16 ; RBHH+15 ; WBGH+16  and Hardy paradoxes constructed using
$01$-gadgets.

An open question, is to find, for given overlap $|\langle
v_{\\_}1|v_{\\_}2\rangle|$, the minimal $01$-gadget and extended $01$-gadget
with the corresponding vertices $v_{\\_}1,v_{\\_}2$ playing the role of the
distinguished vertices. An answer to this question would have applications for
randomness generation from contextuality R17 . Another open question is
whether all state-independent contextual graphs (including those going beyond
KS sets such as that of Yu and Oh YO12 ) contain $01$-gadgets as subgraphs, or
even possibly as induced subgraphs. Finally, while it is known that in
$\mathbb{C}^{3}$ KS sets cannot be constructed using rational vectors GN08 ,
it would be very interesting to study quantum realizations of $01$-gadgets
using rational vectors, to build statistical KS arguments and state-
independent non-contextuality inequalities using these.

Acknowledgments.- We are grateful to Andrzej Grudka, Waldemar Kłobus and David
Roberson for useful discussions. R.R. acknowledges support from the research
project “Causality in quantum theory: foundations and applications” of the
Fondation Wiener-Anspach and from the Interuniversity Attraction Poles 5
program of the Belgian Science Policy Office under the grant IAP P7-35
photonics@be. M. R. is supported by the National Science Centre, Poland, grant
OPUS 9. 2015/17/B/ST2/01945. MH and PH are supported by the John Templeton
Foundation. The opinions expressed in this publication are those of the
authors and do not necessarily reflect the views of the John Templeton
Foundation. KH acknowledges support from the grant Sonata Bis 5 (grant number:
2015/18/E/ST2/00327) from the National Science Centre. S.P. is a Research
Associate of the Fonds de la Recherche Scientifique (F.R.S.-FNRS).

## References

  * (1) S. Kochen and E.P. Specker. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics 17, 59 (1967).
  * (2) A. A. Abbott, C. S. Calude and K. Svozil. A variant of the Kochen-Specker theorem localising value indefiniteness. J. Math. Phys. 56, 102201 (2015).
  * (3) A. A. Abbott, C. S. Calude, J. Conder and K. Svozil. Strong Kochen-Specker theorem and incomputability of quantum randomness. Physical Review A 86(6), 062109 (2012).
  * (4) A. A. Klyachko, M. A. Can, S. Binicoglu and A. S. Shumovsky. A simple test for hidden variables in spin-1 system. Phys. Rev. Lett. 101, 020403 (2008).
  * (5) C. D. Godsil and M. W. Newman. Coloring an orthogonality graph. SIAM J. Discrete Math., 22(2): 683 (2008).
  * (6) A. Cabello, S. Severini and A. Winter. Graph-Theoretic Approach to Quantum Correlations. Phys. Rev. Lett. 112, 040401 (2014).
  * (7) A. Cabello, S. Severini and A. Winter. (Non-)Contextuality of Physical Theories as an Axiom arXiv:1010.2163 (2010).
  * (8) A. A. Abbott, C. S. Calude and K. Svozil. A Quantum Random Number Generator Certified by Value Indefiniteness. Mathematical Structures in Computer Science 24 (Special Issue 3), e240303 (2014).
  * (9) A. A. Abbott, C. S. Calude and K. Svozil. Value-indefinite observables are almost everywhere. Phys. Rev. A 89, 032109 (2014).
  * (10) R. Ramanathan, F. G. S. L. Brandão, K. Horodecki, M. Horodecki, P. Horodecki and H. Wojewódka. Randomness amplification against no-signaling adversaries using two devices. Phys. Rev. Lett. 117, 230501 (2016).
  * (11) F.G.S.L. Brandão, R. Ramanathan, A. Grudka, K. Horodecki, M. Horodecki, P. Horodecki, T. Szarek, and H. Wojewódka. Robust Device-Independent Randomness Amplification with Few Devices. Nat. Comm. 7, 11345 (2016).
  * (12) H. Wojewódka, F. G. S. L. Brandão, A. Grudka, M. Horodecki, K. Horodecki, P. Horodecki, M. Pawĺowski, R. Ramanathan. Amplifying the randomness of weak sources correlated with devices. IEEE Trans. on Inf. Theory. Vol. PP, Issue 99 (2017).
  * (13) A. Cabello, L. E. Danielsen, A. J. Lopez-Tarrida, J. R. Portillo. Basic exclusivity graphs in quantum correlations. Phys. Rev. A 88 032104 (2013).
  * (14) A. Cabello. State-independent quantum contextuality and maximum nonlocality. arXiv:1112.5149 (2011).
  * (15) F. Arends. A lower bound on the size of the smallest Kochen-Specker vector system. Master’s thesis, Oxford University (2009).
  * (16) F. Arends, J. Ouaknine, and C. W. Wampler. On searching for small Kochen-Specker vector systems. In Proc. WG, vol. 6986 of Springer LNCS (2011).
  * (17) R. K. Clifton. Getting Contextual and Nonlocal Elements-of-Reality the Easy Way. American Journal of Physics, 61: 443 (1993).
  * (18) A. Cabello, J. Estebaranz and G. García-Alcaine. Bell-Kochen-Specker Theorem: A Proof with 18 vectors. Physics Letters A 212, 183 (1996).
  * (19) C. Held. The Kochen-Specker Theorem. The Stanford Encyclopedia of Philosophy (Fall 2016 Edition), Edward N. Zalta (ed.), (2016).
  * (20) A. Cabello. Experimentally testable state-independent quantum contextuality. Phys. Rev. Lett. 101, 210401 (2008).
  * (21) A. Cabello and G. García-Alcaine. Bell-Kochen-Specker Theorem for any finite dimension $n\geq 3$. J. Phys A: Math. and Gen., 29, 1025, (1996).
  * (22) I. Pitowsky. Infinite and finite Gleason’s theorems and the logic of indeterminacy. Journal of Mathematical Physics 39, 218 (1998).
  * (23) E. Hrushovski and I. Pitowsky. Generalizations of Kochen and Specker’s theorem and the effectiveness of Gleason’s theorem. Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics 35, 177194. arXiv: 0307139 (2003).
  * (24) A. M. Gleason. Measures on the Closed Subspaces of a Hilbert Space. Journal of Mathematics and Mechanics 6, 885 (1957).
  * (25) S. Yu and C. H. Oh. State-independent proof of Kochen-Specker theorem with 13 rays. Phys. Rev. Lett. 108, 030402 (2012).
  * (26) A. Stairs, Philos. Sci. 50, 578 (1983).
  * (27) T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms, Second Edition. The MIT Press (2001).
  * (28) L. Lovasz, M. Saks, A. Schrijver. Orthogonal representation and connectivity of graphs, Linear Algebra and its applications, 4, 114/115, 439 (1987).
  * (29) R. Ramanathan et al., in preparation.
  * (30) R. Ramanathan, F. G. S. L. Brandão, K. Horodecki, M. Horodecki, P. Horodecki, and Hanna Wojewódka Randomness Amplification under Minimal Fundamental Assumptions on the Devices, Phys. Rev. Lett. 117, 230501 (2016).
  * (31) M. Chudnovsky, N. Robertson, P. Seymour and R. Thomas. The strong perfect graph theorem. Annals of Mathematics, 164 (1): 51 (2006).
  * (32) R. Peeters. Orthogonal representations over finite fields and the chromatic number of graphs. Combinatorica 16, 3, 417 (1996).