###  3.2 Cohomology of commutative partial monoids

We concluded the previous section by explaining that for a $G$-bundle $B$ over
a partial monoid $M$ the problems of extending either a left splitting, right
splitting, or trivialisation, defined on a sub bundle are equivalent. In this
section we show that this problem can be given a cohomological
characterisation. The construction can be seen as a generalisation of _group
cohomology_.

Let $G$ and $K$ be groups. A well-known problem in group theory is to classify
the possible group extensions of $K$ by $G$. An elegant solution to this
problem is given by _group cohomology_ [Bro12]. Two group extensions are
_equivalent_ if they are related by an isomorphism:

${G}$${H}$${K}$${H^{\prime}}$$\scriptstyle{i^{\prime}}$$\scriptstyle{i}$$\scriptstyle{h}$$\scriptstyle{j}$$\scriptstyle{j^{\prime}}$
(3.52)

So in particular an extension splits if it is equivalent to the trivial
extension.

For any group $K$ there is a topological space $X_{K}$ called the _classifying
space_ of $K$. There is a bijection between the second cohomology group
$H^{2}(X_{K},G)$ of $X_{K}$ with coefficients in $G$ , and equivalence classes
of group extensions. In particular, the equivalence class of the trivial
extension correspond to the zero class $0\in H^{2}(X_{K};G)$.

In this section, we first generalise group cohomology. In Section 3.2.1 we
define the _relative cohomology groups_ $H^{n}(M,M^{\prime};G)$ of a partial
monoid $M$ with respect to a sub partial monoid $M\subset M^{\prime}$ with
coefficients in a group $G$. In 3.2.2 we define for any local right splitting
$r$ of a sub-bundle a cohomological obstruction $\mu(r)\in
H^{2}(M,M^{\prime};G)$ and we show that $\mu(r)=0$ if and only if $r$ can be
extended to a global splitting.

####  3.2.1 The cohomology groups of a partial monoid

Let $G$ be a group, $M$ a partial monoid, and $M^{\prime}\subset M$ a sub
partial monoid. In this section, we define the relative cohomology groups
$H^{n}(M,M^{\prime};G)$.

We begin by defining a family of sets $\\{M_{n}\\}_{n\in\mathbb{N}}$ and
_boundary maps_ $\delta_{n,i}:M_{n}\to M_{n-1}$, where $i=1,\dots,n$ encoding
the structure of a partial monoid $M$.

######  Definition 3.2.1.

Let $K$ be a commutative partial monoid. $\\{K_{n}\\}_{n\geq 0}$ and
$\delta_{n,i}:K_{n}\to K_{n-1}$, where $n\geq 1,i=0,\dots,n$ are defined by
$K_{0}:=\\{()\\}$ and when $n\geq 1$

$\displaystyle K_{n}$ $\displaystyle:=\\{(k_{1},k_{2},\cdots,k_{n})\in
K^{n}\mid k_{1}+k_{2}+\cdots+k_{n}\text{ is defined}\\}$ (3.53)
$\displaystyle\delta_{n,i}$
$\displaystyle::=(k_{1},\dots,k_{n})\mapsto(k_{1},\dots,k_{i-1},k_{i}+k_{i+1},k_{i+2},\dots,k_{n})$
(3.54)

By considering the set of functions $f:M_{n}\to G$ that vanish on
$M^{\prime}_{n}\subset M_{n}$ we define the relative co-chain complex

${0}$${C^{0}(M,M^{\prime};G)}$${C^{1}(M,M^{\prime};G)}$${C^{2}(M,M^{\prime};G)}$${\cdots}$$\scriptstyle{d^{-1}:=0}$$\scriptstyle{d^{0}}$$\scriptstyle{d^{1}}$$\scriptstyle{d^{2}}$
(3.55)

######  Definition 3.2.2.

Let $G$ be a group, $M$ a partial monoid, and $M^{\prime}\subset M$ a sub
partial monoid.

  1. 1.

The _relative $n$-cochains_, denoted by $C^{n}(M,N;G)$, is the commutative
group of assignments $f:M_{n}\to G$ that vanish on $M^{\prime}_{n}$.

$\displaystyle C^{n}(M^{\prime},M;G)$ $\displaystyle:=\\{f:M_{n}\to G\mid
f\rvert_{{M^{\prime}}_{n}}=0\\}$ (3.56)

  2. 2.

The $n$’th coboundary map, denoted by $d^{n}$ is the following homomorphism
from the relative $n$-cochains to relative $(n-1)$-cochains

$\displaystyle d^{n}$ $\displaystyle:C^{n}(M^{\prime},M;G)\to
C^{n+1}(M^{\prime},M;G)$ (3.57) $\displaystyle d^{n}(f)$
$\displaystyle:=(m_{1},\dots,m_{n})\mapsto\sum_{i=0}^{n}(-1)^{i}f(\delta_{n,i}(m_{1},\dots,m_{n}))$
(3.58)

The relative cohomology groups $H^{n}(M,M^{\prime};G)$ are the cohomology
groups of this co-chain complex. To verify that this in fact defines a co-
chain complex we need to verify that $d^{n+1}\circ d^{n}=0$. This can be done
by a straightforward computation. In our case, it is only necessary to verify
this for the maps

$\displaystyle d^{2}(f)(m_{1},m_{2},m_{3})$
$\displaystyle=f(m_{2},m_{3})-f(m_{1}+m_{2},m_{3})+f(m_{1},m_{2}+m_{3})-f(m_{1},m_{2})$
(3.59) $\displaystyle d^{1}(f)(m_{1},m_{2})$
$\displaystyle=f(m_{2})-f(m_{1}+m_{2})+f(m_{1})$ (3.60) $\displaystyle d^{0}$
$\displaystyle=0$ (3.61)

which is easily done.

######  Definition 3.2.3.

Let $G$ be a commutative group $M$ a commutative partial monoid and
$M^{\prime}\subset M$ a sub partial monoid.

  1. 1.

The _relative $n$-cocycles_ $Z^{n}(M,N;G):=\ker{d^{n}}$ is the kernel of
$d^{n}:C^{n}(K,M;G)\to C^{n-1}(K,M;G)$.

  2. 2.

The _relative $n$-coboundaries_ is the image
$B^{n}(M,N;G):=\text{im}\,d^{n-1}$ of $d^{n}:C^{n}(K,M;G)\to C^{n-1}(K,M;G)$.

  3. 3.

The _relative cohomology group_ $H^{n}(K,M;G):=Z^{n}(K,M;G)/B^{n}(K,M;G)$ is
the quotient of the relative $n$-cocycles over the relative $n$-coboundaries.

####  3.2.2 The obstruction to extending a local splitting

Let $B=(N,\theta,j)$ be a $G$-bundle over a partial monoid $M$,
$M^{\prime}\subset M$ a sub partial monoid, and $r^{\prime}:M^{\prime}\to
N^{\prime}$ a right splitting of the restriction $B\rvert_{M^{\prime}}$ of $B$
to $M^{\prime}$.

To define the cohomological obstruction $\mu(r^{\prime})\in
H^{2}(M,M^{\prime};G)$ we first choose a function $\eta:M\to N$, not
necessarily a homomorphism, such that $j\circ\eta=\text{id}_{M}$ and
$\eta\rvert_{M^{\prime}}=r^{\prime}$. $\eta$ is not necessarily a homomorphism
but because $j\circ\eta=\text{id}_{M}$ there is for every $m_{1},m_{2}\in M$
some $g\in G$ such that
$\eta(m_{1}+_{M}m_{2})=g\cdot(\eta(m_{1})+_{M}\eta(m_{2}))$. Because $\theta$
is free this $g$ is unique.

######  Definition 3.2.4.

Let $B=(N,j,\theta)$ be an $G$-bundle over a partial monoid $M$,
$M^{\prime}\subset M$ a sub partial monoid, and $\eta:M\to N$ a function such
that $\eta\circ j=\text{id}_{M}$. Write $\Delta\eta:M_{2}\to G$ for the unique
function satisfying

$\displaystyle\eta(m_{1}+m_{2})=\Delta\eta\,(m_{1},m_{2})\cdot(\eta(m_{1})+\eta(m_{2}))$
(3.62)

for all $(m_{1},m_{2})\in M_{2}$.

$\Delta\eta$ can be thought of as measuring the failure of $\eta$ to be a
splitting because $\eta$ is a homomorphism if and only if $\Delta\eta=0$. We
define $\mu(r^{\prime})$ to be the cohomology class of $\Delta\eta$.

######  Definition 3.2.5.

Let $B=(N,j,\theta)$ be an $G$-bundle over $M$, $M^{\prime}\subset M$ a sub-
partial monoid, and $r^{\prime}:M^{\prime}\to N^{\prime}$ a right splitting of
$B\rvert_{M^{\prime}}$. The _obstruction to $r^{\prime}$_, is the cohomology
class

$\displaystyle\mu(r^{\prime}):=[\Delta\eta]\in H^{2}(M^{\prime},M^{\prime};A)$
(3.63)

where $\eta:M\to N$ is any function such that
$\eta\rvert_{M^{\prime}}=r^{\prime}$ and $j\circ\eta=\text{id}_{M}$.

For this to be well defined we need to check that $\Delta\eta$ is a relative
co-cycle and that the cohomology class $[\Delta\eta]$ is independent of the
choice of $\eta$.

######  Lemma 3.2.1.

Let $B=(N,j,\theta)$ be an $A$-bundle over a commutative partial monoid $M$,
$M^{\prime}\subset M$ a sub partial monoid, and $r$ a right splitting of the
restricted bundle $B\rvert_{M^{\prime}}$.

  1. 1.

$\Delta\eta\in Z^{2}(M^{\prime},M;A)$ for any $\eta:M\to N$ such that
$\eta\rvert_{M^{\prime}}=r^{\prime}$ and $j\circ\eta=\text{id}_{M}$.

  2. 2.

$(\Delta\eta-\Delta\eta^{\prime})\in B^{2}(M^{\prime},M;A)$ for any two
$\eta,\eta^{\prime}:M^{\prime}\to N^{\prime}$ such that
$\eta\rvert_{M^{\prime}}=\eta^{\prime}\rvert_{M^{\prime}}=r^{\prime}$ and
$j\circ\eta=j\circ\eta^{\prime}=\text{id}_{M}$.

###### Proof.

For 1. we first have to show that $\Delta\eta$ is a _relative_ cochain, that
is, that $\Delta\eta$ vanishes on $(M_{2}^{\prime})$, and secondly that

$\displaystyle\Delta\eta\,(m_{2},m_{3})-\Delta\eta\,(m_{1}+m_{2},m_{3})+\Delta\eta\,(m_{1},m_{2}+m_{3})-\Delta\eta\,(m_{1},m_{2})=0$
(3.64)

for all $(m_{1},m_{2},m_{3})\in M_{3}$. That $\Delta\eta$ vanishes on
$M_{2}^{\prime}$ is clear because its restriction is a homomorphism. For the
second part we use that $m_{1}+m_{2}+m_{3}$ can be written as both
$m_{1}+(m_{2}+m_{3})$ and $(m_{1}+m_{2})+m_{3}$.

$\displaystyle\eta(m_{1}+(m_{2}+m_{3}))$
$\displaystyle=\Delta\eta\,(m_{1},m_{2}+m_{3})\cdot(\eta(m_{1})+\eta(m_{2}+m_{3}))$
$\displaystyle=(\Delta\eta\,(m_{1},m_{2}+m_{3})+\Delta\eta\,(m_{2},m_{3}))\cdot(\eta(m_{1})+\eta(m_{2})+\eta(m_{3}))$

and similarly

$\displaystyle\eta((m_{1}+m_{2})+m_{2})$
$\displaystyle=(\Delta\eta\,(m_{1}+m_{2},m_{3})+\Delta\eta\,(m_{1},m_{2}))\cdot(\eta(m_{1})+\eta(m_{2})+\eta(m_{3}))$

Because the two terms are equal and the action is free

$\displaystyle\Delta\eta\,(m_{1},m_{2}+m_{3})+\Delta\eta\,(m_{2},m_{3})=\Delta\eta\,(m_{1}+m_{2},m_{3})+\Delta\eta\,(m_{1},m_{2})$
(3.65)

as required.

For 2. suppose that $\eta,\eta^{\prime}$ are two sections that extend $r$. We
have to show that there is some $\gamma:C^{1}(M^{\prime},M;A)$ such that

$\displaystyle\Delta\eta\,(m_{1},m_{2})-\Delta\eta^{\prime}\,(m_{1},m_{2})=\gamma(m_{1})-\gamma(m_{1}+m_{2})+\gamma(m_{2})$
(3.66)

for all $(m_{1},m_{2})\in M_{2}$. Let $\gamma:M\to A$ be the unique function
such that

$\eta=m\mapsto s(m)\cdot\eta^{\prime}(m)$ (3.67)

Because $\eta,\eta^{\prime}$ both extend $r$ we have $s\rvert_{M^{\prime}}=0$
and so $\gamma$ is a relative cochain, $\gamma\in C^{1}(M^{\prime},M;A)$.
Expanding $\eta(m_{1}+m_{2}),\eta(m_{1}),\eta(m_{2})$ in terms of $\gamma$ and
$\eta^{\prime}$ gives

$\displaystyle\eta(m_{1}+m_{2})$
$\displaystyle=\Delta\eta\,(m_{1},m_{2})\cdot(\eta(m_{1})+\eta(m_{2}))$ (3.68)
$\displaystyle=(\Delta\eta\,(m_{1},m_{2})+s(m_{1})+s(m_{2}))\cdot(\eta^{\prime}(m_{1})+\eta^{\prime}(m_{2}))$
(3.69)

and

$\displaystyle\eta(m_{1}+m_{2})$
$\displaystyle=s(m_{1}+m_{2})\eta^{\prime}(m_{1}+m_{2})$ (3.70)
$\displaystyle=(s(m_{1}+m_{2})+\Delta\eta^{\prime}\,(m_{1},m_{2}))\cdot(\eta^{\prime}(m_{1})+\eta^{\prime}(m_{2}))$
(3.71)

hence

$\displaystyle\Delta\eta\,(m_{1},m_{2})+s(m_{1})+s(m_{2})=s(m_{1}+m_{2})+\Delta\eta^{\prime}\,(m_{1},m_{2})$
(3.72)

as required. ∎

Observe that the obstruction is _sound_ in the sense that if $r^{\prime}$ can
be extended to a right splitting $r:M\to N$ then $[\Delta\eta]=0$. This is
true because if such an $r$ exists then the cohomology class $[\Delta\eta]$ is
equal to the cohomology class $[\Delta r]$ had we instead chosen $r$. Because
$r$ is a homomormphism $\Delta r=0$ and so $[\Delta r]=0$ as required.

We now show that the obstruction in fact is complete in the sense that
$\mu(r^{\prime})=0$ if and only if $r^{\prime}$ can be extended globally.

######  Theorem 3.2.1.

Let $B=(N,j,\theta)$ be a $G$-bundle over a partial monoid $M$,
$M^{\prime}\subset M$ a sub partial monoid, and $r$ a right splitting of
$B\rvert_{M^{\prime}}$. There exists a right splitting $r:M\to N$ such that
$r\rvert_{M^{\prime}}=r^{\prime}$ if and only if $\mu(r^{\prime})=0$.

###### Proof.

We have already explained that $\mu(r^{\prime})=0$ if $r^{\prime}$ can be
extended globally. For the converse suppose that $\mu(r^{\prime})=0$.

We extend $r^{\prime}$ to a global right splitting $r:M\to N$ by first
choosing a function $\eta:M\to N$ such that $\eta\circ j=\text{id}_{M}$ and
$\eta\rvert_{M^{\prime}}=r^{\prime}$. Because $[\Delta\eta]=0$ there is a
unique $\gamma\in C^{1}(M^{\prime},M;A)$ such that $\Delta\eta=d^{1}(\gamma)$.
We define $r$ by

$\displaystyle r(m)::=-\gamma(m)\cdot\eta(m)$ (3.73)

for all $m\in M$. To see that $r$ is a homomorphism take $m_{1},m_{2}\in M$
such that $m_{1}+_{M}m_{2}$ is defined. We have

$\displaystyle r(m_{1}+m_{2})$
$\displaystyle=-\gamma(m_{1}+m_{2})\cdot\eta(m_{1}+m_{2})$ (3.74)
$\displaystyle\eta(m_{1}+m_{2})$
$\displaystyle=\Delta\eta\,(m_{1},m_{2})\cdot(\eta(m_{1})+\eta(m_{2}))$ (3.75)
$\displaystyle\Delta\eta\,(m_{1},m_{2})$
$\displaystyle=d^{1}(\gamma)(m_{1},m_{2})=\gamma(m_{1})-\gamma(m_{1}+m_{2})+\gamma(m_{2})$
(3.76)

Hence

