Doctor of Philosophy Trinity 2021 Worcester College

# Comparing two cohomological obstructions for contextuality, and a
generalised construction of quantum advantage with shallow circuits

Sivert Aasnæss

###### Abstract

_Contextuality_ is a fundamental non-classical feature of quantum mechanics.
Abramsky et al. showed that contextuality in a range of examples is detected
by a cohomological invariant based on Čech cohomology. However, the approach
does not give a complete cohomological characterisation of contextuality.
Bravyi, Gosset, and König (BGK) gave the first unconditional proof that a
restricted class of quantum circuits is more powerful than its classical
analogue. The result, for the class of circuits of bounded depth and fan-in
(shallow circuits), exploits a particular family of examples of contextuality.

A different cohomological approach to contextuality was introduced by Okay et
al. Their approach exploits the particular algebraic structure of the Pauli
operators and their qudit generalisations known as Weyl operators. We give an
abstract account of the algebraic structure of the Weyl operators, that Okay
et al. exploit to define their cohomological invariant. We then generalise
their approach to any example of contextuality with this structure. We prove
at this general level that the approach does not give a more complete
characterisation of contextuality than the Čech cohomology approach.

BGK’s quantum circuit and computational problem is derived from a family of
non-local games related to the well known GHZ non-local game. We present a
generalised version of their construction. A systematic way of taking examples
of contextuality and producing unconditional quantum advantage results with
shallow circuits.

###### Contents

  1. 1 Introduction
    1. 1.1 Comparing two obstruction for contextuality
    2. 1.2 A general construction of quantum advantage with shallow circuits
    3. 1.3 Structure of this text
  2. 2 The sheaf-theoretic framework
    1. 2.1 Measurement scenarios
      1. 2.1.1 Quantum scenarios
      2. 2.1.2 Multipartite scenarios
    2. 2.2 Empirical models
      1. 2.2.1 Probabilistic empirical models
      2. 2.2.2 Possibilistic empirical models
      3. 2.2.3 State dependent contextuality
      4. 2.2.4 State independent contextuality
    3. 2.3 Simulations
      1. 2.3.1 Single-round simulations
      2. 2.3.2 Measurement protocols
      3. 2.3.3 General simulations
    4. 2.4 The cohomology of contextuality
      1. 2.4.1 Cohomology groups of a cochain complex
      2. 2.4.2 Čech cohomology
      3. 2.4.3 The obstruction to the extension of a local section
      4. 2.4.4 Generalised AvN arguments
    5. 2.5 Witnessing contextuality through cooperative games
      1. 2.5.1 Cooperative games
      2. 2.5.2 The pullback of a game
    6. 2.6 The contextual fraction
  3. 3 Comparing two obstructions for contextuality
    1. 3.0.1 Structure of chapter
    2. 3.1 Bundles over commutative partial monoids
      1. 3.1.1 Bundles
      2. 3.1.2 The splitting lemma
      3. 3.1.3 Extending local splittings
    3. 3.2 Cohomology of commutative partial monoids
      1. 3.2.1 The cohomology groups of a partial monoid
      2. 3.2.2 The obstruction to extending a local splitting
    4. 3.3 Measurement scenarios with bundle structure
      1. 3.3.1 Detecting contextuality with homomorphisms
      2. 3.3.2 The cohomological obstruction
    5. 3.4 Comparing two obstructions
  4. 4 From contextuality to shallow circuits: a general construction of quantum advantage
    1. 4.0.1 Structure of chapter
    2. 4.1 Circuits
      1. 4.1.1 Circuit strategies
    3. 4.2 Performing measurements far away with teleportation
      1. 4.2.1 Teleportation on a line followed by a measurement
      2. 4.2.2 Teleportation on a line followed by a Weyl measurement
    4. 4.3 Distributing measurements on graphs
      1. 4.3.1 Distributing measurements in two rounds
      2. 4.3.2 Distributing Weyl measurements in a single round
    5. 4.4 Distributing non-local games on graphs
      1. 4.4.1 Two-round distributed non-local games
      2. 4.4.2 Single-round distributed Weyl-measurement games
    6. 4.5 Separating quantum and classical circuits of low depth and fan-in
      1. 4.5.1 Lightcones of simulations
      2. 4.5.2 Classical bound
      3. 4.5.3 Randomised restrictions
    7. 4.6 Quantum advantage with shallow circuits
      1. 4.6.1 Examples
  5. 5 Final Remarks
    1. 5.1 Further work

###### List of Figures

  1. 1.1 Circuit version of the the _GHZ game_. Inputs $x_{1},x_{2},x_{3}\in\\{0,1\\}$ are selected uniformly at random. A Haramard gate followed by two controlled not gates initialises the state $\lvert GHZ\rangle:=\lvert 000\rangle+\lvert 111\rangle$. Each qubit is measured with measurement settings $0\mapsto X,1\mapsto Y$. Outcomes $y_{1},y_{2},y_{3}\in\\{0,1\\}$ are returned according to $1\mapsto 0,-1\mapsto 1$. The circuit wins if $x_{1}\oplus x_{2}\oplus x_{3}=1\oplus y_{1}\oplus y_{2}\oplus y_{3}$.
  2. (a)
  3. (b)
  4. 1.2  (a) The set of quantum measurement operators known as _Mermin’s square_ , and (b) the associated classifying space of the topological approach. In (a) Each row and column represents a context of commuting operators. In (b) each operator labels a loop attached to a single point, and each context a surface.
  5. (a) Mermin’s square
  6. (b) Classifying space for Mermin’s square
  7. 1.3 An interactive circuit (a) is a circuit with several rounds of inputs and outputs. The circuit is evaluated by composing with a classical circuit as in (b).
  8. (a)
  9. (b)
  10. 1.4  The quantum circuit (a) is _contextual_ if it is not equivalent to any classical circuit (b) of the same shape, with the ability to sample an arbitrary random seed $z_{1},\dots,z_{l}$.
  11. (a)
  12. (b)
  13. 1.5 The 2D-GHZ game. The quantum circuit strategy (a) prepares $n^{2}$ qubits in the cluster state of the $n\times n$ grid. It takes inputs $x_{1},\dots,x_{n^{2}}\in\\{1,2,3\\}$, performs controlled Pauli measurements according to $1\mapsto X,2\mapsto Y,3\mapsto Z$, and returns outcomes $y_{1},\dots,y_{n^{2}}\in\\{0,1\\}$ according to $1\mapsto 0,-1\mapsto 1$. The input is randomly sampled as follows. First select nodes $A,B,C\in n\times n$ and paths $u_{AB},u_{BC},u_{CA}\subset n\times n$ in a “sufficiently uniform” way. The circuit wins if the output $y$ satisfies $x_{A}\oplus x_{B}\oplus x_{C}=1\oplus(y_{A}\oplus k_{A}(y))\oplus(y_{B}\oplus k_{B}(y))\oplus(y_{C}\oplus k_{C}(y))$, where $k_{A}(y),k_{B}(y),k_{C}(y)\in\\{0,1\\}$ depends only on the value of $y$ close to $A,B,C$ respectively.
  14. (a)
  15. (b)
  16. 1.6 Given a nonlocal game with players $I$ and state $\psi$, and a graph $G$ with nodes $V$ we consider the scenario (a) consisting of players $I\times V$, here each dotted circle indicate a player and $\bullet$ a qudit in either a maximally entangled state or the state $\psi$. (b) By performing local measurement on the qudits held by each player we can distribute each qudit, up to a random factor on each qudit, to any player on the graph.
  17. (a)
  18. (b)
  19. 1.7  A _Weyl measurement strategy_ is a special quantum strategy using measurements in the basis of Weyl operators. For dimension $d\geq 2$ and $n$-qudit state $\psi$ the Weyl measurement strategy takes inputs $p_{1},\dots,p_{n}\in\mathbb{Z}_{d}^{2}$ and return outcomes $q_{1},\dots,q_{n}\in\mathbb{Z}_{d}$ of performing the single-qudit Weyl measurement $W(p_{i})$ on qudit $i$.
  20. 1.8 Let $\psi$ be an $I$-qudit state and $G=(V,E,r)$ a rooted graph. The quantum circuit strategy (a) prepares a single instance of $\psi$ and a maximally entangled pair of qudits $\lvert\phi\rangle:=\frac{\lvert 00\rangle+\lvert 11\rangle}{\sqrt{2}}$ for each $i\in I$ and edge $e\in E$. The circuit has an input for each $(i,v)\in I\times V$ which controls a measurement on a subset of qudits. This subset includes one of the two qudits of the state $\lvert\phi\rangle$ associated with each edge adjacent to $v$, and when $v=r$ also includes qudit $i$ of $\psi$. The possible measurement settings are either a Weyl operator measurement on a single qudit, or a Bell basis measurement on a pair of qudits. (b) In the nonlocal game Verifier selects inputs $p_{1},\dots,p_{n}$ and an accepting condition $A$ according to the nonlocal game $\Phi$. Verifier then randomly selects a rooted path $(v_{i1},\dots,v_{il_{i}})$ for each $i\in I$ and sends each $(i,v_{il_{i}})$ the input corresponding to a Bell basis measurement, and $(i,v_{il_{i}})$ the Weyl measurement setting $p_{i}$. Verifier accepts the outputs $p_{i1}^{\prime},\dots,p_{i(l_{i}-1)}^{\prime},q_{i}$ if $(q_{1}-[p_{1},p_{1}^{\prime}],\dots,q_{n}-[p_{n},p_{n}^{\prime}])\in A$, where $p_{i}^{\prime}:=p_{i1}^{\prime}+\dots+p_{il_{i}}^{\prime}$.
  21. (a)
  22. (b)
  23. 1.9  Let $\psi$ be an $I$-qudit state and $G=(V,E,r)$ a rooted graph. The quantum circuit strategy (a) prepares a single instance of $\psi$ and a maximally entangled pair of qudits $\lvert\phi\rangle:=\frac{\lvert 00\rangle+\lvert 11\rangle}{\sqrt{2}}$ for each $i\in I$ and edge $e\in E$. The circuit first takes an input for $(i,v)\in I\times V$ which controls a non-destructive measurement on a subset of qudits, it then takes another round of inputs for each $(i,v)\in I\times V$ which control destructive measurements on each subset of qudits. For each $(i,v)$ the subset of qudits which is measured includes one of the two maximally entangled qudits associated with each edge adjacent to $v$, and when $v=r$ also includes qudit $i$ of $\psi$. In the first round the measurement settings are either nothing or a Bell basis measurement on a pair of qudits. In the second round the possible measurements are either nothing or a conjugated measurement $W(p)MW(p)^{\dagger}$ on a single qudit, where $M$ is one of the measurement settings. (b) In the nonlocal game Verifier selects inputs $x_{1},\dots,x_{n}$ and an accepting condition $A$ according to the nonlocal game $\Phi$. Verifier then randomly selects a rooted path $(v_{i1},\dots,v_{il_{i}})$ for each $i\in I$ and first sends each $(i,v_{il_{i}})$ the input corresponding to a Bell basis measurement. If the outcomes of this are $p_{i1},\dots,p_{i(l_{i}-1)}$ Verifier sends $(i,v_{il_{i}})$ the input for the conjugated measurement $W(p_{i})M_{x_{i}}W(p_{i})^{\dagger}$, where $p_{i}^{\prime}:=p_{i1}^{\prime}+\dots+p_{il_{i}}^{\prime}$. Verifier accepts the output $y_{1},\dots,y_{n}$ if $(y_{1},\dots,y_{n})\in A$.
  24. (a)
  25. (b)
  26. (c)
  27. 2.1 Let $(X,\mathcal{M},O)$ be a measurement scenario. In an experimental run with $k$ rounds a sequence of contexts$\\{x_{11},\dots,x_{1n_{1}}\\},\dots,\\{x_{k1},\dots,x_{kn_{k}}\\}\in\mathcal{M}$ satisfying Eq. (2.1) are performed, giving outcomes $\\{o_{11},\dots,o_{1n_{i}}\\},\\{o_{k1},\dots,o_{kn_{k}}\\}$.
  28. 2.2  Consider a multipartite scenario with two measurement sites with measurement settings $\\{a,a^{\prime}\\}$, $\\{b,b^{\prime}\\}$ respectively. The maximal contexts are then $\\{a,b\\},\\{a,b^{\prime}\\},\\{b^{\prime},a^{\prime}\\},\\{b,a^{\prime}\\}$.
  29. 2.3 Bundle diagrams of Hardy’s model and the PR-box. The points above each measurement represents the two outcomes $0,1$ and the line segments the possible joint value assigmnets allowed by each model. A global section corresponds to a cycle visiting each measurement exactly once, for example the section $(a,a^{\prime},b,b^{\prime})=(1,1,0,0)$ in (a). However, (a) is logically contextual at the local section $(a,b)=(0,0)$ as can be seen. It can be seen that (b) is strongly contextual because no cycle visiting each measurement once is possible. .
  30. (a) Hardy’s model
  31. (b) PR-box
  32. 2.4  Consider a setup involving two measurement scenarios $S=(X,\mathcal{M},O),T=(Y,\mathcal{N},P)$. A simulation from $S$ to $T$ maps each measurement $y\in Y$ to a measurement protocol on $S$, and each possible outcome of this protocol to an outcome $p\in P_{y}$. This induces a map on empirical models of $S$ to empirical models of $T$.
  33. 2.5  The Magic Square game. Alice and Bob each hold one of the two qubits of two maximally entangled states $\phi$. Verifier sends Alice and Bob $a,b\in\\{1,2,3\\}$. Alice performs the three observables $(M_{1},M_{2},M_{3})$ in column $b$ of (b) and Bob performs the observables in row $a$. Given outcome $x=(x_{1},x_{2},x_{3}),y=(y_{1},y_{2},y_{3})$ they win if $x_{1}\oplus x_{2}\oplus x_{3}=1$ and $y_{1}\oplus y_{2}\oplus y_{3}=0$, and $x_{b}=y_{a}$.
  34. (a)
  35. (b)
  36. 2.6 The pullback of a game $\Phi$. Consider a game where Verifier plays against a set of players $Y$. Verifier sends $Y$ a context $C$, the players then interact with another set of players $X$ through a measurement protocol $f(C)$. If the result of $f(C)$ is a run $r$ then they respond with $g_{C}(r)$ to Verifier. Verifier accepts if $g_{C}(r)\in A$ satisfies the accepting condition. This game is equivalent to the game where Verifier interacts directly with $X$ by performing the measurement protocol $f(C)$ and accepts a run $r$ if $r\in g_{C}^{-1}(A)$.
  37. 2.7 In the resource view we think about an empirical model as a resource that can be consumed by a classical algorithm solving a computational problem.
  38. 3.1 Examples of classifying spaces taken from Okay et al. [ORBR17]. (a) is the GHZ proof, (b) Mermin’s square.
  39. (a)
  40. (b)
  41. 4.1 (a) A classical circuit with gates $F_{1},F_{2},F_{3},F_{4}$. (b) A quantum circuit with a unitary gate $U$ and a classically controlled measurement gate $M$. Classical wires are drawn as double lines and quantum wires as single lines. (c) The lightcone relationship between inputs and outputs in both circuit (a) and(b).
  42. (a)
  43. (b)
  44. (c)
  45. 4.2 Circuit version of the quantum strategy for the Magic Square game. First, two maximally entangled states are prepared using Hadamard gates and controlled not gates. The classical inputs $x_{1},x_{2}\in\\{1,2,3\\}$ are used to perform a basis change that is followed by computational basis measurements. We observe that under the controlled basis changes the computational basis measurements are equivalent to performing the measurements used in the Magic Square game.
  46. (a)
  47. (b)
  48. 4.3
  49. 4.5 (a) and (b) shows the inputs and outputs from respectively a single and two-round circuit strategy. Here $x_{1},\dots,x_{n}$ and $y_{1},\dots,y_{n}$ are the measurement settings and outcomes, while $z_{1},\dots,z_{l}$ is a random seed. Note that $F$ can be either classical or quantum. (c) We can think of the evaluation of (b) as being performed by “plugging in” a classical circuit $C$.
  50. (a)
  51. (b)
  52. (c)
  53. 4.6  In the teleportation protocol for qudits, Alice and Bob each hold one qudit of a pair in the maximally entangled state $\phi$. Alice first measures her maximally entangled qudit and another qudit in the Bell basis $\mathcal{B}$ giving an outcome $p\in\mathbb{Z}_{d}^{2}$. If Alice’s qudit is initially in the state $\psi$ then the post-measurement state of Bob’s qudit is $W(p)\lvert\psi\rangle$. It follows that if Bob performs the correction $W(-p)$ then up to an unobservable phase his qudit is in the state $\lvert\psi\rangle$. In diagrammatic notation, the protocol is equivalent to the identity wire from Alice to Bob.
  54. 4.7  Any number of agents $A_{1},\dots,A_{n}$ are arranged on a line, such that $A_{1}$ has a qudit $\psi$, and $A_{i},A_{i+1}$, where $i=1,\dots,n-1$ share a maximally entangled pair of qudits. We send $A_{n}$ a measurement setting. The goal is for the agents to implement a measurement on $\psi$, without communicating the measurement setting to any of the other agents $A_{1},\dots,A_{n-1}$.
  55. 4.8  Teleportation along a line followed by a measurement, using two rounds of measurements. Let $\\{M_{x}\\}_{x\in X}$ be a family of quantum measurements. We send a measurement setting $x$ to $A_{n}$ and $A_{1},\dots,A_{n-1}$ perform Bell basis measurements. The respective outcomes $p_{1},\dots,p_{n-1}\in\mathbb{Z}_{d}^{2}$ are sent to $A_{n}$. In the second round $A_{n}$ performs the conjugated measurement $A_{x}(p):=W(p)M_{x}W(p)^{\dagger}$ of $M_{x}$ with the Weyl operator $W(p)$. The effect of the protocol is up to an unobervable phase equivalent to $A_{n}$ performing the measurement $M_{x}$ on $A_{1}$’s qudit and returning the outcome.
  56. 4.9 Teleportation on a line with a simultaneous Weyl operator measurement. We send a measurement setting $p^{\prime}\in\mathbb{Z}_{d}^{2}$ to $A_{n}$. $A_{1},\dots,A_{n-1}$ perform Bell basis measurements with outcomes $p_{1},\dots,p_{n-1}\in\mathbb{Z}_{d}^{2}$, and $A_{n}$ performs a Weyl measurement $W(p^{\prime})$ with outcome $q\in\mathbb{Z}_{d}$. The final outcome is $q-[p,p^{\prime}]$, where $p:=p_{1}+\dots+p_{n-1}$. The protocol is equivalent to $A_{n}$ measuring $W(p^{\prime})$ and returning the outcome.
  57. 4.10  Given a rooted graph $G$ and a multi-qudit state $\psi$ we consider a scenario with an agent for each node of $G$ and qudit of $\psi$. The agents corresponding to the roots have each qudit of $\psi$, and agents given by adjacent nodes have shared entanglement. (a) $\bullet$ denotes a qudit, and each line connecting two dots either the state $\psi$ or a maximally entangled state $\phi$. The set of qudits held by each agent is circled. (b) A path in $G$ for each qudit of $\psi$ defines a sequence of qudits that can be used to implement measurements on $\psi$ by agents that are far away.
  58. (a)
  59. (b)
  60. 4.11 Simulation protocol. (a) In the first round we perform Bell basis measurements along each path. (b) The first step teleports each qudit up to a Weyl operator phase. In the second round we measure with the corrected measurement.
  61. (a)
  62. (b)
  63. 4.12  The state $\lvert\psi,G\rangle$ for a two-qudit state $\psi$ and a depth two binary tree. “$\bullet$” denotes a qudit, two qudits connected by a line a maximally entangled state, and each group of qudits is surrounded by a dotted circle.
  64. 4.13  The two-round quantum circuit strategy $Q_{G,\psi,M}$ uses a multi-qudit register initially set to the computational basis state. The state $\lvert\psi,G\rangle$ is prepared by a single ${\left\lvert I\right\rvert}$-qudit gate $U_{\psi}$ and a two-qudit gate $U_{(i,v,w),(i,w,v)}$ for each $i\in I,\\{v,w\\}\in E$. The first round of inputs $x_{i,v}$ is used to control a non-destructive measurement gate $M_{i,v}$ with measurement settings given by (b), and the second round of inputs $x_{(i,v)}^{\prime}$ controls a destructive measurement gate $M_{i,v}^{\prime}$ also with measurement settings from (b).
  65. (a)
  66. (b)
  67. (c)
  68. 4.14 (a) A generic two-player Weyl measurement game. Alice and Bob share a two-qudit state $\psi$. Verifier randomly selects $q_{1},q_{2}\in\mathbb{Z}_{2}^{2}$ and an accepting condition $A\subset\mathbb{Z}_{d}^{2}$ according to a probability distribution $d(q_{1},q_{2},A)$. Alice and Bob measure the Weyl measurements $W(p_{1}),W(p_{2})$ respectively. Their success probability is the likelihood that $(q_{1},q_{2})\in A$. (b) Graph version of the game (a) played on a tree. randomly selects paths $(r,v_{11},\dots,v_{1k_{1}}),(r,v_{21},\dots,v_{2k_{2}})$ according to a path distribution $d_{\text{paths}}$ and an instance $(p_{1},p_{2},A)$ of (a) with probability $d(p_{1},p_{2},A)$. Verifier sends players $(1,r),(1,v_{11}),\dots,(1,v_{1k_{1}})$ They win if $(q_{1}^{\prime}+[p_{1},p_{1}^{\prime}],q_{2}^{\prime}+[p_{2},p_{2}^{\prime}])\in A$, where $p_{i}^{\prime}=p_{i1}^{\prime}+\dots+p_{i2}^{\prime}$.
  69. (a)
  70. (b)
  71. 4.15 (a) Circuit strategy $Q_{\psi,G}$, where $\psi$ is an $n$-qudit state and $G=(V,E,r)$ is a rooted graph. to entangle each qudit of $\psi$ with a qudit that is far away in the circuit and measures this qudit in the Weyl basis. (b) The effect of the Bell basis measurements is to teleport $\psi$ up to a random phase.
  72. (a)
  73. (b)
  74. (c)
  75. 4.16  Consider a simulation $t$ from a scenario with measurement sites $\\{1,2\\}$ to a scenario with measurement sites $\\{A,B,C,D\\}$ with the input dependencies in (a) and the output dependencies in (c) and a classical circuit $C$ with lightcones in (b).
  76. (a) $\text{In}_{1}(t)$
  77. (b) $\text{LC}_{C}^{\leftarrow}$
  78. (c) $\text{Out}_{1}(t)$
  79. (d) $\text{In}_{1}(t);\text{LC}_{C}^{\leftarrow};\text{Out}_{1}(t)$
  80. (a)
  81. (b)
  82. 4.18 Circuit version of Magic Square game played on a 2D grid.
  83. 4.19 Circuit version of the Magic Square game played on binary trees.
  84. 4.20 Magic square game played on a grid in two rounds.
  85. 4.21 Magic square game played on a tree in two rounds.

