Kochen-Specker contextuality

A central result in the foundations of quantum mechanics is the Kochen-Specker theorem. In short, it states that quantum mechanics is in conflict with classical models in which the result of a measurement does not depend on which other compatible measurements are jointly performed. Here compatible measurements are those that can be implemented simultaneously or, more generally, those that are jointly measurable. This conflict is generically called quantum contextuality. In this review, an introduction to this subject and its current status is presented. Several proofs of the Kochen-Specker theorem and different notions of contextuality are reviewed. How to experimentally test some of these notions is explained, and connections between contextuality and nonlocality or graph theory are discussed. Finally, some applications of contextuality in quantum information processing are reviewed.

Figure 1

The set in the original proof of KS has 117 vectors and 118 contexts. Each node represents a vector. Nodes in the same straight line or circumference represent mutually orthogonal vectors. The red node is orthogonal to all nodes connected to the red edge. We proceed similarly with the green and yellow nodes. A proof of the KS theorem can be obtained as follows. One of the nodes 1, 2, and 11 has to be true. The symmetry of the graph allows us to assume without loss of generality that it is node 1. Therefore, node 9 must be false because of the “bug” subgraph (see Fig. 2) between nodes 1 and 9. Thus, since nodes 2, 9, and 10 are mutually orthogonal and node 2 is connected to node 1, node 10 must be true. Applying the same argument, node 12 must be false and node 13 must be true since nodes 12, 13, and 2 form a basis. When this is repeated twice, node 14 must be true. However, nodes 1 and 14 cannot both be true. This concludes the proof. This figure improves the representation in the work of [283], where the 117 vectors are represented by 120 nodes using two nodes each for 3 of the 117 vectors.

Figure 2

Different representation of the same orthogonality relations. (a) Vectors are represented by nodes, while contexts are represented by straight lines (or, more generally, by smooth lines). Three vectors in the same straight line are mutually orthogonal. This graph is also called a Greechie diagram; see [219]. (b) Vectors are represented by nodes, and orthogonal vectors are connected by edges. In particular, triples of mutually orthogonal vectors form triangles, e.g., nodes 2, 3, and 4. An example of vectors realizing such relations is given by $v_1=(1,-1,1)$, $v_2=(1,1,0)$, $v_3=(0,0,1)$, $v_4=(1,-1,0)$, $v_5=(1,1,-1)$, $v_6=(1,0,1)$, $v_7=(0,1,0)$, and $v_8=(1,0,-1)$. This graph is called the bug ([426]) and it has the property that, for $d=3$, an assignment of true to node 1 implies a false assignment for node 5. In fact, if nodes 1 and 5 are both true, then nodes 2, 4, 6, and 8 must be false (they are connected), which implies that nodes 3 and 7 are true (they are the remaining nodes of two triples), which gives a contradiction since nodes 3 and 7 are connected. As can be seen in Fig. 1, they are the building blocks of the original proof of the KS theorem.

Figure 3

Graphical representation of the 18-vector KS set by [128]. Each node represents a vector. For simplicity, vectors are unnormalized. Each smooth line, i.e., every straight line or ellipse, represents a context. Vectors in each context are mutually orthogonal. Each vector appears in exactly two contexts: $v_{12}$ appears both in context 1 and 2, etc. As a consequence, by assigning a noncontextual true to some vectors, one obtains an even number of true, whereas one should get exactly nine true propositions, one for each context. Therefore, the set is not KS colorable. Notice that there are additional relations of orthogonality not shown in the graph and not used to prove the contradiction. Vectors are also listed in the table, where each row represent a context. For simplicity, we denote $-1$ as $\overline{1}$.

Figure 4

Orthogonality relations between the vectors of the 21-vector, seven-context KS set given by [314]. Vectors are represented by nodes and contexts by straight lines. $1010ab$ denotes the vector $(1,0,1,0,a,b)$, where $a=e^{2\pi i/3}$ and $b=a^2$. For simplicity, normalization factors are omitted. Contexts contain mutually orthogonal vectors. The set has 21 vectors, and each vector is in two contexts. To map one (and only one) of the vectors in each context to 1 and preserve the latter property, one would need to associate 1 with 21/2 vectors, which is not an integer. This makes the mapping impossible and proves that the set is a KS set.

Figure 5