$\displaystyle r(m_{1}+m_{2})$
$\displaystyle=-\gamma(m_{1}+m_{2})\cdot\eta(m_{1}+m_{2})$ (3.77)
$\displaystyle=(-\gamma(m_{1}+m_{2})+\Delta\eta\,(m_{1},m_{2}))\cdot(\eta(m_{1})+\eta(m_{2}))$
(3.78)
$\displaystyle=(-\gamma(m_{1}+m_{2})+\gamma(m_{1})-\gamma(m_{1}+m_{2})+\gamma(m_{2}))\cdot(\eta(m_{1})+\eta(m_{2}))$
(3.79) $\displaystyle=r(m_{1})+r(m_{2})$ (3.80)

as required. ∎

###  3.3 Measurement scenarios with bundle structure

We now introduce a class of measurement scenarios and empirical models
generalising the state-dependent and state independent empirical models
$\mathcal{S}_{\mathcal{O}},\mathcal{S}_{\mathcal{O},\psi}:(\mathcal{O},\mathcal{M},\mathbb{Z}_{d})$
associated with a closed set of Weyl operators $\mathcal{O}\subset P_{n,d}$
and a state $\psi$. We first give an abstract description of the structure of
these models. In Section 3.3.1 we explain that for models of this type a test
for (non) contextuality is to extend a local _homomorphism_ to a global
homomorphism. We give two examples, based on GHZ and Mermin’s square. In
Section 3.3.2 we show that these scenarios can be given a bundle structure,
and that the cohomological obstruction to extending local splittings can be
used to detect contextuality.

Let $\mathcal{O}\subset P_{n,d}$ be a closed set of Weyl operators.
$\mathcal{O}$ contains the identity and is closed under products of commuting
operators. Restricting the group product of $P_{n,d}$ to pairs of commuting
operators , therefore, gives $\mathcal{O}$ the structure of a partial monoid.
The set of operators $\mathcal{O}$ is also closed under the
$\mathbb{Z}_{d}$-action

$\displaystyle\Omega:\mathbb{Z}_{d}\times\mathcal{O}\to\mathcal{O}:=(p,O)\mapsto\omega^{p}O$
(3.81)

where $\omega:=e^{2\pi i/d}$. Note that $\Omega$ is compatible (Definition
3.1.4) with the partial monoid product because

$\displaystyle\omega^{p}O\omega^{p^{\prime}}O^{\prime}=\omega^{p+p^{\prime}}OO^{\prime}$
(3.82)

for all $p\in\mathbb{Z}_{d}$ and commuting $O,O^{\prime}\in\mathcal{O}$.

Let $C\subset\mathcal{O}$ be a maximal context of pairwise commuting
operators. $C$ is then a _submonoid_ of $\mathcal{O}$, i.e. all products are
defined. Because two operators $\omega^{q}O$ and $O$ that differ by some
$\omega^{q}$ commute we also have that $C$ is closed under the action
$\Omega$. Write $\Omega_{C}$ for the restriction of $\Omega$ to $C$. We now
observe that any value assignment $s:C\to\mathbb{Z}_{d}$ that is consistent
with quantum mechanics preserves the action $\Omega_{C}$.

######  Lemma 3.3.1.

Let $\mathcal{O}\subset P_{n,d}$ be a closed set of Weyl operators and
$C\subset\mathcal{O}$ a maximal context. A joint outcome assignment
$s:C\to\mathbb{Z}_{d}$ that is consistent with quantum mechanics is an _action
homomorphism_ (Definition 3.1.6) from $\Omega_{C}$ to the action
$\theta_{\mathbb{Z}_{d}}$ of $\mathbb{Z}_{d}$ on itself.

###### Proof.

A measurement of a Weyl operator $M$ with outcome $q$ correspond to the
$\omega^{q}$ eigenvalue. Let $s:C\to\mathbb{Z}_{d}$ be an outcome assignment
and suppose that $s$ is consistent with quantum mechanics. Let $M_{1},M_{2}\in
C$. There is then some state $\psi$ such that $\psi$ is an eigenvector of
$M_{1},M_{2},M_{1}M_{2}$ with eigenvalues $s(M_{1}),s(M_{2}),s(M_{1}M_{2})$.

$\displaystyle M_{1}\lvert\psi\rangle$
$\displaystyle=\omega^{s(M_{1})}\lvert\psi\rangle$ (3.83) $\displaystyle
M_{2}\lvert\psi\rangle$ $\displaystyle=\omega^{s(M_{2})}\lvert\psi\rangle$
(3.84) $\displaystyle M_{1}M_{2}\lvert\psi\rangle$
$\displaystyle=\omega^{s(M_{1}M_{2})}\lvert\psi\rangle$ (3.85)

Using the first two equations we have

$\displaystyle
M_{1}M_{2}\lvert\psi\rangle=\omega^{s(M_{1})}\omega^{s(M_{2})}\lvert\psi\rangle$
(3.87)

Comparing this to the third equations we have
$s(M_{1}M_{2})=s(M_{1})+s(M_{2})$. That $s(I)=0$ is clear because $I$ only has
one eigenvalue $1$ which is identified with $0$. Finally, if we multiply a
Weyl operator $M$ with a scalar $\omega^{q}$, then the effect is to permute
the eigenvalues, hence $s(\omega^{q}M)=q+s(M)$. ∎

From this it follows that both the state-dependent and state independent
empirical models
$\mathcal{S}_{\mathcal{O}},\mathcal{S}_{\mathcal{O},\psi}:(\mathcal{O},\mathcal{M}_{\mathcal{O}},\mathbb{Z}_{d})$
are instances of the following definition.

######  Definition 3.3.1.

Let $(X,\mathcal{M},G)$ be a measurement scenario equipped with the following
additional structure:

  1. 1.

The outcomes $G$ is a commutative group.

  2. 2.

Each maximal context $C\in\mathcal{M}$ is a commutative monoid with a
compatible action $\theta_{C}:G\times C\to C$, such that for all maximal
contexts $C,C^{\prime}\in\mathcal{M}$, $g\in G$, $x,x^{\prime}\in C\cap
C^{\prime}$:

$\displaystyle 0_{C}$ $\displaystyle=0_{C^{\prime}}$ (3.88) $\displaystyle
x+_{C}x^{\prime}$ $\displaystyle=x+_{C^{\prime}}x^{\prime}$ (3.89)
$\displaystyle\theta_{C}(g,x)$ $\displaystyle=\theta_{C^{\prime}}(g,x)$ (3.90)

An _empirical model_ $\mathcal{S}:(X,\mathcal{M},G)$ is an empirical model (in
the usual sense), such that every local section $s\in\mathcal{S}(C)$ is an
action homomorphism from $\theta_{C}$ to the action $\theta_{G}$ of $G$ on
itself.

####  3.3.1 Detecting contextuality with homomorphisms

Suppose that $\mathcal{S}:(X,\mathcal{M},G)$ is an empirical model and
measurement scenario with the additional structure of Definition 3.3.1. We
first observe that the monoid structures on the contexts $C\in\mathcal{M}$ and
the actions $\theta_{C}$ “glue together” to define a _partial_ monoid and
compatible action on $X$.

$\displaystyle\theta(g,x)$ $\displaystyle:=\theta_{C}(g,x)$ (3.91)
$\displaystyle 0$ $\displaystyle:=0_{C}$ (3.92) $\displaystyle x+x^{\prime}$
$\displaystyle:=x+_{C}x^{\prime}$ (3.93)

for any $C\in\mathcal{M}$, $x,x^{\prime}\in C$, and $g\in G$. That this is
well defined follows from the compatibility conditions in Definition 3.3.1).

Note that in the case of a closed set of Weyl operators $\mathcal{O}\subset
P_{n,d}$ the partial monoid structure on $\mathcal{O}$ is the structure given
by gluing together the monoid structure on each maximal context. This is the
case because two operators $O,O^{\prime}\in\mathcal{O}$ commute if and only if
they are both contained in a maximal context $C\subset\mathcal{O}$. As a
partial monoid $\mathcal{O}$ is therefore completely defined by its
restriction to the maximal submonoids $C\subset\mathcal{O}$.

Because the action $\theta$ and partial monoid structure on $X$ are completely
determined by the monoids and actions on the maximal contexts, it follows that
$s:X\to G$ is an action homomorphism from $\theta$ to $\theta_{G}$ if and only
if $s\rvert_{C}$ is an action homomorphism from $\theta_{C}$ to $\theta_{G}$
for all maximal contexts $C\in\mathcal{M}$. We can therefore consider the
problem of extending a local action homomorphism $s^{\prime}\in\mathcal{S}(C)$
defined on a maximal context $C\in\mathcal{M}$ as a test for contextuality.

This test is sound, but not necessarily complete. There can be action
homomorphisms $s:X\to G$ that are not global sections of $\mathcal{S}$.

We now give two examples, showing that in the case of GHZ and Mermin’s square
the homomorphism condition detects contextuality.

######  Example 3.3.1 (Mermin’s square).

Let $X\subset P_{2}$ be any set of Pauli measurements that is closed under
products of commuting measurements and contains the measurements displayed in
Mermin’s square. We consider the state independent model
$\mathcal{S}_{X}:(X,\mathcal{M},\mathbb{Z}_{2})$ which in this case satisfies
Definition 3.3.1.

Observe that equations (1)-(6) induced by Mermin’s square all can be
rearranged to be on the form

$M_{1}\oplus M_{2}=M_{1}M_{2}$

for $M_{1},M_{2}\in X$ with $M_{1}M_{2}=M_{2}M_{1}$. That the equations are
mutually inconsistent therefore literally says that there is no homomorphism
from $X$ to $\mathbb{Z}_{2}$.

GHZ is an example of state-dependent contextuality. We first show that the set
of operators whose outcome when measuring a given state is deterministic is a
submonoid of the total partial monoid.

######  Lemma 3.3.2.

Let $\mathcal{O}\subset P_{n,d}$ be a closed set of $n$-qudit Weyl operators.
Let $\psi$ be a state and $\mathcal{O}_{\psi}\subset\mathcal{O}$ the subset of
operators whose outcome on $\psi$ is deterministic

$\displaystyle\mathcal{O}_{\psi}:=\\{M\in\mathcal{O}\mid
M\lvert\psi\rangle=\omega^{q}\lvert\psi\rangle,\text{ for some
$q\in\mathbb{Z}_{d}$}\\}$ (3.94)

$\mathcal{O}_{\psi}$ is a sub monoid of $\mathcal{O}$.

###### Proof.

That the identity operator $I$ is contained in $\mathcal{O}_{\psi}$ is clear.
If $M,M^{\prime}\in\mathcal{O}$ with outcomes $q,q^{\prime}$ then
$MM^{\prime}$ has outcome $q+q^{\prime}$. ∎

In the case of state-dependent contextuality, we try to extend the unique
value assignment consistent with $\psi$.

######  Example 3.3.2 (GHZ).

Let
$X:=\bigotimes_{i=1}^{3}\pm\\{\sigma_{{x}},\sigma_{{y}},\sigma_{{z}},I\\}$.
First note that the state-dependent model
$\mathcal{S}_{X,\text{GHZ}}:(X,\mathcal{M},\mathbb{Z}_{2})$ is an instance of
Definition 3.3.1 because $X$ is closed under commuting products and contains
$\pm I$. Next, consider the set $X_{\text{GHZ}}$ of measurements whose outcome
is uniquely determined by $\lvert\text{GHZ}\rangle$ and observe that the
equations in the GHZ example 2.2.1 are all of the form

$M_{1}\oplus M_{2}\oplus M_{3}=s_{\text{GHZ}}(M_{1}M_{2}M_{3})$

where $M_{1},M_{2},M_{3}\in X$ are compatible, $M_{1}M_{2}M_{3}\in
X_{\text{GHZ}}$, and $s_{\text{GHZ}}(M_{1}M_{2}M_{3})$ is the unique outcome
that is consistent with $\lvert\text{GHZ}\rangle$. That the equations are
mutually inconsistent therefore ensures that there is no global action
homomorphism $g:X\to\mathbb{Z}_{2}$ whose restriction to $X_{\text{GHZ}}$ is
$s_{\text{GHZ}}$. It follows that if $C\in\mathcal{M}$ is any context that
contains $X_{\text{GHZ}}$ then there is no $s\in\mathcal{S}_{X,\text{GHZ}}(C)$
that can be extended to a global action homomorphism. Note that such a context
exists because the maximal submonoids of $X$ are the contexts and by Lemma 4.1
$X_{\text{GHZ}}$ is a monoid.

####  3.3.2 The cohomological obstruction

We now generalise the cohomological obstruction of Okay et al. to any
empirical model with the structure of Definition 3.3.1. Let
$\mathcal{S}:(X,\mathcal{M},G)$ be an empirical model and measurement scenario
according to Definition 3.3.1. We first show that the scenario comes with the
structure of a bundle over a partial monoid.

At $X$, and at each maximal context $C\in\mathcal{M}$ we take the quotient
partial monoid with respect to the actions $\theta$, $\theta_{C}$.

######  Definition 3.3.2.

Let $G$ be a group, $M$ a partial monoid, and $\theta:G\times M\to M$ an
action of $G$ on $M$. The _quotient partial monoid_ is the set of orbits
$M/\theta$ with identity and product defined by

$\displaystyle 0_{M/G}$ $\displaystyle:=[0_{M}]_{\theta}$ (3.95)
$\displaystyle[m_{1}]_{\theta}+_{M/G}[m_{2}]$
$\displaystyle:=[m_{1}+_{M}m_{2}]_{\theta}$ (3.96)

for all $m_{1},m_{2}$ such that $m_{1}+_{M}m_{2}$ are defined.

