## Abstract

An important class of contextuality arguments in quantum foundations are the all-versus-nothing (AvN) proofs, generalizing a construction originally due to Mermin. We present a general formulation of AvN arguments and a complete characterization of all such arguments that arise from stabilizer states. We show that every AvN argument for an *n*-qubit stabilizer state can be reduced to an AvN proof for a three-qubit state that is local Clifford-equivalent to the tripartite Greenberger–Horne–Zeilinger state. This is achieved through a combinatorial characterization of AvN arguments, the AvN triple theorem, whose proof makes use of the theory of graph states. This result enables the development of a computational method to generate all the AvN arguments in on *n*-qubit stabilizer states. We also present new insights into the stabilizer formalism and its connections with logic.

This article is part of the themed issue ‘Second quantum revolution: foundational questions’.

## 1. Introduction

Since the classic no-go theorems by Bell [1] and Bell–Kochen–Specker [2,3], contextuality has gained great importance in the development of quantum information and computation. This key characteristic feature of quantum mechanics represents one of the most valuable resources at our disposal to break through the limits of classical computation and information processing, with various concrete applications, e.g. in quantum computation speed-up [4,5] and in device-independent quantum security [6]. Bell's proof of his famous theorem, as well as the subsequent formulation due to Clauser *et al*. [7], relies on the derivation of an inequality involving empirical probabilities, which must be satisfied by any local theory but is violated by quantum mechanics. Greenberger and co-workers [8,9] gave a stronger proof of contextuality, which revolves around only possibilistic features of quantum predictions, without taking into account the actual values of the probabilities. This version of the phenomenon corresponds to the notion of *strong contextuality* in the hierarchy introduced by Abramsky & Brandenburger [10]. In 1990, Mermin presented a simpler proof of this phenomenon, which rests on deriving an inconsistent system of equations in , and became known in the literature as the original ‘all-versus-nothing’ (AvN) argument [11]. Recent work on the mathematical structure of contextuality [10] allowed a powerful formalization and generalization of Mermin's proof to a large class of examples in quantum mechanics using stabilizer theory [12]. This work is of particular significance in the context of measurement-based quantum computation (MBQC), where AvN contextuality plays an important role [5,13–15]. The general theory of AvN arguments introduced in [12] raises the natural question of whether it is possible to identify the states admitting this type of proof of contextuality. In this paper, we address this question by combining the general theory of AvN arguments with the graph-state formalism [16]. We summarize our results as follows:

— We show that generalized AvN arguments on stabilizer states can be completely characterized by

*AvN triples*, proving part of what was previously known as the*AvN triple conjecture*[17].

AvN triples are triples of elements of the Pauli *n*-group satisfying certain combinatorial properties. The presence of such a triple in a stabilizer group was proved in [12] to be a sufficient condition for AvN contextuality. We show that the converse of this statement is also true for the case of *maximal* stabilizer subgroups, or, equivalently, for stabilizer states, yielding a complete combinatorial characterization of AvN arguments using stabilizer states. This new description of AvN arguments leads to another important result:

— We prove that any AvN argument on an

*n*-qubit stabilizer state can be reduced to an AvN argument involving only three qubits that are local Clifford (LC)-equivalent to the tripartite Greenberger–Horne–Zeilinger (GHZ) state.

The last part of the paper is dedicated to an application of this characterization:

— We present a computational method to generate all AvN arguments for

*n*-qubit stabilizer states (for*n*sufficiently small).

Until now, we have had a rather limited number of examples of quantum-realizable strongly contextual models giving rise to AvN arguments. The technique we introduce here gives us a large amount of instances of this type of model.

These findings are introduced after a theoretical digression on general AvN arguments for stabilizer states, which provides interesting new insights on their relationship to logic. In particular:

— We represent the well-known link between subgroups of the Pauli

*n*-group and their stabilizers in the Hilbert space of*n*qubits as a Galois connection, which allows us to establish a relationship with the Galois connection between syntax and semantics in logic (e.g. [18]).

Previous work has already shown a number of connections between logic and contextuality [12,19–21]. For instance, a direct link between the structure of quantum contextuality and classic semantic paradoxes is shown in [12]. The Galois correspondence we exhibit is a step towards a precise understanding of this interaction.

*Outline* The remainder of the paper is organized as follows. In §2, we recall the original AvN argument by Mermin and generalize it to a class of empirical models. Section 3 introduces the stabilizer formalism, the Galois correspondence and the connections with logic. In §4, we prove the AvN triple theorem and investigate its consequences. Finally, in §5, we present and illustrate the method to generate AvN triples.