Subgraph of the Yu-Oh graph given by the vertices $A,B,1,2,4,5,7,8$, corresponding to a basic block of the original KS graph (the bug), with a valid coloring, i.e., $\mathrm{green}=\text{true}$, $\mathrm{red}=\text{false}$. As discussed in Sec. 3a (Fig. 2), $A$ and $B$ must be exclusive events.

Figure 6

(a) PM magic square and (b) Mermin’s magic pentagram. Each dot represents an observable with possible outcome $-1$ or 1. Each line contains mutually compatible observables. For each line, the product of the corresponding observables is the identity, except for the bold lines, where it is minus the identity. A possible choice of observables satisfying the conditions in (a) is given in Eq. (7). A possible choice of observables satisfying the conditions in (b) is the following: $O_1={\sigma }_z^{(1)}\otimes {\sigma }_x^{(2)}\otimes {\sigma }_x^{(3)}$, $O_2={\sigma }_x^{(1)}\otimes {\sigma }_z^{(2)}\otimes {\sigma }_x^{(3)}$, $O_3={\sigma }_x^{(1)}\otimes {\sigma }_x^{(2)}\otimes {\sigma }_z^{(3)}$, $O_4={\sigma }_z^{(1)}\otimes {\sigma }_z^{(2)}\otimes {\sigma }_z^{(3)}$, $O_{12}={\sigma }_x^{(3)}$, $O_{13}={\sigma }_x^{(2)}$, $O_{14}={\sigma }_z^{(1)}$, $O_{24}={\sigma }_z^{(2)}$, and $O_{34}={\sigma }_z^{(3)}$.

Figure 7

Graph of orthogonality between the vectors of the Yu and Oh set ([490]). Adjacent nodes represent orthogonal vectors. For simplicity, the vectors are unnormalized. See the text for further details.

Figure 8

The set of vectors $v_j\in {\mathbb{R}}^3$ giving the dichotomic observables $A_j=2|v_j⟩⟨v_j|-\mathbb{1}$ providing the maximum violation of the KCBS inequality form a regular pentagram, with orthogonal vectors connected by a blue line. The state $\psi$ is directed along its symmetry axis. A realization is $|\psi ⟩=(1,0,0{)}^{\top }$ and $|v_k⟩=(\cos \theta ,\sin \theta \cos {\phi }_k,\sin \theta \sin {\phi }_k{)}^{\top }$, with $\cos \theta =1/\sqrt[4]{5}$, ${\phi }_k=2\pi k/5$, and $k=(2j+1)\text{mod}5$.

Figure 9

Different experimental procedures in Bell and more general noncontextuality scenarios. (a) Two contexts in Bell scenario. The same measurement $A_1$ is performed in two different contexts, either with $B_1$ or with $B_2$. (b) Two contexts in the PM scenario. The measurement of $A$ is performed in two contexts, either with $B$ and $C$ or with $a$ and $\alpha$. As in the Bell scenario, the same measurement procedure, represented by the box with label $A$, is repeated in different contexts. (c) Additional measurements to quantify experimental imperfections. The measurement of $A$ is repeated alone or together with $B$. Subsequent measurements of $A$ must confirm the same outcome, represented by the yellow light on the bottom of the device.

Figure 10

Upper panel: level scheme of a single ${}^{40}{\mathrm{Ca}}^{+}$ ion, highlighting the electronic levels used for the qubit. Lower panel: implementation of the measurement sequence of one column or row. To retrieve only 1 bit of information, a measurement is implemented by first performing a nonlocal unitary transformation, then only one qubit is read out, and finally the unitary transformation is reversed. From [230].

Figure 11

Upper panel: measurement correlations for a sequence of measurements for a partially entangled input state. The color choice indicates whether the product of the three results gives $+1$ (yellow) or $-1$ (red). The volume of a sphere is proportional to the likelihood of finding the corresponding measurement outcome. Lower panel: permutations of the observables within the rows and columns can serve as a test of the compatibility of the measurements. The measured absolute values of the products of the observables for all six possible permutations are shown. For each permutation, 1100 copies of the singlet state were used. From [272].

Figure 12

(a) Encoding of two qubits in one photon. A tunable polarizing beam splitter distributes the photon over two spatial modes, resulting in the spatial qubit. The polarization qubit is adjusted by half- and quarter-wave plates. (b) A row or column of the PM square is measured by a sequence of interferometers. After the sequence, the photon can be in one of eight different outputs, representing the eight outcomes of the sequence of measurements. (c) Detailed interferometric setups for all nine measurements in the PM square. From [27].