##  Chapter 1 Introduction

Quantum contextuality [Spe60, KS75], and in particular nonlocality [Bel64],
has been highly influential in shaping our understanding of the distinction
between quantum and classical physics. Contextuality is a feature of the
empirical data created by measurement experiments. This is a key difference
between contextuality and certain other features of quantum mechanics, for
example, entanglement and superposition, which are internal to the theory
itself. Because contextuality is an empirical phenomenon it says something
about any physical theory that is consistent with the predictions of quantum
mechanics. This is part of why contextuality was seen as so profound, and in
the era of quantum computing, it makes contextuality relevant for proving
quantum advantage. Because it is an empirical phenomenon it makes sense to
talk about classical models creating contextuality, but something like
entanglement and superposition doesn’t have any classical analogue.

No unconditional proof of quantum advantage is known for a general
computational model. This appears to be well beyond the limits of current
techniques. A recent breakthrough by Bravyi, Gosset, and König (BGK) gave the
first unconditional quantum advantage result for a restricted class of
circuits [BGK18]. A _shallow circuit_ is a family of circuits of bounded depth
and fan-in. BGK explicitly defines a shallow quantum family
$\\{Q_{n}\\}_{n\in\mathbb{N}}$ and a family of computational problems
$\\{\text{GHZ-2D(n)}\\}_{n\in\mathbb{N}}$ that are solved perfectly by the
quantum circuit, but not with high accuracy by any classical shallow circuit.

(a)

(b)

Figure 1.1: Circuit version of the the _GHZ game_. Inputs
$x_{1},x_{2},x_{3}\in\\{0,1\\}$ are selected uniformly at random. A Haramard
gate followed by two controlled not gates initialises the state $\lvert
GHZ\rangle:=\lvert 000\rangle+\lvert 111\rangle$. Each qubit is measured with
measurement settings $0\mapsto X,1\mapsto Y$. Outcomes
$y_{1},y_{2},y_{3}\in\\{0,1\\}$ are returned according to $1\mapsto
0,-1\mapsto 1$. The circuit wins if $x_{1}\oplus x_{2}\oplus x_{3}=1\oplus
y_{1}\oplus y_{2}\oplus y_{3}$.

It is well known that certain examples of contextuality can be recast as
cooperative games called _nonlocal games_. An example is Greenberger-Horn-
Zeilling (GHZ) game [GHSZ90, CHTW10]. It was observed by BGK that quantum
strategies for nonlocal games can be recast as circuits (Figure 1.1). The
computational problems $\text{GHZ-2D}(n)$ that BGK considered can be seen as
“distributed” versions of the GHZ game played on an $n\times n$ grid. This
raises the question if every nonlocal game can be turned into a family of
“distributed” games, that gives rise to an unconditional quantum advantage
result with shallow circuits. We show that this is the case. We describe this
result in more detail in Section 1.2

_Cohomology_ can be a powerful technique for detecting structure in data. It
could therefore be a useful tool for studying the empirical data associated
with contextuality. Two prominent cohomological approaches to contextuality is
the _Čech cohomology approach_ introduced by Abramsky, Mansfield, and Barbosa
[AMB12] and the _topological approach_ of Okay, Roberts, Bartlett, and
Raussendorf [ORBR17]. The Čech cohomology approach was further developed by,
for example, Abramsky et al. [ABM17], and by Caru [Car18, Car17, Car19]. The
insight that contextuality has a topological structure [Man20] has lead to a
range of results, for example, the homotopical approach of Okay and
Raussendorf [OR20], the connection with resource theory made by Okay, Tyhurst,
and Raussendorf [OTR18], the classifying space for contextuality [OS21], and
more recent work by Okay, Kharoof, and Ipek has uncovered the simplicial
structure [OKI22].

The Čech cohomology approach is based on the sheaf theoretic framework of
Abramsky and Brandenberger, which describes contextuality as a feature of
abstract families of empirical data, known as _empirical models_ [AB11]. The
Čech cohomology approach is very general. However, this generality comes at
the cost of completeness. The issue of completeness was a main point of
interest in the later work of Abramsky et al. and Caru. The topological
approach lacks some of the generality of the Čech approach. But the additional
structure that the approach requires gives the potential for a more refined
approach. In particular, we are interested in the possibility that the
structure used by the topological approach can help alleviate the issue of
incompleteness in the Čech cohomology approach.

In Section 1.1 we give an account of this structure used by the topological
approach within the sheaf theoretic framework. We show that Okay et al.’s
invariant can be generalised to any empirical model equipped with this
structure. We then show that, in fact, at this level of generality the two
approaches are equivalent with resepect to the question of completeness.

###  1.1 Comparing two obstruction for contextuality

(a) Mermin’s square

(b) Classifying space for Mermin’s square

Figure 1.2:  (a) The set of quantum measurement operators known as _Mermin’s
square_ , and (b) the associated classifying space of the topological
approach. In (a) Each row and column represents a context of commuting
operators. In (b) each operator labels a loop attached to a single point, and
each context a surface.

In the sheaf-theoretic framework contextuality is seen as the failure of a
locally compatible family of data to be given a globally consistent
description. In sheaf theory cohomology is a powerful tool for studying the
transition from local to global. It is therefore natural to consider the
application of cohomological methods to contextuality. Abramsky, Mansfield,
and Barbosa [AMB12] shows that in a range of examples contextuality can be
detected by the non-vanishing of a cohomological invariant based on _Čech
cohomology_.

The sheaf-theoretic framework distinguishes between possibilitstic and
probabilistic empirical models. A possibilistic model only keeps track of
which outcomes are possible, and not their particular probabilities. The Čech
cohomology invariant can be defined for any possibilistic empirical model.
However, it is generally not a complete invariant for contextuality. There are
so called “false negatives”, contextual empirical models where the
cohomological invariant vanishes. False negatives can occur because empirical
models lack the required algebraic structure to directly define the
obstruction. An empirical model is a presheaf of sets, while Čech cohomology
requires a presheaf of abelian groups. Abramsky et al. therefore considers the
Čech cohomology of the free abelian presheaf associated with an empirical
model.

The Čech cohomology invariant lead to further work on developing a complete
cohomological invariant for contextuality. It was shown by Abramsky, Barbosa,
Kishida, Lal, and Mansfield [ABK+15] that Čech cohomology is complete for a
large class of examples captured by generalised AvN arguments. Several other
invariants have been proposed, for example Roumen [Rou17] and Caru [Car18].

The Pauli operators and their qudit generalisations known as _Weyl operators_
have a special role in quantum computing. They are used in for example error
correcting codes and measurement based quantum computing [NC10]. It is well
known that the Pauli operators is a rich source of examples of contextuality,
this is also the case when $d>2$, see for example De Silva for examples
[dS17]. In dimension $d\geq 2$ the Weyl operators form a group $P_{n,d}$,
called the generalised $n$-qudit Pauli group. $P_{n,d}$ is closed under the
_phase_ action of $\mathbb{Z}_{d}$.

$\displaystyle\Omega:\mathbb{Z}_{d}\times P_{n,d}\to
P_{n,d}::(q,O)\mapsto\omega^{q}O$ (1.1)

where $\omega:=e^{2\pi i/d}$.

The _topological approach_ of Okay et al. [ORBR17] studies sets of Weyl
operators that are closed under certain operations. A set of operators
$\mathcal{O}\subset P_{n,d}$ is _closed_ if it satisfies the following
conditions:

  1. 1.

$\mathcal{O}$ contains the identity: $I\in\mathcal{O}$.

  2. 2.

$\mathcal{O}$ is closed under the phase action:
$\Omega(\mathbb{Z}_{d},\mathcal{O})\subset\mathcal{O}$.

  3. 3.

$\mathcal{O}$ is closed under commuting products: If
$O_{1},O_{2}\in\mathcal{O}$ and $O_{1}O_{2}=O_{2}O_{1}$ then
$O_{1}O_{2}\in\mathcal{O}$.

Okay et al. show that questions about contextuality for closed sets of Weyl
operators can be given a topological characterisation (Figure 1.2). The result
generalises an earlier characterisation for Pauli operators by Arkhipov
[Ark12].

The topological approach uses ideas from group cohomology. Recall that a group
extension of a group $K$ by a group $G$ is a short exact sequence of groups

${G}$${H}$${K}$$\scriptstyle{i}$$\scriptstyle{j}$ (1.2)

generalising the direct product of groups $G\times K$. A left splitting, right
splitting, or trivialisation are homomorphisms $l,r,h$ respectively making the
following diagram commute:

${G}$${H}$${K}$${G\times
K}$$\scriptstyle{\text{id}_{G}}$$\scriptstyle{i}$$\scriptstyle{\text{in}_{G}}$$\scriptstyle{h}$$\scriptstyle{j}$$\scriptstyle{l}$$\scriptstyle{\text{id}_{K}}$$\scriptstyle{r}$$\scriptstyle{\pi_{2}}$
(1.3)

Group cohomology is an elegant solution to the problem of classifying group
extensions for fixed $G$ and $K$ [Bro12].

A closed set of Weyl operators is not a group because it is not closed under
inverses and only under commuting products. However, Okay et al. shows that
for any such set one can define a classifying space similar to that of group
cohomology. Using this space they show that both state dependent and state
independent proofs of contextuality can be given a topological
characterisation. They show that state dependent and state independent
contextuality can be detected by the non-vanishing of a cohomology class.

##### Results

We first give a more abstract account of the algebraic structure used by Okay
et al.’s approach.

A _bundle over a commutative partial monoid_ is a generalisation of group
extensions to commutative partial monoids. A closed set of Weyl operators
comes with the structure of a bundle over a commutative partial monoid. Proofs
of contextuality for a closed set of Weyl operators correspond to extending
_local_ left splittings, defined on a sub-bundle, to _global_ left splittings
defined on the whole bundle. For closed sets of Weyl operators the problem of
extending a local left splitting globally can therefore be used as a test for
contextuality.

We prove a version of the splitting lemma for commutative partial monoids, and
we generalise group cohomology to partial commutative monoids. The splitting
lemma shows that for the problems of extending either a local left splitting,
right splitting, or trivialisation of a sub-bundle to the whole bundle are
equivalent. Furthermore, the problem of extending a local splitting to a
global splitting can be given a cohomological characterisation.

We then generalise the cohomological obstruction to any empirical model with
the structure of a bundle over a commutative partial monoid. For such an
empirical model the problem of extending a local splitting is a test for
contextuality. We can therefore use the cohomological obstruction for
extending a local splitting. There can be global splittings that don’t
correspond to valid outcome assignments. This raises the possibility of false
negatives.

We finally show that any false negative of the Čech approach induces a global
splitting that is not consistent with the model.

In summary, our results are:

  * •

Closed sets of Weyl operators come with the structure of a bundle over a
commutative partial monoid. Local (resp. global) outcome assignments induce
local (resp. global) left splittings of the bundle.

  * •

The topological obstruction can be generalised to a class of empirical models
equipped with the structure of a bundle over a commutative partial monoid.

  * •

The vanishing of the Čech cohomology obstruction implies the vanishing of the
generalised topological obstruction.

###  1.2 A general construction of quantum advantage with shallow circuits

Bravyi, Gosset, and König’s initial result was quickly improved in several
ways. For example, it was shown to be noise robust [BGKT20], and it was
extended to the more powerful classical circuit class AC0 [WKST19], of
circuits of bounded depth and unbounded fan-in AND, OR, and NOT gates. It has
also inspired several results for _interactive circuits_ , that is circuits
with more than one round of input and output [GS20].

(a)

(b)

Figure 1.3: An interactive circuit (a) is a circuit with several rounds of
inputs and outputs. The circuit is evaluated by composing with a classical
circuit as in (b).

AC0 is currently at the edge of unconditional circuit separations for
classical circuits. It, therefore, seems unlikely that the techniques used by
BGK can be extended to prove much stronger complexity theoretic results.
However, in the lack of stronger results, we should try to learn as much as
possible.

BGK’s result extends an earlier result by Barrett et al. [BCE+07]. An
interesting point is that after BGK’s result was published it was observed
that Barrett et al.’s construction solves an open problem about quantum
advantage in distributed computing [GNR19].

Nonlocality is a particular type of contextuality that arise in scenarios
where compatible measurements are performed at distinct locations called
measurement sites. We observe that nonlocality can be recast in terms of
circuits. A quantum realisation gives rise to a circuit (Figure 1.4(a)) that
prepares an entangled state and then implements local measurements. The
circuit takes a classical input $x_{i}$ and returns a classical output $y_{i}$
for each measurement site $i$. There is no path through the circuit
$Q_{\text{NC}}$ from input $x_{i}$ to a different output $y_{j}$, where $i\neq
j$. $Q_{\text{NC}}$ is _contextual_ if it is not equivalent to any classical
circuit with the same inputs and outputs, such that there is no path from an
input to a different output (Figure 1.4(b)).

A _nonlocal game_ is usually thought of as being played by a set of spatially
separated players against Verifier. We can equivalently think of a nonlocal
game as a computational problem where some quantum circuit of the form
$Q_{\text{NC}}$ achieves advantage over any classical circuit of the form
$C_{\text{NC}}$. In a nonlocal game $\Phi$ we randomly select an input and an
accepting condition $(x_{1},\dots,x_{n},A)$. We then evaluate the circuit on
inputs $x_{1},\dots,x_{n}$. The circuit wins if $(y_{1},\dots,y_{n})\in A$.
The _success probability_ is the likelihood of the accepting condition being
satisfied. A nonlocal game $\Phi$ is violated by a quantum strategy
$Q_{\text{NC}}$ if there exists a bound $\gamma$ such that

$\displaystyle p_{S}(C_{\text{NC}},\Phi)\leq\gamma<p_{S}(Q_{\text{NC}},\Phi)$
(1.4)

