Minimal true-implies-false and true-implies-true sets of propositions in noncontextual hidden-variable theories

An essential ingredient in many examples of the conflict between quantum theory and noncontextual hidden variables (e.g., the proof of the Kochen-Specker theorem and Hardy's proof of Bell's theorem) is a set of atomic propositions about the outcomes of ideal measurements such that, when outcome noncontextuality is assumed, if proposition $A$ is true, then, due to exclusiveness and completeness, a nonexclusive proposition $B$ ($C$) must be false (true). We call such a set a true-implies-false set (TIFS) [true-implies-true set (TITS)]. Here we identify all the minimal TIFSs and TITSs in every dimension $d\ge 3$, i.e., the sets of each type having the smallest number of propositions. These sets are important because each of them leads to a proof of impossibility of noncontextual hidden variables and corresponds to a simple situation with quantum vs classical advantage. Moreover, the methods developed to identify them may be helpful to solve some open problems regarding minimal Kochen-Specker sets.

Figure 1

Greechie orthogonality diagrams of the minimal (a) TIFS and (b) TITS in $d=3$. Small circles represent propositions, smooth lines represent complete sets (i.e., sets in which one and only one of the propositions must be true); in particular, they indicate that any pair of propositions connected by a smooth line cannot both be true (exclusiveness). (a) If $A$ is true then $B$ is false [2]. (b) If $A$ is true then $C$ is true [3]. These sets are realizable in $S^2$ by taking, for instance, $v_A=\left(1,1,1\right)/\sqrt{3}$, $v_1=\left(1,-1,0\right)/\sqrt{2}$, $v_2=\left(1,0,-1\right)/\sqrt{2}$, $v_3=\left(0,0,1\right)$, $v_4=\left(0,1,0\right)$, $v_5=\left(1,1,0\right)/\sqrt{2}$, $v_6=\left(1,0,1\right)/\sqrt{2}$, $v_B=\left(-1,1,1\right)/\sqrt{3}$, $v_7=\left(0,1,-1\right)/\sqrt{2}$, and $C=\left(2,1,1\right)/\sqrt{6}$. In QT, the proposition $v_i$ is represented by the projector $|v_i\rangle \langle v_i|$. To obtain a TIFS or a TITS in $d=4$ it is enough to add $\langle v|=(0,0,0,1)$, and similarly to obtain TIFS or TITSs in higher dimensions [31].

Figure 2

Greechie orthogonality diagrams of all nonisomorphic seven-vertex (first row) and eight-vertex (the remaining rows) biconnected graphs of minimal valence two, not containing cycles of length four, and containing at least two triangles.

Figure 3

Greechie orthogonality diagram of the simplest quantum state-independent contextuality set in $d=3$ (and in any $d$) [29], the Yu-Oh set [9]. It contains six TIFSs like the one in Fig. 1. One of them is indicated using the same notation used in Fig. 1.

Figure 4

(a)–(c) Greechie orthogonality diagrams of the three minimal TIFS in $d=4$. The one in (a) appears in Hardy's proof of Bell's theorem [22] (see details in Refs. [32, 35, 37]).

Figure 5

(a)–(d) Greechie orthogonality diagrams of the four minimal TIFS in $d=5$. All of them have 10 propositions and nine contexts.

Figure 6

Scheme for constructing a minimal TITS with $d+7$ propositions in dimension $d$. The subgraph $\{A,B,v_1,\cdots ,v_{d+5},B\}$ corresponds to a minimal TIFS. If $A$ is true then $B$ is false and also $v_7,\cdots ,v_{d+3},$ and $v_{d+4}$ are false. Therefore, since $\{v_7,\cdots ,v_{d+3},v_{d+4},B,C\}$ are mutually exclusive, then $C$ must be true.

Figure 7

(a)–(h) Greechie orthogonality diagrams of the eight minimal TIFs in $d=6$. All of them have 11 propositions and nine contexts.