Figure 13

Left panels: setup for the measurement of the correlations $⟨A_i{A}_j⟩$ in the KCBS inequality in Eq. (63). The measurement $A_i$ has the result $-1$ if the corresponding detector clicks; otherwise, the value $+1$ is assigned. Consequently, the product $A_i{A}_j$ has the value $+1$ if both or no detectors register a photon; otherwise, the value is $-1$. Right panels: concrete experimental setup. The transformations $T_i$ are implemented via insertion of the half-wave plates ${\mathrm{WP}}_i$, which in combination with polarizing beam splitters distribute the photons across the modes. From [301].

Figure 14

Different decompositions of the maximally mixed state $\mathbb{1}/2$, represented in the $(x,z)$ plane of the Bloch sphere, in terms of the pairs along opposite lines, (such as $|{\psi }_a⟩,|{\psi }_A⟩$) or triples in the same triangle (such as $|{\psi }_a⟩,|{\psi }_b⟩,|{\psi }_c⟩$).

Figure 15

Experimental setup used by [342]. The quantum system consists of a single photon in which a specific polarization is prepared via a polarizer and two wave plates (preparation $P_{t,b}$) and then measured via two wave plates, a polarized beam splitter, and two detectors (measurement $M_t$). From [342].

Figure 16

Polytope associated with two measurements $A_1$ and $A_2$. The four vertices are the deterministic assignments, with the corresponding coordinate labeling. Equations (75) are associated with the four faces of the tetrahedron; for instance, $p_{12}=0$ is the plane tangent to vertices $(0,0,0)$, $(1,0,0)$, $(0,1,0)$, etc.

Figure 17

Compatibility graph associated with the observables of the KCBS scenario corresponding to the marginal scenario $\{(A_i,A_{i+1}){\}}_{i=0}^4$. This graph can also be used to illustrate the basic notions of paths, cycles, and independent sets. A path is given by any sequence of sequentially connected vertices, such as $(A_i,A_{i+1},A_{i+2})$, for any $i$ and with sum $\mathrm{modulo}5$. A cycle is a closed path such as $(A_0,A_1,\dots ,A_4,A_0)$. An independent set is a set of disconnected vertices such as $(A_i,A_{i+2})$. The pentagon contains independent sets of at most size 2. One can easily show that the complement of a pentagon is again a pentagon with edges $(A_i,A_{i+2})$ for $i=0,\dots ,4$ and sum $\mathrm{modulo}5$.

Figure 18

Exclusivity graph associated with the five events appearing in the inequality (80). The notation $(-1,+1|0,1)$ refers to the event of outcome $-1$ for the measurement of $A_0$ and outcome $+1$ for the measurement of $A_1$, etc.

Figure 19

Different $a:b$ coloring of the pentagon, i.e., $b$ colors associated with each vertex out of $a$ total colors. (a) $3:1$ coloring of the pentagon, i.e., three colors, one for each vertex, giving a chromatic number $\chi =3$. (b) $6:2$ coloring of the pentagon obtained by doubling the colors for each vertex. (c) One color from the $6:2$ coloring can be removed, giving a $5:2$ coloring corresponding to a fractional chromatic number ${\chi }_f=5/2$ for the pentagon.

Figure 20

Examples of a HMM and an $ϵ$ machine for the simulation of a biased coin flip (also called a perturbed coin). The process is given by a coin, which flips with a certain probability, as given by $P(x_i=H)=P(x_i=T)=1/2$ and $P(x_i=T|x_{i-1}=H)=1/2-\delta$ and $P(x_i=H|x_{i-1}=T)=1/2-\delta$. This can be seen as a fair coin ($\delta =0$) that is disturbed toward a constant process. Detailed descriptions of this and the following models were given by [317]. (a) A general HMM could simulate this with three internal states, corresponding to a fair coin and two maximally biased coins, which always give heads or tails. The fact that the biased coin flip tends to reproduce the previous result is modeled by the rule that the automaton acts most of the time as a fair coin, but sometimes this is replaced by a deterministic coin. (b) When constructing the $ϵ$ machine, one first observes that only the last output matters, so this defines the causal states. Since the two outputs are equally probable, the statistical entropy of the process is 1 bit. The HMM in (a) requires less memory, but it contains oracular information. If one knows that the automaton is in a state corresponding to a maximally biased coin, the next output is foreseeable.