where $p_{S}$ denotes success probability and $C_{\text{NC}}$ is any classical
circuit of the same form.

(a)

(b)

Figure 1.4:  The quantum circuit (a) is _contextual_ if it is not equivalent
to any classical circuit (b) of the same shape, with the ability to sample an
arbitrary random seed $z_{1},\dots,z_{l}$.

Bravyi, Gosset, and König introduced a family of nonlocal games
$\\{\text{2D-GHZ}(n)\\}_{n\in\mathbb{N}}$ and a shallow quantum circuit
$\\{Q_{n}\\}_{n\in\mathbb{N}}$ (Figure 1.5). $\text{2D-GHZ}(n)$ is a version
of the GHZ-game played on an $n\times n$ grid. The circuit $Q_{n}$ prepares
$n^{2}$ qubits in the graph state of the $n\times n$ grid and applies
classically controlled Pauli $X,Y$ or $Z$ measurements to each qubit. It can
be shown that the graph state can be prepreaed by a single Hadamard gate on
each qudit, and four layers of controlled $Z$ gates. The circuit $\\{Q_{n}\\}$
is therefore shallow.

The inputs and accepting condition is chosen by Verifier in the nonlocal game
$\text{2D-GHZ}(n)$ is related to the inputs and accepting condition in the
GHZ-game. At the beginning of each round Verifier randomly selects inputs
$x_{A},x_{B},x_{C}$ for the GHZ-game, nodes
$v_{A},v_{B},v_{C}\in\text{Grid}(n,n)$, and paths $u_{AB}:v_{A}\to
v_{B},u_{BC}:v_{B}\to v_{C},u_{CA}:v_{C}\to v_{A}$. Players
$v_{A},v_{B},v_{C}$ are then given inputs $x_{A},x_{B},x_{C}$ and the
remaining players are given inputs that encode that paths
$u_{AB},u_{BC},u_{CA}$. An output for the players $y_{1},\dots y_{n^{2}}$ is
accepted if it satisfies a constraint

$\displaystyle x_{A}\oplus x_{B}\oplus x_{C}=1\oplus(y_{A}\oplus
k_{A}(y))\oplus(y_{B}\oplus k_{B}(y))\oplus(y_{C}\oplus k_{C}(y))$ (1.5)

where $y_{A},y_{B},y_{C}$ are the outputs of $v_{A},v_{B},v_{C}$ and
$k_{A}(y),k_{B}(y),k_{C}(y)$ are “correction factors” that only depend on the
outcomes of players along the paths close to each respective node.

BGK shows that for each $n\in\mathbb{N}$ the game $\text{2D-GHZ}(n)$ is solved
perfectly by the quantum circuit $Q_{n}$, and that it is not solved with high
accuracy by any classical shallow circuit $\\{C_{n}\\}_{n\in\mathbb{N}}$.

(a)

(b)

Figure 1.5: The 2D-GHZ game. The quantum circuit strategy (a) prepares $n^{2}$
qubits in the cluster state of the $n\times n$ grid. It takes inputs
$x_{1},\dots,x_{n^{2}}\in\\{1,2,3\\}$, performs controlled Pauli measurements
according to $1\mapsto X,2\mapsto Y,3\mapsto Z$, and returns outcomes
$y_{1},\dots,y_{n^{2}}\in\\{0,1\\}$ according to $1\mapsto 0,-1\mapsto 1$. The
input is randomly sampled as follows. First select nodes $A,B,C\in n\times n$
and paths $u_{AB},u_{BC},u_{CA}\subset n\times n$ in a “sufficiently uniform”
way. The circuit wins if the output $y$ satisfies $x_{A}\oplus x_{B}\oplus
x_{C}=1\oplus(y_{A}\oplus k_{A}(y))\oplus(y_{B}\oplus
k_{B}(y))\oplus(y_{C}\oplus k_{C}(y))$, where
$k_{A}(y),k_{B}(y),k_{C}(y)\in\\{0,1\\}$ depends only on the value of $y$
close to $A,B,C$ respectively.

######  Theorem [BGK18].

The shallow quantum circuit $\\{Q_{n}\\}_{n\in\mathbb{N}}$ solves the 2D-GHZ
game perfectly for all $n$. However, the 2D-GHZ game is not solved with high
accuracy by any classical shallow circuit $\\{C_{n}\\}_{n\in\mathbb{N}}$.

$\displaystyle p_{S}(Q_{n},\text{2D-GHZ}(n))$ $\displaystyle=1$ (1.6)
$\displaystyle p_{S}(C_{n},\text{2D-GHZ}(n))$ $\displaystyle\leq
3/4+\epsilon_{n}$ (1.7)

where $p_{S}$ denotes _success probability_ and $\epsilon_{n}\in O(1/n)$.

The key to BGK’s result is that single-qubit measurements on an entangled
state with only local entanglement can create entanglement between qubits that
are far away. Depth and fan-in constrain the nonlocal correlations that a
classical circuit can produce, but it also constrains the entangled states and
the measurements that a quantum circuit can use. Observe that in the circuit
$C_{\text{NC}}$ there can only be a path from input $x_{i}$ to output $y_{i}$,
while in a circuit of depth $D$ and maximal fan-in $K$ there can be a path
from at most $K^{D}$ inputs to any given output. As Verifier makes different
choices of players $v_{A},v_{B},v_{C}$ in the 2D-GHZ game this forces the
depth and fan-in of a classical circuit to be large. On the classical side it
can be shown that when the measurement along the paths $u_{AB},u_{BC},u_{CA}$
are made, the effect is to create an entangled $\lvert GHZ\rangle$ state at
qubits $v_{A},v_{B},v_{C}$, up to a local Pauli factors given by
$k_{A},k_{B},k_{C}$. Furthermore, these corrections can be made classically
post measurement.

In summary, the technique relies upon two key properties of the GHZ game: The
use of the GHZ state and Pauli measurements. The choice of state is important
because it can be realised by local measurements on a graph state in different
ways, and the measurements are important because it allows for the corrections
$k_{A},k_{B},k_{C}$ to be performed post-measurement.

##### Results

We first present a quantum protocol that uses teleportation to both distribute
an entangled state on a graph and perform measurements on the distributed
qudits (Figure 1.6). For any multi-qudit state $\psi$ with qudit $i$ and graph
$G$ with nodes $V$ we consider a scenario where a number of agents $I\times
V$, one for each qudit of $\psi$ and node of $G$, share entanglement. Each
qudit of $\psi$ is held by some node on the graph, and each pair of nodes
$(i,v),(i,w)$ such that $v,w$ are adjacent in $G$ share a two-qudit entangled
state. By choosing a path through the graph for each qudit we can then
distribute each qudit of $\psi$ to an arbitrary node on the graph, up to a
random single-qudit phase for each qudit. An important observation is that
this can be done in a constant number of rounds of quantum measurements.

(a)

(b)

Figure 1.6: Given a nonlocal game with players $I$ and state $\psi$, and a
graph $G$ with nodes $V$ we consider the scenario (a) consisting of players
$I\times V$, here each dotted circle indicate a player and $\bullet$ a qudit
in either a maximally entangled state or the state $\psi$. (b) By performing
local measurement on the qudits held by each player we can distribute each
qudit, up to a random factor on each qudit, to any player on the graph.

We then consider the family of protocols arising from a fixed state and a
family of graphs. Using this construction we show that any nonlocal game gives
rise to a family of distributed games. We then show that for certain families
of graphs distributed games gives rise to unconditional quantum advantage
results with shallow circuits.

We present two versions of this construction. The first is completely general,
but the distributed games have two rounds (Figure 1.9). It is a result about
interactive circuits (Figure 1.3). The second result is less general, but for
circuits in the usual sense having only a single round of inputs and outputs
(Figure 1.8). In the second result we consider nonlocal games with quantum
strategies given by measurements of single-qudit Weyl operators. Note that the
states are still completely general.

The outline of the two results is as follows. Suppose that
$(Q_{\text{NC}},\Phi)$ is any nonlocal game with classical bound $\gamma$. For
any family of graphs $\\{G_{n}\\}_{n\in\mathbb{N}}$ we define a family of two-
round cooperative games $\\{\Phi_{n}\\}_{n}$ and two-round interactive quantum
circuits $\\{Q_{n}\\}_{n}$, such that for each $n\in\mathbb{N}$ the quantum
circuit $Q_{n}$ violates the bound $\gamma$. For certain families of graphs we
show that the quantum circuit is shallow and that a classical shallow circuit
$\\{C_{n}\\}_{n}$ violates the bound $\gamma$ only up to a small factor
$\epsilon_{n}$. Where $\text{lim}_{n\to\infty}\epsilon_{n}=0$. The rate of
convergence is a property of the graphs.

######  Theorem I (Informal).

For any nonlocal game $\Phi$ and quantum strategy $Q$ we define a family of
two-round interactive games $\\{\Phi_{n}\\}_{n\in\mathbb{N}}$ and a shallow
two-round quantum circuit $\\{Q_{n}\\}_{n\in\mathbb{N}}$ such that for any
classical two-round interactive shallow circuit $\\{C_{n}\\}_{n\in\mathbb{N}}$

$\displaystyle p_{S}(Q_{n},\Phi_{n})$ $\displaystyle=p_{S}(Q,\Phi)$ (1.8)
$\displaystyle p_{S}(C_{n},\Phi_{n})$ $\displaystyle\leq\gamma+\epsilon_{n}$
(1.9)

for some small $\epsilon_{n}$.

Next, we show that if the quantum strategy uses only single-qudit Weyl
measurements (Figure 1.7)

Figure 1.7:  A _Weyl measurement strategy_ is a special quantum strategy using
measurements in the basis of Weyl operators. For dimension $d\geq 2$ and
$n$-qudit state $\psi$ the Weyl measurement strategy takes inputs
$p_{1},\dots,p_{n}\in\mathbb{Z}_{d}^{2}$ and return outcomes
$q_{1},\dots,q_{n}\in\mathbb{Z}_{d}$ of performing the single-qudit Weyl
measurement $W(p_{i})$ on qudit $i$.

then the number of input-output rounds can be reduced to one.

######  Theorem II (Informal).

For any nonlocal game $\Phi$ and Weyl measurement strategy $Q$ we define a
family of nonlocal games $\\{\Phi_{n}\\}_{n\in\mathbb{N}}$ and a shallow
quantum circuit $\\{Q_{n}\\}_{n\in\mathbb{N}}$ such that for any classical
shallow circuit $\\{C_{n}\\}_{n\in\mathbb{N}}$

$\displaystyle p_{S}(Q_{n},\Phi_{n})$ $\displaystyle=p_{S}(Q,\Phi)$ (1.10)
$\displaystyle p_{S}(C_{n},\Phi_{n})$ $\displaystyle\leq\gamma+\epsilon_{n}$
(1.11)

for some small $\epsilon_{n}$.

where $\epsilon_{n}$ is a different bound.

(a)

(b)

Figure 1.8: Let $\psi$ be an $I$-qudit state and $G=(V,E,r)$ a rooted graph.
The quantum circuit strategy (a) prepares a single instance of $\psi$ and a
maximally entangled pair of qudits $\lvert\phi\rangle:=\frac{\lvert
00\rangle+\lvert 11\rangle}{\sqrt{2}}$ for each $i\in I$ and edge $e\in E$.
The circuit has an input for each $(i,v)\in I\times V$ which controls a
measurement on a subset of qudits. This subset includes one of the two qudits
of the state $\lvert\phi\rangle$ associated with each edge adjacent to $v$,
and when $v=r$ also includes qudit $i$ of $\psi$. The possible measurement
settings are either a Weyl operator measurement on a single qudit, or a Bell
basis measurement on a pair of qudits. (b) In the nonlocal game Verifier
selects inputs $p_{1},\dots,p_{n}$ and an accepting condition $A$ according to
the nonlocal game $\Phi$. Verifier then randomly selects a rooted path
$(v_{i1},\dots,v_{il_{i}})$ for each $i\in I$ and sends each $(i,v_{il_{i}})$
the input corresponding to a Bell basis measurement, and $(i,v_{il_{i}})$ the
Weyl measurement setting $p_{i}$. Verifier accepts the outputs
$p_{i1}^{\prime},\dots,p_{i(l_{i}-1)}^{\prime},q_{i}$ if
$(q_{1}-[p_{1},p_{1}^{\prime}],\dots,q_{n}-[p_{n},p_{n}^{\prime}])\in A$,
where $p_{i}^{\prime}:=p_{i1}^{\prime}+\dots+p_{il_{i}}^{\prime}$.

(a)

(b)

(c)

Figure 1.9:  Let $\psi$ be an $I$-qudit state and $G=(V,E,r)$ a rooted graph.
The quantum circuit strategy (a) prepares a single instance of $\psi$ and a
maximally entangled pair of qudits $\lvert\phi\rangle:=\frac{\lvert
00\rangle+\lvert 11\rangle}{\sqrt{2}}$ for each $i\in I$ and edge $e\in E$.
The circuit first takes an input for $(i,v)\in I\times V$ which controls a
non-destructive measurement on a subset of qudits, it then takes another round
of inputs for each $(i,v)\in I\times V$ which control destructive measurements
on each subset of qudits. For each $(i,v)$ the subset of qudits which is
measured includes one of the two maximally entangled qudits associated with
each edge adjacent to $v$, and when $v=r$ also includes qudit $i$ of $\psi$.
In the first round the measurement settings are either nothing or a Bell basis
measurement on a pair of qudits. In the second round the possible measurements
are either nothing or a conjugated measurement $W(p)MW(p)^{\dagger}$ on a
single qudit, where $M$ is one of the measurement settings. (b) In the
nonlocal game Verifier selects inputs $x_{1},\dots,x_{n}$ and an accepting
condition $A$ according to the nonlocal game $\Phi$. Verifier then randomly
selects a rooted path $(v_{i1},\dots,v_{il_{i}})$ for each $i\in I$ and first
sends each $(i,v_{il_{i}})$ the input corresponding to a Bell basis
measurement. If the outcomes of this are $p_{i1},\dots,p_{i(l_{i}-1)}$
Verifier sends $(i,v_{il_{i}})$ the input for the conjugated measurement
$W(p_{i})M_{x_{i}}W(p_{i})^{\dagger}$, where
$p_{i}^{\prime}:=p_{i1}^{\prime}+\dots+p_{il_{i}}^{\prime}$. Verifier accepts
the output $y_{1},\dots,y_{n}$ if $(y_{1},\dots,y_{n})\in A$.

###  1.3 Structure of this text

In Chapter 2 we present some technical background material on the sheaf-
theoretic framework. We then present the results on cohomology and circuits in
Chapters 3 and 4 respectively, and we conclude with some remarks in Chapter 5.

##  Chapter 2 The sheaf-theoretic framework

An early influential paper on contextually is John Bell’s famous paper on the
Einstein-Podolsky-Rosen (EPR) paradox [Bel64]. The “paradox” of EPR
purportedly showed that quantum mechanics should not be seen as a complete
description of physical reality [EPR35]. Bell’s insight could be understood to
be that the incompleteness highlighted by EPR is not simply a feature of
quantum mechanics, but of any physical theory that is consistent with the
empirical predictions of quantum mechanics. Other influential papers by Kochen
and Specker [KS75], Mermin [Mer90], and Greenberger-Horne-Zeillinger [GHSZ90],
to mention a few.

This early work on contextuality focused on particular examples. Our interest
in contextuality stems from the wish to prove general connections between
contextuality and quantum advantage. It is therefore necessary to work with a
more abstract definition of contextuality. Our approach uses the _sheaf
theoretic_ framework of Abramsky and Brandenberger [AB11]. The sheaf theoretic
approach is among several general definitions of contextuality. For example,
Robert Spekken’s ontological models framework [Spe05], Cabello, Severini, and
Winter’s graph theoretic approach [CSW14], and the _contextuality by default_
approach of Dzhafarov, Kujala, and Cervantes [DKC15]. Further work on the
contextuality by default approach was carried out by Dzhafarov, Kujala, and
Cervantes [DKC15] and connections with psychology were investigated by
Dzhafarov and Kujala [DK16], to mention some. A graph theoretic approach that
refines that of Cabelo, Severini and Winter’s is the approach of Acín, Fritz,
Leverrier, and Sainz [AFLS15].

The sheaf theoretic framework has proved useful for linking contextuality to
constraint satisfaction and database theory [AH12, Abr13].

In this chapter, we give an introduction to contextuality using the sheaf-
theoretic framework, and we introduce several technical notions that will be
used in the following chapters.

##### Overview

The two basic concepts in the sheaf theoretic framework are _measurement
scenarios_ and _empirical models_. We introduce measurement scenarios in
Section 2.1 and empirical models in Section 2.2. In Section 2.3 we define
_simulations_ , a class of structure preserving transformations between
empirical models. In Section 2.4.2 we introduce the Čech cohomology
obstruction for contextuality. In Section 2.5 we define non-local games. In
Section 2.6 we introduce the contextual fraction, and give an example of a
resource inequality.

###  2.1 Measurement scenarios

Figure 2.1: Let $(X,\mathcal{M},O)$ be a measurement scenario. In an
experimental run with $k$ rounds a sequence of
contexts$\\{x_{11},\dots,x_{1n_{1}}\\},\dots,\\{x_{k1},\dots,x_{kn_{k}}\\}\in\mathcal{M}$
satisfying Eq. (2.1) are performed, giving outcomes
$\\{o_{11},\dots,o_{1n_{i}}\\},\\{o_{k1},\dots,o_{kn_{k}}\\}$.

In the sheaf theoretic approach of Abramsky and Brandenberger [AB11] a
measurement scenario represents the abstract type of an experiment. In this
type of experiment some, but not necessarily all, combinations of measurements
can be performed together, either sequentially or in parallel (Figure 2.1). We
will first give the general definition and then consider two types of
scenarios: quantum scenarios (Section 2.1.1) and multipartite scenarios
(Section 2.1.2).

A measurement scenario is specified by a set of measurements, a family of
subsets called the _measurement cover_ specifying which measurements are
compatible, and a set of outcomes for each measurement.

######  Definition 2.1.1.

A _measurement scenario_ is a tuple $(X,\mathcal{M},\\{O_{x}\\}_{x\in X})$
where

  * •

$X$ is a set of _measurements_.

  * •

$\mathcal{M}\subset\mathcal{P}(X)$ is a family of subsets of measurements,
called the _measurement cover_ , such that:

    1. 1.

