State-independent all-versus-nothing arguments

Contextuality as a resource of quantum advantage was first discussed by Raussendorf [19] in a measurement-based quantum computing model (MBQC). His major results state that an MBQC requires contextuality when it computes a non-linear Boolean function with a certain probability. This idea was developed by Bermejo-Vega et al. [20], establishing the explicit proof that contextuality is a necessary resource for a large class of MBQC schemes.

It has also been observed that contextuality plays a crucial role in a gate-based quantum computing model. Bravyi, Gosset, and König [25] reported the quantum advantage of shallow circuits, which was the first mathematical proof of an unconditional quantum advantage for a certain class of quantum circuits. Here they considered strategies for non-local games recast into the circuit, proving a separation between classical and quantum computational models. Subsequently, this strategy was shown to be noise robust [26] and extended to distributed non-local games [18].

Karanjai, Wallman, and Bartlett [23] also developed their own framework of contextuality to prove that the spatial complexity of classical simulation of a quantum measurement process is bounded by contextuality. This result is further developed by Kirby and Love [24], who suggested applying contextuality to evaluate the quantum advantage of the VQE algorithm. They proposed a test to determine whether or not the given objective function for the VQE is contextual, employing the compatibility graph of Pauli operators and the measure, contextual $p$-distance. This test detects the non-classicality of the objective function, thus filtering out classically simulatable procedures. This research has important implications for the application of contextuality to evaluate practical quantum algorithms.

The sheaf-theoretic definition of contextuality has been instrumental in our understanding of contextuality, as it provides precise mathematical structure to the intuitive concept of contextuality. The sheaf-theoretic framework was first proposed by Abramsky and Brandenburger [11, 13], where they defined events and distributions on the measurement scenario and identified the sheaf structure of those concepts. Here, one can connect the global distribution to the hidden-variable model, which is well-known for its failure to explain the distinct features of quantum theory. Further discussion by Abramsky, Barbosa, and Mansfield [16] investigated a measure of contextuality. This work opened the way to quantify contextuality in the given quantum scenario.

The subsequent development in the cohomological approach to contextuality also provides a substantial methodology for witnessing contextuality in a given measurement scenario. Abramsky, Mansfield, and Barbosa [12] proposed the approach based on the Čech cohomology invariant, which leverages powerful tools of sheaf cohomology to detect contextuality in the empirical model. The proposal by Okay, Roberts, Bartlett, and Raussendorf [21] established the topological approach to identifying contextuality, which has the potential to provide a more refined analysis, although an additional topological structure must be concerned. Those approaches were connected by Aasnæss [18], complementing generality and completeness in each approach by translating arguments from one to another.

On the other hand, a stronger form of contextuality, namely, the all-versus-nothing (AvN) argument was also characterized by the same group. Abramsky et al. [14, 15] formalized the logical inconsistency in quantum information systems into an AvN argument referring back to the observation by Mermin [9, 10]. This class of contextuality is also observed as an obstruction in the cohomology group in the work by Aasnæss [18].

While the sheaf-theoretic framework provides the base of arguments in the quantum advantage of MBQCs and shallow circuits, the last case of the application, Refs. 23, 24, roots back to Kochen and Specker’s framework on formalizing contextuality, so-called contextuality in a closed sub-theory. This notion seems to describe the same idea with the sheaf-theoretic contextuality, but it is solely based on arguments on operator algebra of observables. Moreover, the interesting point is that they bring the 2-qubit measurement scenario of certain observables into the stronger class of contextuality, while the 2-qubit scenario was previously claimed to be unable to show strong non-locality [17]. This confliction clearly motivated our research on the classification of contextuality, giving a specific case for the two different points of view. Jumping into the result, it turns out that Kochen-Specker type contextuality actually deals with an abelian partial group generated by the given set of observables. Furthermore, we do find strong contextuality in this generated abelian partial group, i.e., in a partial closure.

In this report, we review the mathematical structure of the sheaf-theoretic formalism of contextuality and refine the framework to characterize the connecting point to Kochen-Specker type contextuality. We first go through strict definitions of measurement scenarios, measurement covers, events, distributions, and empirical models. Under these definitions, we review the connection between contextuality and a sheaf theory. Then, we further develop those ideas to classify strong contextuality and all-versus-nothing (AvN) arguments, which define stronger classes of contextuality. The main proposal of this report is the definition of a state-independent AvN class, which is proven in the text that induces AvN arguments for any state realizing the measurement scenario. Then, we show that Kochen-Specker type contextuality is translated into the state-independent AvN in a partial closure, by considering an abelian partial group structure of a Pauli $n$-group. Finally, we summarize the classes of contextuality in a state-side view and an operator-side view, where we can notice that state-dependent contextual scenarios seem to merge into the state-independent AvN class in a partial closure.