## 2. All-versus-nothing arguments

### (a) Mermin's original formulation

In this section, we review Mermin's AvN proof of strong contextuality of the GHZ state.

Recall the definition of the *Pauli operators*, dichotomic observables corresponding to measuring spin in the *x*-, *y*- and *z*-axes, with eigenvalues ±1:
These matrices are self-adjoint, have eigenvalues ±1, and together with identity matrix *I* satisfy the following relations:
2.1

The GHZ state is a tripartite qubit state, defined by
We consider a tripartite measurement scenario where each party *i*=1,2,3 can perform a Pauli measurement in {*X*_{i},*Y*_{i}} on GHZ, obtaining, as a result, an eigenvalue in {±1}.^{1} By adopting the viewpoint of [10], this experiment can be seen as an empirical model whose support is partially described by table 1 (the remaining choices of measurements give rows with full support and can therefore be ignored).

These partial entries of the table can be characterized by the following equations in :
where denotes the outcome of the measurement *P*_{i}, for all *P*_{i}∈{*X*_{i},*Y*_{i}}. It is straightforward to see that this system is inconsistent. Indeed, if we sum all the equations, we obtain 0=1, as each variable appears twice on the left-hand side. This means that we cannot find a global assignment consistent with the model, showing that the GHZ state is strongly contextual.

### (b) General setting

The description of empirical models as generalized probability tables provided by [10] allows us to generalize Mermin's argument to a larger class of examples.

A *measurement scenario* is a tuple where is a finite set of measurement labels, *O* is a finite set of measurement outcomes, and is a family that is downwards closed and satisfies . The elements of are the *measurement contexts*, i.e. the sets of measurements that can be performed jointly. An *empirical model* over the scenario is a family indexed by the contexts, where *e*_{U} is a probability distribution on *O*^{U}, the set of joint outcomes for the measurements in the context *U*. We can think of an empirical model as a table with rows indexed by the contexts , columns indexed by the joint outcomes *s*∈*O*^{U}, and entries given by the probabilities *e*_{U}(*s*). In the examples considered here, we typically present only the rows corresponding to maximal contexts, as probabilities of outcomes for smaller contexts are determined from these by marginalization—this corresponds to a compatibility condition which is a generalized form of no-signalling [10].

An empirical model *e* is *strongly contextual* if there is no global assignment which is *consistent* with *e* in the sense that the restriction of *g* to each context *U* yields a joint outcome for that context which is possible (has non-zero probability) in *e*. Formally, there is no such that, for all , *e*_{U}(*g*|_{U})>0.

In the setting we will consider, all the measurements are dichotomic and produce outcomes in .^{2}

To an empirical model , we associate an *XOR theory* . It uses a -valued variable for each measurement label . For each context , will include the assertion
whenever the support of *e*_{U} contains joint outcomes of only even parity, i.e. with an even number of 1s, and
whenever it contains joint outcomes of only odd parity, i.e. with an odd number of 1s. In other words, it includes the assertion whenever for all such that *e*_{U}(*s*)>0.

We say that the model *e* is *AvN* if the theory is inconsistent. As an inconsistent theory implies the impossibility of defining a consistent global assignment , we have the following result:

### Proposition 2.1 ([12], Proposition 7)

*If an empirical model e is AvN, then it is strongly contextual*.

As an example, we consider the Popescu–Rohrlich (PR) box model [22] given in table 2.

The XOR theory of the PR box model consists of the following four equations: which lead to 0=1. Hence, the theory is inconsistent and the model is strongly contextual.

Although it is obviously not always the case that parity equations can fully describe the support of an empirical model, this setting is particularly suited for the study of strong contextuality in stabilizer states, as we shall see in the following sections.

## 3. The stabilizer world

Stabilizer quantum mechanics [23,24] is a natural setting for general AvN arguments and allows us to see how AvN models can arise from quantum theory. In this section, we recall the main definitions and present new insights on the connection between AvN arguments and logical paradoxes.

### (a) Stabilizer subgroups

Let *n*≥1 be an integer. The *Pauli* *n*-*group* *P*_{n} is the group whose elements have the form *α*(*P*_{1},…,*P*_{n}), where is an *n*-tuple of Pauli operators, *P*_{i}∈{*X*,*Y*,*Z*,*I*}, with global phase *α*∈{±1,±i}. The multiplication is defined by *α*(*P*_{1},…,*P*_{n})*β*(*Q*_{1},…,*Q*_{n})=*γ*(*R*_{1},…,*R*_{n}), where *P*_{i}*Q*_{i}=*γ*_{i}*R*_{i}, . The unit is . The group *P*_{n} acts on the Hilbert space of *n* qubits via the action
3.1
Given a subgroup *S*≤*P*_{n}, the *stabilizer* of *S* is the linear subspace
The subgroups of *P*_{n} that stabilize non-trivial subspaces must be commutative and contain only elements with global phases ±1. We call such subgroups *stabilizer subgroups*.