Observe that the product operation of $M/\theta$ is well defined because
$\theta:G\times M\to M$ is a homomorphism. For all $a_{1},a_{2}\in A$ and
$m_{1},m_{2}\in M$ such that $m_{1}+_{M}m_{2}$ is defined we have $(a_{1}\cdot
m_{1}+_{M}a_{2}\cdot m_{2}=(a_{1}+_{A}a_{2})\cdot(m_{1}+_{M}m_{2})$. Therefore

$\displaystyle[a_{1}\cdot m_{1}]+_{M/G}[a_{2}\cdot
m_{2}]=[(a_{1}+_{A}a_{2})\cdot(m_{1}+_{M}m_{2})]$ (3.97)

as required.

$X$ is then a bundle over the quotient partial monoid $X/\theta$, with action
$\theta$ and projection map $[\\_]_{\theta}:X\to X/\theta$, and for each
maximal context $C\in\mathcal{M}$ the monoid $C$ is a bundle over
$C/\theta_{C}$ with action $\theta_{C}$ and projection map
$[\\_]_{\theta_{C}}:C\to C/\theta_{C}$. That each local section
$s\in\mathcal{S}(C)$ is an action homomorphism from $\theta_{C}$ to
$\theta_{G}$ means that it is a left splitting of the bundle. The
cohomological obstruction for $s$ is the obstruction to extending the right
splitting $\mathcal{R}(s)$ to a global right splitting of the bundle $X$.

######  Definition 3.3.3.

Let $\mathcal{S}:(X,\mathcal{M},G)$ be a measurement scenario and empirical
model satisfying Definition 3.3.1. For any maximal context $C\in\mathcal{M}$
and $s\in\mathcal{S}(C)$ the cohomological obstruction is the obstruction
$\mu(\mathcal{R})\in H^{2}(X/\theta,C/\theta_{C};G)$ for the right splitting
$\mathcal{R}$ to extend to a global splitting.

Because the homomorphism test for contextuality is not necessarily complete
the cohomological obstruction is also not necessarily complete. However, from
the examples in the previous section we have that it detects contextuality in
the case of GHZ and Mermin’s square.

###  3.4 Comparing two obstructions

We conclude this chapter by comparing the topological obstruction of Okay et
al. 3.3.1 to the Čech cohomology obstruction. The Čech cohomology obstruction
and the topological obstruction are different in the type of algebraic
structure they are defined with. The topological approach relies upon a pre-
existing structure in the measurement scenario and empirical model. The Čech
cohomology approach does not require any pre-existing structure, instead, it
uses a free construction to give the required structure to any empirical
model.

At first glance, it might be surprising that any interesting structure is left
behind by this free construction. An explanation for why the Čech cohomology
obstruction detects contextuality is that many examples of contextuality in
quantum mechanics are of the AvN type. For the examples, GHZ and magic square,
where we have shown that the topological approach also detects contextuality.
The question is then if there are instances of contextuality that are detected
by the topological approach, but not the Čech cohomology approach. We now show
that this is not the case.

Recall that a false negative of the Čech cohomology approach occurs when a
local section $s$ can be extended to a compatible family of the pre-sheaf
$F_{\mathbb{Z}}\mathcal{S}$. If an empirical model $\mathcal{S}$ satisfies
Definition 3.3.1 then each local section in this formal linear combination is
an action homomorphism. Because homomorphisms are closed under affine
combinations we can collapse the formal affine combination to a global
splitting of the bundle.

######  Theorem 3.4.1.

Let $\mathcal{S}:(X,\mathcal{M},G)$ be an empirical model of Definition X. Let
$l\in\mathcal{S}(C)$ be a local section. If the Čech cohomology obstruction
$\gamma(l)$ vanishes, then the topological obstruction $\mu(l)$ vanishes:

$\displaystyle\gamma(s_{0})=0\implies\mu(s_{0})=0$ (3.98)

###### Proof.

Suppose that $s_{0}\in\mathcal{S}(C_{0})$ is a local section such that the
Čech cohomology obstruction vanishes, $\gamma(s_{0})=0$. We need to show that
$s_{0}$ extends to a global right splitting.

Recall that if the measurement cover is connected and $\gamma(s_{0})=0$ then
there is some compatible family $\\{r_{C}\in
F_{\mathbb{Z}}\mathcal{S}(C)\\}_{C\in\mathcal{M}}$ such that $r_{C_{0}}=1\cdot
s_{0}$. Now, any measurement cover by commutative monoids is connected because
the identity element is contained in all contexts. We can therefore take such
a family $\\{r_{C}\\}_{C\in\mathcal{M}}$. Observe now that any such family in
fact is a compatible family of formal affine combinations: For any
$C\in\mathcal{M}$

$\sum_{s\in\mathcal{S}(C)}r_{C}(s)\cdot s\rvert_{C\cap
C_{0}}=r_{C}\rvert_{C\cap C_{0}}=r_{C_{0}}\rvert_{C\cap C_{0}}=1\cdot
s_{0}\rvert_{C\cap C_{0}}$

hence $\sum_{s\in\mathcal{S}(C)}r_{C}(s)=1$.

We now use the unique module action111 i.e. $0\cdot a=0$, and for $n\geq 1$:
$n\cdot a:=a+a+\cdots+a$ ($n$ times) and $-n\cdot a=-(n\cdot a)$. of
$\mathbb{Z}$ on $A$ to collapse this compatible family to a function $g:X\to
A$.

$g(x):=\sum_{s\in\mathcal{S}(C)}r_{C}(s)\cdot s(x),\quad\text{where
$C\in\mathcal{M}$ is any context with $x\in C$}$

Because the set of splittings is closed under affine combinations this
function is in fact a splitting that furthermore extends $s_{0}$. ∎

Another point is that the topological approach uses the equivalence between
right and left splittings. A question we can ask is what the cohomology
classes actually mean.

##  Chapter 4 From contextuality to shallow circuits: a general construction
of quantum advantage

In this chapter, we present a generalised version of Bravyi, Gosset, and
König’s quantum advantage result with shallow circuits. The quantum circuit
$\\{Q_{n}\\}_{n\in\mathbb{N}}$ and the computational problem
$\\{\text{2D-GHZ(n)}\\}_{n\in\mathbb{N}}$ introduced by BGK are relatively
simple to define. Their main technical contribution is the technique used to
prove the classical bound. We start by explaining how this technique can be
recast in the sheaf theoretic framework.

The quantum circuit $Q_{n}$ defines a mapping from inputs to distributions
over outputs $\tilde{Q}_{n}::x\mapsto\sum_{y}\tilde{Q}(x,y)\cdot y$. We can
think of this mapping as an empirical model for a multipartite scenario.
$\tilde{Q}_{n}$ is related to the strategy $e_{\text{GHZ}}$ for the GHZ game
by a simulation $s_{n}$.

$\displaystyle(s_{n})_{*}(\tilde{Q}_{n})=e_{\text{GHZ}}$ (4.1)

The 2D-GHZ problem is the pullback $(s_{n})^{*}(\text{GHZ})$ of the GHZ-game
across $s_{n}$. Because the strategy $e_{\text{GHZ}}$ solves the GHZ-game
perfectly it, therefore, follows that $Q_{n}$ also solves the GHZ game
perfectly.

$\displaystyle
p_{S}(Q_{n},\text{2D-GHZ})=p_{S}((s_{n})_{*}(\tilde{Q}_{n}),\text{GHZ})=1$
(4.2)

We can similarly think of a classical shallow circuit
$\\{C_{n}\\}_{n\in\mathbb{N}}$ as defining a family of empirical models
$\\{\tilde{C}_{n}\\}_{n\in\mathbb{N}}$. This is strictly speaking not true
because $\tilde{C}_{n}::x\mapsto\sum_{y}\tilde{C}_{n}(x,y)\cdot y$ does not
necessarily satisfy the no-signaling assumption.

Recall the resource inequality

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

relating the success probability of an empirical model $e$ on a non-local game
$\Phi$ to the classical bound $\gamma$ and the contextual fraction
$\text{CF}(e)$.

Using this inequality we can bound the success probability of $C_{n}$ on
$\text{2D-GHZ}(n)$ in terms of the contextual fraction of the pushforward
$(s_{n})_{*}(\tilde{C}_{n})$.

$\displaystyle
p_{S}(C_{n},\text{2D-GHZ}(n))=p_{S}((s_{n})_{*}(\tilde{C}_{n}),\text{GHZ})\leq
3/4+\text{CF}((s_{n})_{*}(\tilde{C}_{n}))$ (4.4)

The technically most involved part of their result is to establish a bound on
$\text{CF}((s_{n})_{*}(\tilde{C}_{n}))$. To do this they combine two results.
The simulation $s_{n}$ is a probability distribution over a deterministic
simulation $t$ for each choice of players $v_{A},v_{B},v_{C}$ and paths
$u_{\text{AB}},u_{\text{BC}},u_{\text{CA}}$. BGK first gives a combinatorial
condition involving the paths and the circuit $C$ ensuring that the
pushforward $t_{*}(\tilde{C}_{n})$ is non-contextual. They then prove that
when the paths are chosen sufficiently uniformly then the probability of this
condition being satisfied is high.

####  4.0.1 Structure of chapter

In Section 4.1 we give some elementary background on circuits, and we make the
idea that circuits can implement empirical models and strategies for non-local
games precise. In Section 4.2 we present a protocol based on teleportation
that allows a number of agents to implement measurements on a single-qudit
state at arbitrarily long distances along a line. In Section 4.3 we generalise
the construction from Section 4.2 to a protocol that allows us to simulate
measurements in a distributed way. In Section 4.4 we show that the distributed
simulation protocol can be used to construct non-local games that are solved
by quantum circuit of small depth and fan-in. In Section 4.5.2 we restate
BGK’s technique for proving their classical bound in the sheaf theoretic
framework, and we use it to derive a bound for the games introduced in Section
4.4. In Section 4.6 we put everything together and show that the construction
can be used to derive unconditional quantum advantage results with shallow
circuits from any non-local game.

###  4.1 Circuits

(a)

(b)

(c)

Figure 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).

A _circuit_ can formally be defined as a directed acyclic graph whose nodes
are either input wires, output wires, or gates. The graph structure defines
the order of evaluation for the gates. To evaluate a circuit we first fix an
input value for each of the input wires, then evaluate the gates in the order
given by the graph, and finally return the values of the output wires.

Both the quantum and classical circuits that we work with have only classical
input and output wires. A quantum circuit additionally uses some number of
qudits initially prepared in the computational basis state. In a classical
circuit, gates are probabilistic. In a quantum circuit gates are classically
controlled unitaries and measurement gates.

The _depth_ of a circuit is the length of the longest path from an input to an
output. The fan-in of a gate is its number of inputs, and the _maximal fan-in_
of a circuit is the maximal fan-in over all of the gates. We say that a family
of circuits is shallow if it has both bounded depth and maximal fan-in.

######  Definition 4.1.1.

A _shallow circuit_ is a family of circuits $F=\\{F_{n}\\}_{n\in\mathbb{N}}$
for which there exists $K,D\in\mathbb{N}$ such that $F_{n}$ has depth at most
$D$ and maximal fan-in at most $K$ for all $n\in\mathbb{N}$.

The graph structure of a circuit restricts the possible dependencies between
input wires and output wires. These dependencies are captured by the
_lightcones_ of the circuit.

######  Definition 4.1.2.

Let $F$ be a circuit with input wires $\\{\text{in}_{i}\\}_{i\in I}$ labelled
by a set $I$ and output wires $\\{\text{out}_{j}\\}_{j\in J}$ labelled by a
set $J$.

  * •

The _forward lightcone_ of $i\in I$, denoted by
$\text{LC}_{F}^{\rightarrow}(i)$, is the set of output wires $j\in J$ such
that there is a path in $F$ from $\text{in}_{i}$ to $\text{out}_{j}$.

  * •

The _backward lightcone_ of $j\in J$, denoted by
$\text{LC}_{F}^{\leftarrow}(j)$, is the set of all input wires $i\in I$ such
that there is path in $F$ from $\text{in}_{i}$ to $\text{out}_{j}$.

In a circuit $F$ of depth $D$ and maximal fan-in $K$ each output wire is
reachable from at most $K^{D}$ input wires,
${\left\lvert\text{LC}_{F}^{\leftarrow}(\text{out}_{i})\right\rvert}\leq
K^{D}$ for all output wires $\text{out}_{i}$. If a shallow circuit
$\\{F_{n}\\}_{n\in\mathbb{N}}$ has maximal depth $D$ and fan-in $K$ and
$F_{n}$ has $n$ inputs, then the fraction of inputs that can reach a given
output tends to zero as $n$ increases.

####  4.1.1 Circuit strategies

BGK observed that the quantum strategy for the GHZ game can be seen as a
simple circuit. Figure 4.2 shows a similar example from [BGKT20] based on the
Magic Square game. In this section, we define _circuit strategies_ for
cooperative games with one or more rounds. We then define the _behaviour_ of a
circuit, and we show that ideas like simulations and the contextual fraction
can be applied to these objects.

(a)

(b)

Figure 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.

We first consider the case of a single-round game. Let $S$ be a multipartite
scenario. A circuit strategy is a classical or quantum circuit with a
classical input wire and a classical output wire for each measurement site. In
a multipartite scenario, joint measurements specify at most one measurement
setting for each measurement site. The input to a circuit strategy consists of
a measurement setting for each wire, or a symbol “$\bullet$” denoting no
measurement. The output of the circuit consists of an output for each
measurement site that has been measured, or “$\bullet$” for the measurement
sites that have not been measured.

######  Definition 4.1.3.

Let $S=(I,X,Y)$ be a multipartite scenario. A (single-round) _circuit model_
is a classical or quantum circuit $F$ with an input wire $\text{in}_{i}$ and
an output wire $\text{out}_{i}$ for each measurement site $i\in I$, such that:

  * •

$\text{in}_{i}$ has type $X_{i}\sqcup\\{\bullet\\}$

  * •

When $F$ is evaluated and the input to $\text{in}_{i}$ is $\bullet$ then the
output of $\text{out}_{i}$ is also $\bullet$, otherwise if the input to
$\text{in}_{i}$ is $x\in X_{i}$ then the output of $\text{out}_{i}$ has type
$Y_{i,x}$.

We additionally allow circuit strategies to sample a random seed. Let $F$ be a
circuit strategy for a multipartite scenario $S=(I,X,Y)$. Given a joint
measurement $C$ we evaluate $F$ by setting each input wire $\text{in}_{i}$
where $C$ specifies a measurement setting to this value, and otherwise to
$\bullet$. We then read off the values of $\text{out}_{i}$ and return the
joint outcome $s\in\mathcal{E}_{S}(C)$ by setting $s(i,x)$ to the value of
output wire $i$. This defines a family of probability distributions
$\tilde{F}=\\{\tilde{F}(C)\in\mathcal{E}_{S}(C)\\}$ which we call the
_behaviour_ of $F$.

######  Definition 4.1.4.

Let $S$ be a multipartite scenario and $F$ a circuit strategy. For any context
$C$ of $S$ and local section $s\in\mathcal{E}_{S}(C)$ the probability
$\tilde{F}(C)(s)$ is the probability that the output of $\text{out}_{i}$ is
$y_{i}$ when the input to $\text{in}_{i}$ is $x_{i}$ for all $i\in I$, where

$\displaystyle x_{i}$ $\displaystyle:=\begin{cases}x,&\text{if $(i,x)\in
C$}\\\ \bullet,&\text{otherwise}\end{cases}$ (4.5) $\displaystyle y_{i}$
$\displaystyle:=\begin{cases}s(i,x),&\text{if $(i,x)\in C$}\\\
\bullet,&\text{otherwise}\end{cases}$ (4.6)

Figure 4.3:

and the random seed $z$ is sampled randomly.

Any quantum strategy for a non-local game can be seen as a circuit strategy.
Let $S=(I,X,Y)$ be a multipartite scenario, $e$ a quantum strategy for a non-
local game, using a multi-qudit state $\psi$ and a single-qudit measurement
$M_{i,x}$ for each measurement $(i,x)$ of $S$. We define the quantum circuit
strategy $Q_{\psi,M}$ to be the circuit with a single unitary gate $U_{\psi}$
that prepares the state $\psi$, and performs a classically controlled
$M_{i,x}$ measurement for each qudit and returns the outcomes. By definition
the behaviour of $Q_{\psi,M}$ is equivalent to the empirical model $e$

$\displaystyle\tilde{Q}_{\psi,M}(U)=e_{\psi,M}(U)$ (4.7)

for each measurement context $U$ of $S$.

We will now define circuit strategies for games with more than one round. An
$n$-round circuit strategy is a classical or quantum circuit $F$ with a
classical input wire and a classical output wire for each measurement site and
each of the $n$ rounds (Figure 4.5(b)). We require that the output wires for
round $j$ are not reachable from the input wires in round $j^{\prime}>j$.

######  Definition 4.1.5.

Let $S=(I,X,Y)$ be a multipartite scenario and $n\geq 1$. An $n$-round
_circuit strategy_ is a circuit $F$ with input wires
$\\{\text{in}_{i,j}\\}_{i\in I,j=1,\dots,n}$ and output wires
$\\{\text{out}_{i,j}\\}_{i\in I,j=1,\dots,n}$, such that:

  * •

Input wire $\text{in}_{i,j}$ has type $X_{i}$.

  * •

When $F$ is evaluated and the input to $\text{in}_{ij}$ is $\bullet$ then the
output of $\text{out}_{ij}$ is also $\bullet$, otherwise if the input to
$\text{in}_{ij}$ is $x\in X_{i}$ then the output of $\text{out}_{ij}$ has type
$Y_{i,x}$.

  * •

$\text{in}_{ij}$ is not reachable from $\text{out}_{i^{\prime}j^{\prime}}$
when $j^{\prime}\leq j$:
$\text{in}_{i,j}\notin\text{LC}_{F}^{\rightarrow}(\text{out}_{i^{\prime},j^{\prime}})$.

Interactive circuits can be thought of in two ways. If $i<i^{\prime}$ then
$\text{out}_{i,j}$ is not reachable from $\text{in}_{i^{\prime},j^{\prime}}$
for any $j,j^{\prime}$. It is therefore possible to partially evaluate the
circuit on the inputs in round $i$ without fixing the values for the inputs in
round $i^{\prime}$. Alternatively, we can think of the evaluation as being
performed by “plugging in” a classical circuit $C$ (Figure 4.5(c)).

(a)

(b)

(c)

Figure 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$.

The behaviour of an $n$-round circuit strategy $F$ is a family of probability
distributions
$\tilde{F}=\\{\tilde{F}(m)\in\mathcal{D}(\mathcal{E}_{S}(m))\\}_{m\in\text{MP}_{n}(S)}$
over the runs of each measurement protocol.

######  Definition 4.1.6.

Let $S$ be a multipartite scenario, $n\geq 1$, and $F$ an $n$-round circuit
strategy. For each $n$-round measurement protocol $m$ and run
$r=(U_{1},s_{1}),\dots,(U_{n},s_{n})$ of $m$ write $\tilde{F}(m)(r)$ for the
probability that when $\\{\text{in}_{ij}\\}$ are set to $\\{x_{ij}\\}$ and $F$
is evaluated then the return value of output wires $\\{\text{out}_{ij}\\}$ are
$\\{y_{ij}\\}$, where

$\displaystyle x_{ij}$ $\displaystyle:=\begin{cases}x,&\text{if $(i,x)\in
U_{j}$}\\\ \bullet,&\text{otherwise}\end{cases}$ (4.8) $\displaystyle y_{ij}$
$\displaystyle:=\begin{cases}s(i,x),&\text{if $(i,x)\in U_{j}$}\\\
\bullet,&\text{otherwise}\end{cases}$ (4.9)

The behaviour of a circuit strategy $F$ is not an empirical model. $\tilde{F}$
does not generally satisfy the no-signaling principle, and only specifies what
happens for a given number of rounds of measurements. However, the definition
of the contextual fraction, the success probability on a game, and the
pushforward can be generalised directly.

######  Definition 4.1.7.