For example, the well-known Bell scenario, where two experimenters, Alice and Bob, can each choose between performing one of two different measurements, say, $a_{1}$ or $a_{2}$ for Alice and $b_{1}$ or $b_{2}$ for Bob, obtaining one of two possible outcomes, is represented as follows:

Here, the measurement contexts $C\in\mathcal{M}$ explains that we are allowed to measure either $a_{1}$ or $a_{2}$, but not both (same for $b_{1}$ and $b_{2}$). We will generally assume a measurement scenario $\left<X,\mathcal{M},O\right>$ for the rest of this paper. We also refer to Bell-type measurement scenarios in a tuple $(n,k,l)$, where $n$ is the number of agents, $k$ is the number of possible measurements for each agent, and $l$ is the number of possible outcomes. Thus, the example is a $(2,2,2)$ scenario.

From the example, we also capture the idea that there needs some additional information about $\mathcal{M}$ to describe situations in quantum mechanics. While we described $\mathcal{M}$ as consisting of “sets of measurements that can be performed together,” it remains unclear how many (or how few) sets are needed fully characterize a given scenario. Hence, we aim to collect a sufficient number of sets to cover all possible measurements, while keeping them as compact as possible to represent each set of compatible measurements. Here comes the definition of the measurement cover.

We think of the anti-chain condition because we shall focus on the maximal compatible sets of measurements.

For example, consider the event of observing $a_{1}$ and $b_{1}$ in the Bell scenario and obtaining outcomes 0 and 1, each. We represent this event by a tuple $(a_{1}\mapsto 0,b_{1}\mapsto 1)$, or simply, $(0,1)$. Here we further focus on the mathematical structure of events. We must strictly distinguish events $(a_{1}\mapsto 0,b_{1}\mapsto 1)$ and $(a_{1}\mapsto 0)$. In the latter case, there is no information about what we measured on Bob’s side. It means not only that we do not know the outcome Bob obtained, but also that we even cannot say which measurement either $b_{1}$ or $b_{2}$ Bob actually measured. It implies that the events are given with respect to the set $U$ of measurements as well as assigning a value $o\in O$ for each measurement $x\in U$. In fact, we can define this set of events as a categorical functor including the restriction map, which formalizes “forgetting” information out of what is concerned in the smaller context.

Fig. 1 illustrates an example of an event sheaf defined in the Bell scenario. $\mathcal{E}$ basically maps each subset $U\subset X$ to a set of functions, what we call events on $U$. Each event $s$ is a mapping from $U$ to $O$ such that assigns an outcome for each measurement $x\in U$.

Now we can compose a functor $\mathcal{D}_{R}:\mathbf{Set}\rightarrow\mathbf{Set}$ with the event sheaf $\mathcal{E}:\mathcal{P}(X)^{\mathsf{op}}\rightarrow\mathbf{Set}$ to form a functor $\mathcal{D}_{R}\mathcal{E}:\mathcal{P}(X)^{\mathsf{op}}\rightarrow\mathbf{Set}$. For each $U\subset X$ A distribution $d\in\mathcal{D}_{R}\mathcal{E}(U)$ maps $\mathcal{E}(U)\rightarrow R$.

For example, consider the Bell scenario again. Table 1 realizes the Clauser-Horne-Shimony-Holt (CHSH) model, obtained from local projective measurements equatorial at angles 0 for $a_{1}$, $b_{1}$ and $\pi/3$ for $a_{2}$, $b_{2}$ on the two-qubit Bell state. In the table, each row represents a context $C$, and each column represents an event $s\in\mathcal{E}(C):C\rightarrow O$ indexed by the outcome for each measurement. Then the first row of the table is a distribution $d\in\mathcal{D}_{R}\mathcal{E}(\{a_{1},b_{1}\})$ mapping each event $s\in\mathcal{E}(\{a_{1},b_{1}\})$ to the semiring $\mathbb{R}_{\geq 0}$ as follows:

In the later part of this paper, it turns out to be obvious that the functor $\mathcal{D}_{R}\mathcal{E}$ cannot be a sheaf on the semirings we are concerned. However, we actually deal with a specific family of distributions when we look into a quantum system. This concept is characterized by an empirical model.

Now for our Bell scenario, we can show that it is an empirical model $e$ for a measurement cover $\mathcal{M}=\left\{\{a_{1},b_{1}\},\{a_{1},b_{2}\},\{a_{2},b_{1}\},\{a_{2},b_{2}\}\right\}$ where $e_{C}$ is the distribution specified by each row of the table. The compatibility condition is verified by computing the marginal, for example, for the first two rows:

Thus, we verify that $\left.e_{\{a_{1},b_{1}\}}\right|_{a_{1}}=\left.e_{\{a_{1},b_{2}\}}\right|_{a_{1}}$. Here we denoted the restriction map to the one-point set $\{m\}$ by $\left.s\right|_{m}$ rather than $\left.s\right|_{\{m\}}$. We shall keep this abbreviation throughout this paper since it does not violate our intuition too much. The same computation for the other contexts $C\in\mathcal{M}$ shows that $e$ is a no-signaling empirical model. We shall also use the term empirical model for the no-signaling model as we will only focus on quantum-like models with the no-signaling condition.

We previously defined two functors $\mathcal{E}$ and $\mathcal{D}_{R}\mathcal{E}$. In fact, these two functors can be identified as presheaves. $\mathcal{E}$ can be further identified to be a sheaf, justifying its name, ’event sheaf.’ Here, we will look through the definitions of presheaves and sheaves referring to Ref [28] to make those facts clear. Remark that we can consider the measurement cover $\mathcal{M}$ as a generating set of the topology of $X$, giving each context $C$ an open subset of $X$.

In general, we assume discrete topology for the set of measurements $X$. It is easy to show that $\mathcal{E}$ is a sheaf and $\mathcal{D}_{R}\mathcal{E}$ is a presheaf. However, $\mathcal{D}_{R}\mathcal{E}$ generally fails to achieve the sheaf conditions.

For the counter-example of locality, consider two different probability distributions defined on a measurement context $\{a,b\}$ as Table 2. We can verify that $d_{1}$ and $d_{2}$ do agree on every local measurement event.

For the counter-example of gluing, the best example is actually the PR-box, although it is not a quantum realizable model. Table 3 illustrates the empirical model of PR-box, which is not actually a quantum model but still satisfies the condition of being no-signaling empirical model. We can try gluing the first three rows to obtain the probability distribution over $X$, but in this case, there only exists a unique global distribution $d\in\mathcal{D}_{R}\mathcal{E}(X)$, such that $d((0,0,0,0))=d((1,1,1,1))=1/2$ and 0 otherwise. However, it fails to match with the distribution over the context $\{a_{2},b_{2}\}$ since there is no probability of getting $s(a_{2})\neq s(b_{2})$ from this global distribution.

In general, empirical models are compatible families of distributions. Although the sheaf condition does not hold for the entire presheaf $\mathcal{D}_{R}\mathcal{E}$, it is possible to ask if the gluing property holds for such a specific family $\left\{e_{C}\right\}_{C\in\mathcal{M}}$. This is equivalent to asking the existence of a global distribution $d\in\mathcal{D}_{R}\mathcal{E}(X)$, defined on the entire set of measurements $X$. Such a global distribution defines a distribution on the set $\mathcal{E}(X)=O^{X}$, which marginalizes to yield the behavior of the empirical model: i.e. $\forall C\in\mathcal{M},\left.d\right|_{C}=e_{C}$.

Now, let’s consider the meaning of the existence of a global distribution for a given empirical model $e$. Here we will show that $e$ has a global distribution if and only if it is realized by a factorisable hidden-variable model.

This result provides a definitive justification for equating the phenomena of non-locality and contextuality with obstructions to the existence of global distributions. We shall say the empirical model $e$ is noncontextual if there exists a global distribution for $e$.

The incidence matrix conceptually represents the tuple of restriction maps

At the same time, viewing it as a matrix over the semiring $R$, it acts by matrix multiplication on distributions in $\mathcal{D}_{R}\mathcal{E}(X)$, represented as row vectors:

Thus, the image of this map will be the set of families $\left\{e_{C}\right\}_{C\in\mathcal{M}}$ which arise from global distributions.