### (b) Stabilizer subgroups induce XOR theories

We are interested in a quantum measurement scenario where *n* parties share an *n*-qubit state and can each choose to perform a local Pauli operator *X*, *Y* or *Z* on their respective qubit. The set of measurement labels is thus , and the contexts are subsets of that contain at most one element for each index *i*, as each party can perform at most only one measurement. In other words, the maximal contexts are the sets {*m*_{1},…,*m*_{n}} where *m*_{i}∈{*x*_{i},*y*_{i},*z*_{i}}, and the contexts are subsets of these. Note that this is a Bell-type scenario, of the kind considered in discussions of non-locality, a particular case of contextuality. However, we will often need to consider only a subset of the contexts—and even a subset of the measurement labels—in order to derive an AvN argument.

Let be an element of the Pauli *n*-group and |*ψ*〉∈*H*_{n} a state stabilized by *P* (hence we must have *α*=±1). Then,
and so |*ψ*〉 is a *α*-eigenvector of *P*_{1}⊗⋯⊗*P*_{n}. Consequently, the expected value satisfies
From footnote 1, this means that, given *n* qubits prepared on the state |*ψ*〉, any joint outcome resulting from measuring *P*_{i} at each qubit *i* must have even (respectively, odd) parity when *α*=1 (respectively, *α*=−1).

Therefore, to any stabilizer group *S*≤*P*_{n}, we associate an XOR theory
where
where is such that the element *P* has global phase *α*=(−1)^{a}. We say that *S* is *AvN* if is inconsistent.

Note that, from the discussion above, it follows that this is (a subset of) the XOR theory of every empirical model *e* obtained from local Pauli measurements on any *n*-qubit state stabilized by *S*, i.e. any |*ψ*〉∈*V*_{S}.

Consequently, given an AvN subgroup *S*≤*P*_{n} and any state |*ψ*〉∈*V*_{S}, the *n*-partite empirical model realized by |*ψ*〉 under the Pauli measurements is strongly contextual. Indeed, the inconsistency of implies the impossibility of finding a global assignment compatible with the support of the empirical model [12]:

### Proposition 3.1

*AvN subgroups of P _{n} give rise to strongly contextual empirical models admitting AvN arguments*.

### (c) Galois connections and relations with logic

Proposition 3.1 shows that an AvN argument is essentially a logical paradox: to a strongly contextual model corresponds an inconsistent XOR theory. Previous work has already outlined this intriguing connection between contextuality and logical paradoxes. In [19], it is shown how quantum violations to Bell inequalities can be systematically viewed as arising from logical inconsistencies. In [12], a structural equivalence between PR box models and liar paradoxes is observed. Here, the link between logical XOR paradoxes and the contextuality of stabilizer subgroups is formalized using a Galois connection.

There is a well-known correspondence between the rank of a subgroup *S* of *P*_{n} and the dimension of its stabilizer [24]:
3.2
In particular, when *S* is a maximal stabilizer subgroup, we have *k*=*n*, hence , so *S* stabilizes a unique state (up to global phase). We call such states *stabilizer states*.

We formalize and extend this link by introducing a Galois correspondence between subgroups of *P*_{n} and their stabilizers.

Given two partially ordered sets *A* and *B*, an (*antitone*) *Galois connection* between *A* and *B* is a pair 〈 *f*,*g*〉 of order-reversing maps such that *a*≤*gf*(*a*) for all *a*∈*A*, and *b*≤*fg*(*b*) for all *b*∈*B*.

Define a relation *R*⊆*P*_{n}×*H*_{n} by
This induces a Galois connection between the powersets and , ordered by inclusion:
3.3
Note that *closed sets* *S*^{⊥⊥} and *V* ^{⊥⊥} are subgroups of *P*_{n} and vector subspaces of *H*_{n}, respectively. Therefore, by restricting (3.3) to closed sets, we obtain a Galois connection *SG*(*P*_{n})↔*SS*(*H*_{n}) between the closed subgroups of *P*_{n} and the closed subspaces of *H*_{n}. Explicitly, the connection is given by the maps *F*:*SG*(*P*_{n})↔*SS*(*H*_{n}):*G*, with
where (*P*_{n})_{|ψ〉}:={*A*∈*P*_{n}|*A*⋅|*ψ*〉=|*ψ*〉} denotes the isotropy group of |*ψ*〉. As the Galois connection is constructed through closed sets, it is *tight* in the sense of [25], and hence *F* is an order-isomorphism, with inverse *G*.