Let $S=(X,\mathcal{M},O)$ be a measurement scenario and $n\geq 1$. An
$n$-round behaviour is a family of probability distributions
$B=\\{B(m)\in\mathcal{D}(\mathcal{E}_{S}(m)\\}_{m\in\text{MP}_{n}(S)}$

  1. 1.

The success probability of $B$ on an $n$-round game
$\Phi=\sum_{C,A}\Phi_{C,A}\cdot(C,A)$ is

$\displaystyle p_{S}(B,\Phi):=\sum_{C,A}\Phi_{C,A}\tilde{B}(C)(A)$ (4.10)

where $C$ is an $n$-round measurement protocol and $A$ is a constraint on the
runs of $C$.

  2. 2.

The contextual fraction of $B$ is the least $\epsilon$ such that there exists
a non-contextual empirical model $e$ and another behaviour $B^{\prime}$ such
that for all $n$-round measurement protocols $C$

$\displaystyle B(C)=\epsilon\cdot B^{\prime}(C)+(1-\epsilon)\cdot e_{C}$
(4.11)

  3. 3.

Let $T$ be another measurement scenario, $t:S\to T$ a deterministic $n$-round
simulation, and $s:S\to T$ a probabilistic $n$-round simulation. The
pushforward $t_{*}(B)$ is the single-round behaviour for $T$ defined by

$\displaystyle t_{*}(B)(U)=\sum_{r\in\mathcal{E}_{S}(f(U))}B(f(U))(r)\cdot
g_{U}(r)$ (4.12)

for each context $C$ of $T$. The pushforward $s_{*}(B)$ is a convex
combination of the pushforward $t_{*}(B)$ for each $t$, with weight the
probability $s(t)$ of $t$ occuring.

###  4.2 Performing measurements far away with teleportation

Figure 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.

Quantum teleportation (Figure 4.6) is a way of transferring a single-qudit
state between two agents that share a _maximally entangled state_ $\phi$.

$\displaystyle\lvert\phi\rangle$
$\displaystyle:=\frac{1}{\sqrt{d}}\sum_{j}\lvert j\rangle\lvert j\rangle$
(4.13)

The protocol involves a measurement in the _Bell basis_ $\mathcal{B}$

$\displaystyle\mathcal{B}$ $\displaystyle:=\\{\lvert\phi_{p}\rangle:=(I\otimes
W(p))\lvert\phi\rangle\\}_{p\in\mathbb{Z}_{d}^{2}}$ (4.14)

performed by one of the agents, classical communication of the measurement
outcome $p\in\mathbb{Z}_{d}^{2}$ to the other agent, and finally a Weyl
operator correction $W(-p)$.

Figure 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}$.

In this section we extend the usual teleportation protocol to any number of
agents $A_{1},\dots,A_{n}$ arranged on a line. The first agent has a state
$\psi$ and each consecutive pair $A_{i},A_{i+1}$ have a maximally entangled
pair of qudits. We show that $A_{n}$ can implement a measurement on $\psi$
without communicating the measurement setting to any of the other agents, such
that only constantly many rounds of quantum measurements are performed. We
present two versions of the protocol. In Section 4.2.1 we present a version
for an arbitrary quantum measurement that uses two rounds of parallel
measurements. In Section 4.2.2 we restrict to Weyl operator measurements and
we present a protocol using only a single round of parallel measurements.

####  4.2.1 Teleportation on a line followed by a measurement

Figure 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.

Let $\\{M_{x}\\}_{x\in X}$ be a family of single-qudit measurements and $\psi$
a single-qudit state. Consider the setup in Figure (4.7). Suppose that we
select a measurement setting $x\in X$ and send this to $A_{n}$.

A simple way for the agents to implement the measurement $M_{x}$ is to first
teleport $\psi$ from $A_{1}$ to $A_{n}$ then perform $M_{x}$. The naive way of
doing this uses $n-1$ rounds. In round $i=1,\dots,n-1$ a Bell basis
measurement teleports $\psi$ from $A_{i}$ to $A_{i+1}$ up to a Weyl operator
phase $W(p_{i})$ which is corrected with the operator $W(-p_{i})$.

Weyl operators compose up to an unobservable phase:

$W(p)W(p^{\prime})\approx W(p+p^{\prime})$ (4.15)

Using the composition law we can reduce the number of rounds from $n-1$ to two
(Figure 4.8). In the first round agents $1,\dots,n-1$ perform Bell basis
measurements in parallel. After this the state of $A_{n}$’s qudit is
$W(p_{1}+\dots p_{n-1})\lvert\psi\rangle$. If $A_{n}$ performs the correction
$W(-p)$, where $p:=p_{1}+\dots+p_{n-1}$, then the effect is to teleport $\psi$
to $A_{n}$, using only a single round of parallel measurements.

Instead of performing the correction $W(-p)$ and then the measurement $M_{x}$
the agent $A_{n}$ can equivalently perform a single measurement
$W(p)M_{x}W(p)^{\dagger}$.

Overall we have a protocol for implementing $M_{x}$ using only a single round
of parallel Bell basis measurements, followed by a single measurement
performed by $A_{n}$.

####  4.2.2 Teleportation on a line followed by a Weyl measurement

Figure 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.

Recall that two Weyl operators $W(p),W(p^{\prime})$, where
$p,p^{\prime}\in\mathbb{Z}_{d}^{2}$ commute according to

$\displaystyle W(p)W(p^{\prime})=\omega^{[p,p^{\prime}]}W(p^{\prime})W(p)$
(4.16)

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

$\displaystyle[p,p^{\prime}]:=p_{1}p_{1}^{\prime}+p_{2}p_{2}^{\prime}$ (4.17)

We now consider the case of the teleportation protocol on a line when the set
of measurements we want to perform are given by Weyl operators. Suppose that
we send some Weyl measurement setting $p\in\mathbb{Z}_{d}^{2}$ to $A_{n}$.

If $A_{1},\dots,A_{n-1}$ perform Bell basis measurements with outcomes
$p_{1}^{\prime},\dots,p_{n-1}^{\prime}$ then $\psi$ is teleported to $A_{n}$
up to a phase given by the Weyl operator $W(p^{\prime})$, where
$p^{\prime}:=p_{1}^{\prime}+\dots+p_{n-1}^{\prime}$. We now want to perform
the measurement given by $W(p)$. Because the operators $W(p)$ and
$W(p^{\prime})$ commute up to a factor $\omega^{[p,p]}$ it can be shown that
the adaptive measurement $W(p)W(p^{\prime})W(p)^{\dagger}$ can be replaced by
a measurement of $W(p^{\prime})$ followed by a classical correction
$-[p,p^{\prime}]$.

######  Lemma 4.2.1.

For any $p,p^{\prime}\in\mathbb{Z}_{d}^{2}$ the following are equivalent, up
to an unobservable phase: A Weyl operator measurement $W(p)$ followed by a
classical correction $-[p,p^{\prime}]$, a Weyl operator correction
$W(-p^{\prime})$ followed by a Weyl operator measurement $W(p)$.

(4.18)

###### Proof.

Let $\lvert p,q\rangle$ be an $\omega^{q}$-eigenvector of the Weyl operator
$W(p)$, where $p\in\mathbb{Z}_{d}^{2}$ and $q\in\mathbb{Z}_{d}$. Let
$W(p),W(p^{\prime})$ be Weyl operators, where
$p,p^{\prime}\in\mathbb{Z}_{d}^{2}$. The claim is equivalent to saying that
$W(p^{\prime})$ permutes the eigenvectors of $W(p)$ by sending $\lvert
p,q\rangle$ to $\lvert p,q+[p,p^{\prime}]\rangle$, up to an unobservable
phase:

$W(p^{\prime})\lvert p,q\rangle\approx\lvert p,q+[p,p^{\prime}]\rangle$ (4.19)

where $q\in\mathbb{Z}_{d}$. By the commutation law of Weyl operators we have

$\displaystyle W(p)(W(p^{\prime})\lvert p,q\rangle)$
$\displaystyle=\omega^{[p,p^{\prime}]}W(p^{\prime})W(p)\lvert p,q\rangle$
(4.20) $\displaystyle=\omega^{[p,p^{\prime}]}W(p^{\prime})\omega^{q}\lvert
p,q\rangle$ (4.21)
$\displaystyle=\omega^{[p,p^{\prime}]+q}(W(p^{\prime})\lvert p,q\rangle)$
(4.22)

Hence $W(p^{\prime})\lvert p,q\rangle$ is an eigenvector of $W(p)$ with
eigenvalue $q+[p,p^{\prime}]$, as required. ∎

From the Lemma, it is clear that the protocol in Figure 4.9 is equivalent to
performing a Weyl measurement and returning the outcome.

###  4.3 Distributing measurements on graphs

(a)

(b)

Figure 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.

In Section 4.2 we showed that measurements on a single-qudit state can be
performed at long distances along a line, using only local entanglement and
constantly many rounds of local measurements.

We now extend the scenario from a line to a graph and from a single-qudit
state to multiple qudits. The purpose of this construction is to show that
measurements on a quantum state can be performed in a distributed way, using a
simulation with only a constant number of rounds. In Section 4.3.1 we define a
simulation for arbitrary measurements using two rounds, in Section 4.3.2 we
restrict to Weyl measurements and present a simulation with a single round.

The information specifying the setup is conveniently represented as a _rooted
graph_. We first define rooted graphs and some of their basic properties.

######  Definition 4.3.1.

A _rooted graph_ $G=(V,E,r)$ is an undirected and connected graph with a
distinguished node $r$ called the _root_.

  1. 1.

A _path_ is a non-repetitive list of nodes $v_{1}=r,v_{2},\dots,v_{l}$,
starting with the root, such that $\\{v_{i},v_{i+1}\\}\in E$ for all
$i=1,\dots,l-1$. Write $\text{Paths}(G)$ for the set of paths in $G$.

  2. 2.

The _neighbourhood_ of a node $v\in v$ is the set of nodes $N_{G}(v)=\\{w\in
V\mid\\{v,w\\}\in E\\}$ that are adjacent to $v$.

  3. 3.

The _degree_ of $G$ is the size of the largest neighbourhood:
$\text{deg}(G)=\text{max}_{v\in V}{\left\lvert N_{G}(v)\right\rvert}$.

  4. 4.

The _radius_ of $G$, denoted by $\text{rad}(G)$, is the least $K\geq 1$ such
that every $v\in V$ is reachable by a path of length at most $K$.

Let $\psi$ be a multi-qudit state with qudits labelled by a set $I$ and
$G=(V,E,r)$ a rooted graph. We consider a scenario with agents labelled by
$I\times V$ (Figure 4.10). The agents share a single instance of the state
$\psi$ and a number of maximally entangled two-qudit states $\phi$. Each of
the agents $(i,r)\in I\times V$ has qudit $i$ of $\psi$. Additionally, each
pair of agents $(i,v),(i,w)\in I\times V$ such that $\\{v,w\\}\in E$, has one
qudit each out of a maximally entangled state. Denote the total state by

$\displaystyle\lvert\psi,G\rangle$
$\displaystyle:=\lvert\psi\rangle\otimes\bigotimes_{i\in I,\\{v,w\\}\in
E}\lvert\phi\rangle_{(i,v,w),(i,w,v)}$ (4.23)

The qudit held by agent $(i,v)$ of the maximally entangled state
$\lvert\phi\rangle_{(i,v,w),(i,w,v)}$ is labelled by $(i,v,w)$. Agent $(i,r)$
therefore has the following set of qudits

$\displaystyle\text{Qudits}(i,r)$ $\displaystyle:=\\{i\\}\cup\\{(i,v,w)\mid
w\in N_{G}(r)\\}$ (4.24)

where $N_{G}(r)$ is the neighbourhood of the root, and when $v\neq r$ agent
$(i,v)$ has qudits

$\displaystyle\text{Qudits}(i,v)$ $\displaystyle:=\\{(i,v,w)\mid w\in
N_{G}(v)\\}$ (4.25)

We now consider the following problem. Suppose that we want to perform a
measurement on each qudit of $\psi$. How can this be done in such a way that
1) we minimise the probability that any single agent knows the measurement
setting, 2) we minimise the number of agents involved in the protocol. The
solution is to use the teleportation protocols from the previous section. We
first randomly select a path for each qudit $i\in I$. Let
$r=v_{1},\dots,v_{j},\dots,v_{l}=v_{i}$ be a path in $G$. We teleport qudit
$i$ to agent $(i,v_{i})$ using the sequence of qudits (Figure 4.11)

$\displaystyle
i,(i,v_{1},v_{2}),\dots,(i,v_{j},v_{j-1}),(i,v_{j},v_{j+1}),\dots,(i,v_{l},v_{l-1})$
(4.26)

Here $(i,v_{j},v_{j+1}),(i,v_{j+1},v_{j})$ are maximally entangled,
$i,(i,v_{1},v_{2})\in\text{Qudits}(i,r)$, and
$(i,v_{j},v_{j-1}),(i,v_{j},v_{j+1})\in\text{Qudits}(i,v_{j})$ for each
$j=2,\dots,l-1$. Hence the protocol uses only local measurements at each
agent.

######  Definition 4.3.2.

Given a rooted graph $G$ let $u_{\text{paths}}\in\mathcal{D}(\text{Paths}(G))$
be any distribution such that for any $v\in V$

$\displaystyle u_{\text{paths}}(v_{1},\dots,v_{l})>0$
$\displaystyle\Rightarrow l\leq\text{rad}(G)$ (4.27) $\displaystyle
u_{\text{paths}}(v_{1},\dots,v_{l}\text{ such that $v_{l}=v$})$
$\displaystyle=1/{\left\lvert V\right\rvert}$ (4.28)

If the paths are chosen independently for each qudit $i$ from the distribution
$u_{\text{paths}}$ then the probability that any given player knows the
measurement setting is at most $1/{\left\lvert G\right\rvert}$, and the number
of agents involved in simulating the measurement on $i$ is at most
$\text{rad}(G)$.

####  4.3.1 Distributing measurements in two rounds

(a)

(b)

Figure 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.

We now suppose that $S=(I,X,Y)$ is a multipartite scenario, $e$ is a quantum
realised empirical model with quantum realisation $(\psi,M)$ in qudit
dimension $d$, and $G=(V,E,r)$ is a rooted graph.

We first define a multipartite scenario $T(S,G,d)$. The measurement sites of
$T(S,G,d)$ are $I\times V$, and at each measurement site $(i,v)\in I\times V$
the measurement settings and outcomes are as follows. When $v=r$ the
measurement settings indicate a measurement setting at measurement site $i$ in
the scenario $S$, or one of the neighbors of $r$ in the graph $G$. Otherwise,
when $v\neq r$, the measurement settings indicate either one of the
measurement settings at measurement site $i$ as well as a neighbour of $v$ in
$G$ and one of the Weyl measurement settings $\mathbb{Z}_{d}^{2}$, or two
distinct neighbours of $v$ in $G$. For the measurements involving one of the
measurements from $S$ the outcomes are the outcomes given by $S$, otherwise
the outcomes are $\mathbb{Z}_{d}^{2}$.

######  Definition 4.3.3.

Let $S=(I,X,Y)$ be a multipartite scenario, $d\geq 2$ a dimension, and
$G=(V,E,r)$ a rooted graph. $T(S,G,d)$ is the multipartite scenario with
measurement sites $I\times V$ and the following measurement settings and
outcomes:

(4.34)

for all $i\in I$ and $v\neq r$.

Next, we define a quantum realised empirical model $e^{\prime}$ for the
scenario $T(S,G,d)$. Recall that the quantum realisation $(\psi,M)$ consists
of a state $\psi$ with qudits labelled by the measurement sites $I$, and a
single-qudit measurement $M_{i,x}$ on qudit $i$, for each measurement $(i,x)$
of the scenario $S$.

To define the empirical model $e^{\prime}$ we interpret the measurement
settings of the scenario $T(S,G,d)$ as quantum measurements on the state
$\lvert\psi,G\rangle$ in the following way. At each measurement site $(i,r)\in
I\times V$ the measurement setting $x$ is the measurement $M_{i,x}$ on qudit
$i$, and the measurement setting $w$ is a Bell basis measurement on qudits
$i,(i,r,w)$. Otherwise, when $v\neq r$, the measurement setting $(x,w,p)$ is
the conjugated measurement $W(p)M_{i,x}W(p)^{\dagger}$ on qudit $(i,v,w)$, and
$(w,w^{\prime})$ is a Bell basis measurement on qudits
$(i,v,w),(i,v,w^{\prime})$.

######  Definition 4.3.4.

Let $G=(V,E,r)$ be a rooted graph, $S=(I,X,Y)$ a multipartite scenario, $\psi$
an $I$-qudit state, and $\pi(i,x)$ a single-qudit measurement with outcomes
$Y_{i,x}$ for each $i\in I,x\in X_{i}$. $e_{G,\psi,\pi}:S_{G,d}$ is the
empirical model realised by the following measurements on $\lvert
G,\psi\rangle$.

(4.40)

Using the empirical model $e^{\prime}$ we can simulate the empirical model $e$
in the following way. Suppose that $v$ is a path in $G$. Given any measurement
$(i,x)$ on the scenario $S$ we subject the empirical model $e^{\prime}$ to the
following measurements. In the case that $v=r$ is the path of length one we
perform measurement $x$ on measurement site $(i,r)$. Otherwise, if
$v=v_{1},\dots,v_{l}$ then we perform measurement $v_{2}$ on $(i,r)$, and
measurement $(v_{j-1},v_{j+1})$ on $(i,v_{j})$ for each $j=2,\dots,l-1$. If
the outcomes of these measurements are $p_{1},\dots,p_{l-1}$ then we perform
measurement $(v_{l-1},x,\sum_{j=1}^{l-1}q_{j})$ on $(i,v_{l})$. This defines a
measurement protocol, which we denote by $C_{v,i,x}$.