With this proposition, we can now compute the existence of global distributions from the given empirical model. However, the existence of global distributions depends on the semiring $R$, on which empirical models are discussed. We have naturally thought of probability distributions so far, which are defined on the non-negative reals $\mathbb{R}_{\geq 0}$, but here, let me address how the situation differs according to the semiring.

There are three main examples of semirings discussed in the field of contextuality: the Booleans

the non-negative reals

and the reals

We call the distribution $d\in\mathcal{D}_{\mathbb{B}}$ on Boolean semiring a possibility distribution. In the case of the semiring $\mathbb{R}_{\geq 0}$, $\mathcal{D}_{\mathbb{R}_{\geq 0}}$ is the set of probability distributions. In the case of the reals $\mathbb{R}$, $\mathcal{D}_{\mathbb{R}}$ is the set of signed probability measures with finite support, allowing for ’negative probabilities.’ It can be shown that we can always find global distributions for the given empirical model on the semiring $\mathbb{R}$, making $\mathcal{D}_{\mathbb{R}}$ a sheaf. It is also straightforward to show that the probabilistic global distribution can exist only when the possibilistic global distribution exists.

Now we will extend this discussion about the incidence matrix further to define the measure of contextuality. Here we consider the semiring $\mathbb{R}_{\geq 0}$. First, define a convex sum $\lambda e+(1-\lambda)e^{\prime}$ of two empirical models $e$ and $e^{\prime}$ on the same measurement cover, by taking the convex sum of probability distributions on each context. Compatibility is preserved in the convex sum; hence, it yields a well-defined empirical model.

Then, we will consider the computation of this contextual fraction using the incidence matrix. Recall the equation (1), which is valid only for a noncontextual model. Since now we can no longer guarantee the solution of $\mathbf{M}\mathbf{X}=\mathbf{V}$, we will consider a relaxed condition:

where the comparison is elementwise throughout this section. Let an empirical model $e$ and some convex decomposition $e=\lambda e^{NC}+(1-\lambda)e^{\prime}$ be given. Because both empirical models are defined on the same measurement cover, the incidence matrix is the same for both models. Let $\mathbf{V}^{NC}$ encode the noncontextual model $e^{NC}$ and suppose a vector $\mathbf{X}^{NC}\in\mathbb{R}_{\geq 0}^{n}$ satisfies $\mathbf{M}\mathbf{X}^{NC}=\mathbf{V}^{NC}$, $\left\|\mathbf{X}\right\|_{1}=1$. Then, since $\mathbf{V}=\lambda\mathbf{V}^{NC}+(1-\lambda)\mathbf{V}^{\prime}$,

which implies existence of a solution $\mathbf{M}\mathbf{X}\leq\mathbf{V}$ with a lower bound $\lambda\mathbf{V}^{NC}$. Here, the norm $\left\|\mathbf{X}\right\|_{1}\geq\left\|\lambda\mathbf{X}^{NC}+(1-\lambda)\mathbf{X}^{\prime}\right\|_{1}\geq\lambda$. Thus, an optimal solution $\mathbf{X}^{*}$ of the following linear programming(LP) gives the noncontextual fraction by $\mathsf{NCF}(e)=\max{\lambda}=\left\|\mathbf{X}^{*}\right\|_{1}$:

Thus, we obtain a method computing a contextual fraction of a given empirical model $e$. One can refer to Ref [16] to check that this contextual fraction has monotonicity for the free operations of a resource theory, thus, works as a useful measure.

Once we have this measure of contextuality, one can notice the empirical models whose contextuality equals 1. In fact, an empirical model has a contextual fraction of 1 if and only if it is strongly contextual. Here we define strong contextuality based on a possibilistic empirical model and show the equivalence of maximally contextual and strongly contextual.

Before we start, let’s first look into the simple example of state-independent AvN. Fig. 2 shows the Mermin’s square [10] that consists of mutually commuting Pauli observables on two qubits. In each row and each column, the product of the first two operators equals the last one, except for the last column: $XX\cdot ZZ=-YY$. Once we rearrange the product, we get that the product of every row and column equals $\pm I$: $+I$ for all three rows and the first two columns from the left, and $-I$ for the last column.

Here, consider a measurement scenario $\left<X,\mathcal{M},\mathbb{Z}_{2}\right>$ where each row and each column translates to a measurement context $C\in\mathcal{M}$. Then, try assigning a global assignment $g:X\rightarrow\mathbb{Z}_{2}$ to this measurement scenario. The product equations are mapped to the following linear equations,