This result suggests an intriguing relation with the Galois connection between syntax and semantics in logic [18,26]:
3.4
where is a formal language. The Galois closure operators correspond to deductive closure on the side of theories, and closure under the equivalence induced by the logic on the side of models. Let ⊕-**Th** denote the set of all XOR theories. The map
is order-preserving and allows us to establish a link between the Galois connection *SG*(*P*_{n})↔*SS*(*H*_{n}) and the one described in (3.4). In particular, we have the following commutative diagram:

where ⊕-**Str** denotes the set of XOR structures, and the order-preserving function maps a subspace *V* of *H*_{n} to the set
Note that, in categorical terms, an antitone Galois connection is a dual adjunction between poset categories. One can easily show that the pair of functors is a monomorphism of adjunctions [27].

## 4. Characterizing all-versus-nothing arguments

Using the general theory of AvN arguments for stabilizer states reviewed in the last section, we present a characterization of AvN arguments based on the combinatorial concept of an AvN triple [12]. To achieve this result, we will take advantage of the graph-state formalism, which will also enable us to conclude that a tripartite GHZ state always underlies any AvN argument for stabilizer states.

### (a) All-versus-nothing triples

As AvN subgroups give rise to strongly contextual empirical models, we are naturally interested in characterizing this property. In [12], this problem is addressed by introducing the notion of AvN triple. We rephrase the definition from [12] in slightly more general terms:

### Definition 4.1 (cf. [12], definition 3)

An *AvN triple* in *P*_{n} is a triple 〈*e*,*f*,*g*〉 of elements of *P*_{n} with global phases ±1 that pairwise commute and that satisfy the following conditions:

(i) For each

*i*=1,…,*n*, at least two of*e*_{i},*f*_{i},*g*_{i}are equal.(ii) The number of ‘

*i*'s such that*e*_{i}=*g*_{i}≠*f*_{i}, all distinct from*I*, is odd.

Note that the only difference with respect to the original definition from [12] is that we allow elements of an AvN triple to have global phase −1.

A key result from [12] is that AvN triples provide a sufficient condition for AvN proofs of strong contextuality. A similar argument shows that this is still true for the slightly more general notion of AvN triple.

### Theorem 4.2 (cf. [12], theorem 4)

*Any subgroup S of* *P*_{n} *containing an AvN triple is AvN.*

### Proof.

Let 〈*e*,*f*,*g*〉 be an AvN triple in *P*_{n}, where , and , with . We denote by *N*_{f} the number of ‘*i*'s such that *e*_{i}=*g*_{i}≠*f*_{i} and *e*_{i},*f*_{i},*g*_{i}≠*I*, which is odd by definition 4.1(ii). The global phase of *h*:=*efg* is given by
Indeed, we get a local phase −1 for each of the *N*_{f} indices where *e*_{i}=*g*_{i}≠*f*_{i}, because *e*_{i}*f*_{i}*g*_{i}=−*e*_{i}*g*_{i}*f*_{i}=−*f*_{i}. Thus, if we consider the four equations corresponding to these elements in the XOR theory of the subgroup, summing their right-hand sides yields *a*⊕*b*⊕*c*⊕(*a*⊕*b*⊕*c*⊕1)=1. On the other hand, by definition 4.1(i), we have {*e*_{i},*f*_{i},*g*_{i}}={*P*,*Q*} with at least two elements equal to *P*. Thus, by (2.1), the product *e*_{i}*f*_{i}*g*_{i} will be *Q* up to a phase, and so, as this is absorbed into the global phase, *h*_{i}=*Q*. This means that each column of the four equations contains two ‘*P*'s and two ‘*Q*'s. Therefore, summing all the four equations, we obtain 0=1. ▪

It was conjectured by the first author that the presence of an AvN triple in a stabilizer subgroup is also necessary for the existence of an AvN proof of strong contextuality. The intuition is that short AvN proofs suffice. This is the *AvN triple conjecture* [17]. We will now prove the AvN triple conjecture for the case of maximal stabilizer subgroups, or, equivalently, for stabilizer states, by taking advantage of the graph-state formalism, which is briefly reviewed in the following subsection.

### (b) Graph states