$\mathcal{M}$ covers $X$: $\bigcup_{C\in\mathcal{M}}C=X$.

    2. 2.

$\mathcal{M}$ is downwards closed: If $C\in\mathcal{M}$ and $C^{\prime}\subset
C$ then $C^{\prime}\in\mathcal{M}$.

  * •

$O_{x}$ is a set of _outcomes_.

The elements of the measurement cover are called _contexts_.

Let $(X,\mathcal{M},O)$ be a measurement scenario. Each context
$C\in\mathcal{M}$ represents a set of compatible measurements that can be
performed either sequentially in any order, or in parallel. We make the
restriction that a measurement can only be performed once. A sequence of
contexts $C_{1},\dots,C_{n}\in\mathcal{M}$ is valid if it has no repeated
measurements and its union is a context:

$\displaystyle\bigcup_{i}C_{i}\in\mathcal{M}\quad\text{ and }\quad C_{i}\cap
C_{j}=\emptyset\quad\text{ for all }i\neq j$ (2.1)

A joint outcome $s\in\prod_{x\in X^{\prime}}O_{x}$ to a subset of measurements
is sometimes called a _local section_. This assignment is called the _event
sheaf_.

######  Definition 2.1.2.

Let $S=(X,\mathcal{M},O)$ be a measurement scenario. The _event sheaf_ ,
denoted by $\mathcal{E}_{S}$, assigns to each $U\subset X$ the set of _local
sections_ $\mathcal{E}(U):=\prod_{x\in U}O_{x}$, and for each $V\subset U$
restrictions $s\in\mathcal{E}(U)$ to a local section $s\rvert_{V}$ by the
usual functional restriction.

Recall that a _presheaf_ on a topological space $X$ is a contravariant
function $F:X^{\text{op}}\to\text{Set}$. Here $X$ is seen as a category with
objects given by the open sets, and morphisms inclusion. For each inclusion
$U\subset V$ the map $F(U\subset V):F(V)\to F(U)$ is called the restriction
map. A _sheaf_ is a presheaf satisfying the following the _sheaf condition_. A
compatible family for the open cover $\mathcal{U}$ is a family$\\{f_{U}\in
F(U)\\}_{U\in\mathcal{U}}$ whose restrictions on overlaps are compatible:

$\displaystyle F(U\cap V\subset U)(f_{U})=F(U\cap V\subset V)(f_{V})$ (2.2)

for all $U,V\in\mathcal{U}$. The _sheaf condition_ states that any compatible
family arises as the family of restrictions

$\displaystyle f_{U}=F(U\subset X)(f)$ (2.3)

of some _global section_ $f\in F(U)$.

####  2.1.1 Quantum scenarios

The first example of a measurement scenario that we work with arise from sets
of _projective measurements_. A projective measurement is a family of
projectors $M=\\{M_{o}\\}_{o\in O}$, where $O$ labels the outcomes, such that
$\sum_{o\in O}M_{o}=I$. Two measurements $M=\\{M_{o}\\}_{o\in O}$, and
$N=\\{N_{p}\\}_{p\in P}$ commute if their projective elements commute:

$\displaystyle M_{o}N_{p}=N_{p}M_{o}\quad\text{for all $o\in O$, $p\in P$}$
(2.4)

A set of pairwise commuting projective measurements is said to be compatible.

######  Example 2.1.1.

Let $\boldsymbol{M}$ be a set of projective measurements.
$(\boldsymbol{M},\mathcal{M},O)$ is the measurement scenario with measurement
cover the maximal subsets of pairwise commuting measurements, and outcomes $O$
given by the outcomes of each measurement.

The _$n$ -Pauli group_, denoted by $P_{n}$, is the group of $n$-qubit unitary
operators generated by the single-qubit Pauli operators

$\displaystyle I:=\begin{bmatrix}1&0\\\ 0&1\\\
\end{bmatrix}\quad\sigma_{{x}}:=\begin{bmatrix}0&1\\\ 1&0\\\
\end{bmatrix}\quad\sigma_{{y}}:=\begin{bmatrix}0&-i\\\ i&0\\\
\end{bmatrix}\quad\sigma_{{z}}:=\begin{bmatrix}1&0\\\ 0&-1\\\ \end{bmatrix}$

We denote the application of the Pauli operator
$\sigma_{{p}}=\sigma_{{x}},\sigma_{{y}},\sigma_{{z}}$ to qubit $i$ as

$\displaystyle\sigma_{{p}}^{i}=I\otimes\dots\otimes\sigma_{{p}}\otimes\dots\otimes
I$ (2.5)

recall that the single-qubit Pauli operators satisfy the commutativity
relation

$\displaystyle\sigma_{{x}}\sigma_{{y}}=-\sigma_{{y}}\sigma_{{x}}$ (2.6)
$\displaystyle\sigma_{{x}}\sigma_{{z}}=-\sigma_{{z}}\sigma_{{x}}$ (2.7)
$\displaystyle\sigma_{{y}}\sigma_{{z}}=-\sigma_{{z}}\sigma_{{y}}$ (2.8)

It therefore follows that two $n$-qubit Pauli operators commute if and only if
they anti-commute at an even number of qubits. An $n$-qubit Pauli operator
specifies a projective measurement with outcomes $\\{0,1\\}$. Two $n$-qubit
Pauli operators commute, and therefore their projective measurements there
also commute, if and only if they anti-commute at an even number of qubits.

######  Example 2.1.2.

A quantum scenario $(\mathcal{O},\mathcal{M},\mathbb{Z})$ is given by the set
of two-qubit Pauli operators

(2.15)

where each row and column make up a maximal context.

####  2.1.2 Multipartite scenarios

The second type of measurement scenario that we consider represents scenarios
where measurements can be performed independently at a number of locations
(Figure 2.2). This is sometimes called a _non-locality scenario_. We prefer
the terminology “multipartite” because it avoids the implication that the
locations are necessarily spatially separated.

A multipartite scenario is specified by a set of _measurement sites_ $I$, for
each measurement site $i$ a set of _measurement settings_ $X_{i}$, and for
each measurement setting $x\in X_{i}$ a set of _measurement outcomes_
$Y_{i,x}$. Two measurements are compatible if and only if they belong to a
different measurement site. First a comment about notation. Recall that
$\coprod_{i\in I}X_{i}$ is defined as

$\displaystyle\coprod_{i\in I}X_{i}:=\\{(i,x)\mid i\in I,x\in X_{i}\\}$ (2.16)

######  Definition 2.1.3.

A _multipartite scenario_ $(I,X,Y)$ is the measurement scenario
$(\coprod_{i\in I}X_{i},\mathcal{M},Y)$, where the measurement cover
$\mathcal{M}$ is defined by

$\displaystyle\mathcal{M}:=\\{C\subset\coprod_{i\in
I}X_{i}\mid(i,x),(i,x^{\prime})\in C\Rightarrow x=x^{\prime}\\}$ (2.17)

and $Y_{i,x}$ is the set of outcomes for each $(i,x)$.

Figure 2.2:  Consider a multipartite scenario with two measurement sites with
measurement settings $\\{a,a^{\prime}\\}$, $\\{b,b^{\prime}\\}$ respectively.
The maximal contexts are then
$\\{a,b\\},\\{a,b^{\prime}\\},\\{b^{\prime},a^{\prime}\\},\\{b,a^{\prime}\\}$.

###  2.2 Empirical models

While a measurement scenario describes an experimental setup Abramsky and
Brandenberger introduced the concept of an empirical model to capture the
empirical data generated in an experiment. They introduced two types of
empirical models, capturing different types of data. In Section 2.2.1 we
define _probabilistic_ empirical models, and _probabilistic contextuality_. In
Section 2.2.2 we define _possibilistic_ empirical models, and _possibilistic
contextuality_.

####  2.2.1 Probabilistic empirical models

For any set $X$ write $\mathcal{D}(X)$ for the set of probability
distributions over $X$. It is sometimes convenient to write a probability
distribution $d\in\mathcal{D}(X)$ as a _formal sum_ $d=\sum_{x\in X}d(x)\cdot
x$ over the elements of $X$. Note that $\mathcal{D}$ is a functor with action
on functions $f:X\to Y$ given by the _pushforward_

$\displaystyle f_{*}:\mathcal{D}(X)\to\mathcal{D}(Y)$
$\displaystyle::\sum_{x\in X}d(x)\cdot x\mapsto\sum_{x\in X}d(x)\cdot f(x)$
(2.18)