$\displaystyle C_{r,i,x}$ $\displaystyle:=(i,r)\mapsto x$ (4.41)

and
$C_{(v_{1},\dots,v_{l},i,x}=C_{(v_{1},\dots,v_{l},i,x}^{1},C_{(v_{1},\dots,v_{l},i,x}^{2}(s_{1})$,
where

$\displaystyle C_{(v_{1},\dots,v_{l}),i,x}^{1}$
$\displaystyle:=\begin{cases}(i,r)&\mapsto v_{2}\\\
(i,v_{j})&\mapsto(v_{j-1},v_{j+1})\end{cases}$ (4.42) $\displaystyle
C_{(v_{1},\dots,v_{l}),i,x}^{2}(s_{1})$
$\displaystyle:=(i,v_{l})\mapsto(v_{l-1},x,\sum_{j=1}^{l-1}s_{1}(i,v_{j}))$
(4.43)

After performing these measurements we return the outcome of the measurement
performed at measurement site $(i,v_{l})$. Write
$g_{v,i,x}:\mathcal{E}_{S}(C_{v,i,x})\to Y_{i,x}$ for the function from runs
of $C_{v,i,x}$ to outcomes of $(i,x)$.

$\displaystyle g_{r,i,x}$ $\displaystyle:=s\mapsto s(i,r)$ (4.44)
$\displaystyle g_{(v_{1},\dots,v_{l}),i,x}$
$\displaystyle=(s_{1},s_{2})\mapsto s_{2}(i,v_{l})$ (4.45)

######  Definition 4.3.5.

Let $G=(V,E,r)$ be a rooted graph, $S=(I,X,Y)$ a multipartite scenario, and
$d\geq 2$. $s(S,G,d):T(S,G,d)\to S$ is the simulation

$\displaystyle\sum_{v\in\text{Paths}(G)^{I}}\big{[}\prod_{i\in
I}u_{\text{paths}}(v_{i})\big{]}\cdot t_{v}$ (4.46)

where for each $v=\\{v_{i}\in\text{Paths}(G)\\}_{i\in I}$ the deterministic
simulation $t_{v}$ is defined by $t_{v}:=(\\{C_{v_{i},i,x}\\}_{i\in I,x\in
X_{i}},\\{g_{v_{i},i,x}\\}_{i\in I,x\in X_{i}})$.

When one of the deterministic simulations $t_{v}$ is applied to the empirical
model $e^{\prime}$ the effect is to perform the two-round teleportation
protocol along a choice of path $v_{i}$ for each measurement site $i\in I$. It
is therefore clear that $e^{\prime}$ in fact simulates the empirical model
$e$.

######  Lemma 4.3.1.

Let $e_{\psi,M}:S$ be a quantum realised empirical mode, $G=(V,E,r)$ a rooted
graph. $s(S,G,d)$ simulates $e_{\psi,M}$ using $e_{G,\psi,M}$ as a resource.

$\displaystyle s(S,G,d)_{*}(e_{G,\psi,M})=e_{\psi,M}$ (4.47)

####  4.3.2 Distributing Weyl measurements in a single round

Consider a multipartite scenario $(I,\mathbb{Z}_{d}^{2},\mathbb{Z}_{d})$, a
quantum realised empirical model $e$ along with a quantum realisation
$(\psi,W)$ where $W(i,p)$ is the Weyl measurement $W(p)$ on qudit $i$, and
$G=(V,E,r)$ a rooted graph.

Figure 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.

We first define a multipartite scenario $T(I,G,d)$ with measurement sites
$I\times V$. At each measurement site $(i,r)\in I\times V$ the measurement
settings are either one of the Weyl measurement settings $\mathbb{Z}_{d}^{2}$
or a neighbour of $r$. Otherwise, when $v\neq r$, the measurement settings at
$(i,v)$ are either a distinct pair of neighbours of $v$ or a Weyl measurement
setting as well as a neighbour of $v$. The outcomes are either
$\mathbb{Z}_{d}^{2}$ or $\mathbb{Z}_{d}$.

######  Definition 4.3.6.

Let $I$ be a set, $d\geq 2$, and $G=(V,E,r)$ a rooted graph. $T(I,G,d)$ is the
multipartite scenario with measurement sites $I\times V$ and the following
measurement settings and outcomes:

(4.53)

for all $i\in I$ and $v\neq r$.

We interpret the measurement settings of the scenario $T(I,G,d)$ as quantum
measurements on the state $\lvert\psi,G\rangle$. At each measurement site
$(i,r)\in I\times V$ measurement setting $p$ is a Weyl measurement $W(p)$ on
qudit $i$, and measurement setting $w$ is a Bell basis measurement on qudits
$i,(i,r,w)$. Otherwise, when $v\neq r$, measurement setting $(p,w)$ is a Weyl
measurement on qudit $(i,v,w)$ and $(w,w^{\prime})$ a Bell basis measurement
on qudits $(i,v,w),(i,v,w^{\prime})$.

######  Definition 4.3.7.

Let $I$ be a set, $d\geq 2$, $\psi$ an $I$-qudit state, and $G=(V,E,r)$ a
rooted graph. The empirical model $e_{G,\psi}:S_{G,I,d}$ is the empirical
model realised by the state $\lvert G,\psi\rangle$ and measurements:

(4.59)

for all $i\in I$ and $v\neq r$.

We define a simulation from $T(I,G,d)$ to
$(I,\mathbb{Z}_{d}^{2},\mathbb{Z}_{2})$ in the following way (Figure 4.12).
Given a path $v$ in $G$ an a measurement setting $(i,p)$ for the scenario
$(I,\mathbb{Z}_{d}^{2},\mathbb{Z}_{2})$ perform the measurement $p$ on
measurement site $(i,r)$ in the case that $v=r$, otherwise if
$v=v_{1},\dots,v_{l}$ perform measurement $v_{2}$ on $(i,r)$,
$(v_{j-1},v_{j+1})$ on $(i,v_{j})$ where $j=2,\dots,l-1$, and measurement
setting $(v_{l-1},p)$ on $(i,v_{l})$. If the outcomes of these measurements
are $p_{1},\dots,p_{l-1},q$ then we return the outcome $q-[p,p_{1}+\dots
p_{l-1}]$.

Write $f_{v,i,p}$ for the measurement context, and
$g_{v,i,p}:\mathcal{E}_{T(I,G,d)}(f_{v,i,p})\to\mathbb{Z}_{d}$ for the outcome
map:

$\displaystyle f_{r,i,p}$ $\displaystyle:=(i,r)\mapsto p$ (4.60)
$\displaystyle g_{r,i,p}$ $\displaystyle:=s\mapsto s(i,r)$ (4.61)
$\displaystyle f_{(v_{1},\dots,v_{l},i,p}$
$\displaystyle:=\begin{cases}(i,v_{1})&\mapsto v_{2}\\\
(i,v_{j})&\mapsto(v_{j-1},v_{j+1})\\\ (i,v_{l})&\mapsto(v_{l-1},p)\end{cases}$
(4.62) $\displaystyle g_{v_{1},\dots,v_{l},i,p}$ $\displaystyle:=s\mapsto
s(i,v_{l})+[p,\sum_{j=1}^{l-1}s(i,v_{j})]$ (4.63)

######  Definition 4.3.8.

Let $I$ be a set, $d\geq 2$, and $G=(V,E,r)$ a rooted graph.
$s(I,G,d):T(I,G,d)\to(I,\mathbb{Z}_{d}^{2},\mathbb{Z}_{d})$ is the simulation

$\displaystyle\sum_{v\in\text{Paths}(G)^{I}}\big{[}\prod_{i\in
I}u_{\text{paths}}(v_{i})\big{]}\cdot t_{v}$ (4.64)

where $t_{v}$ is the deterministic simulation $(\\{f(v_{i})_{i,p}\\}_{i\in
I,p\in\mathbb{Z}_{d}^{2}},\\{g(v_{i})_{i,p}\\}_{i\in
I,p\in\mathbb{Z}_{d}^{2}})$.

When the simulation is applied to the empirical model $e$ the effect is to
perform the single-round teleportation protocol on a line. It is therefore
clear that the pushforward of $e_{G,\psi,M}$ is $e$.

######  Lemma 4.3.2.

Let $e_{\psi}:(I,\\{\mathbb{Z}_{d}^{2}\\},\\{\mathbb{Z}_{d}\\})$ be a Pauli
measurement model and $G$ a rooted graph.
$s_{G}:S_{G,I,d}\to(I,\mathbb{Z}_{d}^{2},\mathbb{Z}_{d})$ simulates $e_{\psi}$
using $e_{\psi,G}$ as a resource.

$(s_{G})_{*}(e_{\psi,G})=e_{\psi}$ (4.65)

###  4.4 Distributing non-local games on graphs

In Section 4.3 we showed that measurements on a multi-qudit state can be
simulated in a distributed way, using a graph as a template. We now use this
construction to define distributed versions of non-local games and show that
they are solved by quantum circuits of low depth and fan-in. We present two
versions of this. In Section 4.4.1 we use the two-round teleportation
protocol, and we work with general non-local games. In Section 4.4.2 we use
the single-round protocol and we restrict attention to non-local games using
Weyl measurements.

####  4.4.1 Two-round distributed non-local games

Let $S=(I,X,Y)$ be a multipartite scenario, $(e,\Phi)$ a non-local game along
with a quantum realisation $(\psi,M)$ of $e$ in qudit dimension $d\geq 2$, and
$G=(V,E,r)$ a rooted graph.

In Section 4.3.1 we defined a measurement scenario $T(S,G,d)$, a quantum
realised empirical model $e^{\prime}$, and a simulation $s(S,G,d):T(S,G,d)\to
S$ such that ${s(S,G,d)}_{*}(e^{\prime})=e$. We now consider the pullback of
the cooperative game $\Phi$ across the simulation $s(S,G,d)$. Because
$e^{\prime}$ simulates $e$ we have that the success probability of
$e^{\prime}$ on the pullback problem is equal to the success probability of
$e$. $e^{\prime}$ therefore violates the classical bound for the non-local
game $(e,\Phi)$.

$\displaystyle p_{S}(e^{\prime},{s(S,G,d)}^{*}(\Phi))=p_{S}(e,\Phi)>\gamma$
(4.66)

where $\gamma$ is the classical bound.

We can implement $e^{\prime}$ as a two-round quantum circuit strategy (Figure
4.13). We first have to prepare $\lvert\psi,G\rangle$. This can be done with a
single unitary gate of fan-in ${\left\lvert I\right\rvert}$ and a number of
unitary two-qudit gates. We then have to implement measurements. The
measurements corresponding to each measurement site $(i,v)$ act on
$\text{Qudits}(i,v)$. The fan-in of these gates, therefore, depends only on
the _degree_ of $G$.

(a)

$\displaystyle U_{\psi,G}$ $\displaystyle=U_{\psi}\otimes\bigotimes_{i\in
I,\\{v,w\\}\in E}U_{(i,v,w),(i,w,v)}$ $\displaystyle U_{\psi}\lvert 0\dots
0\rangle$ $\displaystyle=\lvert\psi\rangle$ $\displaystyle
U_{(i,v,w),(i,w,v)}\lvert 00\rangle$ $\displaystyle=\lvert\phi\rangle$ (b)

Measurement site | Input value | Measurement setting
---|---|---
$(i,r)$ | $w\in N_{G}(r)$ | Bell basis on qudits $i,(i,r,w)$
| $x\in X_{i}$ |  $M_{i,x}$ on qudit $i$
| $\bullet$ | Identity
$(i,v)$ | $w,w^{\prime}\in N_{G}(v).\ w\neq w^{\prime}$ | Bell basis on qudits $(i,v,w),(i,v,w^{\prime})$
| $(x,w,p)\in X_{i}\times N_{G}(v)\times\mathbb{Z}_{d}^{2}$ |  $W(p)M_{i,x}W(-p)$ on qudit $(i,v,w)$
| $\bullet$ | Identity
(c)

Figure 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).

######  Lemma 4.4.1.

Let $S=(I,X,Y)$ be a multipartite scenario and $(e,\Phi)$ a non-local game
with classical bound $\gamma$. Suppose that $e$ has a quantum realisation in
qudit dimension $d\geq 2$. There exists a two-round cooperative game
$\Phi^{\prime}$ with classical bound $\gamma$ and quantum circuit strategy $Q$
such that

  1. 1.

The success probability of $Q$ exceeds $\gamma$:
$p_{S}(Q,\Phi^{\prime})>\gamma$.

  2. 2.

The depth and maximal fan-in of $Q$ depends only on the size of $I$ and the
degree of $G$.

(a)

(b)

Figure 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}$.

####  4.4.2 Single-round distributed Weyl-measurement games

Let $(e,\Phi)$ be a non-local game for a multipartite scenario on the form
$(I,\mathbb{Z}_{d}^{2},\mathbb{Z}_{d})$, such that $e$ has a quantum
realisation on an $I$-qudit state $\psi$, where the measurement $(i,p)$ is the
Weyl measurement $W(p)$ on qudit $i$. Let $G=(V,E,r)$ be a rooted graph.

In Section 4.3.2 we defined a quantum realised empirical model $e^{\prime}$
and a single-round simulation $s(I,G,d)$ such that
${s(I,G,d)}_{*}(e^{\prime})=e$. Taking the pullback $s(I,G,d)^{*}(\Phi)$ we
then have

$\displaystyle p_{S}(e^{\prime},s(I,G,d)^{*}(\Phi))>\gamma$ (4.67)

where $\gamma$ is the classical bound of $(e,\Phi$. We can implement
$e^{\prime}$ as the quantum circuit in Figure (4.15).

######  Lemma 4.4.2.

Let $(e,\Phi)$ be a Weyl measurement game with classical bound $\gamma$ and
$G$ a rooted graph. Consider the pullback of $\Phi$ across the single-round
simulation. This game has a quantum circuit strategy $Q$ such that that

  1. 1.

The success probability of $Q$ at the pullback of $\Phi$ is the success
probability of $e$ at $\Phi$, which exceeds $\gamma$:
$p_{S}(Q,s(I,G,d)^{*}(\Phi))>\gamma$.

  2. 2.

The depth and maximal fan-in of $Q$ is only dependent on the size of $I$ and
the degree of $G$.

We can describe the pullback game more directly as follows. Recall $\Phi$ is
defined as a convex combination $\sum_{U,A}\Phi_{U,A}\cdot(U,A)$ where $U$ is
a joint measurement for the scenario $(I,\mathbb{Z}_{d}^{2},\mathbb{Z}_{d})$
and $A\subset\mathcal{E}_{(I,\mathbb{Z}_{d}^{2},\mathbb{Z}_{d})}(U)$ is an
accepting condition.

In the pullback game Verifier randomly selects $U,A$ with probability
$\Phi_{U,A}$. For each joint input $(i,p_{i})\in U$ Verifier then selects a
path $v_{i}=(v_{i1},\dots,v_{il_{i}})$ in $G$ with probability
$u_{\text{paths}}(v_{i})$. If $v_{i}$ is the trivial path then Verifier gives
input $p_{i}$ to $(i,r)$, otherwise if $l>1$, Verifier gives input $v_{i2}$ to
$(i,r)$, input $(v_{i(j-1)},v_{i(j+1)})$ to $(i,v_{j})$, and finally input
$(v_{i(l_{i}-1)},p_{i})$ to and $(i,v_{l_{i}})$. The total joint input is then

$\displaystyle U_{v}:=\begin{cases}(i,r)\mapsto p_{i},&\text{if $(i,p_{i})\in
U$ and $v_{i}=r$}\\\ (i,r)\mapsto v_{2},&\text{if $(i,p_{i})\in U$ and
$l_{i}>1$}\\\ (i,v_{ij}\mapsto(v_{i(j-1)},v_{i(j+1)}),&\text{if $(i,p_{i})\in
U$ and $j=2,\dots,l_{i}-1$}\\\
(i,v_{il_{i}})\mapsto(v_{i(l_{i}-1)},p_{i}),&\text{if $(i,p_{i})\in U$ and
$l_{i}>2$}\end{cases}$ (4.68)

The players then respond with a joint output
$s\in\mathcal{E}_{S_{G,I,d}}(U_{v,p})$. The output is accepted if

$\displaystyle A_{v,U}(s):\iff\big{(}(i,p_{i})\mapsto
s(i,v_{il_{i}})+[p_{i},\sum_{j=1}^{l_{i}-1}s(i,v_{ij})]\big{)}_{(i,p_{i})\in
U}\in A$ (4.69)

As a convex combination the pullback is then the game

$\displaystyle\sum_{v,U,A}\big{[}\prod_{i\in
I}u_{\text{paths}}(v_{i})\big{]}\Phi_{U,A}\cdot(U_{v},A_{v,U})$ (4.70)

(a)

$\displaystyle U_{\psi,G}$ $\displaystyle=U_{\psi}\otimes\bigotimes_{i\in
I,\\{v,w\\}\in E}U_{(i,v,w),(i,w,v)}$ $\displaystyle U_{\psi}\lvert 0\dots
0\rangle$ $\displaystyle=\lvert\psi\rangle$ $\displaystyle
U_{(i,v,w),(i,w,v)}\lvert 00\rangle$ $\displaystyle=\lvert\phi\rangle$ (b)

Input wire | Value | Measurement setting
---|---|---
$(i,r)$ | $p\in\mathbb{Z}_{d}^{2}$ |  $W(p)$ on qudit $i$
| $w\in N_{G}(r)$ | Bell basis on qudits $i$ $(i,r,w)$
| $\bullet$ | Identity measurement
$(i,v)$ | $(w,p)\in N_{G}(v)\mathbb{Z}_{d}^{2}$ |  $W(p)$ on qudit $(i,v,w)$
| $(w,w^{\prime})\in N_{G}(v)^{2}.\ w\neq w^{\prime}$ | Bell basis on qudits $(i,v,w)$ $(i,v,w^{\prime})$
| $\bullet$ | Identity measurement
(c)

Figure 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.

###  4.5 Separating quantum and classical circuits of low depth and fan-in

In Section 4.3 we defined two simulations $s(S,G,d)$ and $s(I,G,d)$ with
respectively one and two rounds, that perform measurements on a quantum state
in a distributed way. The simulations where then used in Section 4.4 to define
distributed versions of non-local games, such that the quantum strategies can
be recast as circuits of small depth and fan-in. The purpose of this section
is to bound the success probability of classical circuits on these problems.
Recall the resource inequality

$\displaystyle p_{S}(e^{\prime},\Phi)\leq\gamma+\text{CF}(e^{\prime})$ (4.71)

relating the success probability of an arbitrary empirical model $e^{\prime}$
to the classical bound $\gamma$ for a non-local game and its contextual
fraction $\text{CF}(e^{\prime})$. We observe that the derivation of this bound
does not rely on the no-disturbance condition. In Section 4.1 we explained
that circuit strategies give rise to empirical models that don’t satisfy the
no-disturbance condition, we called these objects “behaviours”, and explained
that constructions like simulations and the contextual fraction can be
generalised. Because the bound $\gamma+\text{CF}(e^{\prime})$ does not rely on
no-disturbance we have a bound

$\displaystyle p_{S}(B,\Phi)\leq\gamma+\text{CF}(B)$ (4.72)

for any behaviour $B$.

We want to bound the contextual fraction of a classical circuit $C$ on the
pullback $s^{*}(\Phi)$ of a game $\Phi$ across some simulation $s$. To do this
we bound the contextual fraction of the pushforward $s_{*}(\tilde{C})$ and
rely on the inequality 4.72.

Although we use a different terminology this is precisely what Bravyi, Gosset,
and König did. We will work at a general level, first stating the result as a
general property of simulations, and then restrict to the two simulations.

The idea is to consider a general simulation $s:S\to T$. Recall that $s$ is
defined as a probability distribution over deterministic simulations $t:S\to
T$. In Section 4.5.1 we consider the case of a deterministic simulation. We
derive a combinatorial condition involving the lightcones of the circuit $C$
that ensures that the pushforward $t_{*}(\tilde{C})$ is non-contextual. In
Section 4.5.2 we first present a lemma due to BGK, and we restate this as a
bound on the probability that this condition holds, when $t$ is selected
randomly from a simulation $s$. We finally apply this to the simulations
$s(G,I,d)$ and $s(S,G,d)$.

####  4.5.1 Lightcones of simulations

The simulations $s(S,G,d)$ and $s(I,G,d)$ are defined as probability
distributions over deterministic simulations $t_{v}$ corresponding to each
choice of paths $v\in\text{Paths}(G)^{I}$. Consider these simulations for a
fixed choice of paths $v$. The measurements performed in these simulations are
independent of the input for all but a small number of measurement sites, and
the outcome we return only depends on the outcomes of the measurements on a
small number of measurement sites. In the two-round case, given a measurement
$(i,x)$ for the scenario $S$ we first perform a measurement
$C_{v_{i},i,x}^{1}$ that is independent of $x$ and in the second round we
perform a measurement $C_{v_{i},i,x}$ that is only defined on
$(i,v_{il_{i}})$. The final outcome only depends on the outcome at
$(i,v_{il_{i}})$. In the single-round case, we perform a single measurement
where only the setting at $(i,v_{il_{i}})$ depends on $x$. And the outcome
returned depends only on the subset of measurement sites $\\{(i,v_{ij})\\}$.

For any deterministic simulation $t:S\to T$ we can identify the unique minimal
subset of measurement sites such that the measurement setting in round $k$
depends on the input, and the outcome uses the measurement outcome. For each
round $k\leq n$ and $j\in J$ we define the input and output dependencies of
the simulation as follows.

######  Definition 4.5.1.

Let $S=(I,X,Y),T=(J,Z,W)$ be two multipartite scenarios and
$t=(\\{C_{j,z}\\}_{j\in J,z\in Z_{j}},\\{g_{j,z}\\}_{j\in J,z\in Z_{j}}):S\to
T$ an $n$-round deterministic simulation, where $C_{j,z}$ is the measurement
protocol

$\displaystyle
C_{i,z}=C_{i,z}^{1},\dots,C_{i,z}^{k}(s_{1},\dots,s_{k-1}),\dots,C_{i,z}^{n}(s_{1},\dots,s_{n-1})$
(4.73)

and $g_{j,z}:\mathcal{E}_{S}(C_{j,z})\to W_{j,z}$. For any measurement site
$j\in J$ and round $k=1,\dots,n$ let
$\text{In}_{k}(t)(j),\text{Out}_{k}(t)(j)\subset I$ as follows

  * •

$\text{In}_{k}(t)(j)$ is the least $I^{\prime}\subset I$ such that for each
$z\in Z_{j}$ and run $(s_{1},\dots,s_{n})\in\mathcal{E}_{S}(C_{j,z})$ the
joint measurement $C_{j,z}^{k}(s_{1},\dots,s_{k-1})$ can be written as a union

$\displaystyle C_{j,z}^{k}(s_{1},\dots,s_{k-1})=U(s_{1},\dots,s_{k-1})\cup
U_{z}(s_{1},\dots,s_{k-1})$ (4.74)

where $U(s_{1},\dots,s_{k-1})$ is independent of $z$ and
$U_{z}(s_{1},\dots,s_{k-1})$ is a joint measurement for the measurement sites
$I^{\prime}$.

  * •

$\text{Out}_{k}(t)(j)\subset I$ is the least $I^{\prime}\subset I$ such that
for each run $(s_{1},\dots,s_{n})\in\mathcal{E}_{S}(C_{j,z})$ the outcome
$g_{j,z}(s_{1},\dots,s_{n})\in W_{j,z}$ is independent of the value of $s_{k}$
on measurement sites $I\setminus I^{\prime}$:

$\displaystyle
g_{j,z}(s_{1},\dots,s_{n})=g_{j}(s_{1},\dots,s_{k}\rvert_{I^{\prime}},\dots,s_{n})(x)$
(4.75)

where $g_{j}$ is some function.

For example, for the two-round simulation $t:=t(S,G,d,v)$ we have

$\displaystyle\text{In}_{1}(t)(i)$ $\displaystyle=\emptyset$ (4.76)
$\displaystyle\text{In}_{2}(t)(i)$ $\displaystyle=\\{(i,v_{il_{i}})\\}$ (4.77)
$\displaystyle\text{Out}_{2}(t)(i)$ $\displaystyle=\\{(i,v_{il_{i}})\\}$
(4.78)

and for the single-round simulation $t:=t(I,G,d,v)$

$\displaystyle\text{In}_{1}(t)(i)$ $\displaystyle=\\{(i,v_{il_{i}})\\}$ (4.79)
$\displaystyle\text{Out}_{1}(t)(i)$
$\displaystyle=\\{(i,v_{ij})\\}_{j=1}^{l_{i}}$ (4.80)

If $t:S\to T$ is an $n$-round simulation such that $\text{In}_{k}(t)(j)$ is
empty for all $k<n$ and $C$ is a classical strategy such that
$t_{*}(\tilde{C})$ is contextual. Then there must be some $j\neq j^{\prime}$
and $i\in\text{In}_{n}(t)(j),i^{\prime}\in\text{Out}_{n}(t)(j^{\prime})$ such
that there is path through $C$ from $\text{in}_{in}$ to
$\text{out}_{i^{\prime}n}$. Let the relation
$\text{In}_{n}(t);\text{LC}_{C}^{\leftarrow};\text{Out}_{n}(t)\subset J\times
J$ be defined by

$\displaystyle\exists i,i^{\prime}\in I:\
i\in\text{In}_{n}(t)(j)\land\text{in}_{ni}\in\text{LC}_{C}^{\leftarrow}(\text{out}_{ni^{\prime}})\land
i^{\prime}\in\text{Out}_{n}(j^{\prime})$ (4.81)

for all $(j,j^{\prime})\in J\times J$ (Figure 4.16). In other words, if
$\text{In}_{n}(t);\text{LC}_{C}^{\leftarrow};\text{Out}_{n}(t)\subset\text{id}_{J}$,
where $\text{id}_{J}\subset J\times J$ is the identity relation, then
$t_{*}(\tilde{C})$ is non-contextual.

(a) $\text{In}_{1}(t)$

(b) $\text{LC}_{C}^{\leftarrow}$

(c) $\text{Out}_{1}(t)$

(d) $\text{In}_{1}(t);\text{LC}_{C}^{\leftarrow};\text{Out}_{1}(t)$

Figure 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).

######  Lemma 4.5.1.

Let $S$ and $T=(J,Z,W)$ be two multipartite scenarios, $t:S\to T$ an $n$-round
deterministic simulation, and $C$ an $n$-round classical circuit strategy for
$S$. If for all $k<n$ and $j\in J$ we have $\text{In}_{k}(t)(j)=\emptyset$,
and
$\text{In}_{n}(t);\text{LC}_{C}^{\leftarrow};\text{Out}_{n}(t)\subset\text{id}_{J}$
then $t_{*}(\tilde{C})$ is non-contextual.

###### Proof.

Let $t:S\to T$ be an $n$-round deterministic simulation and $C$ an $n$-round
classical circuit strategy. By definition $t_{*}(\tilde{C})$ is defined for
any context $U$ of $T$ by

$\displaystyle
t_{*}(\tilde{C})(U)=\sum_{(s_{1},\dots,s_{n})\in\mathcal{E}_{S}(f(U))}\tilde{C}(f(U))(s_{1},\dots,s_{n})\cdot
g_{U}(s_{1},\dots,s_{n})$ (4.82)

where $f(U)\in\text{MP}_{n}(S)$ and
$g_{U}:\mathcal{E}_{S}(f(U))\to\mathcal{E}_{T}(U)$. By assumption the first
$n-1$ measurements are independent of $U$, so that $f(U)$ is of the form:

$\displaystyle
f(U)=V_{1},V_{2}(s_{1}),\dots,V_{n-1}(s_{1},\dots,s_{n-2}),V_{n}(U)(s_{1},\dots,s_{n-1})$
(4.83)

Because $C$ is a classical circuit we can write the probability distribution
$\tilde{C}(F(U))$ as a convex combination of hidden variables $\lambda$, such
that

$\displaystyle\tilde{C}(f(U))=\sum_{\lambda}p_{\lambda}\cdot(\lambda_{1},\dots,\lambda_{n-1},\lambda_{n}(V_{n}(U)(\lambda_{1},\dots,\lambda_{n-1})))$
(4.84)

and the value of $\lambda_{n}(U)(\lambda_{1},\dots,\lambda_{n-1})$ at any
measurement site $i\in I$ depends only on the measurement setting of
$V_{n}(U)$ on the subset of measurement sites

$\displaystyle\overleftarrow{i}=\\{i^{\prime}\in
I\mid\text{in}_{i^{\prime}}\in\text{LC}_{C}^{\leftarrow}(\text{out}_{i})\\}$
(4.85)

Plugging the hidden variable expression for $\tilde{C}(f(U))$ into the first
equation we get a hidden variable expression for the pushforward
$t_{*}(\tilde{C})(U)$

$\displaystyle t_{*}(\tilde{C})(U)=\sum_{\lambda}p_{\lambda}\cdot
g_{U}(\lambda_{1},\dots,\lambda_{n-1},\lambda_{n}(V_{n}(U)(\lambda_{1},\dots,\lambda_{n-1})))$
(4.86)

To see that $t_{*}(\tilde{C})$ it is sufficient to show that the value of

$\displaystyle
g_{U}(\lambda_{1},\dots,\lambda_{n-1},\lambda_{n}(V_{n}(U)(\lambda_{1},\dots,\lambda_{n-1})))$
(4.87)

on a measurement $(j,z)$ is independent of $U$.

Suppose therefore that $(j,z)$ is any measurement for $T$ and for any $U$
consider the outcome assigned to $(j,z)$. That is, the value

$\displaystyle
g_{U}(\lambda_{1},\dots,\lambda_{n-1},\lambda_{n}(V_{n}(U)(\lambda_{1},\dots,\lambda_{n-1})))(j,z)$
(4.88)

First we have that the outcome of $(j,z)$ only depends on the value of
$\lambda_{n}(V_{n}(U)(\lambda_{1},\dots,\lambda_{n-1})))$ on the subset of
measurement sites $\text{Out}_{n}(t)(j)\subset I$. Furthermore, the value of
$\lambda_{n}(V_{n}(U)(\lambda_{1},\dots,\lambda_{n-1})))$ on measurement sites
$\text{Out}_{n}(t)(j)$ depends only on the value of
$V_{n}(U)(\lambda_{1},\dots,\lambda_{n-1}))$ on