Graph states are special types of multi-qubit states that can be represented by a graph. Let *G*=(*V*,*E*) be an undirected graph. For each *u*∈*V* , consider the element with global phase +1 and components
4.1
where denotes the neighbourhood of *u*, i.e. the set of all the vertices adjacent to *u*. The *graph state* |*G*〉 associated to *G* is the unique^{3} state stabilized by the subgroup generated by these elements,
4.2

One of the key properties of graph states is their generality with respect to stabilizer states, as stated in the following theorem due to Schlingemann [28]. Recall the definition of the LC group on *n* qubits,
where *U* acts by conjugation on elements of *P*_{n} via the representation of as the operator *αP*_{1}⊗⋯⊗*P*_{n}. Two states |*ψ*〉,|*ψ*′〉∈*H*_{n} are said to be LC-equivalent whenever there is a such that |*ψ*′〉=*U*|*ψ*〉.

### Theorem 4.3 ([28,29])

*Any stabilizer state |S〉 is LC-equivalent to some graph state |G〉, i.e. |S〉=U|G〉 for some LC unitary* .

An instance of this result will be important for us. Consider the *n*-partite GHZ state
We apply an LC transformation consisting of a Hadamard unitary
at every qubit of GHZ except the *k*th one (where 1≤*k*≤*n* can be chosen arbitrarily) to obtain
The stabilizer group of |*ψ*〉 is generated by the elements *e*,*f*^{1},*f*^{2},…,*f*^{k−1},*f*^{k+1},…,*f*^{n}, where
By the definition of a graph state, this list of stabilizers coincides with the *star graph* centred at the vertex corresponding to the *k*th qubit (figure 1). As *k* was chosen arbitrarily, all the graph states corresponding to star graphs on *n* vertices and different centres are LC-equivalent.

Another important property of graph states is that they allow us to characterize LC-equivalence between them by a simple operation on the underlying graphs. This is the notion of local complementation. Given a graph *G*=(*V*,*E*) and a vertex *v*∈*V* , the *local complement* of *G* at *v*, denoted by *G*⋆*v*, is obtained by complementing the subgraph of *G* induced by the neighbourhood of *v* and leaving the rest of the graph unchanged [30]. The following theorem is due to Van den Nest *et al*. [31] (see also [32]).

### Theorem 4.4 ([31], theorem 3)

*By local complementation of a graph G=(V,E) at some vertex v∈V , one obtains an LC-equivalent graph state. Moreover, two graph states* |*G*〉 *and* |*G′*〉 *are LC-equivalent if and only if the corresponding graphs are related by a sequence of local complementations, i.e.*
*for some v*_{1}*,…,v*_{n}*∈V .*

Thanks to this theorem, we can show that the *n*-partite GHZ state is LC-equivalent both to the state corresponding to the star graph (cf. figure 1) and to the one corresponding to the complete graph on *n* vertices. Indeed, it is sufficient to choose a vertex *v* of the complete graph and apply a local complementation to it to obtain a star graph centred at *v*, as illustrated in figure 2.

### (c) The all-versus-nothing triple theorem and its consequences

In this section, we prove the theorem characterizing AvN arguments on stabilizer states.

Firstly, we need to make some observations. Note that the Born rule is invariant under any unitary action acting simultaneously on the measurement by conjugation and on the state. Therefore, if we have a quantum-realizable empirical model specified by a state |*ψ*〉 and a set of measurements , then, given any unitary *U*, the empirical model specified by the state *U*|*ψ*〉 and the set of measurements is equivalent to the original one, in the sense that it assigns the same probabilities, which of course implies that it has the same contextuality properties.

In the particular case when |*ψ*〉 is a stabilizer state for the subgroup *S*≤*P*_{n} and *U* is an LC operation, then the state *U*|*ψ*〉 is a stabilizer state for the subgroup *USU*^{†}={*UPU*^{†}|*P*∈*S*}.

An important fact we shall need is that AvN triples are sent to AvN triples by such LC operations. The reason is that LC operations are composed of local unitaries that act as permutations on the set {±*X*,±*Y*,±*Z*}, and therefore preserve all the conditions of definition 4.1.

We now show that AvN triples fully characterize AvN arguments for stabilizer states and that a tripartite GHZ state is always responsible for the existence of such an AvN proof of strong contextuality.

### Theorem 4.5 (AvN triple theorem)

*A maximal stabilizer subgroup S of* *P*_{n} *is AvN if and only if it contains an AvN triple. The AvN argument can be reduced to one concerning only three qubits. The state induced by the subgraph for these three qubits is LC-equivalent to a tripartite GHZ state.*

### Proof.