Let $S=(X,\mathcal{M},O)$ be a measurement scenario. Consider the assignment
$U\mapsto\mathcal{D}(\mathcal{E}_{S}(U)$ of the set of probability
distributions over the local sections at a set of measurements $U\subset X$.
$\mathcal{D}\circ\mathcal{E}_{S}:X^{\text{op}}\to\text{Set}$ is a presheaf,
but not in general a sheaf. For each $U\subset V$ and
$d\in\mathcal{D}(\mathcal{E}_{S}(V)$ the restriction map is the marginal
distribution $d\rvert_{U}\in\mathcal{D}(\mathcal{E}_{S}(U))$

$\displaystyle d\rvert_{U}:=\sum_{s\in\mathcal{E}_{S}(V)}d_{s}\cdot
s\rvert_{U}$ (2.19)

where $s\rvert_{U}$ is the restriction of the section $s$ to $U$.

######  Definition 2.2.1.

Let $(X,\mathcal{M},O)$ be a measurement scenario. A probabilistic empirical
model is a family of probability distributions
$e=\\{e_{C}\in\mathcal{D}(\mathcal{E}(C))\\}_{C\in\mathcal{M}}$ such that

$C\subset C^{\prime}\Rightarrow e_{C^{\prime}}\rvert_{C}=e_{C}$ (2.20)

An experimental run for a scenario $S=(X,\mathcal{M},O)$ is a sequence
$(C_{1},s_{1}),\dots,(C_{n},s_{n})$ where $C_{1},\dots,C_{n}\in\mathcal{M}$ is
a valid sequence of contexts and $s_{1},\dots,s_{n}$ are local sections for
the respective contexts. If $e$ is an empirical model then the probability of
the run is

$\displaystyle e(C_{1},s_{1},\dots,C_{n},s_{n}):=e(C_{1}\cup\dots\cup
C_{n})(s_{1}\cup\dots\cup s_{n})$ (2.21)

Local compatibility is motivated by the “no-disturbance” principle in quantum
mechanics. For multipartite scenarios, this is more commonly called “no-
signalling”. Let $\boldsymbol{M}$ be a set of projective measurements and
$\psi$ a state. The measurement postulate of quantum mechanics defines an
empirical model $e$ for the scenario $(\boldsymbol{M},\mathcal{M},O)$ given by

$\displaystyle e(C)(s):=\lVert\big{[}\prod_{M\in
C}M_{s(M)}\big{]}\psi\rVert^{2}$ (2.22)

The no-disturbance principle is the observation that the probability
distribution given by a context $C\subset\boldsymbol{M}$ is independent of
which other compatible measurements it is performed in. Marginalising from the
maximal contexts, therefore, gives the correct behavior for quantum
measurements.

For a multipartite scenario, the measurement settings are not themselves
quantum measurements. We, therefore, have to choose some interpretations of
them as quantum measurements. To ensure that the measurements are compatible
we do this on independent subsystems.

######  Definition 2.2.2.

Let $S=(I,X,Y)$ be a multipartite scenario. A _quantum realised_ empirical
model $e_{\psi,\pi}$ is given by an $I$-qudit state $\psi$, and a single-qudit
measurement $\pi(i,x)$ for each $i\in I$, $x\in X_{i}$ with outcomes
$Y_{i,x}$. $e_{\psi,\pi}$ is defined by

$e(C)=\sum_{s\in\mathcal{E}_{S}(C)}\lVert\big{[}\bigotimes_{(i,x)\in
C}\pi(i,x)_{s(i,x)}\big{]}\psi\rVert^{2}\cdot s$ (2.23)

The following example of an abstract empirical model is taken from [AB11].

######  Example 2.2.1.

An empirical model for the two-partite scenario with measurement sites $A,B$
and measurement settings $\\{a,a^{\prime}\\},\\{b,b^{\prime}\\}$ respectively
and outcome $\\{0,1\\}$ is given by the table

A | B | (0,0) | (0,1) | (1, 0) | (1,1)
---|---|---|---|---|---
a | b | 1/2 | 0 | 0 | 1/2
a | b’ | 3/8 | 1/8 | 1/8 | 3/8
a’ | b | 3/8 | 1/8 | 1/8 | 3/8
a’ | b’ | 1/8 | 3/8 | 3/8 | 1/8
(2.24)

The entries of the table give a probability to the outcomes of each maximal
context. If the measurement $a$ is performed on its own, then the probability
of $0$ is $1/2$, which can be seen by marginalising from either context
$(a,b)$ or $(a,b^{\prime})$.

$\displaystyle P(a=0)$ $\displaystyle=P((a,b)=(0,1),(0,0))=1/2+0$ (2.25)
$\displaystyle P(a=0)$
$\displaystyle=P((a,b^{\prime})=(0,1),(0,0))=3/8+1/8=1/2$ (2.26)

##### Contextuality

Although $\mathcal{D}\circ\mathcal{E}_{S}:X^{\text{op}}\to\text{Set}$ is a
presheaf, it is not necessarily a sheaf. There can be compatible families that
do not arise as a family of restrictions from a global section. Probabilistic
contextuality is defined as the failure of an empirical model to be explained
as a family of restrictions.

######  Definition 2.2.3.

Let $S=(X,\mathcal{M},O)$ be a measurement scenario and $e$ an empirical
model. $e$ is _contextual_ if there is no
$d\in\mathcal{D}(\mathcal{E}_{S}(X))$ such that for all maximal contexts
$C\in\mathcal{M}_{*}$

$e_{C}=d\rvert_{C}$ (2.27)

An example of contextuality can therefore be thought of as a family of locally
compatible data that cannot be “glued together” to a consistent global picture
of the data. We now give some examples.

######  Example 2.2.2.

Consider the multipartite scenario $(\\{A,B\\},\\{0,1\\},\\{0,1\\})$ with
measurement sites $A,B$ and two measurement settings each with two outcomes.
The empirical model given by the following probability table is contextual.

A | B | (0,0) | (0,1) | (1, 0) | (1,1)
---|---|---|---|---|---
a | b | 1/2 | 0 | 0 | 1/2
a | b’ | 1/2 | 0 | 0 | 1/2
a’ | b | 1/2 | 0 | 0 | 1/2
a’ | b’ | 0 | 1/2 | 1/2 | 0
(2.28)

###### Proof.

Suppose that there exists a probability distribution $d$ over the global
sections whose restriction to each maximal context gives the table. From the
probability table we have that each of the following events occur with
certainty:

$\displaystyle d(a=b)=1$ (2.29) $\displaystyle d(a=b^{\prime})=1$ (2.30)
$\displaystyle d(a^{\prime}=b)=1$ (2.31) $\displaystyle
d(a^{\prime}=b^{\prime})=0$ (2.32)

However, this is not possible because the constraints are mutually exclusive.
∎

######  Example 2.2.1 (The GHZ model [GHSZ90]).

Consider the multipartite scenario
$(\\{0,1,2\\},\\{\mathbb{Z}_{2}\\},\\{\mathbb{Z}_{2}\\})$ with three
measurement sites, two measurement settings at each measurement site, and two
outcomes for each measurement setting. Let
$\lvert\text{GHZ}\rangle:=\frac{1}{\sqrt{2}}(\lvert 000\rangle+\lvert
111\rangle$ and $\pi$ the mapping of measurement setting $0$ to a Pauli
$X$-basis measurement, and $1$ to a Pauli $Y$-basis measurement

$\pi::=(i,0)\mapsto X,(i,1)\mapsto Y$ (2.34)

The quantum realised empirical model $e_{\text{GHZ}}$ given by measurements
$\pi$ on the state $\lvert GHZ\rangle$ is contextual.

###### Proof.

Write $X$ for the total set of measurements, suppose that there exists a
probability distribution $d$ on the set of global sections
$g:X\to\mathbb{Z}_{2}$ that gives the empirical model $e_{\text{GHZ}}$.
$\lvert\text{GHZ}\rangle$ is a $+1$-eigenstate of
$\sigma_{{x}}^{1}\sigma_{{x}}^{2}\sigma_{{x}}^{3}$ while it is a
$-1$-eigenstate of $\sigma_{{x}}^{1}\sigma_{{y}}^{2}\sigma_{{y}}^{3}$,
$\sigma_{{y}}^{1}\sigma_{{x}}^{2}\sigma_{{y}}^{3}$, and
$\sigma_{{y}}^{1}\sigma_{{y}}^{2}\sigma_{{x}}^{3}$. With the identification
$\\{-1,1\\}\cong\mathbb{Z}_{2}$ this means that any global section
$g:X\to\mathbb{Z}_{2}$ satisfies

$\displaystyle\sigma_{{x}}^{1}\oplus\sigma_{{x}}^{2}\oplus\sigma_{{x}}^{3}$
$\displaystyle=0$ (2.35)
$\displaystyle\sigma_{{x}}^{1}\oplus\sigma_{{y}}^{2}\oplus\sigma_{{y}}^{3}$
$\displaystyle=1$ (2.36)
$\displaystyle\sigma_{{y}}^{1}\oplus\sigma_{{x}}^{2}\oplus\sigma_{{y}}^{3}$
$\displaystyle=1$ (2.37)
$\displaystyle\sigma_{{y}}^{1}\oplus\sigma_{{y}}^{2}\oplus\sigma_{{x}}^{3}$
$\displaystyle=1$ (2.38)

However, summing them together results in $0=1$. There is therefore no global
section $g$, and in particular no distribution $d$. ∎

Another famous example is the so-called CHSH model [CHSH69]. This illustrates
an important technique for proving contextuality. It uses an argument
involving an inequality satisfied by all non-contextual models.

######  Example 2.2.3 (The CHSH model).

Consider the multipartite scenario
$(\mathbb{Z}_{2},\\{\mathbb{Z}_{2}\\},\\{\mathbb{Z}_{2}\\})$ with two
measurement sites, two measurement settings at each measurement site, and two
outcomes for each measurement setting. The CHSH model, $e_{\text{CHSH}}$, is
the empirical model realised by the state $\Phi:=\frac{1}{\sqrt{2}}(\lvert
00\rangle+\lvert 11\rangle)$ and

$\pi::=\begin{cases}(0,0)\mapsto Z,\\\ (0,1)\mapsto X,\\\ (1,0)\mapsto A,\\\
(1,1)\mapsto B\end{cases}$ (2.39)

where

$\displaystyle\lvert a_{0}\rangle$ $\displaystyle:=\cos{\frac{\pi}{8}}\lvert
0\rangle+\sin{\frac{\pi}{8}}\lvert 1\rangle,\quad\lvert
a_{1}\rangle:=-\sin{\frac{\pi}{8}}\lvert 0\rangle+\cos{\frac{\pi}{8}}\lvert
1\rangle$ (2.40) $\displaystyle\lvert b_{0}\rangle$
$\displaystyle:=\cos{\frac{\pi}{8}}\lvert 0\rangle-\sin{\frac{\pi}{8}}\lvert
1\rangle,\quad\lvert b_{1}\rangle:=\sin{\frac{\pi}{8}}\lvert
0\rangle+\cos{\frac{\pi}{8}}\lvert 1\rangle$ (2.41)

######  Lemma 2.2.1.

The CHSH model is contextual. For any non-contextual model the sum
$\sum_{x,y}x_{1}\oplus x_{2}=y_{1}\land y_{2}\leq 0.75$. For $e_{\text{CHSH}}$
the sum is $\cos^{2}{\frac{\pi}{8}}\approx 0.85>0.75$.

####  2.2.2 Possibilistic empirical models

(a) Hardy’s model

(b) PR-box

Figure 2.3: Bundle diagrams of Hardy’s model and the PR-box. The points above
each measurement represents the two outcomes $0,1$ and the line segments the
possible joint value assigmnets allowed by each model. A global section
corresponds to a cycle visiting each measurement exactly once, for example the
section $(a,a^{\prime},b,b^{\prime})=(1,1,0,0)$ in (a). However, (a) is
logically contextual at the local section $(a,b)=(0,0)$ as can be seen. It can
be seen that (b) is strongly contextual because no cycle visiting each
measurement once is possible. .

Let $d\in\mathcal{D}(X)$ be a probability distribution over a set $X$. The
_support_ of $d$ is the subset ${\left\lvert d\right\rvert}:=\\{x\in X\mid
d(x)>0\\}$.

Observe that examples 2.2.2 and 2.2.1 we do not refer to particular
probabilities. The proofs show that there is no global section
$s\in\mathcal{E}_{S}(X)$ that is consistent with the _support_ of the models.
Given any probabilistic empirical model $e$ we can “forget” about the
probabilities and only consider the family of supports $\\{{\left\lvert
e_{C}\right\rvert}\subset\mathcal{E}_{S}(C)\\}_{C\in\mathcal{M}_{*}}$. This is
an example of a _probabilistic_ empirical model. Probabilistic empirical
models can be seen as presheafs in the following way.

######  Definition 2.2.4.

A _possibilistic empirical model_ $\mathcal{S}:(X,\mathcal{M},O)$ is a
subpresheaf of $\mathcal{E}_{S}$ such that

  1. 1.

Every compatible family for the measurement cover $\mathcal{M}$ induces a
global section.

  2. 2.

$\mathcal{S}$ is _flasque beneath the cover_ : If $C,C^{\prime}\in\mathcal{M}$
and $C\subset C^{\prime}$ then every $s\in\mathcal{S}(C)$ is the restriction
of some $s^{\prime}\in\mathcal{S}(C^{\prime})$.

Note that although any probabilistic empirical model gives rise to a
probabilistic empirical model, the converse is not necessarily true. Not all
possibilistic empirical models is the support of a probabilistic model.

Possibilistic empirical models can be represented as _boolean tables_. An
example is given by the _Hardy model_

A | B | (0,0) | (0,1) | (1, 0) | (1,1)
---|---|---|---|---|---
a | b | 1 | 1 | 1 | 1
a | b’ | 0 | 1 | 1 | 1
a’ | b | 0 | 1 | 1 | 1
a’ | b’ | 1 | 1 | 1 | 0
(2.42)

and the _Popescu-Rohrlich (PR) box_.

A | B | (0,0) | (0,1) | (1, 0) | (1,1)
---|---|---|---|---|---
a | b | 1 | 0 | 0 | 1
a | b’ | 1 | 0 | 0 | 1
a’ | b | 1 | 0 | 0 | 1
a’ | b’ | 0 | 1 | 1 | 0
(2.43)

In the possibilistic setting there are two natural forms of contextuality that
we can consider. Logical and strong.

######  Definition 2.2.5.

Let $\mathcal{S}$ be a possibilistic empirical model for a measurement
scenario $(X,\mathcal{M},O)$. We say that $\mathcal{S}$ is

  * •

logically contextual at $s\in\mathcal{S}(C)$ if there is no global section
$g\in\mathcal{S}(X)$ such that $g\rvert_{C}=s$.

  * •

logically contextual if $\mathcal{S}$ is logically contextual at _some_ local
section. Otherwise, it is _non-contextual_.

  * •

strongly contextual if $\mathcal{S}$ has no global section:
$\mathcal{S}(X)=\emptyset$.

We consider three types of contextuality forming a hierarchy:

$\text{Probabilistic Contextuality}<\text{Logical Contextuality}<\text{Strong
Contextuality}$ (2.44)

Possibilistic empirical models can be represented by bundle diagrams. When an
empirical model is represented as a bundle diagram logical and strong
contextuality have particularly elegant interpretations. Logical contextuality
is the failure of a single line to extend to a path, and strong contextuality
is the property of every line extending to a path (Figure 2.3).

######  Lemma 2.2.2.

The Hardy model (2.42) is logically contextual, but not strongly contextual.
The PR-box is strongly contextual.

###### Proof.

This can be seen by inspecting the bundle diagrams. ∎

####  2.2.3 State dependent contextuality

Let $\boldsymbol{M}$ be a set of projective measurements,
$C\subset\boldsymbol{M}$ a context of commuting measurements, and $\psi$ a
state. An outcome assignment $s$ for $C$ is _consistent with $\psi$_ if $s$
has non-zero probability according to the measurement postulate

$\displaystyle\big{[}\prod_{M\in\boldsymbol{M}}M_{s(M)}\big{]}\psi\neq 0$
(2.45)

######  Definition 2.2.6.

Let $\boldsymbol{M}$ be a set of projective measurements and $\psi$ a state.
The _state dependent model_ $\mathcal{S}_{\boldsymbol{M},\psi}$ is the
possibilistic empirical model

$\mathcal{S}_{\boldsymbol{M},\psi}(V):=\\{s\in\mathcal{E}_{\boldsymbol{M},\mathcal{M},O}(V)\mid\text{$s$
is consistent with $\psi$}\\}$ (2.46)

The set of measurements $\boldsymbol{M}$ is state dependently contextual if
$\mathcal{S}_{\boldsymbol{M},\psi}$ is contextual for some state $\psi$. An
example of a state-dependent contextuality proof is the GHZ-example.

####  2.2.4 State independent contextuality

For some sets of quantum measurements, the state $\psi$ is not needed for the
proof of contextuality.

######  Definition 2.2.7.

Let $\boldsymbol{M}$ be a set of projective measurements. The _state
independent_ model $\mathcal{S}_{X}$ is defined at any _below the cover_ by

$\mathcal{S}_{X}(V):=\\{s\in\mathcal{E}_{\boldsymbol{M},\mathcal{M},O}(V)\mid\text{$s$
is consistent with \emph{some} state}\\}$ (2.47)

The set of measurements $\boldsymbol{M}$ is said to be state-independently
contextual if $\mathcal{S}_{X}$ is contextual.

######  Example 2.2.2 (Mermin’s square [Mer90]).

Let $\mathcal{S}_{X}:(X,\mathcal{M},\mathbb{Z}_{2})$ be the state independent
model induced by the set of measurements displayed in _Mermin’s square_

$\sigma_{{x}}^{1}$ | $\sigma_{{x}}^{2}$ | $\sigma_{{x}}^{1}\sigma_{{x}}^{2}$ | $I$
---|---|---|---
$\sigma_{{z}}^{2}$ | $\sigma_{{z}}^{1}$ | $\sigma_{{z}}^{1}\sigma_{{z}}^{2}$ | $I$
$\sigma_{{x}}^{1}\sigma_{{z}}^{2}$ | $\sigma_{{z}}^{1}\sigma_{{x}}^{2}$ | $\sigma_{{y}}^{1}\sigma_{{y}}^{2}$ | $I$
$I$ | $I$ | $-I$ |

Observe that the measurements displayed in any row or column
$M_{1},M_{2},M_{3},M_{4}$ defines a context and furthermore satisfies
$M_{1}M_{2}M_{3}=M_{4}$, where $M_{4}=\pm I$. By Lemma 2.1 any local section
$s\in\mathcal{S}(C)$ therefore satisfies one of the following equations

$\displaystyle\sigma_{{x}}^{1}\oplus\sigma_{{x}}^{2}\oplus\sigma_{{x}}^{1}\sigma_{{x}}^{2}$
$\displaystyle=0$ (2.48)
$\displaystyle\sigma_{{z}}^{1}\oplus\sigma_{{z}}^{2}\oplus\sigma_{{z}}^{1}\sigma_{{z}}^{2}$
$\displaystyle=0$ (2.49)
$\displaystyle\sigma_{{x}}^{1}\oplus\sigma_{{z}}^{2}\oplus\sigma_{{x}}^{1}\sigma_{{z}}^{2}$
$\displaystyle=0$ (2.50)
$\displaystyle\sigma_{{z}}^{1}\oplus\sigma_{{x}}^{2}\oplus\sigma_{{z}}^{1}\sigma_{{x}}^{2}$
$\displaystyle=0$ (2.51)
$\displaystyle\sigma_{{x}}^{1}\sigma_{{z}}^{2}\oplus\sigma_{{z}}^{1}\sigma_{{x}}^{2}\oplus\sigma_{{y}}^{1}\sigma_{{y}}^{2}$
$\displaystyle=0$ (2.52)
$\displaystyle\sigma_{{x}}^{1}\sigma_{{x}}^{2}\oplus\sigma_{{z}}^{1}\sigma_{{z}}^{2}\oplus\sigma_{{y}}^{1}\sigma_{{y}}^{2}$
$\displaystyle=1$ (2.53)

Any global section $g\in\mathcal{S}_{X}(C)$ therefore simultaneously satisfies
all equations. However, these equations are mutually inconsistent. Summing
together all of the equations gives $0=1$, because each measurement appears in
exactly two equations. $\mathcal{S}_{X}$ is therefore strongly contextual.

###  2.3 Simulations

Figure 2.4:  Consider a setup involving two measurement scenarios
$S=(X,\mathcal{M},O),T=(Y,\mathcal{N},P)$. A simulation from $S$ to $T$ maps
each measurement $y\in Y$ to a measurement protocol on $S$, and each possible
outcome of this protocol to an outcome $p\in P_{y}$. This induces a map on
empirical models of $S$ to empirical models of $T$.

The motivation behind introducing simulations is to equip the sheaf-theoretic
framework with a class of structure-preserving transformations. The problem of
what the right notion of structure-preserving transformation is for empirical
models was considered by Karvonen [Kar19]. The work of Karvonen later formed
the basis for the more developed idea of simulation laid out by Abramsky,
Barbosa, Karvonen, and Mansfield [ABKM19a]. See also For further work on
simulations see the work of Barbosa, Karvonen, and Mansfield [BKM21] and
Abramsky, Barbosa, Karvonen, and Mansfield [ABKM19b].

The notion of simulation that we present here was defined by Abramsky et al.
[ABKM19a], based on earlier work by The idea of studying examples of
contextuality up to a class of structure-preserving transformations have also
been considered by others, for example Amaral et al. [ACCA18].

Informally, a simulation $s$ from a measurement scenario $S$ to another
scenario $T$ describes how we can translate measurements on $T$ into
measurements on $S$, and outcomes of these measurements on $S$ into outcomes
in $T$ (Figure 2.4). This defines a map at the level of empirical models
called the _pushforward_.

This section is structured as follows. In Section 2.3.1 we introduce the most
simple example of a simulation, deterministic single-round simulations. We
then introduce measurement protocols, describing adaptive sequence of
measurements. We finally present the general notion of simulation.

####  2.3.1 Single-round simulations

We will now present the notion of simulation that Karvonen [Kar19] considered.

######  Definition 2.3.1.

A deterministic single-round simulation from a measurement scenario
$S=(X_{S},\mathcal{M}_{S},O_{S})$ to another measurement scenario
$T=(X_{T},\mathcal{M}_{T},O_{T})$ is a pair

$\displaystyle f$ $\displaystyle:X_{T}\to\mathcal{M}_{S}$ (2.54)
$\displaystyle g$
$\displaystyle=\\{g_{y}:\mathcal{E}_{S}(f(x))\to(O_{T})_{x}\\}_{x\in X_{T}}$
(2.55)

such that $\bigcup_{x\in C}f(x)\in\mathcal{M}_{S}$ for every
$C\in\mathcal{M}_{T}$.

Let $e$ be an empirical model for the scenario $S$. The pushforward
$(f,g)_{*}(e)$ is then the empirical model for the scenario $T$, defined by

$\displaystyle(f,g)_{*}(e)(C):=\sum_{s\in\mathcal{E}_{S}(\cup_{x\in
C}f(x))}e(\cup_{x\in C}f(x))(s)\cdot(x\mapsto g_{x}(s\rvert_{f(x)})$ (2.56)

for all contexts $C$ in $T$. Suppose now that $e$ is non-contextual, and
therefore a convex combination of global sections

$\displaystyle
e(C)=\sum_{\lambda\in\mathcal{E}(X_{S})}p_{x}\cdot\lambda\rvert_{C}$ (2.57)

$(f,g)_{*}(e)$ is then a convex combination

$\displaystyle(f,g)_{*}(e)(C)=\sum_{\lambda\in\mathcal{E}(X_{S})}p_{\lambda}\cdot
g_{U}(\lambda\rvert_{f(U)})$ (2.58)

If we define the global section $\lambda^{\prime}\in\mathcal{E}_{T}(Y)$ by

$\displaystyle\lambda^{\prime}(y)=g_{y}(\lambda\rvert_{C_{y}})$ (2.59)

for each global section $\lambda\in\mathcal{E}(X_{S})$, then

$\displaystyle g_{U}(\lambda\rvert_{f(U)})=\lambda^{\prime}\rvert_{U}$ (2.60)

hence $e$ is a convex combination of global sections, and hence non-
contextual.

We, therefore, observe that if translate each measurement $y\in Y$ into a
fixed measurement $f(y)\subset\mathcal{M}$ that is independent of the
measurement context that $y$ is performed in, then the induced map on
empirical models preserve non-contextuality. A _simulation_ extends this in
two ways, by allowing for randomness and several rounds of measurements.

####  2.3.2 Measurement protocols

While Karvonen initially only considered single-round simulations it is
natural to consider simulations with more than one round of measurements. To
capture this Abramsky, Mansfield, Barbosa, and Karvonen introduced what they
called _measurement protocols_.

A _measurement protocol_ of length $n$ on a measurement scenario $S$

$\displaystyle
C=\\{C_{1},\dots,C_{i}(s_{1},\dots,s_{i-1}),\dots,C_{n}(s_{1},\dots,s_{n-1})\in\mathcal{M}_{X}\\}_{s_{1}\in
C_{1},\dots,(s_{1},\dots,s_{n-1})\in C_{n-2}(s_{1},\dots,s_{n-2})}$ (2.61)

represents a deterministic strategy that someone can follow to perform
measurements on $S$, in an adaptive way. The measurement setting $C_{i}$ is a
function of the previous $i-1$ measurement outcomes. We require that for all
outcomes $s_{1},\dots,s_{n-1}$ the sequence of contexts is valid, that is
satisfying Eq. 2.1. We write $\text{MP}_{n}(S)$ for the set of measurement
protocols of length $n$. A _run_ of an adaptive measurement sequence
$\\{C_{i}(s_{1},\dots,s_{i-1})\\}_{n\in\mathbb{N}}$ is a sequence of contexts
and local sections $\\{(U_{i},s_{i})\\}_{n\in\mathbb{N}}$ such that
$s_{i}\in\mathcal{E}_{S}(U_{i})$ and $U_{i}=C_{i}(s_{1},\dots,s_{i-1})$ for
all $i\in\mathbb{N}$. We write $\mathcal{E}_{S}(C)$ for the set of runs of a
measurement protocol $C$.

A set of measurement protocols $\\{C^{j}\\}_{j\in J}$ that can be performed in
parallel is said to be _compatible_. For any compatible set of measurement
protocols $\\{C^{j}\\}_{j\in J}$ their parallel product is denoted by
$\otimes_{i\in I}C^{j}$.

When a measurement protocol $C$ is performed the outcome is a run. By the no-
disturbance assumption the probability of a given run can be defined by

$\displaystyle e(C)(r):=e(U_{1}\cup\dots\cup U_{n})(s_{1}\cup\dots\cup s_{n})$
(2.62)

where $r=\\{(U_{i},s_{i})\\}_{i=1}^{N}$ is a run.

####  2.3.3 General simulations

The idea of describing probabilistic simulations as probability distributions
over deterministic simulations is how Karvonen described simulations. Although
only for single-round simulations. Later this was also how Abramsky, Barbosa,
Mansfield, and Karvonen formalised probabilistic simulations with more than
one round.

We now define deterministic $n$-round simulations, and general simulations as
probability distributions over deterministic simulations.

######  Definition 2.3.2.

A deterministic simulation from a measurement scenario $S$ to another
measurement scenario $T$ of depth $n$ is a pair $(f,g)$ where

  * •

$f:X_{T}\to\text{MP}_{n}(S)$ is a function such that $\\{f(x)\\}_{x\in C}$ is
compatible for all $C\in\mathcal{M}_{T}$.

  * •

$g=\\{g_{x}:\mathcal{E}(f(x))\to(O_{T})_{x}\\}_{x\in X_{T}}$ is a family of
functions.

Let $S=(X,\mathcal{M},O)$, $T=(Y,\mathcal{N},P)$ be two measurement scenarios,
and $t=(f,g):S\to T$ a deterministic $n$-round simulation. For each context
$C\in\mathcal{N}$ write $f_{C}$ for the parallel product of the measurement
protocols $\\{f(y)\\}_{y\in C}$

$\displaystyle f_{C}:=\otimes_{y\in C}f(y)$ (2.63)

The family of functions $\\{g_{y}\\}_{y\in C}$ defines a function

$\displaystyle g_{C}:\mathcal{E}_{S}(f_{C})\to\mathcal{E}_{T}(C)$ (2.64)

defined at each $y\in C$ by the function $g_{y}$. For any empirical model $e$
of $S$ we define the pushforward $t_{*}(e)$ to be the empirical model for the
scenario $T$ given by the convex combination

$\displaystyle t_{*}(e)_{C}:=\sum_{r\in\mathcal{E}_{S}(f(C))}e(f(C))(r)\cdot
g_{C}(r)$ (2.65)

for each context $C$ of $T$.

######  Definition 2.3.3.

Let $S$ and $T$ be measurement scenarios. An _$n$ -round simulation_ from $S$
to $T$, denoted $s:S\to T$, is a probability distribution over the set of
deterministic $n$-round simulations from $S$ to $T$.

We generalise the definition of the pushforward model by taking the convex
combination of empirical models:

$\displaystyle s_{*}(e)=\sum_{t:S\to T}s(t)\cdot t_{*}(e)$ (2.66)

where $s=\sum_{t:S\to T}s(t)\cdot t$ is a simulation, and $e$ is an empirical
model.

###  2.4 The cohomology of contextuality

A cohomology theory assigns an algebraic invariant to each element of some
class of objects. Cohomology theories are useful when one can find invariants
that can be computed easily, yet characterise an important property of the
objects we are studying. An example is the _simplicial cohomology_ of a
topological space. Using for example triangulation we can compute the
simplicial cohomology of a large class of spaces. In topology this is an
invaluable tool for resolving many questions in a simple way.

In the sheaf-theoretic framework, a possibilistic empirical model is a sheaf
of sets $\mathcal{S}:X^{\text{op}}\to\textbf{Set}$. Contextuality is seen as
the failure of a local section $s\in\mathcal{S}(C)$ to extend to a global
section $g\in\mathcal{S}(X)$. For presheafs of _abelian groups_
$\mathcal{F}:X^{\text{op}}\to\textbf{AbGrp}$ this transition from local to
global is characterised by a _cohomological obstruction_. It is therefore
natural to consider if this obstruction can detect contextuality. Abramsky et
al. showed that this is the case in a range of examples [AMB12], but also that
it is not complete. A more precise characterisation of the class of models
where it is complete was later given [ABK+15].

In this section we present the _Čech cohomology obstruciton_ of Abramsky et
al. [AMB12]. We first define the cohomology groups of a cochain complex in
Section 2.4.1. In Section 2.4.2 we define the _Čech cohomology_ groups of a
presheaf of abelian groups. In Section 2.4 we define the obstruction for
contextuality.

####  2.4.1 Cohomology groups of a cochain complex

To define the cohomology groups of an object we use a family of abelian groups
connected by homomorphisms. This is called a _cochain complex_.

######  Definition 2.4.1.

A _cochain complex_ is a sequence

${0}$${C^{0}}$${C^{1}}$${C^{2}}$${\cdots}$$\scriptstyle{d^{-1}:=0}$$\scriptstyle{d^{0}}$$\scriptstyle{d^{1}}$$\scriptstyle{d^{2}}$
(2.67)

where $C^{0},C^{1},\dots$ are abelian groups, and $d^{0},d^{1},\dots$ are
homomorphisms such that $d^{n+1}\circ d^{n}=0$. The elements of $C^{n}$ are
known as the _$n$ -cochains_ and $d^{n}$ is the _$n$ ’th coboundary map_.
$\text{im}(d^{n})$ are the _$n$ -coboundaries_ and $\text{ker}(d^{n+1})$ the
_$n$ -cocycles_.

The requirement that $d^{n+1}\circ d^{n}=0$ equivalently says that every
$n$-coboundary is an $n$-cocycle,
$\text{im}(d^{n})\subset\text{ker}(d^{n+1})$. A sequence such that
$\text{im}(d^{n})=\text{ker}(d^{n+1})$ is said to be _exact_ at $n$.
Cohomology measures the failure of a sequence to be exact.

######  Definition 2.4.2.

The $n$-th cohomology group is the quotient of the coboundaries to the
cocycles. $H^{n}:=\text{im}(d^{n})/\text{ker}(d^{n-1})$.

The cohomology class $[x]\in H^{n}$ of a cocycle $x$ can be thought of as an
obstruction for $x$ to be a coboundary, because $[x]=0$ if and only if $x$ is
a coboundary.

When we assign a cochain complex to some mathematical object it is common to
use a free construction. This free construction loses some of the structure of
the original object. However, it can also be the case that the cohomology
groups capture some interesting feature of the object. The classic example is
simplicial cohomology, which relates to the number of “holes” in a topological
space.

####  2.4.2 Čech cohomology

Let $X$ be a topological space, and
$\mathcal{F}:X^{\text{op}}\to\mathbf{AbGrp}$ a presheaf of abelian groups. In
this section we define the _Čech cohomology_ groups of $\mathcal{F}$. To do
this we assign to $\mathcal{F}$ a cochain complex. This complex is defined
using an open cover $\mathcal{U}$ of $X$. First, we define an object encoding
the combinatorial structure of the open cover.

######  Definition 2.4.3.

Let $\mathcal{U}$ be an open cover of a topological space $X$. The _$n$
-simplices_ of the _nerve_ of $\mathcal{U}$, denoted by
$\mathcal{N}_{n}(\mathcal{U})$, are $n+1$-tuples of intersecting open sets.

$\displaystyle\mathcal{N}_{n}(\mathcal{U})$
$\displaystyle:=\\{(U_{0},\dots,U_{n})\in\mathcal{U}^{n+1}\mid
U_{0}\cap\dots\cap U_{n}\neq\emptyset\\}$ (2.68)

The boundary maps
$\partial_{i}:\mathcal{N}_{n+1}(\mathcal{U})\to\mathcal{N}_{n}(\mathcal{U})$
remove the $i$’th open set:

$\partial_{i}::(U_{0},\dots,U_{n+1})\mapsto(U_{0},\dots,U_{i-1},U_{i+1},\dots,U_{n+1})$
(2.69)

Let ${\left\lvert(U_{0},\dots,U_{n})\right\rvert}:=\cap_{i}U_{i}$.

######  Definition 2.4.4.

Let $X$ be a topological space, $\mathcal{U}$ an open cover of $X$ and
$\mathcal{F}$ a presheaf of abelian groups on $X$. The Čech cohomology group
$H^{n}(\mathcal{F})$ is the $n$’th cohomology group of the cochain complex

${0}$${C^{0}(\mathcal{U},\mathcal{F})}$${C^{1}(\mathcal{U},\mathcal{F})}$${C^{2}(\mathcal{U},\mathcal{F})}$${\cdots}$$\scriptstyle{d^{-1}:=0}$$\scriptstyle{d^{0}}$$\scriptstyle{d^{1}}$$\scriptstyle{d^{2}}$
(2.70)

where

  * •

The $n$-cochains
$C^{n}(\mathcal{U},\mathcal{F}):=\bigoplus_{U\in\mathcal{N}_{n}(\mathcal{U})}\mathcal{F}({\left\lvert
U\right\rvert})$.

  * •

The coboundary map
$d^{n}(\omega)(U):=\sum_{i=0}^{q}{(-1)}^{i}\mathcal{F}({\left\lvert\partial_{i}U\right\rvert}\subset
U)(\omega(\partial_{i}U))$

It can be verified that $d^{q+1}\circ d^{q}=0$.

####  2.4.3 The obstruction to the extension of a local section

Let $S=(X,\mathcal{M},O)$ be a measurement scenario, $\mathcal{S}$ a
possibilistic empirical model, and $s_{0}\in\mathcal{S}(C_{0})$ a local
section. We define the Čech cohomology obstruction for $s_{0}$ to extend to a
global section.

We can give $\mathcal{S}$ the structure of an abelian presheaf by composing
with the the functor $F_{\mathbb{Z}}:\textbf{Set}\to\textbf{AbGrp}$ assigning
to each set $X$ the _free abelian group_ on $X$, that is, the group of formal
linear combinations of $X$.

$\displaystyle F_{\mathbb{Z}}(X)$ $\displaystyle:=\\{\sum_{x\in X}k_{x}\cdot
x\mid k_{x}\neq 0\text{ for finitely many $x\in X$}\\}$ (2.71) $\displaystyle
F_{\mathbb{Z}}(f:X\to Y)$ $\displaystyle:=\sum_{x\in X}k_{x}\mapsto\sum_{x\in
X}k_{x}\cdot f(x)$ (2.72)

Let $\mathcal{F}:=F_{\mathbb{Z}}\circ\mathcal{S}$. Note that even though
$\mathcal{S}$ is a sheaf, $\mathcal{F}$ is generally only a presheaf.

The construction employs two auxiliary presheaves. For any subset $U\subset X$
we define $\mathcal{F}\rvert_{C_{0}}$ to be the restriction of each $U$ to
$U\cap C_{0}$, and $\mathcal{F}_{\tilde{C_{0}}}$ assigns to each $U$ the
subset of elements whose restriction to $U\cap C_{0}$ vanishes.

######  Definition 2.4.5.

Let $\mathcal{F}$ be an abelian presheaf and $C_{0}$ an open set.

$\mathcal{F}_{\tilde{C_{0}}}::U\mapsto\ker{\mathcal{F}(U\cap C_{0}\subset
U)}\quad\mathcal{F}\rvert_{C_{0}}::U\mapsto\mathcal{F}(C_{0}\cap U)$ (2.73)

At any $U\subset X$ these presheaves are related to $\mathcal{F}$ by a
sequence

${0}$${\mathcal{F}_{\tilde{C_{0}}}(U)}$${\mathcal{F}(U)}$${\mathcal{F}\rvert_{C_{0}}(U)}$${0}$$\scriptstyle{\text{res}^{U}_{U\cap
C_{0}}}$

which in fact is exact, because $\mathcal{F}$ is flasque beneath the cover.
When lifted to the level of cochain complexes it, therefore, gives rise to a
short exact sequence

${0}$${C^{*}(\mathcal{M},\mathcal{F}_{\tilde{C_{0}}})}$${C^{*}(\mathcal{M},\mathcal{F})}$${C^{*}(\mathcal{M},\mathcal{F}\rvert_{C_{0}})}$${0}$

Using standard techniques from homological algebra this short exact sequence
of cochain complexes induces a _long exact sequence_ of cohomology groups

${0}$${H^{0}(\mathcal{M},\mathcal{F}_{\tilde{C_{0}}})}$${H^{0}(\mathcal{M},\mathcal{F})}$${H^{0}(\mathcal{M},\mathcal{F}\rvert_{C_{0}})}$${H^{1}(\mathcal{M},\mathcal{F}_{\tilde{C_{0}}})}$${H^{1}(\mathcal{M},\mathcal{F})}$${H^{1}(\mathcal{M},\mathcal{S}\rvert_{C_{0}})}$${\cdots}$$\scriptstyle{\gamma}$

where $\gamma$ is the connecting homomorphism. For details about this see for
example [Wei94]. Using the identification $\mathcal{F}(C_{0})\cong
H^{0}(\mathcal{M},\mathcal{F}\rvert_{C_{0}})$ we define the _obstruction for
$s_{0}$_ to extend to a global section to be $\gamma(1\cdot s_{0})\in
H^{1}(\mathcal{M},\mathcal{F}_{\tilde{C_{0}}})$.

######  Lemma 2.4.1 ([AMB12]).

If the cover $\mathcal{M}$ is _connected_ 111 i.e. All pairs
$C,C^{\prime}\in\mathcal{M}$ are connected by a sequence
$C_{0}=C,C_{1},C_{2},\cdots,C_{n-1},C_{n}=C^{\prime}$ with $C_{i}\cap
C_{i+1}\neq\emptyset$. This assumption is harmless because non-connected
components are completely independent in terms of contextuality. Incidentally,
all of the scenarios we will consider are connected.  then $\gamma(1\cdot
s_{0})=0$ if and only if $1\cdot s_{0}$ extends to a compatible family of
$F_{\mathbb{Z}}\mathcal{S}$.

######  Definition 2.4.6.

Let $\mathcal{S}:(X,\mathcal{M},O)$ be a possibilistic empirical model and
$s_{0}\in\mathcal{S}(C_{0})$ a local section. The _cohomological obstruction_
to $s_{0}$ lifting to a global section is the cohomological obstruction to
$1\cdot s_{0}$ extending to a compatible family in
$F_{\mathbb{Z}}\circ\mathcal{S}$.

Observe that if $s_{0}$ extends to a global section $s$ in $\mathcal{S}$, then
$1\cdot s_{0}$ extends to a global section $1\cdot s$ in $\mathcal{F}$, hence
the obstruction is _sound_.

######  Lemma 2.4.2.

The Čech cohomology obstruction for contextuality is sound: If $\gamma(g)\neq
0$ then $\mathcal{S}$ is logically contextual at $s$.

####  2.4.4 Generalised AvN arguments

The Čech cohomology obstruction is not complete. There are so-called _false
negatives_ , contextual empirical models where the obstruction vanishes. The
approach detects contextuality in many cases, but an example where the
approach is not complete is Hardy’s paradox. Work has been carried out by Caru
on understanding false negatives and refining the approach [Car18].

The Čech cohomology obstruction is complete for a large fragment of models
that can be described by generalised AvN models. Abramsky et al. [ABK+15] take
this terminology from Mermin [Mer90] who used the term “all versus nothing” to
describe his proof of contextuality. These proofs can be understood as
exhibiting an inconsistent set of equations over $\mathbb{Z}_{2}$ that is
locally satisfied by the model. The all versus nothing terminology was also
used by for example Cabello [Cab01]. The Čech cohomology obstruction is
complete for the _generalised AvN models_ , the class of models that locally
satisfies a system of inconsistent equations over any ring $R$ [ABK+15].

######  Definition 2.4.7.

Let $(X,\mathcal{M},R)$ be a measurement scenario where $R$ is a ring. An _$R$
-linear equation_ is a triple $(C,r,a)$ where $C\in\mathcal{M}$ is a context,
$r:C\to R$ assigns a coefficient in $R$ to each $x\in C$, and $a\in R$ is a
constant. A local section $s:C\to R$ _satisfies_ $(C,r,a)$ if

$\displaystyle\sum_{x\in C}r(x)\cdot s(x)=a$ (2.74)

where $\cdot$ denotes multiplication in $R$.

Let $\mathcal{S}$ be an empirical model. The _$R$ -linear theory of
$\mathcal{S}$_ is the set of all $R$-linear equations that are consistent with
$\mathcal{S}$.

$\displaystyle\text{Th}_{R}(\mathcal{S}):=\bigcup_{C\in\mathcal{M}}\\{(C,r,a)\mid
s\text{ satisfies $(C,r,a)$ for all $s\in\mathcal{S}(C)$}\\}$ (2.75)

######  Definition 2.4.8.

$\mathcal{S}$ is $\text{AvN}_{R}$ if its $R$-linear theory is _inconsistent_.
i.e. there is no $s:X\to R$ such that $s\rvert_{C}\models\phi$, for every
context $C\in\mathcal{M}$ and formula $\phi\in\text{Th}_{R}(\mathcal{S})$ at
$C$.

######  Theorem 2.4.1 ([ABK+15]).

If $\mathcal{S}$ is $\text{AvN}_{R}$ then $\gamma(1\cdot s)\neq 0$ for all
$C\in\mathcal{M}$ and $s\in\mathcal{S}(C)$.

###  2.5 Witnessing contextuality through cooperative games

(a)

| $a=1$ | $a=2$ | $a=3$
---|---|---|---
$b=1$ | $X_{1}$ | $X_{2}$ | $X_{1}X_{2}$
$b=2$ | $Z_{2}$ | $Z_{1}$ | $Z_{1}Z_{2}$
$b=3$ | $-X_{1}Z_{2}$ | $-Z_{1}X_{2}$ | $Y_{1}Y_{2}$
(b)

Figure 2.5:  The Magic Square game. Alice and Bob each hold one of the two
qubits of two maximally entangled states $\phi$. Verifier sends Alice and Bob
$a,b\in\\{1,2,3\\}$. Alice performs the three observables
$(M_{1},M_{2},M_{3})$ in column $b$ of (b) and Bob performs the observables in
row $a$. Given outcome $x=(x_{1},x_{2},x_{3}),y=(y_{1},y_{2},y_{3})$ they win
if $x_{1}\oplus x_{2}\oplus x_{3}=1$ and $y_{1}\oplus y_{2}\oplus y_{3}=0$,
and $x_{b}=y_{a}$.

There are different ways of proving that an empirical model is contextual. For
example, using inequalities [CHSH69, Bel64] or using systems of logical
formulas [Mer90]. A systematic treatment of contextuality proofs is given by
Abramsky and Hardy [AH12]. It is well known that certain contextuality proofs
can be recast as cooperative games known as _non-local games_. For example,
the Magic Square game (Figure 2.5) [CHTW10].

In this section, we first define cooperative games and non-local games. We
then explain that simulations can be used to translate a cooperative game from
one scenario to another.

####  2.5.1 Cooperative games

Let $S=(I,X,Y)$ be a multipartite scenario.

A _game_ is played by $I$, thought of as players, against _Verifier_. A game
is played over one or more rounds of the following form. Verifier sends each
player $i\in I^{\prime}$, in a subset $I^{\prime}\subset$, a value $x_{i}\in
X_{i}$, and each player responds with a value $y_{i}\in Y_{x}$. We assume that
the players are not allowed to communicate and that each player is sent at
most one value. A strategy for Verifier is therefore an $n$-round measurement
protocol $C$, and a strategy for the players is an empirical model $e$.

At the beginning of each game Verifier randomly selects a strategy $C$ and an
_accepting condition_ $A\subset\mathcal{E}_{S}(m)$. The goal of the players is
to maximize the probability that their responses $s_{1},\dots,s_{n}$ satisfies
the accepting condition.

######  Definition 2.5.1.

Let $S=(I,X,Y)$ be a multipartite measurement scenario. An $n$-round _game_ is
a convex combination
$\Phi=\sum_{C\in\text{MP}_{n}(S),A\subset\mathcal{E}_{S}(C)}\Phi_{C,A}\cdot(m,A)$.
The _success probability_ of an empirical model $e$ is

$\displaystyle
p_{S}(e,\Phi):=\sum_{C\in\text{MP}_{n}(S),A\subset\mathcal{E}_{S}(C)}\Phi_{C,A}e(C)(A)$
(2.76)

A _non-local game_ is a single-round cooperative game along with a quantum
strategy exceeding that of any non-contextual strategy.

######  Definition 2.5.2.

Let $S=(I,X,Y)$ be a multipartite scenario. A _non-local game_ is a pair
$(e,\Phi)$ where $e$ is a quantum realised empirical model, and $\Phi$ is a
single-round game, such that there exists a $\gamma$ such that for all non-
contextual empirical models $e_{\text{NC}}$

$\displaystyle p_{S}(e_{\text{NC}},\Phi)\leq\gamma<p_{S}(e,\Phi)$ (2.77)

the least such $\gamma^{*}$, is called the classical upper bound.

A well-known example is the Greenberger-Horne-Zeillinger (GHZ) game [GHSZ90].

######  Example 2.5.1.

The GHZ game is played by three players $A,B,C$. Verifier selects inputs
$x_{A},x_{B},x_{C}\in\mathbb{Z}_{2}$ with uniform probability. The players win
if their outputs $y_{A},y_{B},y_{C}\in\mathbb{Z}_{2}$ satisfies

$A_{\text{GHZ}}(x_{A},x_{B},x_{C})(y_{A},y_{B},y_{C})\iff x_{A}\lor x_{B}\lor
x_{B}=y_{A}\oplus y_{B}\oplus y_{C}$ (2.78)

A winning quantum strategy is given where each player performs a Pauli $X$
measurement if the input is $0$ and a Pauli $Y$ measurement if the input is
$1$. However, any non-contextual strategy solves the game with at most $3/4$.

####  2.5.2 The pullback of a game

Figure 2.6: The pullback of a game $\Phi$. Consider a game where Verifier
plays against a set of players $Y$. Verifier sends $Y$ a context $C$, the
players then interact with another set of players $X$ through a measurement
protocol $f(C)$. If the result of $f(C)$ is a run $r$ then they respond with
$g_{C}(r)$ to Verifier. Verifier accepts if $g_{C}(r)\in A$ satisfies the
accepting condition. This game is equivalent to the game where Verifier
interacts directly with $X$ by performing the measurement protocol $f(C)$ and
accepts a run $r$ if $r\in g_{C}^{-1}(A)$.

Let $S$ and $T$ be measurement scenarios, and $s:S\to T$ an $n$-round
simulation. We have explained that $s$ induces a map on empirical models going
from $S$ to $T$, called the pushforward. Simulations also have a natural
action on games (Figure 2.6). The _pullback_ $s^{*}$ maps $k$-round games of
$T$ to $kn$-round games on $S$.

The defining property of the pullback is that for any empirical model $e$ of
$S$ and game $\Phi$ of $T$, the success probability of $e$ on $s^{*}(\Phi)$ is
the success probability of $s_{*}(e)$ on $\Phi$:

$\displaystyle p_{S}(e,s^{*}(\Phi))=p_{S}(s_{*}(e),\Phi)$ (2.79)

We can define the pullback directly as follows.

######  Definition 2.5.3.

Let $S$ and $T=(Y,\mathcal{N},P)$ be measurement scenarios, $s:S\to T$ an
$n$-round simulation, and $\Phi$ a single-round game. The _pullback_
$s^{*}(\Phi)$ is the $n$-round game for the scenario $S$, defined as

$\displaystyle s^{*}(\Phi):=\sum_{(f,g):S\to
T,C\in\mathcal{N},A\subset\mathcal{E}_{T}(C)}s(f,g)\Phi_{C,A}\cdot(f_{C},g_{C}^{-1}(A))$
(2.80)

where $\Phi_{C,A}$ is the probability of Verifier selecting the context $C$
and accepting condition $A$, $s(f,g)$ is the probability of the deterministic
simulation $(f,g)$ given by $s$, and $f_{C}\in\text{MP}_{n}(S)$,
$g_{C}:\mathcal{E}_{S}(f_{C})\to\mathcal{E}_{T}(C)$ are the maps defined by
the deterministic simulation.

###  2.6 The contextual fraction

Figure 2.7: In the resource view we think about an empirical model as a
resource that can be consumed by a classical algorithm solving a computational
problem.

The _contextual fraction_ is a measure of contextuality introduced by
Abramsky, Barbosa, and Mansfield [ABM17]. See Barbosa, Douce, Emeriau,
Kashefi, and Mansfield for a generalisation of the contextual fraction for
continuous variables [BDE+22].

The contextual fraction was motivated by the consideration of situations where
a source of contextuality is consumed to solve a computational problem (Figure
2.7). Abramsky, Barbosa, and Mansfield observed that several results of this
type can be refined to give _resource inequalities_ on the form

$p_{F}\geq(1-\text{CF}(e))v(f)$ (2.81)

relating the degree of failure $p_{F}$ in a situation where an empirical model
$e$ is consumed to solve a problem $f$, to the contextual fraction
$\text{CF}(e)$ and some intrinsic measure $v(f)$ of the hardness of $f$.

An example of such a resource inequality arises from measurement-based quantum
computing (MBQC). In MBQC a classical control computer that can only perform
mod-2 linear computations interacts with an empirical model. Raussendorf
[Rau13] building on Anders and Browne [AB09] showed that any MBQC that can
compute a non mod-2 linear function requires a strongly contextual empirical
model. This was later refined into a resource inequality relating the
contextual fraction to the likelihood of an MBQC computing a non-mod 2 linear
function.

In this section, we first define the contextual fraction and then show that
non-local games give another example of a resource inequality. The contextual
fraction is a measure of contextuality that can be seen as the fraction of an
empirical model that cannot be explained by a non-contextual model.

######  Definition 2.6.1.

Let $e$ be an empirical model. The _non-contextual fraction_ of $e$, denoted
by $\text{NCF}(e)$, is the greatest $\epsilon$ such that $e$ is a convex
combination of a non-contextual empirical model $e^{\prime}$ and another
empirical model $e^{\prime\prime}$.

$e=\epsilon\cdot e^{\prime}+(1-\epsilon)\cdot e^{\prime\prime}$ (2.82)

The _contextual fraction_ , denoted by $\text{CF}(e)$, is defined as
$1-\text{NCF}(e)$.

Let $S$ be a measurement scenario and $\Phi$ a game such that the success
probability of any non-contextual empirical model is at most $\gamma$. The
violation of $\gamma$ by any empirical model $e:S$ is at most $\text{CF}(e)$.

######  Lemma 2.6.1.

Let $(\Phi,e)$ be a non-local game with bound $\gamma$. For any empirical
model $e^{\prime}$ the violation of $\gamma$ by $e^{\prime}$ is bounded by the
classical limit and the contextual fraction.

$p_{S}(e,\Phi)\leq\gamma+\text{CF}(e)$ (2.83)

###### Proof.

Let $e$ be an empirical model. We can write $e$ as a convex combination

$\displaystyle e=\text{CF}(e)\cdot e^{\prime}+(1-\text{CF}(e))\cdot
e_{\text{NC}}$ (2.84)

where $e_{\text{NC}}$ is non-contextual. The success probability of $e$ is
then

$\displaystyle
p_{s}(e,\Phi)=\text{CF}(e)p_{S}(e^{\prime},\Phi)+(1-\text{CF}(e))p_{S}(e_{\text{NC}},\Phi)$
(2.85)

The success probability of $e^{\prime}$ is at most one, and the success
probability of $e_{\text{NC}}$ at most $\gamma$. Therefore

$\displaystyle p_{S}(e,\Phi)$
$\displaystyle\leq\text{CF}(e)+(1-\text{CF}(e))\gamma$ (2.86)
$\displaystyle\leq\gamma+\text{CF}(e)$ (2.87)

∎

##  Chapter 3 Comparing two obstructions for contextuality

Cohomological invariants can be a powerful mathematical tool. Abramsky et al.
[AMB12, ABK+15] showed that a cohomological invariant based on Čech cohomology
can detect contextuality in a range of examples. However, the Čech cohomology
approach is generally not complete. There are instances of contextuality,
called “false negatives”, where the cohomological obstruction vanishes. In
this chapter, we compare the Čech cohomology approach to a different
cohomological approach for detecting contextuality.

The _topological approach_ of Okay, Bartlett, Roberts, and Raussendorf
[ORBR17] studies certain sets of quantum measurement operators. Recall that
for any dimension $d\geq 2$ the single-qudit Weyl operators are a set of
$d^{2}$ unitary operators generalising the Pauli operators. The generalised
$n$-qudit Pauli group is the group of operators generated by $n$-fold tensor
products of single-qudit Weyl operators.

######  Definition 3.0.1.

For any dimension $d\geq 2$, and $p_{1},p_{2}\in\mathbb{Z}_{d}^{2}$ the
_single-qudit Weyl operator_ $W(p_{1},p_{2})$ is defined by

$\displaystyle W(p_{1},p_{2}):=\lvert j\rangle\mapsto\omega^{jp_{2}}\lvert
j+p_{1}\rangle$ (3.1)

where $\omega=e^{2\pi i/d}$. The _$n$ -qudit generalised Pauli group
$P_{n,d}$_ is the group of operators on the form

$\displaystyle\omega^{q}W(p_{11},p_{12})\otimes\dots\otimes W(p_{n1},p_{n2})$
(3.2)

where $p_{11},p_{12},\dots,p_{n1},p_{n2}\in\mathbb{Z}_{d}$.

The topological approach studies sets of $n$-qudit Weyl operators that contain
the identity operator, is closed under commuting products and
$\omega^{q}$-phases.

######  Definition 3.0.2.

A set of $n$-qudit generalised Pauli operators $\mathcal{O}\subset P_{n,d}$ is
_closed_ if

  1. 1.

$\mathcal{O}$ contains the identity operator: $I\in\mathcal{O}$.

  2. 2.

$\mathcal{O}$ is closed under commuting products: If
$O_{1},O_{2}\in\mathcal{O}$ and $O_{1}O_{2}=O_{2}O_{1}$ then
$O_{1}O_{2}\in\mathcal{O}$.

  3. 3.

$\mathcal{O}$ is closed under $\\{\omega^{k}\\}$-phases: If $O\in\mathcal{O}$
and $k\in\mathbb{Z}_{d}$ then $\omega^{k}O\in\mathcal{O}$.

(a)

(b)

Figure 3.1: Examples of classifying spaces taken from Okay et al. [ORBR17].
(a) is the GHZ proof, (b) Mermin’s square.

For any closed set of Weyl operators Okay et al. defines a topological space
(Figure 3.1). They show that key properties of the set of operators are
reflected in the topology of this space. One of their results is that both
state-dependent and state-independent contextuality can be detected by the
non-vanishing of a cohomology class. Recall that each $n$-qudit Weyl operator
$W(p_{1},p_{2})\neq I$ has $d$ distinct eigenvalues
$\omega^{0},\dots,\omega^{d-1}$. Under the identification $\omega^{i}\mapsto
i$ each Weyl operator defines a projective measurement with outcomes
$\mathbb{Z}_{d}$. A state-dependent or state-independent contextuality proof
is a proof that either the state-dependent or state-independent empirical
models

$\mathcal{S}_{\mathcal{O}}:(\mathcal{O},\mathcal{M},\mathbb{Z}_{d}),\quad\mathcal{S}_{\mathcal{O},\psi}:(\mathcal{O},\mathcal{M},\mathbb{Z}_{d})$
(3.3)

are contextual.

In this chapter, we consider the following problem. What is the minimal
structure required to define the topological obstruction at the level of
empirical models. Secondly, assuming that the topological obstruction can be
defined, are there instances where the Čech cohomology obstruction vanishes,
but the topological obstruction does not?

####  3.0.1 Structure of chapter

In Section 3.1 we introduce bundles over commutative partial monoids and we
prove the splitting lemma, relating left splittings, right splittings, and
trivialisations. In Section 3.2 we define the cohomology of a commutative
partial monoid. We show that the problem extending a local right splitting of
a bundle is characterised by a cohomological obstruction. In Section 3.3 we
introduce a class of measurement scenarios and empirical models generalising
closed sets of Weyl operators. We show that for any such empirical model a
cohomological obstruction can be defined. Finally, in Section 3.4 we show that
this obstruction is not stronger than the Čech cohomology obstruction.

###  3.1 Bundles over commutative partial monoids

In this chapter, we are working with commutative groups, monoids, and partial
monoids. We will therefore ommit the word commutative to avoid unnecessarily
complicating terminology.

Recall that if $G$ and $H$ are groups then a group extension of $H$ by $G$ is
a sequence of groups and homomorphisms

${G}$${H}$${K}$$\scriptstyle{i}$$\scriptstyle{j}$ (3.4)

such that $i$ is injective, $j$ is surjective, and
$\text{im}(i)=\text{ker}(j)$. The simplest example of a group extension of $H$
by $G$ is the product $G\times H$ along with the inclusion $\text{in}_{1}:G\to
G\times H$ and the projection $\pi_{2}:G\times H\to H$.

${G}$${G\times H}$${H}$$\scriptstyle{\text{in}_{1}}$$\scriptstyle{\pi_{2}}$
(3.5)

As a group extension, the direct product is not interesting because its
structure is determined completely by $G$ and $H$. It is therefore called the
_trivial_ extension. A homomorphism $h:G\to G\times K$ that is compatible with
both the inclusion and projection maps, that is the diagram

${G}$${H}$${K}$${G\times
K}$$\scriptstyle{\text{in}_{1}}$$\scriptstyle{i}$$\scriptstyle{h}$$\scriptstyle{j}$$\scriptstyle{\pi_{2}}$
(3.6)

commutes is called a trivialisation. It can be shown that any trivialisation
is an isomorphism. A bundle that has a splitting is said to split, and its
structure is therefore also determined completely by $G$ and $K$. The
_splitting lemma_ for groups gives a necessary and sufficient characterisation
of when a group extension has a splitting.

Partial monoids generalise groups by omitting the requirement that elements
have inverses, and the requirement that all products are defined.

######  Definition 3.1.1.

A _(commutative) partial monoid_ is a tuple $(M,+,0)$ where $M$ is a set, the
_product_ $+:M^{2}\to M$ is a partial function, and $0\in M$ is the _identity_
, such that the following conditions hold:

  * •

Commutativity: $m+m^{\prime}$ is defined if and only if $m^{\prime}+m$ is
defined and $m+m^{\prime}=m^{\prime}+m$, for all $m,m^{\prime}\in M$.

  * •

Identity: $0+m$ is defined and $0+m=m$ for all $m\in M$.

  * •

Associativity: For all $m,m^{\prime},m^{\prime\prime}\in M$

    * –

If $(m+m^{\prime})+m^{\prime\prime}$ and $m+(m^{\prime}+m^{\prime\prime})$ are
both defined then they are equal.

    * –

If $m+m^{\prime},m+m^{\prime\prime},m^{\prime}+m^{\prime\prime}$ are all
defined then $(m+m^{\prime})+m^{\prime\prime}$ and
$m+(m^{\prime}+m^{\prime\prime})$ are both defined.

If the product $+$ is a total function then $(M,+,0)$ is a _commutative
monoid_.

In this section, we introduce a generalisation of group extensions to partial
monoids and we show that the splitting lemma generalises, and the problem of
extending a local splitting to a global splitting is equivalent.

####  3.1.1 Bundles

To generalise the definition of a group extension to partial monoids we first
recast the definition to emphasise the role of a group action.

######  Definition 3.1.2.

Let $\theta:G\times X\to X$ be a group action. $\theta$ is _free_ if
$\theta(\\_,x):G\to X$ is injective for all $x\in X$. The _orbit_ of $x\in X$,
is the set of elements that are equivalent to $x$ up to the action of $G$:

$[x]_{\theta}:=\\{\theta(g,x)\mid g\in G\\}$ (3.7)

We write $X/\theta$ for the set of orbits. When a particular group action is
assumed we will simplify notation by defining $g\cdot x:=\theta(g,x)$.

Observe that for any group extension
${G}$${H}$${K}$$\scriptstyle{i}$$\scriptstyle{j}$ there is an action of $G$ on
$H$ defined by

$\displaystyle\theta:G\times H\to H::(g,h)\mapsto i(g)+_{H}h$ (3.8)

This action is _free_ because $i$ is injective and $H$ has inverses. It is
also _compatible_ with the group structures of $G$ and $H$ in the sense that
it is a homomorphism from $G\times H$ to $H$. The requirement that
$\text{im}(i)=\text{ker}(j)$ is equivalent to saying that the orbits of
$\theta$ and the fibers of $j$ are the same:

$H/\theta=\\{j^{-1}(k)\mid k\in K\\}$ (3.9)

We can recast the definition of a group extension in terms of this action. A
group extension can be defined as a surjective homomorphism $j:H\to K$ and a
free, compatible group action $\theta$ such that the orbits of $\theta$ are
the fibers of $j$. We will use this view of group extensions to generalise
them to partial monoids.

For a partial monoid the natural notion of homomorphism is a function on the
underlying set that preserves the identity and products whenever they are
defined.

######  Definition 3.1.3.

A _homomorphism_ of partial monoids $h:M\to M^{\prime}$ is a function between
the underlying sets, such that:

  * •

$h$ preserves the identity element: $h(0_{M})=0_{M^{\prime}}$.

  * •

$h$ preserves products: $h(m_{1})+_{M^{\prime}}(m_{2})$ is defined and
$h(m_{1}+_{M}m_{2})=h(m_{1})+_{M^{\prime}}h(m_{2})$, for all $m_{1},m_{2}$
such that $m_{1}+_{M}m_{2}$ is defined.

If $G$ is a group and $M$ is a partial monoid then the set product $G\times M$
is a partial monoid with identity and product defined component-wise.

$\displaystyle 0_{G\times M}$ $\displaystyle=(0_{G},0_{M})$ (3.10)
$\displaystyle(g,m)+_{G\times M}(g^{\prime},m^{\prime})$
$\displaystyle=(g+_{A}g^{\prime},m+_{M}m^{\prime})$ (3.11)

for all $g,g^{\prime}\in G$ and $m,m^{\prime}\in M$ such that
$m+_{M}m^{\prime}$ is defined. We define an action of a group $G$ on $M$ to be
a group action, in the usual sense, that is furthermore a homomorphism from
$G\times M$ to $M$.

######  Definition 3.1.4.

Let $G$ be a group and $M$ a partial monoid. An _action of $G$ on $M$_ is a
_homomorphism_ $\theta:G\times M\to M$ such that the following conditions
hold:

$\displaystyle\theta(0,\\_)$ $\displaystyle=\text{id}_{M}$ (3.12)
$\displaystyle\theta(g,\\_)\circ\theta(g^{\prime},\\_)$
$\displaystyle=\theta(g+g^{\prime},\\_),\quad\text{for all $g,g^{\prime}\in
G$}$ (3.13)

We define a bundle over a partial monoid to be a partial monoid equipped with
a compatible group action and a surjective homomorphism such that the fibers
of the homomorphism and the orbits of the action are the same.

######  Definition 3.1.5.

Let $G$ be a group and $M$ a partial monoid. A _$G$ -bundle_ over $M$ is a
tuple $(N,j,\theta)$, where

  * •

$N$ is a partial monoid,

  * •

$\theta:G\times N\to N$ is a free action,

  * •

$j:N\to M$ is a surjective homomorphism,

such that the orbits of $\theta$ are the fibers of $j$:

$N/\theta=\\{j^{-1}(m)\mid m\in M\\}$ (3.14)

$\theta$ is called the _bundle action_ and $j$ the _bundle map_.

The simplest example of a $G$-bundle over $M$ is given by the product $G\times
M$. Write $\theta_{G\times M}$ for the action of $G$ on $G\times M$ applying
the group operation of $G$ on the first component, and $\pi_{2}:G\times M\to
M$ for the projection onto the second component.

$\displaystyle\theta(g,(g^{\prime},m)):=(g+g^{\prime},m)$ (3.15)

The triple $(G\times M,\theta_{G\times M},\pi_{2})$ is called the _trivial
bundle_. As a bundle it has no interesting structure because it is completely
determined by $G$ and $M$ alone.

####  3.1.2 The splitting lemma

Let ${G}$${H}$${K}$$\scriptstyle{i}$$\scriptstyle{j}$ be a group extension.
The splitting lemma for groups gives the following characterisation of
trivialisations, that is homomorphisms $h:H\to G\times K$ such that the
following diagram commutes:

${G}$${H}$${K}$${G\times
K}$$\scriptstyle{\text{in}_{1}}$$\scriptstyle{i}$$\scriptstyle{h}$$\scriptstyle{j}$$\scriptstyle{\pi_{2}}$
(3.16)

in other words, $\text{in}_{1}=h\circ i$ and $j=\pi_{2}\circ h$.
Trivialisations are necessarily isomorphisms. Any group extension that has a
trivialisation is therefore isomorphic to the product group extension.

A _left splitting_ is a homomorphism $s:H\to G$ such that $i\circ
l=\text{id}_{H}$. A _right splitting_ a homomorphism $r:K\to H$ such that
$r\circ j=\text{id}_{K}$. The _splitting lemma_ for groups states that the
three are equivalent: A group extension has a left splitting if and only if it
has a right splitting, if and only if it has a trivialisation.

To generalise left splittings and trivialisations we observe that their
definitions can be recast in terms of the group action of $G$ on $H$.

######  Definition 3.1.6.

Let $G$ be a group, $M,M^{\prime}$ partial monoids, and $\theta:G\times M\to
M$, $\theta^{\prime}:G\times M^{\prime}\to M^{\prime}$ group actions. An
_action homomorphism_ $h:\theta\to\theta^{\prime}$ is a partial monoid
homomorphism $h:M\to M^{\prime}$ such that
$\theta^{\prime}(g,f(x))=f(\theta(g,x))$ for all $g\in G,x\in X$.

For any group $G$ write write $\theta_{G}$ for the group action of $G$ on
itself: $\theta_{G}(g,g^{\prime}):=g+_{G}g^{\prime}$. A left splitting of a
group extension is then equivalently an action homomorphism from the bundle
action $\theta$ to $\theta_{G}$. The requirement that a trivialisation is
compatible with the inclusion maps, that is $\text{in}_{1}=h\circ i$ is
equivalent to $h$ being an action homomorphism from the bundle action $\theta$
to the bundle action on the product bundle $\theta_{G\times M}$.

######  Definition 3.1.7.

Let $G$ be a group, $M$ a partial monoid, and $B=(N,j,\theta)$ a $G$-bundle
over $M$.

  1. 1.

A _left splitting_ is an action homomorphism $l:\theta\to\theta_{G}$.

  2. 2.

A _right splitting_ is a partial monoid homomorphism $r:M\to N$ such that
$j\circ r=\text{id}_{M}$.

  3. 3.

A _trivialisation_ is an action homomorphism $h:\theta\to\theta_{G\times M}$
such that $j=\pi_{2}\circ h$.

For example, the trivial bundle $(G\times M,\theta_{G\times M},\pi_{2})$ has a
left splitting $\pi_{1}$ and a right splitting $\text{in}_{2}$:

$\displaystyle\pi_{1}:G\times M\to G$ $\displaystyle::(g,m)\mapsto b$ (3.17)
$\displaystyle\text{in}_{2}:M\to G\times M$
$\displaystyle::=m\mapsto(0_{B},m)$ (3.18)

Let $B=(N,j,\theta)$ be a $G$-bundle over a partial monoid $M$ and let $l:N\to
G$ be a left splitting. There is then a natural map from $N$ to $G\times M$
given by

$\displaystyle\langle l,j\rangle:N\to G\times M::=n\mapsto(l(n),j(n))$ (3.19)

Because $l$ is a left splitting and therefore an action homomorphism from
$\theta$ to $\theta_{G}$ we have that $\langle l,j\rangle$ is an action
homomorphism from $\theta$ to the bundle action $\theta_{G\times M}$ of the
trivial bundle. $\langle l,j\rangle$ is a trivialisation.

We then clearly have $\pi_{2}\circ\langle l,j\rangle=j$. Because $l$ is an
action homomorphism from $\theta$ to $\theta_{G}$ we have that $\langle
l,j\rangle$ is an action homomorphism from $\theta$ to $\theta_{G\times M}$.
Conversely if $h:N\to G\times M$ is a trivialisation then we can define a left
splitting by projecting onto the first component: $\pi_{1}\circ h$.

Because the bundle action $\theta$ is free something similar is true for right
splittings. For any left splitting $l$ let $\mathcal{R}(l)$ be the function

$\displaystyle\mathcal{R}(l):M\to N::=m\mapsto-l(\eta(m))\cdot\eta(m)$ (3.20)

where $\eta:M\to N$ is any function such that $j\circ\eta=\text{id}_{M}$.
Observe that the definition is independent of the choice of $\eta$ because

$\displaystyle-l(g\cdot\eta(m))\cdot(g\cdot\eta(m))$
$\displaystyle=(-l(\eta(m))-g+g)\cdot\eta(m)$ (3.21)
$\displaystyle=-l(\eta(m))\cdot\eta(m)$ (3.22)

for any $m\in M$ and $g\in G$.

######  Lemma 3.1.1 (Splitting lemma).

Let $B=(N,\theta,j)$ be a $G$-bundle over a partial monoid $M$.

  1. 1.

The map $l\mapsto<l,j>$ is a bijection between left splittings and
trivialisations.

  2. 2.

The map $l\mapsto\mathcal{R}(l)$ is a bijection between left and right
splittings.

###### Proof.

1\. $h\mapsto\pi_{1}\circ h$ is an inverse to $l\mapsto<l,j>$. $\pi_{1}\circ
h$ is an action homomorphism from $\theta$ to $\theta_{G}$ if and only if $h$
is an action homomorphism from $\theta$ to $\theta_{G\times M}$.

For 2. we first check that $\mathcal{R}(l)$ is a homomorphism. It preserves
the identity. We have $\eta(0)=a\cdot 0$ for some unique $a$. Hence
$\mathcal{R}(l)(0)=(-l(\eta(0)))\cdot\eta(0)=-l(a\cdot 0)\cdot(a\cdot
0)=(0-a+a)\cdot 0$ as required. To see that it preserves products, take
$m,m^{\prime}$ such that $m+_{M}m^{\prime}$ is defined. There is a unique $g$
such that $\eta(m+m^{\prime})=g\cdot(\eta(m)+\eta(m^{\prime}))$. Therefore

$\displaystyle\mathcal{R}(l)(m+m^{\prime})$
$\displaystyle=(-l(\eta(m+m^{\prime})))\cdot\eta(m+m^{\prime})$ (3.23)
$\displaystyle=(-l(g\cdot(\eta(m)+\eta(m^{\prime})))\cdot(g\cdot(\eta(m)+\eta(m^{\prime})))$
(3.24)
$\displaystyle=(-l(\eta(m))-l(\eta(m^{\prime}))-g+g)\cdot(\eta(m)+\eta(m^{\prime}))$
(3.25) $\displaystyle=\mathcal{R})(l)(m)+\mathcal{R}(l)(m^{\prime})$ (3.26)

To see that $\mathcal{R}$ is a bijection we can define the inverse directly as
follows. For any right splitting $r:M\to N$ there is a unique function
$\mathcal{R}^{-1}(r):M\to N$ such that

$\displaystyle\mathcal{R}^{-1}(r)(n)\cdot n=r(j(n))$ (3.27)

for all $n\in N$.

We first check that it is a homomorphism. For the identity we have $h(j(0))=0$
and $h(j(0))=s(0)\cdot 0$, hence $s(0)=0$ as required. That it preserves
products we have both

$\displaystyle h(j(n+n^{\prime}))=s(n+n^{\prime})\cdot(n+n^{\prime})$ (3.28)

and

$\displaystyle h(j(n+n^{\prime}))$ $\displaystyle=h(j(n))+h(j(n^{\prime}))$
(3.29) $\displaystyle=s(n)\cdot n+s(n^{\prime})\cdot n^{\prime}$ (3.30)
$\displaystyle=(s(n)+s(n^{\prime}))\cdot(n+n^{\prime})$ (3.31)

Therefore, by uniqueness of $s$ we have $s(n+n^{\prime})=s(n)+s(n^{\prime})$.
Finally to see that it preserves the action, we have $r(j(g\cdot n))=r(j(n))$.
Hence

$\displaystyle\mathcal{R}^{-1}(r)(g\cdot n)\cdot(g\cdot
n)=\mathcal{R}^{-1}(r)(n)\cdot n$ (3.32)

$\mathcal{R}^{-1}(r)(g\cdot n)=g+\mathcal{R}^{-1}(r)(n)$

Finally we check that $\mathcal{R}^{-1}$ in fact is an inverse to
$\mathcal{R}$.

$\displaystyle R_{B}(R_{B}^{-1}(r))$
$\displaystyle=m\mapsto(-s_{r}(\eta(m)))\cdot\eta(n)$ (3.33)
$\displaystyle=m\mapsto r(j(\eta(m)))=m\mapsto r(m)$ (3.34)

and

$\displaystyle(h^{-1}\circ\text{in}_{M})(j(n))$ $\displaystyle=h^{-1}(0,j(n))$
(3.35) $\displaystyle=(0-h_{1}(n))\cdot n$ (3.36)

Hence by uniqueness $(h^{-1}\circ\text{in}_{M})\mapsto h$ and so $\mathcal{R}$
is a left inverse to $\mathcal{R}^{-1}$. ∎

Similarly, as for groups, trivialisations of bundles are necessarily
isomorphisms. The splitting lemma, therefore, gives a characterisation of when
a bundle is isomorphic to the trivial bundle. A natural candidate for the
inverse of a trivialisation $h$ is the map given by first taking the left
splitting $\pi_{1}\circ h:N\to G$, then composing the right splitting
associated with $\pi_{1}\circ h$ with the projection $\pi_{2}$:
$\mathcal{R}(\pi_{1}\circ h)\circ\pi_{2}$. It can be verified that this map in
fact is an inverse.

######  Lemma 3.1.2.

Trivialisations are isomorphisms. Let $B=(N,j,\theta)$ be an $A$-bundle over a
commutative partial monoid $M$ and $h:N\to A\times M$ a trivialisation. The
inverse of $h$ is

$h^{-1}:A\times M\to N::=(a,m)\mapsto(a-h_{1}(\eta(m)))\cdot\eta(m)$ (3.37)

where $\eta:\prod_{m\in M}j^{-1}(m)$ is an arbitrary section and
$h_{1}=\text{proj}_{1}\circ h:N\to A$ is the first component of $h$.

###### Proof.

We first show that $h^{-1}$ is independent of the choice of the section
$\eta$. Any other section $\eta^{\prime}=m\mapsto\gamma(m)\cdot\eta(m)$
differs from $\eta$ by some $\gamma:M\to A$. If we expand the definition of
$h^{-1}$ using the section $\eta^{\prime}$ in terms of $\gamma$ and $\eta$ we
see that the terms involving $\gamma$ cancels out. For any $m\in M$ we have

$\displaystyle(a-h_{1}(\eta^{\prime}(m)))\cdot\eta^{\prime}(m)$
$\displaystyle=(a-h_{1}(\gamma(m)\cdot\eta(m)))\cdot(\gamma(m)\cdot\eta(m))$
(3.38) $\displaystyle=(a-\gamma(m)-h_{1}(\eta(m))+\gamma(m))\cdot\eta(m)$
(3.39) $\displaystyle=(a-h_{1}(\eta(m)))\cdot\eta(m)$ (3.40)

Therefore $h^{-1}$ is independent of the choice of $\eta$.

Next, we check that $h^{-1}$ is a left inverse to $h$. Let $n\in N$. To see
that $h^{-1}(h(n))=n$ we first expand $h(n)=(h_{1}(n),h_{2}(n))$ into the two
components of the product. Using the section $\eta$ we can write $n$ uniquely
on the form

$n=a\cdot\eta(m)$ (3.41)

where $a\in A$ and $m=j(n)$. Because $h$ is a trivialisation $j(n)=h_{2}(n)$.

$\displaystyle h^{-1}(h(n))$ $\displaystyle=h^{-1}(h_{1}(n),h_{2}(n))$ (3.42)
$\displaystyle=h^{-1}(h_{1}(n),m)$ (3.43)

Because both $h$ and $\text{proj}_{1}$ preserve the action of $A$ we have
$h_{1}(a\cdot\eta(m))=a+h_{1}(\eta(m))$ therefore if we plug $(h_{1}(n),m)$
into $h^{-1}$ the terms involving $h_{1}(\eta(m))$ cancels out

$\displaystyle h^{-1}(h_{1}(n),m)$
$\displaystyle=(h_{1}(n)-h_{1}(\eta(m)))\cdot\eta(m)$ (3.44)
$\displaystyle=(h_{1}(a\cdot\eta(m))-h_{1}(\eta(m)))\cdot\eta(m)$ (3.45)
$\displaystyle=(a+h_{1}(\eta(m))-h_{1}(\eta(m)))\cdot\eta(m)$ (3.46)
$\displaystyle=a\cdot\eta(m)=n$ (3.47)

as required.

Finally, we check that $h^{-1}$ is a right inverse to $h$. Let $(a,m)\in
A\times M$. We first expand the definition of $h^{-1}(a,m)$

$\displaystyle h(h^{-1}(a,m))$
$\displaystyle=h((a-h_{1}(\eta(m)))\cdot\eta(m))$ (3.48)

and then separately check that $h_{1}(h^{-1}(a,m))=a$ and
$h_{2}(h^{-1}(a,m))_{2}=m$. For the first part we use the fact that $h_{1}$ is
an $A$-action homomorphism

$\displaystyle
h_{1}((a-h_{1}(\eta(m)))\cdot\eta(m))=(a-h_{1}(\eta(m)))+h_{1}(\eta(m))=a$
(3.49)

The second part follows because $h$ maps the fiber $j^{-1}(m)$ to
$A\times\\{m\\}$

$\displaystyle h_{2}((a-h_{1}(\eta(m)))\cdot\eta(m))=m$ (3.50)

as required. ∎

####  3.1.3 Extending local splittings

The splitting lemma gives a correspondence between left splittings, right
splittings, and trivialisations. We now show that this correspondence is
compatible with restrictions. This means that the problem of extending a right
splitting, left splitting, or trivialisations defined on a sub-bundle are all
equivalent.

Suppose that $B=(N,j,\theta)$ is a $G$-bundle over a partial monoid $M$, and
that $M^{\prime}\subset M$ is a sub partial monoid. We first explain that $B$
restricts to a sub bundle over $M^{\prime}$.

The pre-image $j^{-1}(M^{\prime})\subset N$ is a sub-partial monoid of $N$,
and it is closed under the action $\theta$. We can therefore restrict $B$ to a
$G$-bundle over $M^{\prime}$ by restricting both the bundle map $j$ and action
$\theta$.

######  Definition 3.1.8.

Let $B=(N,j,\theta)$ be a $G$-bundle over a partial monoid $M$ and
$M^{\prime}\subset M$ a sub partial monoid. The _restriction of $B$ to
$M^{\prime}$_, denoted by $B\rvert_{M^{\prime}}$, is the $G$-bundle over
$M^{\prime}$

$B\rvert_{M^{\prime}}:=\big{(}N^{\prime},j^{\prime},\theta^{\prime}\big{)}$
(3.51)

where $N^{\prime}:=j^{-1}(M^{\prime})$ and $j^{\prime}:N^{\prime}\to
M^{\prime},\theta^{\prime}:G\times N^{\prime}\to N^{\prime}$ are the
restrictions of $j$ and $\theta$ to $N^{\prime}$.

Because the maps in the splitting lemma are defined pointwise they are natural
with respect to restrictions. The problems of extending a left splitting,
right splitting, or trivialisation of the restricted bundle
$B\rvert_{M^{\prime}}$ to $B$ are therefore equivalent.

######  Lemma 3.1.3.

Let $B=(N,j,\theta)$ be a $G$-bundle over a partial monoid $M$,
$M^{\prime}\subset M$ a sub partial monoid, and $l^{\prime}:M^{\prime}\to G$ a
left splitting of the restricted bundle $B\rvert_{M^{\prime}}$. The following
conditions are equivalent:

  * •

There exists a left splitting $l:N\to G$ such that
$l\rvert_{M^{\prime}}=l^{\prime}$.

  * •

There exists a trivialisation $h:N\to G\times M$ such that
$h\rvert_{N^{\prime}}=<l^{\prime},j>$.

  * •

There exists a right splitting $r:M\to N$ such that
$r\rvert_{M^{\prime}}=\mathcal{R}(l^{\prime})$.