$\displaystyle\overleftarrow{\text{Out}_{n}(t)(j)}:=\bigcup_{i\in\text{Out}_{n}(t)(j)}\overleftarrow{i}$
(4.89)

Hence the outcome of $(j,z)$ depends only on the value of
$V_{n}(U)(\lambda_{1},\dots,\lambda_{n-1})$ on each $i^{\prime}$ such that
there exists an $i$ such that
$\text{in}_{i^{\prime}n}\in\text{LC}_{C}^{\leftarrow}(\text{out}_{in}$ and
$i\in\text{Out}_{n}(t)(j)$. Finally, we have that the value of
$V_{n}(U)(\lambda_{1},\dots,\lambda_{n-1})$ on $i$ only depends on the value
of $U$ on $j$ such that $i\in\text{In}_{n}(t)(j)$. Therefore, if the condition
holds then it is non-contextual. ∎

####  4.5.2 Classical bound

Suppose that $s:S\to T$ is a probabilistic simulation from a multipartite
scenario $S$ to another multipartite scenario $T$ and $C$ a classical strategy
for $S$. Suppose that we randomly select a deterministic simulation $t:S\to T$
with probability given by $s$. Lemma 4.5.1 gives a condition ensuring that the
pushforward $t_{*}(\tilde{C})$ is non-contextual, involving the relation
$\text{In}_{n}(t);\text{LC}_{C}^{\leftarrow};\text{Out}_{n}(t)$. We now
consider the probability that this condition is satisfied when $t$ is chosen
randomly from the simulation $s$.

The following lemma from BGK shows that $C$ has low depth and fan-in,
$\text{In}_{n}(t)(j)$ is small, and $\text{Out}_{n}(t)(j)$ is distributed in a
uniform way, then the probability that the condition holds is high.

######  Lemma 4.5.2.

(BGK) Let $C$ be a circuit with inputs $\\{\text{in}_{i}\\}_{i\in I}$ and
outputs $\\{\text{out}_{i}\\}_{i\in I}$ of depth $D$ and fan-in at most $K$.
Suppose that we randomly select a family of sets
$\\{I_{\text{in}}(j),I_{\text{out}}(j)\subset I\\}_{j\in J}$ and consider the
relation $I_{\text{in}};\text{LC}_{C}^{\leftarrow};I_{\text{out}}\subset
J\times J$ given by

$\displaystyle\exists i,i^{\prime}\in I.\ i\in
I_{\text{in}}(j)\land\text{in}_{i}\in\text{LC}_{C}^{\leftarrow}(\text{out}_{i^{\prime}})\land
i^{\prime}\in I_{\text{out}}(j^{\prime})$ (4.90)

for all $(j,j^{\prime})\in J\times J$. Suppose that the following conditions
hold:

  1. 1.

The size of $I_{\text{out}}(j)$ is at most $A$, for all $j\in J$.

  2. 2.

For all $j\in J$ and $i\in I$. If we randomly select
$\\{I_{\text{in}}(j),I_{\text{out}}(j)\\}_{j\in J}$ from the marginal
distribution fixing $I_{\text{out}}(j)$, then for each $j^{\prime}\in J$, such
that $j\neq j^{\prime}$, the probability that $i\in I_{\text{in}}(j)$ is at
most $\epsilon$:

$\text{Prob}(i\in I_{\text{in}}(j)\mid
I_{\text{out}}(j^{\prime}))\leq\epsilon$ (4.91)

The probability that the condition
$I_{\text{in}};\text{LC}_{C}^{\leftarrow};I_{\text{out}}\subset\text{id}_{J}$
fails is at most $K^{D}{\left\lvert J\right\rvert}^{2}A\epsilon$.

###### Proof.

For some $j\neq j^{\prime}\in J$ suppose that $I_{\text{out}}(j^{\prime})$ is
fixed and that $I_{\text{in}}(j)$ is chosen randomly.

$\displaystyle\text{Prob}(\text{LC}_{C}(I_{\text{in}}(j),I_{\text{out}}(j^{\prime})))$
$\displaystyle\leq\sum_{i\in
I_{\text{out}}(j^{\prime})}\text{Prob}(\text{LC}_{C}(I_{\text{in}}(j),i)$
(4.92)
$\displaystyle\leq\sum_{i\in\text{LC}_{C}^{\leftarrow}(I_{\text{out}}(j^{\prime}))}\text{Prob}(i\in
I_{\text{in}}(j))$ (4.93)
$\displaystyle\leq\sum_{i\in\text{LC}_{C}^{\leftarrow}(I_{\text{out}}(j^{\prime}))}\epsilon$
(4.94) $\displaystyle\leq K^{D}A\epsilon$ (4.95)

If $\\{I_{\text{in}}(j),I_{\text{out}}(j)\subset I\\}_{j\in J}$ is chosen
randomly we therefore have by the union bound that

$\displaystyle\text{Prob}(\exists j\neq j^{\prime}\in J.\
\text{LC}_{C}(I_{\text{in}}(j),I_{\text{out}}(j^{\prime})))$
$\displaystyle\leq\sum_{j\neq j^{\prime}\in
J}\text{Prob}(\text{LC}_{C}(I_{\text{in}}(j),I_{\text{out}}(j^{\prime})))$
(4.96) $\displaystyle\leq\frac{{\left\lvert J\right\rvert}({\left\lvert
J\right\rvert}-1)}{2}K^{D}A\epsilon$ (4.97) $\displaystyle\leq{\left\lvert
J\right\rvert}^{2}K^{D}A\epsilon$ (4.98)

∎

We next restate this as a bound on the contextual fraction.

######  Lemma 4.5.3.

Let $S$ and $T$ be two multipartite scenarios, $s:S\to T$ an $n$-round
simulation, and $C$ a classical $n$-round circuit strategy of depth $D$ and
maximal fan-in $K$. Suppose that the following conditions hold when a
deterministic simulation $t$ is chosen randomly with probability $s(t)$:

  * •

For each $k<n$ and $j\in J$ we have $\text{In}_{k}(t)(j)=\emptyset$.

  * •

For each $j\in J$ we have ${\left\lvert\text{In}_{n}(t)(j)\right\rvert}\leq
A$.

  * •

For all $j,j^{\prime}\in J$ and $i\in I$ such that $j\neq j^{\prime}$:

$s(i\in\text{In}_{n}(t)(j)\mid\text{Out}_{n}(t)(j^{\prime}))\leq\epsilon$
(4.99)

The contextual fraction of the pushforward $s_{*}(\tilde{C})$ is at most
${\left\lvert J\right\rvert}^{2}K^{D}A\epsilon$

$\displaystyle\text{CF}(s_{*}(\tilde{C}))\leq{\left\lvert
J\right\rvert}^{2}K^{D}A\epsilon$ (4.100)

###### Proof.

The pushforward $s_{*}(\tilde{C})$ is defined for each context $U$ of $T$ as
the convex combination

$\displaystyle s_{*}(\tilde{C})(U)=\sum_{t}s(t)\cdot t_{*}(\tilde{C})(U)$
(4.101)

The non-contextual fraction of $s_{*}(\tilde{C})$ (Definition 2.6.1) is the
greatest weight assigned to the non-contextual part of any convex
decomposition of $s_{*}(\tilde{C})$ into a non-contextual model and another
empirical model. The non-contextual fraction of $s_{*}(\tilde{C})$ is
therefore bounded from below by the probability that $t_{*}(\tilde{C})$ is
non-contextual when $t$ is chosen randomly according to $s$.

$\displaystyle s(t_{*}(\tilde{C})\text{ is non-
contextual})\leq\text{NCF}(s_{*}(\tilde{C}))$ (4.102)

Or equivalently

$\displaystyle\text{CF}(s_{*}(\tilde{C}))\leq s(t_{*}(\tilde{C})\text{ is
contextual})$ (4.103)

By Lemma 4.5.1 if $t_{*}(\tilde{C})$ is contextual then
$\text{In}_{n}(t);\text{LC}_{C}^{\leftarrow};\text{Out}_{n}(t)\not\subset\text{id}_{I}$.

$\displaystyle s(t_{*}(e)\text{ is contextual})\leq
s(\text{In}_{n}(t);\text{LC}_{C}^{\leftarrow};\text{Out}_{n}(t)\not\subset\text{id}_{I})$
(4.104)

By Lemma 4.5.2 the probability of
$\text{In}_{n}(t);\text{LC}_{C}^{\leftarrow};\text{Out}_{n}(t)\not\subset\text{id}_{J}$
is at most ${\left\lvert J\right\rvert}^{2}K^{D}A\epsilon$, as required. ∎

We now consider the two simulations $s(S,G,d),s(I,G,d)$ from Section 4.3.

######  Lemma 4.5.4.

Let $G$ be a rooted graph, $d\geq 2$ a dimension, $I$ a finite set, and
$S=(I,X,Y)$ a multipartite scenario.

  1. 1.

Let $C$ a two-round classical circuit strategy for the scenario $T(S,G,d)$ of
depth $D$ and maximal fan-in $K$.

$\text{CF}(s(S,G,d)_{*}(\tilde{C}))\leq{\left\lvert
I\right\rvert}^{2}K^{D}{\left\lvert G\right\rvert}^{-1}$ (4.105)

  2. 2.

Let $C$ be a single-round classical circuit strategy for the scenario
$T(I,G,d)$ of depth $D$ and maximal fan-in $K$.

$\text{CF}(s(I,G,d)_{*}(\tilde{C}))\leq{\left\lvert
I\right\rvert}^{2}K^{D}{\left\lvert G\right\rvert}^{-1}\text{rad}(G)$ (4.106)

###### Proof.

In each case the simulation is defined as a convex combination

$\displaystyle\sum_{v\in\text{Paths}(G)^{I}}\big{[}\prod_{i\in
I}u_{\text{paths}}(v_{i})\big{]}\cdot t_{v}$ (4.107)

where $t_{v}$ is a simulation with either

$\displaystyle\text{In}_{1}(t)(i)$ $\displaystyle=\emptyset$ (4.108)
$\displaystyle\text{In}_{2}(t)(i)$ $\displaystyle=\\{(i,v_{il_{i}})\\}$
(4.109) $\displaystyle\text{Out}_{2}(t)(i)$
$\displaystyle=\\{(i,v_{il_{i}})\\}$ (4.110)

in the two-round case, or

$\displaystyle\text{In}_{1}(t)(i)$ $\displaystyle=\\{(i,v_{il_{i}})\\}$
(4.111) $\displaystyle\text{Out}_{1}(t)(i)$
$\displaystyle=\\{(i,v_{ij})\\}_{j=1}^{l_{i}}$ (4.112)

in the single-round case.

In either case condition 1. of Lemma 4.5.3 is satisfied. For the second
condition we have $A=1$ in the first case and $A\leq\text{rad}(G)$ in the
second case.

Note that choice of paths are independent for different $i,i^{\prime}\in I$.
For the third condition we therefore have bound $\epsilon=1/{\left\lvert
G\right\rvert}$. ∎

####  4.5.3 Randomised restrictions

A common technique in complexity theory is to look at randomised restrictions
of circuits. In this section we explain why this is not sufficient to prove a
separation between shallow quantum and classical circuits.

######  Definition 4.5.2.

Let $S=(I,X,Y)$ be a multipartite scenario and $B$ a single-round behaviour. A
_restriction_ is a pair $(U,I^{\prime})$ where $I^{\prime}\subset I$ is a
subset of measurement sites and $U$ is a joint measurement for the remaining
measurement sites $I\setminus I^{\prime}$. Write $S\rvert_{I^{\prime}}$ for
the multipartite scenario $(I^{\prime},(X_{i})_{i\in I},(Y_{i,x})_{i\in
I^{\prime},x\in X_{i}})$ and $e\rvert_{U,I^{\prime}}:S\rvert_{I^{\prime}}$ for
the behaviour given by fixing the measurement setting at measurement sites
$I\setminus I^{\prime}$ according to $x$.

Let $C$ be a classical circuit strategy of depth $D$ and maximal fan-in $K$.
We consider the probability that $\tilde{C}\rvert_{U,I^{\prime}}$ is
contextual when $(U,I^{\prime})$ is selected randomly. Classically we require
communication to produce contextuality: If $\tilde{C}$ is contextual then
there must be some some $i\neq i^{\prime}\in I$ such that input wire $i$
communicates to output wire $i^{\prime}$ through $C$, i.e.
$\text{in}_{i}\in\text{LC}_{C}^{\leftarrow}(\text{out}_{i^{\prime}})$. Hence
if the restriction $\tilde{C}\rvert_{U,I^{\prime}}$ is contextual then there
are $i\neq i^{\prime}\in I^{\prime}$ such that
$\text{in}_{i}\in\text{LC}_{C}^{\leftarrow}(\text{out}_{i^{\prime}})$. Because
$I^{\prime}$ is small and uniformly distributed it can be shown that the
probability that this occurs is at most $\epsilon K^{D}$ for some small
$\epsilon$. $\tilde{C}\rvert_{U,I^{\prime}}$ is therefore non-contextual with
probability at most $\epsilon K^{D}$.

$\displaystyle\text{Prob}(e\rvert_{U,I^{\prime}}\text{ is contextual})$
$\displaystyle\leq\text{Prob}(\exists i\neq i^{\prime}\in I^{\prime}.\
i\in\text{LC}_{C}^{\leftarrow}(i^{\prime}))$ (4.113)
$\displaystyle\leq\epsilon K^{D}$ (4.114)

Suppose next that $Q$ is a quantum circuit model of depth $D$ and maximal fan-
in $K$. Quantum mechanically we require shared entanglement to produce
contextuality. Because we are interested in unconditional separations we do
not allow quantum circuits to start with an entangled state. If $\tilde{Q}$ is
contextual we therefore have some $i\neq i^{\prime}\in I$ such that
$\text{LC}_{Q}^{\leftarrow}(\text{out}_{i})\cap\text{LC}_{Q}^{\leftarrow}(\text{out}_{i^{\prime}})\neq\emptyset$.
It can be shown that the probability of this occurring is at most
$\epsilon(K^{D})^{2}$, where $\epsilon$ is the same small parameter. We,
therefore, have that the probability of the restriction
$\tilde{Q}\rvert_{U,I^{\prime}}$ is contextual is bounded by
$\epsilon(K^{D})^{2}$.

$\displaystyle\text{Prob}(\tilde{Q}\rvert_{U,I^{\prime}}\text{ is
contextual})$ $\displaystyle\leq\text{Prob}(\exists i\neq i^{\prime}\in
I^{\prime}.\
\text{LC}_{Q}^{\leftarrow}(i)\cap\text{LC}_{Q}^{\leftarrow}(i^{\prime})\neq\emptyset)$
(4.115) $\displaystyle\leq\epsilon(K^{D})^{2}$ (4.116)

Hence by looking at the restrictions we can only detect a constant difference
between shallow quantum and classical circuits.

###  4.6 Quantum advantage with shallow circuits

(a) (b) Figure 4.17:  Examples of rooted graphs. The circle denotes the root
node. (a) A 3-dimensional hypergrid. (b) A binary tree.

A shallow circuit is a family of circuits, not a single circuit. We now move
from single circuits to families of circuits by considering families of rooted
graphs $\\{G_{n}\\}_{n\in\mathbb{N}}$. We first present the two results. We
then explain the proof of both results, and in section 4.6.1 we give some
examples of families of graphs and shallow circuits.

Suppose first that $(e,\Phi)$ is a non-local game with classical bound
$\gamma$. In Section 4.3.1 we define a quantum circuit $Q_{n}$ that depends
only on the number of qudits of $\psi$ and the degree of $G_{n}$. If
$\\{G_{n}\\}_{n\in\mathbb{N}}$ has bounded degree then
$\\{Q_{n}\\}_{n\in\mathbb{N}}$ is shallow. We also define a game $\Phi_{n}$
such that the success probability of $Q_{n}$ exceeds $\gamma$. In Section
4.5.2 we showed that for any classical circuit the success probability is
bounded. We, therefore, have the following result.

######  Theorem 4.6.1.

Let $(e_{\psi,\pi},\Phi,\gamma)$ be a qudit non-local game and
$\\{G_{n}\\}_{n\in\mathbb{N}}$ a family of rooted graphs of bounded degree and
unbounded size. There exists two-round interactive games
$\\{\Phi_{G_{n}}\\}_{n\in\mathbb{N}}$ and a shallow quantum circuit strategy
$\\{U_{G_{n},\psi,\pi}\\}_{n\in\mathbb{N}}$ such that

  1. 1.

The success probability of $Q_{G_{n},\psi,\pi}$ on $\Phi_{G_{n}}$ violates
$\gamma$:

$\displaystyle p_{S}(Q_{G_{n},\psi,\pi},\Phi_{G_{n}})>\gamma$ (4.117)

  2. 2.

Let $\\{C_{n}\\}_{n\in\mathbb{N}}$ be any shallow circuit strategy. The
success probability of $C_{n}$ on $\Phi_{G_{n}}$ tends to $\gamma$ as $n$
increases.

$\displaystyle p_{S}(C_{n},\Phi_{G_{n}})$
$\displaystyle\leq\gamma+\epsilon_{n}$

where $\gamma<1$ is the classical bound of $\Phi$ and $\epsilon_{n}\in
O({\left\lvert G_{n}\right\rvert}^{-1})$.

Before giving the proof we state the analogous result for Weyl measurement
games. Suppose that the quantum strategy $e$ is realised by Weyl measurements
on a single-qudit state. We can then instead consider the quantum circuit
$Q_{n}$ and non-local game $\Phi_{n}$ defined in Section 4.3.1. This gives the
following result.

######  Theorem 4.6.2.

Let $(\Phi,\psi,\gamma)$ be a Weyl measurement game, and
$\\{G_{n}\\}_{n\in\mathbb{N}}$ a family of rooted graphs such that
$\text{deg}(G_{n})\in O(1)$ and
$\text{lim}_{n\to\infty}\text{rad}(G_{n})/{\left\lvert G_{n}\right\rvert}=0$.
There exists non-local games $\\{\Phi_{G_{n}}\\}_{n\in\mathbb{N}}$ and quantum
circuit strategies $\\{U_{\psi,G_{n}}\\}_{n\in\mathbb{N}}$ such that

  1. 1.

$\\{U_{\psi,G_{n}}\\}_{n\in\mathbb{N}}$ is shallow, and the success
probability of $U_{\psi,G_{n}}$ on $\Phi_{G_{n}}$ exceeds $\gamma$:

$\displaystyle p_{S}(U_{\psi,G_{n}},\Phi_{G_{n}})>\gamma$ (4.118)

  2. 2.

If $\\{C_{n}\\}_{n\in\mathbb{N}}$ is any shallow classical circuit strategy
then the violation of $\gamma$ by $C_{n}$ tends to $0$ for large $n$:

$\displaystyle p_{S}(C_{n},\Phi_{G_{n}})\leq\gamma+\epsilon_{n}$

where $\epsilon_{n}\in O(\text{rad}(G_{n})/{\left\lvert G_{n}\right\rvert})$.

The proofs take the same form.

###### Proof.

(Theorem I and II)
The proof of both statements follow the same pattern. We take a non-local game
$(e,\Phi)$ with a particular quantum realisation and a family of graphs
$\\{G_{n}\\}_{n\in\mathbb{N}}$. Write $\\{e_{n}\\}_{n}$ for the associated
family of quantum realised empirical models, $\\{s_{n}\\}_{n}$ for the family
of simulations. Because $e_{n}$ simulates $e$ its success probability on the
pullback problem $(s_{n})^{*}(\Phi)$ is equal to the success probability of
$e$, which violates the classical bound of the non-local game.

Under the assumptions on the graphs $\\{G_{n}\\}_{n}$ the model these
empirical models can be recast as a shallow quantum circuit $\\{Q_{n}\\}_{n}$.

For the classical bound, we can use Section 4.5.2 to derive a bound on the
form

$\displaystyle\text{CF}((s_{n})_{*}(\tilde{C}_{n}))\leq\epsilon_{n}$ (4.119)

for any classical shallow circuit $\\{C_{n}\\}_{n\in\mathbb{N}}$. The
violation of $(s_{n})_{*}(\tilde{C_{n}})$ of the classical bound $\gamma$ for
the non-local game $(e,\Phi)$ is therefore at most $\epsilon_{n}$. It follows
that the violation of $C_{n}$ of $\gamma$ on the pullback problem is also
bounded by $\epsilon_{n}$.

We also comment that the circuits we use are equivalent up to a constant
factor in-depth and fan-in to circuits using only input/output wires with bits
and only quantum wires that are qubits. An important point is that the number
of measurement settings at each measurement site does not blow up. ∎

####  4.6.1 Examples

We will now present some concrete examples of circuits arising from the
construction we have presented. We first define two classes of rooted graphs
(Figure 4.17(a)).

######  Definition 4.6.1.

The _hypergrid graph_ $[n]^{k}$, where $n,k\in\mathbb{N}$, has nodes
$\\{(a_{1},\dots,a_{k})\mid 1\leq a_{1},\dots,a_{k}\leq n\\}$, root
$(1,\dots,1)$, and an edge $\\{(a_{1},\dots,a_{k}),(b_{1},\dots,b_{k})\\}$
whenever ${\left\lvert a_{j}-b_{j}\right\rvert}=1$ for some $j$ and
$a_{j^{\prime}}=b_{j^{\prime}}$ for all $j^{\prime}\neq j$.

Note that $[n]^{1}$ is a line, $[n]^{2}$ is a square grid, $[n]^{3}$ is a 3D
grid, etc.

######  Definition 4.6.2.

Let $n,k\in\mathbb{N}$. The _$k$ -ary tree $T_{k,n}$ of depth $n$_ is the
rooted graph with nodes $\\{(i,j)\mid
i\in\\{1,\dots,n\\},j\in\\{1,\dots,k^{i-1}\\}\\}$, root $(1,1)$, and edges
$\\{(i,j),(i^{\prime},j^{\prime})\\}$ whenever $i^{\prime}=i+1$ and
$k(j-1)<j^{\prime}\leq kj$.

Let $n,k\in\mathbb{N}$. The hypergrid $[n]^{k}$ has degree $2k$ and the tree
$T_{n,k}$ has degree $k$. For a fixed $k\in\mathbb{N}$ the families
$\\{[n]^{k}\\}_{n\in\mathbb{N}}$ or $\\{T_{n,k}\\}_{n\in\mathbb{N}}$ therefore
have bounded degree. If we use either family to define a family of quantum
circuits $\\{Q_{n}\\}_{n\in\mathbb{N}}$ then the resulting circuit is shallow.
Furthermore, $[n]^{k}$ has radius $nk$ and size $n^{k}$. while $T_{n,k}$ has
radius $k$ and size $k^{n+1}-1$. In Theorem I the parameters $\epsilon_{n}$
therefore converge at a rate of $O(1/n^{k})$ or $O(1/{k^{n}})$ respectively.
And in Theorem II the rate of converge is $O(1/n^{k-1})$ or $O(1/{k^{n-1}})$
respectively.

For the hypergrid graphs the quantum circuits have polynomial size $O(n^{k})$,
while for tree graphs it has exponential size $O(k^{n})$.

The game $\Phi_{G}$ and the quantum circuit strategy $\tilde{Q}_{\psi,G}$ is a
distributed circuit version of any non-local game. We showed that this game is
solved with high probability by $Q_{\psi,G}$ whose depth and maximal fan-in
only depend on the size of $I$ and the maximal degree of $G$. However, for any
classical circuit strategy the success probability is bounded by a bound
involving the size of $G$ and the radius of $G$.

The quantum circuits arising from the Magic Square game and 2D graphs and
binary trees are shown in the following figures (Figures 4.18 \- 4.21).

Figure 4.18: Circuit version of Magic Square game played on a 2D grid.  Figure
4.19: Circuit version of the Magic Square game played on binary trees. Figure
4.20: Magic square game played on a grid in two rounds. Figure 4.21: Magic
square game played on a tree in two rounds.

##  Chapter 5 Final Remarks

The motivation behind this thesis is the idea that contextuality can be a
useful phenomena for understanding quantum advantage in computing. The results
that we have presented touches on two different aspects of this idea. We need
more refined ways of identifying types of contextuality, and we need concrete
examples relating these types of contextuality to quantum advantage.

Cohomology is in many settings a powerful technique for identifying useful
structure in data. For example, the simplicial cohomology of a topological
space is related to its number of “holes”. In the sheaf theoretic framework it
is natural to consider Čech cohomology as an invariant of contextuality. Čech
cohomology can detect contextuality in a range of examples, indicating that it
could be a useful way of identifying types of contextuality. Another promising
technique for studying contextuality is the topological approach of Okay et
al. We have shown that any false negative of the Čech approach induces a false
negative of the topological approach. As far as detecting contextuality the
topological approach therefore cannot go further than the Čech cohomology
approach.

Bravyi, Gosset, and König’s quantum advantage result with shallow circuits
currently is the strongest example of quantum advantage using contextuality.
We have highlighted the role of simulations in their result as a way of
bounding the success probability of classical circuits. We have extended their
result by giving a systematic way of promoting any quantum realised
multipartite empirical model to a quantum advantage result with shallow
circuits. The construction is parametrised by a family of graphs that are used
as templates to spread entanglement using teleportation. By considering
different families of graphs we can achieve a different tradeoff in size vs
strength of separation.

There are measurements making any (pure) entangled $n$-qudit state contextual
[Har93, ACY16]. One can therefore use any (pure) entangled state.

###  5.1 Further work

An unconditional quantum advantage result for a general computational model
appears to be far away. However, BGK’s result has spawned a new interest in
trying to prove unconditional results for models of computation with
structural restrictions. Perhaps by studying such models we can identify the
common structures that are important. A potential candidate for such a model
is the _cell probe model_.

Contextuality has shown itself to be useful for proving unconditional bounds
on memory complexity. Karanjai et al. [KWB18] proves that the memory
complexity of the Gottesmann Knill algorithm [AG04] is asymptotically optimal.
The proof appears to exploit a particular type of contextuality. It might be
interesting to see if this structure can be given a concise description using
methods like cohomology or simulations and if it can similarly be generalised
to give a general connection between contextuality and quantum advantage.

## References

  * [AB09] J. Anders and D. Browne.  Computational power of correlations.  Physical review letters, 2009.
  * [AB11] Samson Abramsky and Adam Brandenburger.  The Sheaf-Theoretic Structure Of Non-Locality and Contextuality.  New Journal of Physics, 13(11):113036, November 2011.  arXiv: 1102.0264.
  * [ABK+15] Samson Abramsky, Rui Soares Barbosa, Kohei Kishida, Raymond Lal, and Shane Mansfield.  Contextuality, Cohomology and Paradox.  arXiv:1502.03097 [quant-ph], page 18 pages, 2015.  arXiv: 1502.03097.
  * [ABKM19a] Samson Abramsky, Rui Soares Barbosa, Martti Karvonen, and Shane Mansfield.  A comonadic view of simulation and quantum resources.  2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–12, June 2019.  arXiv: 1904.10035.
  * [ABKM19b] Samson Abramsky, Rui Soares Barbosa, Martti Karvonen, and Shane Mansfield.  Simulations of quantum resources and the degrees of contextuality.  TACL 2019, page 1, 2019.
  * [ABM17] Samson Abramsky, Rui Soares Barbosa, and Shane Mansfield.  The contextual fraction as a measure of contextuality.  Physical Review Letters, 119(5):050504, August 2017.  arXiv: 1705.07918.
  * [Abr13] Samson Abramsky.  Relational Databases and Bell’s Theorem.  arXiv:1208.6416 [quant-ph], July 2013.  arXiv: 1208.6416.
  * [ACCA18] Barbara Amaral, Adán Cabello, Marcelo Terra Cunha, and Leandro Aolita.  Noncontextual wirings.  Physical Review Letters, 120(13):130403, March 2018.  arXiv:1705.07911 [quant-ph].
  * [ACY16] Samson Abramsky, Carmen M. Constantin, and Shenggang Ying.  Hardy is (almost) everywhere: Nonlocality without inequalities for almost all entangled multipartite states.  Information and Computation, 250:3–14, October 2016.
  * [AFLS15] Antonio Acín, Tobias Fritz, Anthony Leverrier, and Ana Belén Sainz.  A Combinatorial Approach to Nonlocality and Contextuality.  Communications in Mathematical Physics, 334(2):533–628, March 2015\.
  * [AG04] Scott Aaronson and Daniel Gottesman.  Improved Simulation of Stabilizer Circuits.  Physical Review A, 70(5):052328, November 2004.  arXiv: quant-ph/0406196.
  * [AH12] Samson Abramsky and Lucien Hardy.  Logical Bell Inequalities.  Physical Review A, 85(6):062114, June 2012.  arXiv: 1203.1352.
  * [AMB12] Samson Abramsky, Shane Mansfield, and Rui Soares Barbosa.  The Cohomology of Non-Locality and Contextuality.  Electronic Proceedings in Theoretical Computer Science, 95:1–14, October 2012.  arXiv: 1111.3620.
  * [Ark12] Alex Arkhipov.  Extending and Characterizing Quantum Magic Games.  arXiv:1209.3819 [quant-ph], September 2012.  arXiv: 1209.3819.
  * [BCE+07] Jonathan Barrett, Carlton M. Caves, Bryan Eastin, Matthew B. Elliott, and Stefano Pironio.  Modeling Pauli measurements on graph states with nearest-neighbor classical communication.  Physical Review A, 75(1):012103, January 2007.  arXiv: quant-ph/0603032.
  * [BDE+22] Rui Soares Barbosa, Tom Douce, Pierre-Emmanuel Emeriau, Elham Kashefi, and Shane Mansfield.  Continuous-variable nonlocality and contextuality.  Communications in Mathematical Physics, 391(3):1047–1089, 2022\.  Publisher: Springer.
  * [Bel64] J. S. Bell.  On the Einstein Podolsky Rosen paradox.  Physics Physique Fizika, 1(3):195–200, November 1964.  Publisher: American Physical Society.
  * [BGK18] Sergey Bravyi, David Gosset, and Robert Koenig.  Quantum advantage with shallow circuits.  Science, 362(6412):308–311, October 2018.  arXiv: 1704.00690.
  * [BGKT20] Sergey Bravyi, David Gosset, Robert König, and Marco Tomamichel.  Quantum advantage with noisy shallow circuits.  Nature Physics, 16(10):1040–1045, October 2020.  Bandiera_abtest: a Cg_type: Nature Research Journals Number: 10 Primary_atype: Research Publisher: Nature Publishing Group Subject_term: Information theory and computation;Quantum information Subject_term_id: information-theory-and-computation;quantum-information.
  * [BKM21] Rui Soares Barbosa, Martti Karvonen, and Shane Mansfield.  Closing Bell: Boxing black box simulations in the resource theory of contextuality.  arXiv preprint arXiv:2104.11241, 2021.
  * [Bro12] Kenneth S. Brown.  Cohomology of Groups.  Springer Science & Business Media, December 2012.  Google-Books-ID: 2fzlBwAAQBAJ.
  * [Cab01] Adán Cabello.  “All versus nothing” inseparability for two observers.  Physical Review Letters, 87(1):010403, 2001.  Publisher: APS.
  * [Car17] Giovanni Caru.  On the cohomology of contextuality.  arXiv preprint arXiv:1701.00656, 2017.
  * [Car18] Giovanni Carù.  Towards a complete cohomology invariant for non-locality and contextuality.  arXiv:1807.04203 [quant-ph], July 2018.  arXiv: 1807.04203.
  * [Car19] Giovanni Carú.  Logical and topological contextuality in quantum mechanics and beyond.  PhD Thesis, University of Oxford, 2019.
  * [CHSH69] John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt.  Proposed Experiment to Test Local Hidden-Variable Theories.  Physical Review Letters, 23(15):880–884, October 1969.  Publisher: American Physical Society.
  * [CHTW10] Richard Cleve, Peter Hoyer, Ben Toner, and John Watrous.  Consequences and Limits of Nonlocal Strategies.  arXiv:quant-ph/0404076, January 2010.  arXiv: quant-ph/0404076.
  * [CSW14] Adán Cabello, Simone Severini, and Andreas Winter.  Graph-theoretic approach to quantum correlations.  Physical review letters, 112(4):040401, 2014.  Publisher: APS.
  * [DK16] Ehtibar N. Dzhafarov and Janne V. Kujala.  Context–content systems of random variables: The Contextuality-by-Default theory.  Journal of Mathematical Psychology, 74:11–33, 2016.  Publisher: Elsevier.
  * [DKC15] Ehtibar N. Dzhafarov, Janne V. Kujala, and Victor H. Cervantes.  Contextuality-by-default: a brief overview of ideas, concepts, and terminology.  In International Symposium on Quantum Interaction, pages 12–23. Springer, 2015.
  * [dS17] Nadish de Silva.  Logical paradoxes in quantum computation.  August 2017.
  * [EPR35] A. Einstein, B. Podolsky, and N. Rosen.  Can Quantum-Mechanical Description of Physical Reality Be Considered Complete?  Physical Review, 47(10):777–780, May 1935.  Publisher: American Physical Society.
  * [GHSZ90] Daniel M. Greenberger, Michael A. Horne, Abner Shimony, and Anton Zeilinger.  Bell’s theorem without inequalities.  American Journal of Physics, 58(12):1131–1143, December 1990.  Publisher: American Association of Physics Teachers.
  * [GNR19] François Le Gall, Harumichi Nishimura, and Ansis Rosmanis.  Quantum Advantage for the LOCAL Model in Distributed Computing.  page 14 pages, 2019.  arXiv:1810.10838 [quant-ph].
  * [GS20] Daniel Grier and Luke Schaeffer.  Interactive shallow Clifford circuits: Quantum advantage against NC¹ and beyond.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, pages 875–888, New York, NY, USA, June 2020. Association for Computing Machinery.
  * [Har93] Lucien Hardy.  Nonlocality for two particles without inequalities for almost all entangled states.  Physical Review Letters, 71(11):1665–1668, September 1993.  Publisher: American Physical Society.
  * [Kar19] Martti Karvonen.  Categories of Empirical Models.  Electronic Proceedings in Theoretical Computer Science, 287:239–252, January 2019.  arXiv: 1804.01514.
  * [KS75] Simon Kochen and E. P. Specker.  The Problem of Hidden Variables in Quantum Mechanics.  In C. A. Hooker, editor, The Logico-Algebraic Approach to Quantum Mechanics: Volume I: Historical Evolution, The University of Western Ontario Series in Philosophy of Science, pages 293–328. Springer Netherlands, Dordrecht, 1975.
  * [KWB18] Angela Karanjai, Joel J. Wallman, and Stephen D. Bartlett.  Contextuality bounds the efficiency of classical simulation of quantum processes.  arXiv:1802.07744 [quant-ph], February 2018.  arXiv: 1802.07744.
  * [Man20] Shane Mansfield.  Contextuality is topological.  Quantum Views, 4:31, 2020.  Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften.
  * [Mer90] N. David Mermin.  Extreme quantum entanglement in a superposition of macroscopically distinct states.  Physical Review Letters, 65(15):1838–1840, October 1990.  Publisher: American Physical Society.
  * [NC10] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, December 2010.
  * [OKI22] Cihan Okay, Aziz Kharoof, and Selman Ipek.  Simplicial quantum contextuality.  arXiv preprint arXiv:2204.06648, 2022.
  * [OR20] Cihan Okay and Robert Raussendorf.  Homotopical approach to quantum contextuality.  Quantum, 4:217, 2020.  Publisher: Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften.
  * [ORBR17] Cihan Okay, Sam Roberts, Stephen D. Bartlett, and Robert Raussendorf.  Topological proofs of contextuality in quantum mechanics.  arXiv:1701.01888 [quant-ph], October 2017.  arXiv: 1701.01888.
  * [OS21] Cihan Okay and Daniel Sheinbaum.  Classifying space for quantum contextuality.  In Annales Henri Poincaré, volume 22, pages 529–562. Springer, 2021.  Issue: 2.
  * [OTR18] Cihan Okay, Emily Tyhurst, and Robert Raussendorf.  The cohomological and the resource-theoretic perspective on quantum contextuality: common ground through the contextual fraction.  arXiv preprint arXiv:1806.04657, 2018.
  * [Rau13] Robert Raussendorf.  Contextuality in measurement-based quantum computation.  Physical Review A, 88(2):022322, 2013.  Publisher: APS.
  * [Rou17] Frank Roumen.  Cohomology of Effect Algebras.  Electronic Proceedings in Theoretical Computer Science, 236:174–201, January 2017.  arXiv: 1602.00567 version: 2.
  * [Spe60] E. Specker.  E. Specker: ”The logic of non-simultaneously decidable propositions” (1960), 1960.  arXiv:1103.4537 [physics, physics:quant-ph].
  * [Spe05] R. W. Spekkens.  Contextuality for preparations, transformations, and unsharp measurements.  Physical Review A, 71(5):052108, May 2005.  Publisher: American Physical Society.
  * [Wei94] Charles A. Weibel.  An Introduction to Homological Algebra.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1994.
  * [WKST19] Adam Bene Watts, Robin Kothari, Luke Schaeffer, and Avishay Tal.  Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits.  Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 515–526, June 2019.  arXiv: 1906.08890.