Sufficiency follows from proposition 4.2. So, suppose that the maximal stabilizer subgroup *S* is AvN. Let |*ψ*〉 be the stabilizer state corresponding to *S*. As any stabilizer state is LC-equivalent to a graph state by theorem 4.3 and as LC transformations preserve AvN triples, we can suppose without the loss of generality that |*ψ*〉 is a graph state |*G*〉 induced by a graph *G*=(*V*,*E*), and consequently that *S*=*S*_{G} as in (4.2).

Given that the empirical model obtained from the state |*G*〉 and local Pauli operators is strongly contextual, there must exist at least one vertex *u* with degree at least 2, i.e. . Indeed, if *G* has no such vertex, *G* is a union of disconnected edges and vertices, which implies that |*G*〉 is a tensor product of 1-qubit and 2-qubit states, which do not present strongly contextual behaviour for any choice of local measurements [33,34].

Let *u*∈*V* have degree ≥2 and let *v*,*w* be two distinct vertices in . We have two possible cases:

There is an edge between

*v*and*w*. Then, in accordance with (4.1), the elements*g*^{u},*g*^{v},*g*^{w}of*S*_{G}have the form^{4}: 4.3 which are easily seen to constitute an AvN triple.There is no edge between

*v*and*w*. Then, we have and the elements 〈*g*^{u},*g*^{u}*g*^{v},*g*^{u}*g*^{w}〉 form an AvN triple:

Notice that in both cases the AvN argument is reduced to just three qubits. Moreover, by the discussion at the end of the previous subsection, we know that the state corresponding to the subgraph induced by *u*,*v*,*w* in either of these two cases is LC-equivalent to a tripartite GHZ state: in case 1, we have a complete graph on three vertices, while in case 2, we have a star graph centred at *u*. ▪

The second part of the above result means that the essence of the contradiction is witnessed by looking at only three qubits. In fact, in the contexts being considered, the experimenters at the remaining *n*−3 parties perform either no measurement or a *Z* measurement. We could imagine that, in trying to build a consistent global assignment of outcomes in to all the measurements, each of these *n*−3 parties *i* is allowed to freely choose a value 0 or 1 for the variable . Then, the equations for the variables representing the measurements of the remaining three parties would be those of the usual GHZ argument, up to flipping an even number of the values on the right-hand side. In terms of the state, we can use the ‘partial inner product’ operation described, for example, in [35], p. 129^{5} to apply the eigenvectors corresponding to the chosen values for the other *n*−3 parties to |*G*〉, resulting in a three-qubit pure state that is LC-equivalent to the GHZ state.

From this theorem, we immediately obtain the following corollaries:

### Corollary 4.6

*A graph state* |*G*〉 *is strongly contextual if and only if* *G* *has a vertex of degree at least* *2*.

### Corollary 4.7

*Every strongly contextual three-qubit stabilizer state is LC-equivalent to the GHZ state*.

The graph theoretic arguments used in the proof of the AvN triple theorem present some similarities to the techniques developed in [37] to derive Bell inequalities that are maximally violated by some graph states. In fact, corollary 4.6 also follows from theorem 1 in [37]. However, it is important to note that the AvN triple theorem goes beyond the graph-state formalism to expose the underlying algebraic structure of AvN arguments, which ultimately rests on AvN triples.

We provide some examples to clarify the statement of theorem 4.5. Cluster states are a fundamental resource in MBQC [15,38–40]. The four-qubit two-dimensional cluster state is described by the graph in figure 3. Its stabilizer group *S* is generated by the following elements of *P*_{4}:

The stabilizer group *S* contains the following four AvN triples, corresponding to the triples of qubits highlighted in figure 4:
4.4

As another example, consider the graph state |*G*〉 represented in figure 5. Its stabilizer *S* is generated by the following elements of *P*_{4}:

and contains the following AvN triples: 4.5 which correspond to the triples of qubits illustrated in figure 6.

## 5. Applications

In this section, we take advantage of the characterization introduced above to develop a computational method to identify all the possible AvN arguments.

### (a) Counting all-versus-nothing triples

We start by introducing an alternative definition of AvN triple.

### Definition 5.1 (alternative definition of AvN triple)

An *AvN triple* in the Pauli *n*-group P_{n} is a triple 〈*e*,*f*,*g*〉 with global phases ±1, such that:

(i) For each

*i*=1,…,*n*, at least two of*e*_{i},*f*_{i},*g*_{i}are equal.(ii) The number

*N*_{g}of ‘*i*'s such that*e*_{i}=*f*_{i}≠*g*_{i}, all distinct from*I*, is odd.(iii) The number

*N*_{e}of ‘*i*'s such that*e*_{i}≠*f*_{i}=*g*_{i}, all distinct from*I*, is odd.(iv) The number

*N*_{f}of ‘*i*'s such that*e*_{i}=*g*_{i}≠*f*_{i}, all distinct from*I*, is odd.

The equivalence of the two definitions follows directly from the following lemma.

### Lemma 5.2

*Let* *n*≥3. *Suppose* *e*,*f*,*g*∈*P*_{n} *have global phase* ±1 *and are such that, for each* *i*=1,…,*n*, *at least two of* *e*_{i},*f*_{i},*g*_{i} *are equal. Then* *e*,*f*,*g* *commute pairwise if and only if* *N*_{e},*N*_{f} *and* *N*_{g} *have the same parity*.

### Proof.

Given two arbitrary elements *h*,*k*∈*P*_{n}, we have
Thus, *e* and *f* commute if and only if *N*:=|{*i*|*e*_{i}≠*f*_{i}∧*e*_{i},*f*_{i}≠*I*}| is even. By hypothesis, for each *i*, at least two of *e*_{i}, *f*_{i}, *g*_{i} are equal, hence
Therefore,
Similarly,
and the result follows. ▪

Note that this new definition can be used to derive an alternative proof of the fact that any AvN triple for *n*-partite states can be reduced to an AvN triple that involves only three qubits, in accordance with theorem 4.5. Indeed, given an AvN triple 〈*e*,*f*,*g*〉 in *P*_{n}, as *N*_{g},*N*_{e},*N*_{f} are odd, we can always choose three indices 1≤*i*_{1},*i*_{2},*i*_{3}≤*n* such that
Clearly, the elements of the triple restricted to these indices constitute an AvN triple in *P*_{3} and therefore an AvN argument.

The rationale for introducing definition 5.1 is that it allows us to better understand AvN triples from a computational perspective. We show a first example by providing a closed formula for the number of AvN triples in *P*_{n}.

### Proposition 5.3

*Let* *n*≥3. *The number of AvN triples in* P_{n} *is given by*
*where* *denotes the parity of* *n*.

### Proof.

The factor of 2^{3}=8 corresponds to the possible choices of global phase ±1 for each element in the triple.

By definition 5.1, an AvN triple 〈*e*,*f*,*g*〉 is essentially determined by three odd numbers *N*_{e},*N*_{f} and *N*_{g}. Their sum *S*:=*N*_{e}+*N*_{f}+*N*_{g}≤*n* can be seen as the number of columns of the triple that play an active part in the AvN argument. Let us compute the amount of AvN triples having *S* ‘relevant’ columns. We start by counting the number of solutions to the equation
where *N*_{e},*N*_{f},*N*_{g} and *S* are all odd numbers. Let *k*,*e*,*f*,*g*≥0 be integers such that *S*=2*k*+1 and *N*_{i}=2*i*+1 for *i*=*e*,*f*,*g*. We have
By stars and bars [41], the number of solutions to this equation is (*k*+1 *k*−1) . By condition (i) of definition 5.1, we must choose two observables in {*X*,*Y*,*Z*} (the order counts) in each of the *S* relevant columns, for a total of . Finally, we have eight possible configurations of each of the remaining *n*−*S* non-relevant columns, namely
where *P* has to be chosen in {*X*,*Y*,*Z*} for a total of (3⋅7+1)^{n−S}=22^{n−2k−1} possibilities. Hence, the number of AvN triples in *P*_{n} having *S*=2*k*+1 relevant columns is
Now, the amount of odd numbers of relevant columns *S*≤*n* that we can select is given by
and the result follows. ▪

### (b) Generating all-versus-nothing triples

We devote this last section to the presentation of a computational method to generate all the AvN triples contained in *P*_{n}. Until now, we only had a rather limited number of examples of quantum-realizable models featuring AvN proofs of strong contextuality. Thanks to the AvN triple theorem 4.5, the technique we introduce allows us to find all such models for a sufficiently small *n*.

*Check vectors* [23] are a useful way to represent elements of *P*_{n} in a computation-friendly way. Given an element , its check vector *r*(*P*) is a 2*n*-vector
whose entries are defined as follows:
Every check vector *r*(*P*) completely determines *P* up to phase (i.e. *r*(*P*)=*r*(*αP*) for all *α*∈{±1,±i}). We can use this representation to express the conditions for an AvN triple. More specifically, we represent an AvN triple, up to the global phases of each of its elements, as a matrix whose rows are the check vectors of each element of the triple. Condition (i) of definition 5.1 can be rewritten as
5.1
The numbers *N*_{e},*N*_{f} and *N*_{g} can also be easily computed. For instance, *N*_{g} equals the cardinality of the set
Hence, in order to find all the AvN triples in *P*_{n}, we need to solve the following problem:
which is easily programmable.

An implementation of this method using Mathematica [42] can be found in [43], where we present the algorithm and the resulting list of all 216 AvN triples in *P*_{3} and all 19 008 AvN triples in *P*_{4}, disregarding the choice of global phases ±1 for each element—in order to get the total number of AvN triples from proposition 5.3, note that these numbers need to be multiplied by a factor of 8 to account for this choice of these global phases. By theorem 4.5, this list generates all the possible AvN arguments for three-qubit and four-qubit stabilizer states.

We note that extensive computations of AvN arguments have been carried out in [44]; it would be interesting to relate this work to our approach.

## 6. Conclusion

The recent formalization and generalization of AvN arguments in stabilizer quantum mechanics [12] allowed us to study their properties from a purely mathematical standpoint.

Thanks to this framework, we have introduced an important characterization of AvN arguments based on the combinatorial concept of AvN triple [12], leading to a computational technique to identify all such arguments for stabilizer states. The graph-state formalism, which played a crucial role in the proof of the AvN triple theorem, also allowed us to infer an important structural feature of AvN arguments, namely that any such argument can be reduced to an AvN proof on three qubits, which is essentially a standard GHZ argument. This result shows in particular that the GHZ state is the only three-qubit stabilizer state, up to LC-equivalence, admitting an AvN argument for strong contextuality.

Our computations provide a very large number of quantum-realizable strongly contextual empirical models admitting AvN arguments. These new models could potentially find applications in quantum information and computation, as well as contributing to the ongoing theoretical study of strong contextuality as a key feature of quantum mechanics [10,12,19,34].

The abstract formulation of generalized AvN arguments has also allowed us to introduce new insights into the connections between logic and the study of contextuality. Recent work on logical Bell inequalities [19] and the relation between contextuality and semantic paradoxes [12] suggests a strong connection between these two domains. In this work, we have taken a first step towards a formal characterization of this link in the quantum-realizable case by showing the existence of a Galois connection between subgroups of the Pauli *n*-group and subspaces of the Hilbert space of *n* qubits, which can be seen as the stabilizer-theoretic counterpart of the Galois connection between syntax and semantics in logic.

## Data accessibility

This article has no additional data.

## Authors' contributions

All authors contributed equally to this work and gave final approval for publication. Their names are listed in alphabetical order.

## Competing interests

The authors declare no competing interests.

## Funding

Support from the following is gratefully acknowledged: the Simons Institute for the Theory of Computing; EPSRC EP/N018745/1, ‘Contextuality as a Resource in Quantum Computation’ (S.A., R.S.B.); EPSRC Doctoral Training Partnership; and Oxford–Google Deepmind Graduate Scholarship (G.C.).

## Acknowledgements

The authors thank Nadish de Silva, Kohei Kishida and Shane Mansfield for helpful discussions. This work was carried out in part while the authors visited the Simons Institute for the Theory of Computing (supported by the Simons Foundation) at the University of California, Berkeley, as participants of the Logical Structures in Computation programme.

## Footnotes

One contribution of 15 to a theme issue ‘Second quantum revolution: foundational questions’.

↵1 It is convenient to relabel +1,−1 and × as 0,1 and ⊕, respectively, where ⊕ is addition modulo 2. The eigenvalues of a joint measurement

*A*_{1}⊗*A*_{2}⊗⋯⊗*A*_{n}are the products of eigenvalues at each site, so they are also ±1. Thus, joint measurements are still dichotomic and distinguish joint outcomes only up to parity.↵2 More generally, one can define the notion of AvN arguments for models with outcomes valued in a unital, commutative ring. However, for the purposes of this paper, we are concerned only with AvN parity arguments arising from stabilizer quantum theory.

↵3 Uniqueness follows from (3.2) because there is an independent generator for each vertex.

↵4 The notation in (4.3) indicates that , , and is either

*Z*or*I*for every other vertex*z*∈*V*∖{*u*,*v*,*w*}, and analogously for the other lines.↵5 This is actually the application of a linear map to a vector under map–state duality [36].

- Accepted August 1, 2017.

- © 2017 The Authors.

Published by the Royal Society under the terms of the Creative Commons Attribution License http://creativecommons.org/licenses/by/4.0/, which permits unrestricted use, provided the original author and source are credited.