# Connecting XOR and XOR* games

Lorenzo Catani1,∗, Ricardo Faleiro2,†, Pierre-Emmanuel Emeriau3, Shane
Mansfield3, and Anna Pappa1 $1-$Electrical Engineering and Computer Science
Department,
Technische Universitat Berlin, 10587 Berlin, Germany  $2-$ Instituto de
Telecomunicações, 049-001, Lisboa, Portugal  $3-$ Quandela, 7 Rue Léonard de
Vinci, 91300 Massy, France  $^{*}\;$lorenzo.catani@tu-
<EMAIL_ADDRESS>
###### Abstract

In this work we focus on two classes of games: XOR nonlocal games and XOR*
sequential games with monopartite resources. XOR games have been widely
studied in the literature of nonlocal games, and we introduce XOR* games as
their natural counterpart within the class of games where a resource system is
subjected to a sequence of controlled operations and a final measurement.
Examples of XOR* games are $2\rightarrow 1$ quantum random access codes (QRAC)
and the CHSH* game introduced by Henaut et al. in [PRA 98,060302(2018)]. We
prove, using the diagrammatic language of process theories, that under certain
assumptions these two classes of games can be related via an explicit theorem
that connects their optimal strategies, and so their classical (Bell) and
quantum (Tsirelson) bounds. We also show that two of such assumptions – the
reversibility of transformations and the bi-dimensionality of the resource
system in the XOR* games – are strictly necessary for the theorem to hold by
providing explicit counterexamples. We conclude with several examples of pairs
of XOR/XOR* games and by discussing in detail the possible resources that
power the quantum computational advantages in XOR* games.

[name=Theorem]thm [name=Lemma]lemm [name=Proposition]prop

##  1 Introduction

Computational tasks for which quantum strategies outperform classical ones
have long been and are still an important focus of study. A well-known example
is the CHSH game, a way of recasting the Clauser-Horne-Shimony-Holt (CHSH)
formulation [1] of Bell’s celebrated theorem [2] into a game for which quantum
strategies can provide an advantage over classical ones. It is a cooperative
game with two players, Alice and Bob, who agree on a strategy before the game
begins but are separated and unable to communicate with each other once the
game is in progress. A referee poses one of two binary questions to each
player, and the players win if the sum of their answers equals the product of
the questions (arithmetic is modulo $2$). The bound on the performances of
classical strategies is known as the Bell bound, while in the quantum case the
maximum winning probability is known as the Tsirelson bound [3]. The CHSH game
is of great importance due to the dependence of its optimal success
probability on the underlying theory describing the implemented strategies,
which gives us a tool to experimentally distinguish between distinct physical
theories. Scenarios that involve violations of the Bell bound are said to
manifest “nonlocality” (meaning that the statistics they show are inconsistent
with a description in terms of a local hidden variable model [2]), and the
Tsirelson bound can be interpreted as a quantifier of how nonlocal quantum
theory is within the broader landscape of all possible no-signaling theories.
Nonlocality is also known to be a useful resource for applications in quantum
technology, e.g., in device-independent cryptography [4, 5, 6] and it can be
considered to be a special form of the more general notion of contextuality
[7, 8], known to be a necessary ingredient for quantum advantage and speedups
in a variety of settings [9, 20, 29, 30, 31, 32, 33, 34, 35, 10, 11, 12, 13,
14, 15, 16, 17, 18, 19, 21, 22, 23, 24, 25, 26, 27, 28].

Inspired by the CHSH game, broad classes of nonlocal cooperative games have
been proposed. These involve, in their simplest formulation, two spatially
separated parties performing operations on some shared resource system, while
being forbidden from communicating. Moreover, there also exist games cast in
different setups that show the same classical and quantum bounds as the CHSH
game [36, 37, 9, 38, 39]. These do not involve two spatially separated parties
performing local operations on the corresponding systems, but only an input
resource system subjected to an ordered sequence of transformations or
measurements. We refer to this kind of games as monopartite sequential games.
Obviously, in these cases, the Tsirelson bound cannot be read as a quantifier
of the nonlocality of quantum theory and it becomes natural to wonder about
the nature of the source of the quantum-over-classical advantage in such
games, and whether there is a deep connection between these protocols and
nonlocal games.

In this work we address these questions for particular classes of nonlocal and
monopartite sequential games that include various known games studied in the
literature. More precisely, we focus on a precise subclass of nonlocal games –
XOR games [40] – where the goal is to satisfy the condition that a (possibly
nonlinear) function of the inputs equals the XOR (or sum modulo $2$) of the
output bits. Via Theorem 1, we relate a subset of these to a class of
monopartite sequential games – the XOR* games – where the goal is to obtain,
as single output, the (possibly nonlinear) function of the inputs. The already
mentioned CHSH game is the most famous example of an XOR game, but other
examples within this class exist in the literature, such as the EAOS game [41,
42] where Alice and Bob have to compute a Kronecker-delta function of the
input trits. Regarding XOR* games, examples are the $2\rightarrow 1$ quantum
random access codes (QRACs)[37], $2\rightarrow 1$ parity oblivious
multiplexing (POM) [9] and CHSH* [39] games. By virtue of our categorisation,
the CHSH* game emerges as the natural XOR* version of the CHSH game and the
QRACs read as the XOR* versions of an XOR game which is different from the
CHSH game. This may sound surprising, as the $2\rightarrow 1$ QRAC is usually
associated to the CHSH game in that it shares the same values for the Bell and
Tsirelson bounds [43].

Crucial in our work is Theorem 1: it allows us to connect the optimal quantum
strategies for the classes of XOR and XOR* games. The theorem involves certain
assumptions: bounding the cardinalities of the inputs (as a consequence of the
use of a lemma due to Cleve et al. [40]) and restricting the XOR* games to
those involving only two-dimensional (2D) resource systems. These constraints
do not prevent the result to apply to a number of known XOR and XOR* games
present in the literature. We describe the main ones in subsection 3.3 and, as
a consequence of our framework, we also define the XOR versions of known XOR*
games such as the $2\rightarrow 1$ QRAC [37], the binary output Torpedo game
[26], and the Gallego et al. [44] dimensional witness. Theorem 1 also assumes
that the strategies of the XOR* games involve only reversible gates. We show
how this assumption is strictly necessary for the theorem to hold by providing
an example of XOR* game where the use of (irreversible) reset gates can create
a quantum-classical performance gap that does not arise if considering only
reversible gates. We refer to this feature as reset-induced gap activation.
The mapping described in Theorem 1 can be used to show that preparation
contextuality [45] is a resource for outperforming classical strategies in
certain XOR* games (see B). The reason is that the established proofs of
nonlocality as a resource for outperforming classical strategies in XOR
nonlocal games can be mapped to proofs of preparation contextuality in
monopartite sequential games (interpreted as prepare and measure scenarios)
via the mapping of the theorem. However, this argument does not apply to all
the XOR* games that mimic the quantum over classical computational advantages
of the XOR games and, crucially, does not apply to what we define as dual XOR*
games of the XOR games under consideration. For example, it does not apply to
the CHSH* game. We provide a thorough analysis of this fact and of why other
typical candidates employed to explain the origin of the quantum advantage do
not work in the case of XOR* games. We conclude by outlining a proposal to
develop a new notion of nonclassicality in the spirit of generalized
contextuality that applies to these games.

The remainder of the paper is structured as follows. In section 2 we describe
nonlocal games and monopartite sequential games, focusing specifically on XOR
and XOR* games. In section 3 we relate XOR and XOR* games via Theorem 1, which
establishes a mapping between these two classes. In particular, we prove
Theorem 1 using a diagrammatic approach according to the formalism of process
theories [46], and we give various examples of games within these classes. In
section 4 we discuss why the typical features employed to explain the quantum
computational advantage in information processing tasks do not apply in the
case of XOR* games and we advance a proposal to overcome this problem. In
section 5 we discuss the significance of the results and we outline future
challenges. Finally, we relegate all proofs of the stated lemmas to A.

##  2 XOR nonlocal games and XOR* monopartite sequential games

A cooperative game consists of a protocol involving some number of agents
(players) that cooperate to perform a certain task. In order to win the game
the players have to come up with a strategy to produce outputs which
successfully compute a task function of the inputs provided by a referee. We
formulate the winning condition as a predicate that equates the task function
with a function of the outputs. A game is also specified by the setup it is
played in. The setup is defined by a list of elements that compose the
protocol, e.g., the kind and number of resource systems involved, the number
and cardinalities of inputs and outputs, and the number and sequential order
of operations like transformations or measurements (controlled by the
players). The list of actions that each player has to adopt given particular
values of the inputs defines a strategy for the game. Each strategy has to
obey possible restrictions that, given the specification of the setup, the
protocol posits. The typical example of such a restriction, in the context of
nonlocal games where the players are spatially separated and cannot
communicate, is the principle of no-signaling. Notice that these restrictions
are theory-independent, in the sense that they must be obeyed independently of
the precise operational theory (e.g., classical or quantum theory) that the
strategies of the players are formulated in.111The term “theory-independent”
is standard in the literature of device-independent protocols (see for example
[47]). With this it is meant that the restrictions have to be obeyed by all
the operational theories that are under comparison (e.g., classical, quantum
and GPTs).

Finally, a game, in general, can also be specified by extra constraints that
do not emerge from the setup, but are artificial constraints that are imposed
on the set of possible strategies. Examples of these are the parity
obliviousness in the parity oblivious multiplexing game [9], the dimensional
constraint in quantum random access codes [36, 37] and, more recently, the
information restriction on the communication channel in the protocols
considered in [47]. The purpose of introducing these artificial constraints is
to allow for an interesting categorisation of the strategies, i.e., to create
a performance gap between distinct operational theories. In other words,
thanks to these constraints, it is possible to separate the performances of
the strategies depending on the operational theory they are formulated in. In
particular, they allow to observe performance gaps between classical and
quantum strategies. Given some game $G$, such a gap is characterised by a
positive quantum-over-classical advantage,222In the following, we will refer
to the quantum-over-classical advantage also as “quantum-classical gap” or
“performance gap”. $\Omega(G):=\omega_{q}(G)-\omega_{c}(G)>0$, where
$\omega_{q}(G)$ and $\omega_{c}(G)$ denote the highest probabilities to win
$G$ by means of quantum and a classical strategy, respectively called the
quantum value and classical value of the game. Notice that when we say
“classical” and “quantum” strategies we mean strategies that employ systems
that are prepared, transformed and measured according to the rules of the
respective theory. Furthermore, when referring to the quantum-over-classical
advantage and/or the classical and quantum values for games bearing artificial
constraints, we will explicitly write the type of constraint in the notation.
For instance, XOR* games restricted to two-dimensional resources and
reversible operations, which we will extensively deal with later on, have
their quantum-over-classical advantage written as
$\Omega(\textup{XOR}^{*}|^{Rev}_{2D}):=\omega_{q}(\textup{XOR}^{*}|^{Rev}_{2D})-\omega_{c}(\textup{XOR}^{*}|^{Rev}_{2D}).$

In summary, a game is formally defined by a specification of a setup,
predicate, restrictions and possible artificial constraints. In this section
we are interested in two broad classes of games: nonlocal games and
monopartite sequential games, which we now define in the case of two players
(figure 1).

######  Definition 1 (Two-player Nonlocal game).

  * •

Setup: the two players, Alice and Bob, receive inputs $s\in\mathcal{S}$ and
$t\in\mathcal{T}$, respectively, sampled from a known probability distribution
$p(s,t)$, where $\mathcal{S}$ and $\mathcal{T}$ denote tuples of dits of
finite dimension. Before the game starts, Alice and Bob can agree on a
strategy, while they cannot communicate after the game starts. Such a strategy
could involve using a shared resource system on which they perform local
operations (transformations and measurements) controlled by the values of
their respective inputs. Each player has to provide an output, denoted with
$a\in\mathcal{A}$ for Alice and $b\in\mathcal{B}$ for Bob, where $\mathcal{A}$
and $\mathcal{B}$ denote tuples of dits of finite dimension.

  * •

Restriction: the restriction of the setup is the no-signalling condition, that
prevents Alice and Bob – in spatially separated locations – from communicating
during the game,

$p(a|st)=p(a|s);\;p(b|st)=p(b|t).$ (1)

  * •

Predicate:

$W_{g|f}(a,b|s,t)=\left\\{\begin{array}[]{ll}1\hskip 2.84544pt\textup{if
}\hskip 2.84544ptf(s,t)=g(a,b)\\\ 0\hskip 2.84544pt\textup{otherwise}.\\\
\end{array}\right.$ (2)

The function $f(s,t)$ is what we called the “task function” at the beginning
of the section.

######  Definition 2 (Two-player Monopartite Sequential game).

  * •

Setup: the two players, Alice and Bob, receive inputs $s\in\mathcal{S}$ and
$t\in\mathcal{T}$, respectively, sampled from a known probability distribution
$p(s,t)$, where $\mathcal{S}$ and $\mathcal{T}$ denote tuples of dits of
finite dimension. They are ordered in sequence, say Alice before Bob ( denoted
as “$A<B$”). Alice is given a single resource system on which she applies one
operation controlled by the value of the input $s$ she receives. The system is
forwarded to Bob on which he also applies one operation controlled by the
value of the input $t$ he receives. At the end the resource system is
subjected to a fixed measurement. In this way it is subjected to a ordered
sequence of operations (transformations or measurements) controlled by the
inputs, and the strategy the players agree on consists of choosing the
resource system, the controlled operations and the measurement. The outcome
$m\in\mathcal{M}$ of the measurement is the output of the game, where
$\mathcal{M}$ denotes a tuple of dits of finite dimension.

  * •

Restriction: analogously to the principle of no-signaling in nonlocal games,
the physical restriction on the game is here that the communication between
the players cannot violate the causal structure imposed by the setup. This
means that Bob cannot signal backwards to Alice. This is called the principle
of weak-causality [48] and can be written as follows,

$p(a|s,t)=p(a|s),$ (3)

where $a$ is the variable associated with Alice’s choice of operation.

  * •

Artificial constraints: They might be of various types. For example,
reversibility of operations, dimensional constraints on the resource, parity
obliviousness, informational restriction of the channels, etc.

  * •

Predicate:

$W_{f}(m|s,t)=\left\\{\begin{array}[]{ll}1\hskip 2.84544pt\textup{if }\hskip
2.84544ptf(s,t)=m\\\ 0\hskip 2.84544pt\textup{otherwise}.\\\
\end{array}\right.$ (4)

Again, the function $f(s,t)$ is what we called the “task function” at the
beginning of the section.

Figure 1: Setup of monopartite sequential games (left) and nonlocal games
(right). In the former case the binary outcome $m$ is obtained from a unique
measurement after two controlled operations $U_{s}$ and $V_{t}$ performed on a
monopartite resource system whose state is denoted with $\psi$. In the latter
case the outcomes $a,b$ are obtained via two spatially separated measurements,
which are implemented after two controlled operations $U_{s}$ and $V_{t}$ have
been performed on a bipartite resource system denoted with $\phi$. In addition
to illustrating the setups of the games just described, the figure above can
be read as a process diagram composed of systems (wires) and processes
(boxes), where states are special processes with trivial inputs (upside-down
triangles), and effects special processes with trivial outputs (triangles). We
will use the language of process theories later on when proving our main
result.

A widely known class of two-player nonlocal games are the XOR games. First
introduced in [40], they have been studied in the context of multi-interactive
proof systems with entanglement. XOR games form a subset within the class of
binary nonlocal games, which are nonlocal games where the players output bits
(even though the inputs do not necessarily need to be bits). An XOR game
further restricts such a class by requiring, as the winning condition, that
the particular task function must equate the parity (or XOR) of the output
bits. The CHSH game is one example of an XOR game, where the winning condition
states that the parity of the output bits must equal the product of the input
bits. Other XOR games might consider different input sets, and distinct
functions over such inputs; for instance, in the EAOS game [42] the function
is a Kronecker-delta of the input trits.

Regarding monopartite sequential games, the precise subset that we will focus
on, are XOR* games, where the winning condition is that the particular task
function must equate the output bit. Our motivation for focusing on these
specific games is to identify the class of monopartite sequential games that
reproduce the same classical, quantum bounds present in XOR games, in analogy
to the CHSH* and CHSH example first studied in [39]. This fact also motivates
the name “XOR*”. Following this approach we will connect the two classes of
games via a theorem that relates their strategies and we will clarify the
relationship between various examples of games that have been extensively
studied and whose performances manifest the same bounds. We now characterise
XOR and XOR* games in agreement with the previous definitions of nonlocal
games (definition 1) and monopartite sequential games (definition 2).

######  Definition 3 (XOR games).

  * •

Setup: Two-player nonlocal game setup, where the outputs are one bit for each
player, i.e., $\mathcal{A}=\mathbb{Z}_{2}$ and $\mathcal{B}=\mathbb{Z}_{2}$.

  * •

Restriction: No-signalling condition,

$p(a|st)=p(a|s);\;p(b|st)=p(b|t).$ (5)

  * •

Predicate:

$W_{f}(a\oplus b|s,t)=\left\\{\begin{array}[]{ll}1\hskip 2.84544pt\textup{if
}\hskip 2.84544ptf(s,t)=a\oplus b\\\ 0\hskip 2.84544pt\textup{otherwise}.\\\
\end{array}\right.$ (6)

######  Definition 4 (XOR* games).

  * •

Setup: Two-player monopartite sequential game setup, where the output is a
bit, i.e., $\mathcal{M}=\mathbb{Z}_{2}$. .

  * •

Restriction: Weak-causality,

$p(a|s,t)=p(a|s);$ (7)

where $a$ is a classical variable labeling the state after Alice’s operation.

  * •

Artificial constraints: Various types. For example, reversible operations,
dimensional constraints on the resource, parity obliviousness, etc.

  * •

Predicate:

$W_{f}(m|s,t)=\left\\{\begin{array}[]{ll}1,\hskip 2.84544pt\textup{if }\hskip
2.84544ptf(s,t)=m\\\ 0,\hskip 2.84544pt\textup{otherwise}.\\\
\end{array}\right.$ (8)

Notice how XOR* games are nothing but binary monopartite sequential games.

##  3 Relating XOR and XOR* games

In this section we connect XOR and XOR* games. In order to do so, we impose
constraints on the cardinality of inputs, as well as on the dimensionality of
the resource system and the type of transformations in the XOR* games. In the
following, with the aid of known results about XOR games and extending a proof
contained in [39], we first prove our main theorem. We then show that both
assumptions of reversibility of transformations and bi-dimensionality of the
resource system in XOR* games are crucial for the theorem to hold by providing
counter examples where such assumptions do not hold and the mapping of the
theorem breaks down.

###  3.1 Main result

We start by focusing on a subset of XOR games, which we call ebit XOR games.
They are XOR games for which the Tsirelson bound is obtained with strategies
using one Bell state, that is, exploiting what is called an ebit—a single bit
of shared bipartite entanglement [49]. We now state two lemmas concerning ebit
XOR games that will be useful to prove our main theorem, Theorem 1.

######  Lemma 1.

Any XOR game where $\textup{min}(|\mathcal{S}|,|\mathcal{T}|)\leq 4$ is an
ebit-XOR game.

###### Proof.

From Theorem 10 of Cleve et al. [40], we know that $\lceil{m/2}\rceil$ qubits
in a maximally entangled state, for $m=min(|\mathcal{S}|,|\mathcal{T}|)$, are
sufficient to implement an optimal quantum strategy in an XOR game.
Consequently, a Bell state (a maximally entangled state of two qubits) is
sufficient to implement an optimal quantum strategy when
$min(|\mathcal{S}|,|\mathcal{T}|)\leq 4$. ∎

######  Lemma 2 (V.1,[50]).

Given inputs $(s,t)$ for Alice and Bob specifying their respective projective
single-qubit measurements, $A_{a|s},B_{b|t}$, applied, respectively, to the
first and second qubit of the two-qubit system in the Bell state
$\ket{\phi^{+}}=\frac{1}{\sqrt{2}}\ket{00}+\ket{11}$, the probability
$p(a,b|s,t)$ of obtaining output bits $(a,b)$ is such that
$p(0,0|s,t)=p(1,1|s,t)$ and $p(0,1|s,t)=p(1,0|s,t)$.

###### Proof.

According to the Born rule, the probability $p(a,b|s,t)$ is given by
$p(a,b|s,t)=\textrm{Tr}[(A_{a|s}\otimes
B_{b|t})\outerproduct{\phi^{+}}{\phi^{+}}]$, where $A_{a|s},B_{b|t}$ are given
by
$\\{A_{0|s}=\outerproduct{0_{s}}{0_{s}},A_{1|s}\outerproduct{1_{s}}{1_{s}}\\}$
and
$\\{B_{0|t}=\outerproduct{0_{t}}{0_{t}},B_{1|t}=\outerproduct{1_{t}}{1_{t}}\\}$,
respectively, with

$\displaystyle\ket{0_{i}}$
$\displaystyle=\cos\frac{\theta_{i}}{2}\ket{0}+e^{i\phi_{i}}\sin\frac{\theta_{i}}{2}\ket{1}$
(9) $\displaystyle\ket{1_{i}}$
$\displaystyle=\sin\frac{\theta_{i}}{2}\ket{0}-e^{-i\phi_{i}}\cos\frac{\theta_{i}}{2}\ket{1},$
(10)

where $\theta_{i}$ and $\phi_{i}$ are the angles defining the Bloch
representation of the vectors, with $i\in\\{s,t\\}.$ Given that
$\innerproduct{0_{s}0_{t}}{\phi^{+}}=e^{-i(\phi_{s}+\phi_{t})}\innerproduct{1_{s}1_{t}}{\phi^{+}}$
and
$\innerproduct{0_{s}1_{t}}{\phi^{+}}=-e^{-i(\phi_{s}-\phi_{t})}\innerproduct{1_{s}0_{t}}{\phi^{+}}$,
we obtain

$p(0,0|s,t)=|\innerproduct{0_{s}0_{t}}{\phi^{+}}|^{2}=|\innerproduct{1_{s}1_{t}}{\phi^{+}}|^{2}=p(1,1|s,t)$

and

$p(0,1|s,t)=|\innerproduct{0_{s}1_{t}}{\phi^{+}}|^{2}=|\innerproduct{1_{s}0_{t}}{\phi^{+}}|^{2}=p(1,0|s,t).$

∎

We now state and prove our main theorem relating XOR and XOR* games. Most of
the proof consists of showing that for any strategy employing a Bell state in
an XOR game there exists a two-dimensional reversible strategy – that is, a
strategy involving a resource system which is two-dimensional (e.g., a bit or
a qubit) and controlled gates that are reversible transformations – in the
corresponding XOR* game achieving the same performance, and vice versa. We
denote the equivalence between the two quantum-over-classical computational
advantages for the two classes of games as
$\Omega(\textup{XOR})=\Omega(\textup{XOR}^{*}|^{Rev}_{2D})$. In the proof we
adopt a diagrammatic approach (see Figure 2) exploiting the sliding rule
(Proposition 4.30, [46]), which is standard in the formulation of quantum
mechanics as a process theory [46]. Quantum mechanics as a process theory
inherits the structure of a symmetric monoidal category, and so can be
represented by a theory of systems (wires) and processes (boxes) admitting
sequential and parallel composition. States and effects are special types of
processes represented as boxes with trivial inputs and outputs, respectively.
Cup or cap shaped wire deformations are interpreted as Bell states and
effects, which are fundamental for establishing a duality between processes
and bipartite states [51, 52].

######  Theorem 1.

Consider two sets $\mathcal{S}$ and $\mathcal{T}$ where
$\textup{min}(|\mathcal{S}|,|\mathcal{T}|)\leq 4$. For every XOR game with
output bits $a$ and $b$, whose inputs $s,t$ are elements of the sets
$\mathcal{S}$ and $\mathcal{T}$, there exists an XOR* game with a two-
dimensional resource system and involving reversible gates that has the same
inputs $s\in\mathcal{S}$ and $t\in\mathcal{T}$ and output bit $m=a\oplus b$
such that the XOR and XOR* games have the same classical and quantum bounds.
The converse implication also holds. As a consequence, the games show the same
quantum-over-classical advantage, i.e.,
$\Omega(\textup{XOR})=\Omega(\textup{XOR}^{*}|^{Rev}_{2D})$.

###### Proof.

We start by establishing the connection between the quantum strategies in XOR*
games and ebit-XOR games following a diagrammatic approach (see figure 2),
explained below.

Figure 2: Diagrammatic representation of the mapping between the set of
quantum strategies for ebit XOR games and bi-dimensional quantum reversible
strategies for XOR* games.

Let us consider the diagram on the left side of figure 2,333Although we are
given a description of the diagrammatic proof left-to-right, because the
sliding rule is symmetric the proof can alternatively be read from right-to-
left, which is why the result holds in both directions, from the nonlocal to
the monopartite sequential games, and vice versa. that corresponds to the
probability $p(m|s,t)$ associated with the setup of the XOR* game, which, for
now, we assume it involves a qubit as resource system. Without loss of
generality, we fix the state of the resource system to be $\ket{0}$ (choosing
any other state would just correspond to implement an extra unitary in the
controlled transformations).

  * •

The first equivalence comes from the fact that a cup can always be introduced
in a diagram, through which we slide the state $\ket{0}$, turning it to an
effect (associated to the measurement element $\outerproduct{0}{0}$).

  * •

The second equivalence comes from the fact that, according to the sliding rule
(Proposition 4.30 [46]), Alice’s unitary transformation can be sled through
the cup, becoming its transpose in the process.

  * •

The third equivalence is essentially the identification of the cup with a Bell
state. In this way we can now read the last diagram on the right side of
figure 2 as describing a nonlocal game being played with such a Bell state.

The diagrammatic equivalence in Figure 2 only works for transformations
$U_{s},V_{t}$ that are reversible and act on two-dimensional systems, and it
shows that the probability $p(m|s,t)$ associated with the XOR* game is
equivalent to the probability $p(a=0,b=m|s,t)$ associated with the ebit-XOR
game. We can extend this equivalence to any $p(a,b|s,t)$, with values of $a$
different from $0$, because, for XOR games, via Lemma 2, we have that
$p(0,0|s,t)=p(1,1|s,t)$ and $p(0,1|s,t)=p(1,0|s,t)$.

As shown by the previous diagram, there is a bijective mapping between the
sets of strategies using at most 1-ebit resources in XOR games and the set of
two-dimensional reversible strategies in XOR* games. This means that, for any
(classical or quantum) strategy one can produce in one game, a corresponding
strategy can be produced in the other achieving the same performance, and vice
versa. Furthermore, since in ebit-XOR games the Tsirelson-bound is necessarily
achievable by at most 1-ebit strategies, and from Lemma 1 we know that any XOR
game where $\textup{min}(|\mathcal{S}|,|\mathcal{T}|)\leq 4$ is of this kind,
then we are guaranteed that for games whose input sets’ cardinality does not
exceed 4 the quantum optimal strategies in both games provide the same values.

Let us now consider the classical case. Since optimal classical strategies can
be understood as deterministic assignments from inputs to outputs [40], and
the input and output sets of a pair of XOR and XOR* games are by definition
equal,444The output set in the case of XOR games is intended to be the set
whose elements are the XOR of Alice’s and Bob’s output elements. the set of
reversible functions for both the XOR games (about which irreversible
strategies cannot outperform reversible ones 555This fact can be deduced from
Proposition 2 in [40], whose consequence is that optimal strategies for XOR
games are guaranteed by unitary operations in the quantum case, and reversible
functions in the classical case.) and XOR* games coincide, as do their Bell
bounds.

∎

For those unfamiliar with the formalism of process theories, the proof can
alternatively be stated with the standard quantum mechanical formalism. In
particular, the sliding rule used in the diagrammatic proof above corresponds
to a standard teleportation protocol, where by exploiting shared entanglement
Alice teleports her gate to Bob’s wing.666For an explicit circuit diagram, see
Figure 2 of [39].

###  3.2 On the assumptions of the theorem

Theorem 1 crucially relies on three assumptions: an upper bound on the minimum
cardinalities of the input sets, the reversibility of the gates and the two-
dimensionality of the resource system in the XOR* games. The first assumption
imposes a constraint on the XOR side of the proof and is a direct consequence
of Lemma 1. It guarantees that for XOR games respecting the bound on the
cardinalities the quantum bound can be achieved with a strategy involving a
Bell pair, which is crucial for establishing the mapping in the direction from
the XOR to the XOR* games. Notice that the assumption is sufficient but not
necessary for guaranteeing that XOR games can be optimally won with a strategy
employing a Bell pair, i.e., there could exist ebit XOR games violating the
assumption.

The remaining assumptions (reversibility and bi-dimensionality of the resource
systems) impose constraints on the XOR* side of the proof, and guarantee that
the map holds from the XOR* to the XOR games. These assumptions are necessary
for establishing the mapping in the theorem, indeed there exist XOR* games for
which increasing the dimension of the resource system or using irreversible
gates allow to obtain higher classical and quantum bounds, while leaving
unchanged the bounds in the corresponding XOR game. Notice how this does not
mean that the difference between the quantum and classical bounds can increase
by dropping any of the two assumptions. Hence, given that one may just be
interested in obtaining the highest quantum-over-classical advantage, it is
not obvious whether increasing the dimension of the resource system or
adopting irreversible gates can serve for such a purpose. For example, in the
CHSH* game [39] it is shown that either considering a Reset gate (irreversible
transformation) or going to dimension three, increases both the classical and
quantum bounds to the value 1, thus decreasing the quantum-classical
performance gap. In what follows, we show that not all XOR* games are like the
CHSH* game, in that there exist examples whose quantum-classical gap can
increase by introducing resource systems of dimension greater than two or
Reset gates.

#### Increasing the dimensionality of the resource system –

An XOR* game showing an increase in the quantum-classical performance gap due
to the use of a resource system with dimension greater than two is the binary
output Torpedo game introduced in Emeriau et al. [26]. The latter is an XOR*
game with 3 inputs for Alice and 4 for Bob (see Example 5 in subsection 3.3).
It has been shown in [26] with numeric methods that the game manifests the
following quantum-classical gaps: $\Omega(\textup{Bit-Torp.}|_{2D})=0.039$ and
$\Omega(\textup{Bit-Torp.}|_{3D})=0.042$. The fact that the dual XOR version
of the binary output Torpedo game has quantum-classical gap equal to the one
of the binary output Torpedo game with bi-dimensional resource system is then
enough to show that Theorem 1 without the bi-dimensionality assumption of the
resource system does not hold.

#### Employing irreversible transformations –

In A we provide an example of an XOR* game which shows how irreversibility can
increase the quantum-classical gap. Remarkably, this example demonstrates the
potentially resourceful role of irreversibility for establishing a quantum-
over-classical advantage in XOR* games: the game manifests zero quantum-
classical gap when allowing only reversible gates, but it shows a positive
quantum-classical gap when employing Reset gates. This demonstrates a
phenomenon of reset-induced gap activation, and shows how irreversibility can
create a quantum-classical gap, rather than just increase an already existing
one. It is not known whether this type of activation is also possible in the
previous case where one increases the bi-dimensionality of the resource
system.

###  3.3 Examples

Theorem 1 states that any two-player XOR (or XOR*) game defined over the
inputs sets $\mathcal{S}$ and $\mathcal{T}$, respecting a cardinality upper
bound $min(\mathcal{S},\mathcal{T})\leq 4$, is guaranteed to have a natural
XOR* (or XOR) version, exhibiting the same classical and quantum bounds, for
strategies in the XOR* game with a two-dimensional resource system and
involving reversible gates. Accordingly, a number of examples of XOR games
have a natural XOR* counterpart exhibiting the same quantum-over-classical
advantage. This was already known for the CHSH game whose counterpart is the
CHSH* game, but it is also true for other instances of XOR games already
present in the literature. On the other hand, protocols that belong to the
class of XOR* games subjected to the appropriate artificial constraints also
have a natural XOR variant, like the $2\rightarrow 1$ QRAC. In fact, it is
often thought that the CHSH game and the $2\rightarrow 1$ QRAC are intimately
related just by merit of them sharing the same classical and quantum bounds.
However, according to our categorization the CHSH game is the natural XOR
version of the CHSH* game, and the QRAC has a natural XOR game counterpart
(wich we call $2\rightarrow 1$ QRAC${}^{\oplus})$, see Example 5) distinct
from the CHSH game, as we detail below.

Because of the connection established by this theorem, we will call a couple
of connected XOR and XOR* games as a dual pair XOR/XOR*, specified by the
input sets, corresponding probability distributions, and the shared task
function $f$. It is implicit that there is a unique output bit, $m$, in the
XOR* game, and two individual output bits $a,b$ in the nonlocal game, such
that they are related by $m=a\oplus b$. We now provide several examples of
dual pairs of XOR/XOR* games.

######  Example 1 (CHSH [1]/CHSH* [39]).

A two-player XOR/XOR* game with inputs $s,t\in\\{0,1\\}$ where,
$\forall_{s,t}\;p(s,t)={1}/{4},$ and

$f(s,t):=s\cdot t.$ (11)

Classical bounds:
$\omega_{c}(\textup{CHSH})=\omega_{c}(\textup{CHSH}^{*}|^{Rev}_{2D})=3/4.\\\ $
Quantum bounds:
$\omega_{q}(\textup{CHSH})=\omega_{q}(\textup{CHSH}^{*}|^{Rev}_{2D})=\cos^{2}(\pi/8)\simeq
0.85.$

######  Example 2 ($n$-Odd Cycle [40]/$n$-Odd Cycle*).

A two-player dual pair XOR/XOR* with inputs $s\in\\{1,2,...,n\\}$ for odd
$n\geq 3$, and $t\in\\{s,\;s\oplus 1\mod n\\}$ where,
$\forall_{s,t}\;\;\;p(s,t=s)={1}/{2},\;\;p(s,t=s\oplus 1)={1}/{2},$ and

$f(s,t):=[s\oplus 1=t\;(\textup{mod}\;n)],$ (12)

where the notation $[s\oplus 1=t\;(\textup{mod}\;n)]$ denotes the truth value
of the proposition $s\oplus 1=t\;(\textup{mod}\;n)$.

Classical bounds:
$\omega_{c}(n\textup{-OC})=\omega_{c}(n\textup{-OC}^{*}|^{Rev}_{2D})=1-1/2n.\\\
$ Quantum bounds:
$\omega_{q}(n\textup{-OC})=\omega_{q}(n\textup{-OC}^{*}|^{Rev}_{2D})=\cos^{2}(\pi/4n).$

######  Example 3 (EAOS [41, 42]/EAOS* [53] ).

A two-player dual pair XOR/XOR* with inputs $s,t\in\\{1,2,3\\}$ where,
$\forall_{s,t}\;p(s,t)={1}/{9},$ and

$f(s,t):=\overline{\delta(s,t)},$ (13)

where $\delta(s,t)$ is the Kronecker delta function evaluating to 1 only when
$s=t$ and 0 otherwise, and $\overline{\delta(s,t)}$ its negation.

Classical bounds:
$\omega_{c}(\textup{EAOS})=\omega_{c}(\textup{EAOS}^{*}|^{Rev}_{2D})=7/9.\\\ $
Quantum bounds:
$\omega_{q}(\textup{EAOS})=\omega_{q}(\textup{EAOS}^{*}|^{Rev}_{2D})=5/6.$

######  Example 4 ($2\rightarrow 1$ QRAC⊕/ $2\rightarrow 1$ QRAC [37]).

A two-player dual pair XOR/XOR* with inputs $\textbf{s}=(s_{0},s_{1})$ for
$s_{0},s_{1}\in\\{0,1\\}$, $t\in\\{0,1\\}$ where,
$\forall_{s,t}\;p(\textbf{s},t)={1}/{8},$ and

$f(\textbf{s},t):=s_{0}\cdot(t\oplus 1)\oplus s_{1}\cdot t.$ (14)

Classical bounds: $\omega_{c}(\textup{$2\rightarrow 1$
QRAC${}^{\oplus}$})=\omega_{c}(\textup{$2\rightarrow 1$
QRAC}|^{Rev}_{2D})=3/4.\\\ $ Quantum bounds: $\omega_{q}(\textup{$2\rightarrow
1$ QRAC${}^{\oplus}$})=\omega_{q}(\textup{$2\rightarrow 1$
QRAC}|^{Rev}_{2D})=\cos^{2}(\pi/8)\simeq 0.85.$

Notice how, according to our framework, the natural nonlocal XOR game
associated to the $2\rightarrow 1$ QRAC is not the CHSH game, but an XOR game,
that we denote as $2\rightarrow 1$ QRAC⊕.

######  Example 5 (Bit-Torpedo⊕/ Bit-Torpedo [26]).

A two-player dual pair XOR/XOR* with inputs $\textbf{s}=(s_{0},s_{1})$ for
$s_{0},s_{1}\in\\{0,1\\}$, $t\in\\{0,1,2\\}$ where,
$\forall_{s,t}\;p(\textbf{s},t)={1}/{12},$ and

$f(\textbf{s},t):=\left(s_{0}\cdot(t\oplus_{3}1)\\!\\!\\!\\!\mod
2\right)\oplus\left(s_{1}\cdot t\\!\\!\\!\\!\mod
2\right)\oplus\left((s_{0}\oplus s_{1})\cdot(t\oplus_{3}2)\\!\\!\\!\\!\mod
2\right).$ (15)

Classical bounds: $\omega_{c}(\textup{{Bit-
Torp.}${}^{\oplus}$})=\omega_{c}(\textup{Bit-Torp.}|^{Rev}_{2D})=3/4.\\\ $
Quantum bounds:
$\omega_{q}(\textup{Bit-{Torp.}${}^{\oplus}$})=\omega_{q}(\textup{Bit-
Torp.}|^{Rev}_{2D})\simeq 0.789.\\\ $

Notice that we write “$\oplus_{3}$” to denote the sum modulo 3 and distinguish
it from the usual XOR operation “$\oplus$” that denotes the sum modulo 2. In
comparison with Example 4, the task function for the binary output Torpedo
game – here denoted as “Bit-Torpedo” – can be seen to be a generalisation of
the $2\rightarrow 1$ QRAC, where, in addition of Bob possibly being asked to
output either bit corresponding to Alice’s inputs, he can be further asked to
output their parity. Notice also that due to the mapping of Theorem 1, we are
able to automatically give a nonlocal version of the binary output Torpedo
game, that we denote as “Bit-Torpedo⊕”.

######  Example 6 (GBHA-$I_{3}^{\oplus}$/ GBHA-$I_{3}$ [44]).

A two-player dual pair XOR/XOR* with inputs $s\in\\{0,1,2\\}$ and
$t\in\\{0,1\\}$ where $p(2,1)=0$ and $p(s,t)={1}/{5}$ otherwise, and

$f(s,t):=\Theta_{2}(s+t),$ (16)

where $\Theta_{2}(s+t)$ is the Heaviside step-function evaluating to 1 when
$s+t\geq 2$, and 0 otherwise.
Classical bounds:
$\omega_{c}(\textup{GBHA-}I_{3}^{\oplus})=\omega_{c}(\textup{GBHA-}I_{3}|^{Rev}_{2D})=4/5.\\\
$ Quantum bounds:
$\omega_{q}(\textup{GBHA-}I_{3}^{\oplus})=\omega_{q}(\textup{GBHA-}I_{3}|^{Rev}_{2D})\simeq
0.88\\\ $

The previous game was introduced in Gallego et al. [44] to serve as a
dimensional witness (detecting, from the performance of the game, whether the
dimension of the resource system is greater than two). The game is a
straightforward generalization of the CHSH* game, where Alice instead of
receiving a bit receives a trit. Indeed, by reducing Alice’s input cardinality
from three to two, one eliminates the (2,0) and (2,1) input possibilities, the
Heaviside function reduces to the AND operation (or product) of the input
bits, and the game becomes a version of the CHSH* game.

##  4 On the source of quantum computational advantage in XOR* games

Although for XOR games nonlocality has been shown to be a source of the
quantum advantage [54], it is still not clear which nonclassical feature plays
the same role in XOR* games. Since such games employ monopartite computational
resources, nonlocality can be immediately excluded as a possible candidate.
Similarly, since these protocols only consider a final fixed measurement on a
two level system, Kochen-Specker contextuality, which requires varied sets of
commuting observables in order to be witnessed, and which in any case does not
arise in Hilbert spaces of dimension two, can also be excluded as a possible
candidate.

It is possible to identify a resource for computational advantage in at least
one specific class of XOR* games. In communication tasks with appropriate
parity constraints it is known that preparation contextuality provides a
resource for the advantage [55, 56], the golden example being the
$2\rightarrow 1$ parity oblivious multiplexing task [9]. Can we extend these
results to the whole class of XOR* games? One thing that we can do is to
leverage the result of Theorem 1 and the mapping it involves to show that XOR*
games, if interpreted as prepare-and-measure scenarios, are powered by
preparation contextuality. Indeed, we know that in XOR games nonlocality is a
resource to outperform classical strategies and, in a (bipartite) Bell
scenario like that of XOR games, any proof of nonlocality can be mapped to a
proof of preparation contextuality in either wing of the experiment: in Bob’s
(Alice’s) wing one considers the prepare and measure scenario where the
preparation is specified by the state Alice (Bob) steers Bob’s (Alice’s)
system to, and the measurement is Bob’s (Alice’s) measurement. This steering
process corresponds exactly to the mapping involved in Theorem 1, which turns
the Bell scenario into a prepare-and-measure scenario. In LABEL:appendix we
provide the definitions of ontological models, preparation noncontextuality,
and a detailed proof of the above claim.

There is an important consideration to bear in mind about the role of
preparation contextuality in XOR* games, however. The mapping of Theorem 1,
via the above argument, does not send proofs of nonlocality in a given XOR
game to proofs of preparation contextuality in the dual XOR* game, but rather
guarantees such a proof for an XOR* game in a scenario whose set of inputs has
larger cardinality – see B. As a crucial consequence, we cannot prove
preparation contextuality via the mapping above in the case of an XOR* game
with binary inputs, $s,t\in\mathbb{Z}_{2},$ as is the case for the CHSH* game.
The CHSH* game indeed seems not to allow for a proof of preparation
contextuality as it only involves four inputs in total, and yet four inputs
cannot select four preparations and two measurements, which is known to be the
minimum requirement for a proof of preparation contextuality [57]. Due to this
observation, it cannot be said that the mapping from XOR to XOR* games lifts
in an obvious way to a mapping from the source of advantage in XOR games to
that in XOR* games.

In summary, when confronted with the appearance of a quantum-over-classical
advantage in XOR* games, we are pressed to pursue new ways of identifying the
feature that corresponds to nonlocality in XOR games. Given that the only
degrees of freedom in the XOR* games are in the choices of controlled
transformations, it seems natural to focus on a property of transformations as
the source of computational advantage. In this respect, let us consider the
notion of sequential transformation contextuality developed in [14], that has
indeed been proven to be necessary for quantum advantage in a broad class of
information retrieval games (which are instances of monopartite sequential
games) [26] as well as the CHSH* game.

A caveat to the latter results is that sequential transformation contextuality
applies either (a) to cases where the ontological model is required to
preserve the dimensional restriction defining the operational setting or (b)
to cases where the ontological model is required to satisfy $\oplus
L$-ontology, which essentially restricts transformations to being represented
as sums modulo $2$ (this assumption is advocated for in cases where the
operational setting is the one of a parity computer [14]). So, sequential
transformation contextuality is only relevant relative to the extent to which
these conditions hold. While the conditions can be argued to be natural in
certain informational or computational tasks, we cannot claim that they will
always be reasonable assumptions in general.

Is assumption (a) – rather than (b), which is unwarranted – natural in the
case of XOR* games? If one takes the notion of naturalness as the notion of
Leibnizianity [58] (also stated as a no fine-tuning principle [59]) – i.e.,
that the operational equivalences predicted in principle to hold by the theory
are preserved at the ontological level – which is at the base of the principle
of generalized noncontextuality, assumption (a) is natural as long as the
dimensional restriction is written in terms of operational quantities and is
empirically verifiable. However, it is important to notice that it is the
notion of sequential transformation noncontextuality, where contexts are
sequences of transformations, that is not natural in this perspective because,
in general, one cannot verify an operational equivalence. Indeed, it is not
possible to isolate a transformation in order to perform process tomography on
it since it manifests in a specific context or sequence of transformations.
Therefore, if one wants to stick to the credentials of the principle of
generalized noncontextuality one would also need to replace sequential
transformation noncontextuality accordingly. Rather than such credentials, the
latter is motivated from a perspective in which compositionality is taken to
be the notion of naturalness – meaning that operational composition should be
reflected at the ontological level.

Let us conclude by stressing that, whatever the notion of noncontextuality
adopted, it seems unavoidable the need to impose restrictions on the
ontological models associated with the setup of XOR* games, for otherwise no
meaningful results can be obtained (clearly there always exists a
noncontextual ontological model that can compute a function $f(s,t)=m$ – and
that is the one associated with a classical computer). In particular, it would
seem natural that the ontological models have to be restricted such that the
operational features of the XOR* games are preserved therein, i.e., the
transition matrices associated with the transformations are reversible
(permutations in the discrete case) and the dimensionality of the ontological
model is constrained according to the fact that the resource system is a two-
level system. Then, for one who subscribes to the credentials of
Leibnizianity/no-fine tuning, the aim would be to adopt the notion of
noncontextuality that exploits operational equivalences arising in the XOR*
games. A possibility is that the operational equivalences arise in fact from
the operational restrictions – reversibility and the bi-dimensionality of the
resource system – defining the XOR* games, and so assuming noncontextuality
would already take care of appropriately restricting the ontological models.
Ultimately, it would be desirable to show that every time one implements a
strategy that wins the game with a probability greater than the Bell bound,
this is inconsistent with the naturally justified restrictions on the
ontological models and the adopted notion of (transformation)
noncontextuality. We leave the development of this project for future
research.

##  5 Conclusion

The CHSH* game and its relationship to the CHSH game were first studied in
[39]. Although belonging to distinct setups—the CHSH game being a nonlocal
game and the CHSH* game a monopartite sequential game—they show the same
classical and quantum bounds and they can be connected via an explicit
mapping. In this work we generalised such mapping to a broader class of games.
More precisely, we defined a new class of monopartite sequential games—the
XOR* games—with the idea of providing a natural generalisation of the CHSH*
game, in the same way XOR games are a generalisation of the CHSH game. In
addition to providing this new categorization of nonlocal and monopartite
sequential games, we proved a theorem stating that for two input sets whose
cardinality does not exceed $4$, there is a mapping between dual pairs of
XOR/XOR* games such that they manifest the same quantum and classical
performance bounds, for strategies in the XOR* game involving two-dimensional
resource systems and reversible gates. We further presented two examples of
XOR* games to demonstrate how lifting the assumptions of reversibility of
gates and bi-dimensionality of the resource system assumptions leads to the
mapping no longer holding.

To summarize our main contribution, we showed that under certain conditions
the dual pair XOR/XOR* manifests the same quantum-over-classical advantage,
and the dual pair CHSH/CHSH* is a particular example of this. We also provided
other examples of such dual pairs (namely, $n$-Odd Cycle/$n$-Odd Cycle* games,
EAOS/EAOS* games, $2\rightarrow 1$ QRAC⊕/ $2\rightarrow 1$ QRAC games, Bit-
Torpedo⊕/ Bit-Torpedo games). In addition to this finding, we also pointed out
how the mapping that we established in Theorem 1, supplemented with the fact
that nonlocality is a resource for outperforming classical strategies in XOR
games, provides a way of showing that preparation contextuality is a resource
that powers certain XOR* games when treated as prepare and measure scenarios.
However, we also highlighted the limitations of this claim, the main one being
that it does not apply to the CHSH* game.

Our work is related to other works focused on monopartite sequential protocols
that show the same performances of the CHSH game. In particular, protocols
known as temporal CHSH scenarios use controlled measurements on a single
system and are proven to manifest the same Bell and Tsirelson bounds as the
CHSH game [38, 62, 63, 64, 65, 66, 67, 68, 69, 60, 61]. However, their focus
is mostly on characterizing the set of allowed correlations and to test the
assumptions of macrorealism and non-invasiveness (Legget-Garg inequalities)
[70, 71, 72]. Alternatively, in [73] the authors have aimed to provide a
different characterisation of non-classicality in the temporal setting, other
than the Legget-Garg type, by analysing the cost (in terms of channel
capacity) of classically simulating temporal correlations. It should be noted
that, although from their perspective any temporal qubit correlations are
trivially classically simulatable by means of implementation of Toner-Bacon
protocols [74], this would require extra ancillary systems, and thus, it is
forbidden within our XOR* setup since it contradicts the assumption of using a
single monopartite resource.111The single monopartite assumption is closer to
the “restricted working memory” constraint considered in the recently
introduced computation model proposed by researchers at IBM [75]. A work that
is more focused on the characterisation of games and their artificial
constraints is [11], that shows how preparation contextuality is a resource
for communication games with constraints akin to the parity obliviousness in
[9]. However, these games do not always belong to the set of XOR* games that
we consider in our work and therefore do not obey in general the mapping that
we show in Theorem 1. That said, both the communication games studied in [11]
and our XOR* games are strictly related to nonlocal games. Namely, in [11] a
construction is shown that allows one to define communication games from
nonlocal games, which in spirit bears some resemblance with the mapping from
our Theorem 1. It should be noted, however, that even for examples of games
that fit into both frameworks the mappings differ. For instance, in our
framework the CHSH game is mapped naturally to the CHSH* game, whereas in [11]
the CHSH game is mapped to the $2\rightarrow 1$ POM which, although an XOR*
game, it is evidently different from the CHSH* game. Our XOR* games are also
related to the protocols in [44], even if in there they are treated as prepare
and measure scenarios and are specifically devised to provide dimensional
witnesses [76, 77, 32, 78, 79].

We conclude by listing a couple of open questions originating from our work.
First, it would be interesting to further generalise Theorem 1 by enlarging
the classes of games to consider, in particular by finding a proof strategy
that does not rely on Lemma 1 from [40]. The approach of [80] developed to
find a non trivial nonlocal version of the three dimensional Torpedo game [26]
might provide a first intuition towards such generalization. They use the same
construction with Wigner negative states and phase-point operators of [26] and
they devise a strategy to appropriately modify the predicate of some
monopartite sequential game in a way that the classical and quantum bounds of
a corresponding nonlocal game match those of the original sequential
monopartite game. This would allow to generalize Theorem 1 to input sets of
arbitrary cardinalities. Second, in terms of the resources for computational
advantage in XOR* games, it is worth exploring whether properties of
transformations can be proven to be necessary for the quantum-over-classical
advantage. In particular, we have advocated for the development of a notion of
transformation noncontextuality with restrictions on the ontological models
endorsing the same credentials of generalized noncontextuality.

## Acknowledgements

LC and AP acknowledge support from the Einstein Research Unit ‘Perspectives of
a Quantum Digital Transformation’. AP also acknowledges support from the Emmy
Noether DFG grant No. 418294583, and from the BMWK via the project Qompiler.
RF thanks Emmanuel Zambrini Cruzeiro and Flavien Hirsch for discussions about
the reset-induced gap activation example, and acknowledges funding from
FCT/MCTES through national funds and when applicable EU funds under the
project UIDB/50008/2020, and the QuantaGENOMICS-QuantERA/0001/2021 project,
through the EU H2020 QuantERA II Programme, Grant Agreement No 101017733.

## References

  * [1] John F. Clauser, Michael A. Horne, Abner Shimony and Richard A. Holt “Proposed Experiment to Test Local Hidden-Variable Theories” In _Phys. Rev. Lett._ 23 American Physical Society, 1969, pp. 880–884 DOI: 10.1103/PhysRevLett.23.880
  * [2] J.. Bell “On the Einstein Podolsky Rosen paradox” In _Physics Physique Fizika_ 1 American Physical Society, 1964, pp. 195–200 DOI: 10.1103/PhysicsPhysiqueFizika.1.195
  * [3] B.. Cirel’son “Quantum generalizations of Bell’s inequality” In _Letters in Mathematical Physics_ 4 D. Reidel Publishing Company, 1980, pp. 93–100 DOI: 10.1007/BF00417500
  * [4] Dominic Mayers and Andrew Yao “Self Testing Quantum Apparatus” In _Quantum Info. Comput._ 4.4 Paramus, NJ: Rinton Press, Incorporated, 2004, pp. 273–286
  * [5] Stefano Pironio et al. “Random numbers certified by Bell’s theorem” In _Nature_ 464.7291 Nature Publishing Group, 2010, pp. 1021–1024
  * [6] Umesh Vazirani and Thomas Vidick “Fully Device-Independent Quantum Key Distribution” In _Phys. Rev. Lett._ 113 American Physical Society, 2014, pp. 140501 DOI: 10.1103/PhysRevLett.113.140501
  * [7] Arthur Fine “Hidden Variables, Joint Probability, and the Bell Inequalities” In _Phys. Rev. Lett._ 48 American Physical Society, 1982, pp. 291–295 DOI: 10.1103/PhysRevLett.48.291
  * [8] Samson Abramsky and Adam Brandenburger “The sheaf-theoretic structure of non-locality and contextuality” In _New J. Phys. 13 113036_ , 2011 DOI: 10.1088/1367-2630/13/11/113036
  * [9] Robert W. Spekkens et al. “Preparation contextuality powers parity-oblivious multiplexing” arXiv: 0805.1463 In _Physical Review Letters_ 102.1, 2009, pp. 010401 DOI: 10.1103/PhysRevLett.102.010401
  * [10] Juan Bermejo-Vega et al. “Contextuality as a Resource for Models of Quantum Computation with Qubits” In _Phys. Rev. Lett._ 119 American Physical Society, 2017, pp. 120505 DOI: 10.1103/PhysRevLett.119.120505
  * [11] Alley Hameedi, Armin Tavakoli, Breno Marques and Mohamed Bourennane “Communication Games Reveal Preparation Contextuality” In _Phys. Rev. Lett._ 119 American Physical Society, 2017, pp. 220402 DOI: 10.1103/PhysRevLett.119.220402
  * [12] André L. Oestereich and Ernesto F. Galvão “Reliable computation from contextual correlations” In _Phys. Rev. A_ 96 American Physical Society, 2017, pp. 062305 DOI: 10.1103/PhysRevA.96.062305
  * [13] Lorenzo Catani and Dan E. Browne “State-injection schemes of quantum computation in Spekkens’ toy theory” In _Phys. Rev. A_ 98 American Physical Society, 2018, pp. 052108 DOI: 10.1103/PhysRevA.98.052108
  * [14] Shane Mansfield and Elham Kashefi “Quantum Advantage from Sequential-Transformation Contextuality” arXiv: 1801.08150 In _Physical Review Letters_ 121.23, 2018, pp. 230401 DOI: 10.1103/PhysRevLett.121.230401
  * [15] David Schmid and Robert W. Spekkens “Contextual Advantage for State Discrimination” In _Phys. Rev. X_ 8 American Physical Society, 2018, pp. 011015 DOI: 10.1103/PhysRevX.8.011015
  * [16] Markus Frembs, Sam Roberts and Stephen D Bartlett “Contextuality as a resource for measurement-based quantum computation beyond qubits” In _New Journal of Physics_ 20.10 IOP Publishing, 2018, pp. 103011 DOI: 10.1088/1367-2630/aae3ad
  * [17] Robert Raussendorf et al. “Phase-space-simulation method for quantum computation with magic states on qubits” In _Phys. Rev. A_ 101 American Physical Society, 2020, pp. 012350 DOI: 10.1103/PhysRevA.101.012350
  * [18] Debashis Saha, Paweł Horodecki and Marcin Pawłowski “State independent contextuality advances one-way communication” In _New Journal of Physics_ 21.9 IOP Publishing, 2019, pp. 093057 DOI: 10.1088/1367-2630/ab4149
  * [19] Debashis Saha and Anubhav Chaturvedi “Preparation contextuality as an essential feature underlying quantum communication advantage” In _Phys. Rev. A_ 100 American Physical Society, 2019, pp. 022108 DOI: 10.1103/PhysRevA.100.022108
  * [20] Alastair A. Abbott, Cristian S. Calude, Jonathan Conder and Karl Svozil “Strong Kochen-Specker theorem and incomputability of quantum randomness” In _Phys. Rev. A_ 86 American Physical Society, 2012, pp. 062109 DOI: 10.1103/PhysRevA.86.062109
  * [21] Kishor Bharti et al. “Robust Self-Testing of Quantum Systems via Noncontextuality Inequalities” In _Phys. Rev. Lett._ 122 American Physical Society, 2019, pp. 250403 DOI: 10.1103/PhysRevLett.122.250403
  * [22] Matteo Lostaglio and Gabriel Senno “Contextual advantage for state-dependent cloning” In _Quantum_ 4 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2020, pp. 258 DOI: 10.22331/q-2020-04-27-258
  * [23] Matteo Lostaglio “Certifying quantum signatures in thermodynamics and metrology via contextuality of quantum linear response” In _Physical Review Letters_ 125.23 APS, 2020, pp. 230603
  * [24] Shiv Akshar Yadavalli and Ravi Kunjwal “Contextuality in entanglement-assisted one-shot classical communication” In _arXiv:2006.00469_ , 2020
  * [25] Mark Um et al. “Randomness Expansion Secured by Quantum Contextuality” In _Phys. Rev. Applied_ 13 American Physical Society, 2020, pp. 034077 DOI: 10.1103/PhysRevApplied.13.034077
  * [26] Pierre-Emmanuel Emeriau, Mark Howard and Shane Mansfield “Quantum Advantage in Information Retrieval” In _PRX Quantum_ 3 American Physical Society, 2022, pp. 020307 DOI: 10.1103/PRXQuantum.3.020307
  * [27] Kieran Flatt et al. “Contextual advantages and certification for maximum confidence discrimination” arXiv, 2021 DOI: 10.48550/ARXIV.2112.09626
  * [28] Carles Roch I Carceller et al. “Quantum vs. noncontextual semi-device-independent randomness certification” arXiv, 2021 DOI: 10.48550/ARXIV.2112.09678
  * [29] Robert Raussendorf “Contextuality in measurement-based quantum computation” In _Phys. Rev. A_ 88 American Physical Society, 2013, pp. 022322 DOI: 10.1103/PhysRevA.88.022322
  * [30] Mark Um et al. “Experimental Certification of Random Numbers via Quantum Contextuality” In _Scientific Reports_ 3.1, 2013, pp. 1627 DOI: 10.1038/srep01627
  * [31] Mark Howard, Joel Wallman, Victor Veitch and Joseph Emerson “Contextuality supplies the ‘magic’ for quantum computation” In _Nature_ 510.7505, 2014, pp. 351–355 DOI: 10.1038/nature13460
  * [32] Otfried Gühne et al. “Bounding the quantum dimension with contextuality” In _Phys. Rev. A_ 89 American Physical Society, 2014, pp. 062107 DOI: 10.1103/PhysRevA.89.062107
  * [33] Nicolas Delfosse, Philippe Allard Guerin, Jacob Bian and Robert Raussendorf “Wigner Function Negativity and Contextuality in Quantum Computation on Rebits” In _Phys. Rev. X_ 5 American Physical Society, 2015, pp. 021003 DOI: 10.1103/PhysRevX.5.021003
  * [34] André Chailloux, Iordanis Kerenidis, Srijita Kundu and Jamie Sikora “Optimal bounds for parity-oblivious random access codes” In _New Journal of Physics_ 18.4 IOP Publishing, 2016, pp. 045003 DOI: 10.1088/1367-2630/18/4/045003
  * [35] Robert Raussendorf et al. “Contextuality and Wigner-function negativity in qubit quantum computation” In _Phys. Rev. A_ 95 American Physical Society, 2017, pp. 052334 DOI: 10.1103/PhysRevA.95.052334
  * [36] Stephen Wiesner “Conjugate Coding” In _SIGACT News_ 15.1 New York, NY, USA: Association for Computing Machinery, 1983, pp. 78–88 DOI: 10.1145/1008908.1008920
  * [37] Andris Ambainis, Ashwin Nayak, Ammon Ta-Shma and Umesh Vazirani “Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata” In _Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing_ , STOC ’99 Atlanta, Georgia, USA: Association for Computing Machinery, 1999, pp. 376–383 DOI: 10.1145/301250.301347
  * [38] Tobias Fritz “Quantum correlations in the temporal Clauser–Horne–Shimony–Holt (CHSH) scenario” In _New Journal of Physics_ 12.8 IOP Publishing, 2010, pp. 083055 DOI: 10.1088/1367-2630/12/8/083055
  * [39] Luciana Henaut et al. “Tsirelson’s bound and Landauer’s principle in a single-system game” arXiv: 1806.05624 In _Physical Review A_ 98.6, 2018, pp. 060302 DOI: 10.1103/PhysRevA.98.060302
  * [40] Richard Cleve, Peter Hoyer, Ben Toner and John Watrous “Consequences and Limits of Nonlocal Strategies” arXiv: quant-ph/0404076 In _arXiv:quant-ph/0404076_ , 2010 URL: http://arxiv.org/abs/quant-ph/0404076
  * [41] Caslav Brukner, Nikola Paunkovic, Terry Rudolph and Vlatko Vedral “Entanglement-assisted orientation in space” Publisher: World Scientific Publishing Co. In _International Journal of Quantum Information_ 04.02, 2006, pp. 365–370 DOI: 10.1142/S0219749906001839
  * [42] Ricardo Faleiro “Quantum strategies for simple two-player XOR games” In _Quantum Inf Process 19, 229 (2020)_ , 2020 URL: http://arxiv.org/abs/1910.04478
  * [43] Ernesto F. Galvao “Foundations of quantum theory and quantum information applications”, 2002 arXiv:quant-ph/0212124 [quant-ph]
  * [44] Rodrigo Gallego, Nicolas Brunner, Christopher Hadley and Antonio Acı́n “Device-Independent Tests of Classical and Quantum Dimensions” In _Phys. Rev. Lett._ 105 American Physical Society, 2010, pp. 230501 DOI: 10.1103/PhysRevLett.105.230501
  * [45] R.. Spekkens “Contextuality for preparations, transformations, and unsharp measurements” arXiv: quant-ph/0406166 In _Physical Review A_ 71.5, 2005, pp. 052108 DOI: 10.1103/PhysRevA.71.052108
  * [46] Bob Coecke and Aleks Kissinger “Picturing quantum processes” In _International Conference on Theory and Application of Diagrams_ , 2018, pp. 28–31 Springer
  * [47] Armin Tavakoli, Emmanuel Zambrini Cruzeiro, Erik Woodhead and Stefano Pironio “Informationally restricted correlations: a general framework for classical and quantum systems” In _Quantum_ 6 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2022, pp. 620 DOI: 10.22331/q-2022-01-05-620
  * [48] David T. Pegg “Causality in quantum mechanics” In _Physics Letters A_ 349.6, 2006, pp. 411–414 DOI: https://doi.org/10.1016/j.physleta.2005.09.061
  * [49] Mark M. Wilde “Preface to the Second Edition” In _Quantum Information Theory_ Cambridge University Press, 2017 DOI: 10.1017/9781316809976.001
  * [50] Shane Mansfield “Consequences and applications of the completeness of Hardy’s nonlocality” In _Physical Review A_ 95.2 APS, 2017, pp. 022122
  * [51] A. Jamiołkowski “Linear transformations which preserve trace and positive semidefiniteness of operators” In _Reports on Mathematical Physics_ 3.4, 1972, pp. 275–278 DOI: https://doi.org/10.1016/0034-4877(72)90011-0
  * [52] Man-Duen Choi “Completely positive linear maps on complex matrices” In _Linear Algebra and its Applications_ 10.3, 1975, pp. 285–290 DOI: https://doi.org/10.1016/0024-3795(75)90075-0
  * [53] Xavier Coiteux-Roy and Stefan Wolf “On the Advantage of Irreversible Processes in Single-System Games” arXiv: 2001.04713 In _arXiv:2001.04713 [quant-ph]_ , 2020 URL: http://arxiv.org/abs/2001.04713
  * [54] Nicolas Brunner et al. “Bell nonlocality” In _Rev. Mod. Phys._ 86 American Physical Society, 2014, pp. 419–478 DOI: 10.1103/RevModPhys.86.419
  * [55] Anubhav Chaturvedi, Marcin Pawlowski and Karol Horodecki “Random access codes and nonlocal resources” In _Phys. Rev. A_ 96 American Physical Society, 2017, pp. 022125 DOI: 10.1103/PhysRevA.96.022125
  * [56] Andris Ambainis et al. “Parity oblivious d-level random access codes and class of noncontextuality inequalities” In _Quantum Information Processing_ 18.4, 2019, pp. 111 DOI: 10.1007/s11128-019-2228-3
  * [57] Matthew F. Pusey “Robust preparation noncontextuality inequalities in the simplest scenario” In _Phys. Rev. A_ 98 American Physical Society, 2018, pp. 022112 DOI: 10.1103/PhysRevA.98.022112
  * [58] David Schmid, John H. Selby and Robert W. Spekkens “Unscrambling the omelette of causation and inference: The framework of causal-inferential theories” In _arXiv:2009.03297_ , 2021 URL: https://arxiv.org/abs/2009.03297
  * [59] Lorenzo Catani and Matthew Leifer “A mathematical framework for operational fine tunings” In _arXiv:2003.10050_ , 2020 URL: https://arxiv.org/abs/2003.10050
  * [60] Lucas B. Vieira and Costantino Budroni “Temporal correlations in the simplest measurement sequences” In _Quantum_ 6 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2022, pp. 623 DOI: 10.22331/q-2022-01-18-623
  * [61] Yuanyuan Mao, Cornelia Spee, Zhen-Peng Xu and Otfried Gühne “Structure of dimension-bounded temporal correlations” In _Phys. Rev. A_ 105 American Physical Society, 2022, pp. L020201 DOI: 10.1103/PhysRevA.105.L020201
  * [62] Costantino Budroni, Tobias Moroder, Matthias Kleinmann and Otfried Gühne “Bounding Temporal Quantum Correlations” In _Phys. Rev. Lett._ 111 American Physical Society, 2013, pp. 020403 DOI: 10.1103/PhysRevLett.111.020403
  * [63] Costantino Budroni and Clive Emary “Temporal Quantum Correlations and Leggett-Garg Inequalities in Multilevel Systems” In _Phys. Rev. Lett._ 113 American Physical Society, 2014, pp. 050401 DOI: 10.1103/PhysRevLett.113.050401
  * [64] Marcin Markiewicz, Anna Przysi ę żna, Stephen Brierley and Tomasz Paterek “Genuinely multipoint temporal quantum correlations and universal measurement-based quantum computing” In _Phys. Rev. A_ 89 American Physical Society, 2014, pp. 062319 DOI: 10.1103/PhysRevA.89.062319
  * [65] Thao Le et al. “Divisible quantum dynamics satisfies temporal Tsirelson’s bound” In _Journal of Physics A: Mathematical and Theoretical_ 50.5 IOP Publishing, 2017, pp. 055302 DOI: 10.1088/1751-8121/aa52b1
  * [66] Jannik Hoffmann, Cornelia Spee, Otfried Gühne and Costantino Budroni “Structure of temporal correlations of a qubit” In _New Journal of Physics_ 20.10 IOP Publishing, 2018, pp. 102001 DOI: 10.1088/1367-2630/aae87f
  * [67] Costantino Budroni, Gabriel Fagundes and Matthias Kleinmann “Memory cost of temporal correlations” In _New Journal of Physics_ 21.9 IOP Publishing, 2019, pp. 093018 DOI: 10.1088/1367-2630/ab3cb4
  * [68] Cornelia Spee et al. “Genuine temporal correlations can certify the quantum dimension” In _New Journal of Physics_ 22.2 IOP Publishing, 2020, pp. 023028 DOI: 10.1088/1367-2630/ab6d42
  * [69] Cornelia Spee, Costantino Budroni and Otfried Gühne “Simulating extremal temporal correlations” In _New Journal of Physics_ 22.10 IOP Publishing, 2020, pp. 103037 DOI: 10.1088/1367-2630/abb899
  * [70] A.. Leggett and Anupam Garg “Quantum mechanics versus macroscopic realism: Is the flux there when nobody looks?” In _Phys. Rev. Lett._ 54 American Physical Society, 1985, pp. 857–860 DOI: 10.1103/PhysRevLett.54.857
  * [71] R Lapiedra “Joint reality and Bell inequalities for consecutive measurements” In _Europhysics Letters (EPL)_ 75.2 IOP Publishing, 2006, pp. 202–208 DOI: 10.1209/epl/i2005-10600-6
  * [72] David Avis, Patrick Hayden and Mark M. Wilde “Leggett-Garg inequalities and the geometry of the cut polytope” In _Phys. Rev. A_ 82 American Physical Society, 2010, pp. 030102 DOI: 10.1103/PhysRevA.82.030102
  * [73] Stephen Brierley et al. “Nonclassicality of Temporal Correlations” In _Phys. Rev. Lett._ 115 American Physical Society, 2015, pp. 120404 DOI: 10.1103/PhysRevLett.115.120404
  * [74] B.. Toner and D. Bacon “Communication Cost of Simulating Bell Correlations” In _Phys. Rev. Lett._ 91 American Physical Society, 2003, pp. 187904 DOI: 10.1103/PhysRevLett.91.187904
  * [75] Dmitri Maslov et al. “Quantum advantage for computations with limited space” In _preprint_ , 2020 DOI: https://arxiv.org/abs/2008.06478
  * [76] Nicolas Brunner et al. “Testing the Dimension of Hilbert Spaces” In _Phys. Rev. Lett._ 100 American Physical Society, 2008, pp. 210503 DOI: 10.1103/PhysRevLett.100.210503
  * [77] Nicolas Brunner, Miguel Navascués and Tamás Vértesi “Dimension Witnesses and Quantum State Discrimination” In _Phys. Rev. Lett._ 110 American Physical Society, 2013, pp. 150501 DOI: 10.1103/PhysRevLett.110.150501
  * [78] Hong-Wei Li et al. “Three-observer classical dimension witness violation with weak measurement” In _Communications Physics_ 1.1, 2018, pp. 10 DOI: 10.1038/s42005-018-0011-x
  * [79] Adel Sohbi, Damian Markham, Jaewan Kim and Marco Túlio Quintino “Certifying dimension of quantum systems by sequential projective measurements” In _Quantum_ 5 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2021, pp. 472 DOI: 10.22331/q-2021-06-10-472
  * [80] Chang-Jiang Huang et al. “Nonlocality, Steering, and Quantum State Tomography in a Single Experiment” In _Phys. Rev. Lett._ 127 American Physical Society, 2021, pp. 020401 DOI: 10.1103/PhysRevLett.127.020401
  * [81] John Watrous “The Theory of Quantum Information” Cambridge University Press, 2018 DOI: 10.1017/9781316848142
  * [82] Nicholas Harrigan and Robert W. Spekkens “Einstein, Incompleteness, and the Epistemic View of Quantum States” In _Foundations of Physics_ 40.2, 2010, pp. 125–157 DOI: 10.1007/s10701-009-9347-0
  * [83] J.. Bell “The theory of local beables” In _Speakable and Unspeakable in Quantum Mechanics_ Cambridge University Press, 2004, pp. 52–68

##  Appendix A (Reset-induced gap activation in XOR* games)

In this appendix we introduce an example of XOR* game whose quantum-classical
gap can be activated by allowing irreversibility. First, before introducing
the example, we state two salient features of the role of irreversibility in
XOR* games.

######  Remark 1.

For XOR* games restricted to bi-dimensional resources:

  1. 1.

The only useful irreversible transformation is the Reset gate (as defined
below).

  2. 2.

The Reset gate is only useful when applied by the second player (Bob).

######  Definition 5 (Reset gate).

The Reset gate $\mathrm{R}$ is represented by the completely positive trace-
preserving map, $\mathrm{R}(\rho)=\outerproduct{0}{0}$ for all possible qubit
states $\rho$.

The Reset gate can be interpreted as a particular case of a replacement
channel [81], where the replaced state is always the $\outerproduct{0}{0}$
pure state. Such channels represent the action of discarding the original
state and replacing it with some other state.

For classical strategies it is well known that deterministic functions between
inputs and outputs suffice to achieve optimality [40]. That is, neither shared
randomness nor local randomness are useful. Thus, we can only consider the
four possible deterministic maps for bi-dimensional systems, that are:
identity, NOT, reset to zero and reset to one. Among these, the only
irreversible ones are the reset to zero or the reset to one. The fact that
implementing the Reset gate can only be useful for the second player is also
straightforward to show. Since the first player receives the resource always
initialized in a fixed state (classically, either zero or one), the effect of
implementing a Reset gate is tantamount to implementing a reversible gate
that, for the initialized fixed state input, produces the same output, e.g,
for a state initialized at zero a reset to zero gives the same output as
implementing an identity, and for a state initialized at one the reset to zero
gives the same output as implementing a NOT gate. Thus, the Reset gate, being
a constant function, can only be leveraged by the second player to discard the
actions of the first player.

Regarding the case of employing irreversibility in quantum strategies, one
might wonder if there may exist extra operations (like a “quantum Reset
gate”), other than the previously defined Reset gate, that could be even more
useful than the Reset gate. If so, such operations should be purity preserving
on the grounds that classical randomness is not beneficial, just like in the
classical case. Then, such an hypothethical “quantum Reset gate” would act as
$\mathrm{R}_{q}(\rho)=\sigma$ for all $\rho$, where $\sigma$ has the same
degree of mixedness as $\rho$. In particular, in the pure state case,
$\mathrm{R}_{q}(\outerproduct{\psi}{\psi})=\outerproduct{\phi}{\phi}$. This,
in turn, can be re-written as
$\mathrm{R}_{q}(\outerproduct{\psi}{\psi})=U_{\phi}\outerproduct{0}{0}U^{\dagger}_{\phi}=U_{\phi}\mathrm{R}(\outerproduct{\psi}{\psi})U^{\dagger}_{\phi}$,
where $\ket{\phi}=U_{\phi}\ket{0},$ thus showing that such a “quantum Reset
gate” is nothing more than a composition of a regular Reset gate to $\ket{0}$
and a unitary evolution, for the appropriate unitary $U_{\phi}$. As such, the
Reset gate as defined in definition 5 is the only type of irreversible
operation that is useful to consider for XOR* games restricted to (classical
or quantum) bi-dimensional resources.

######  Example 7 (Reset-induced gap activation (RA) XOR* game).

Two-player XOR* game with inputs $s,t\in\\{0,1,2,3\\}$ where
$\forall_{s,t}\;p(s,t)={1}/{16}$, and $f(s,t):={\delta(s\cdot
t,0)}\oplus\delta(s\cdot t,3)$.

The previous example is by construction a legitimate XOR* game. Nevertheless,
under the assumption of reversibility and of two-dimensional systems the
game’s classical and quantum values are numerically computed to be identical,
namely $\omega_{q}(\textup{RA-XOR}^{*}|^{Rev}_{2D})=\omega_{c}(\textup{RA-
XOR}^{*}|^{Rev}_{2D})=13/16=0.8125$. This game represents then an interesting
example where the quantum-classical gap is null, without being trivial in the
sense that both classical and quantum strategies allow a winning probability
of one. From the previous results on the role of the Reset gate, we are
motivated to pursue a strategy where Bob uses such gates. Ideally, the Reset
gate is implemented for input configurations whose evaluation by the task
function only depends on Bob’s input. Precisely, from the function of the
previous example: $\forall_{s}\;f(s,0):={\delta(0,0)}\oplus\delta(0,3)=1$.
This means that a strategy where Bob for input 0 resets to 1 always wins for
all of Alice’s inputs. The winning probability of an irreversible classical
strategy implementing the Reset gate in this way can be easily numerically
computed to be optimal and yields the classical value $\omega_{c}(\textup{RA-
XOR}^{*}|^{Irr}_{2D})=14/16=0.875$, which is higher than both the classical
and quantum value in the reversible setting.

Given the considerations above, it is now straightforward to construct an
irreversible quantum strategy that outperforms the optimal classical
irreversible strategy. It is enough to implement a Reset gate in the same way
as before, where Bob for input 0 always resets to $\ket{1}$, and to optimise
for quantum reversible strategies in the remaining input configurations. This
yields a winning probability of $W_{q}(\textup{RA-XOR}^{*}|^{Irr}_{2D})\simeq
0.885$ 222Numerical findings suggest that this winning probability is the
optimal quantum value in the irreversible setting. Notice that finding the
optimal quantum value is not needed for showing Reset-induced gap activation.,
which means that the quantum-classical gap goes from zero, in the reversible
setting, to a strictly positive value in the irreversible setting,
$\Omega(\textup{RA-XOR}^{*}|^{Irr}_{2D})\geq 0.01>0=\Omega(\textup{RA-
XOR}^{*}|^{Rev}_{2D})$. This then shows an instance of quantum-classical gap
creation by employing irreversibility in the form of the Reset gates, i.e.
Reset-induced gap activation.

##  Appendix B (Preparation contextuality in XOR* games)

In this appendix we first provide the definition of preparation
noncontextuality [45] and then prove how preparation noncontextuality in the
prepare and measure scenario associated with any wing of the Bell scenario
implies locality therein (this is an already known fact – see for example
section V. and appendix A of [24] ). The latter is equivalent to show that
nonlocality in Bell scenario – in our case defining an XOR game – implies
preparation contextuality in any wing of such scenario – here defining an XOR*
game.

The notion of preparation noncontextuality is defined in the framework of
ontological models [82]. The role of an ontological model for a given physical
theory, like quantum theory, is to reproduce and provide an explanation of the
statistics predicted by the theory. It does so by associating the physical
state of the system under consideration at a given time – the ontic state – to
a point $\lambda$ in a measurable set $\Lambda,$ and the experimental
procedures – classified in preparations, transformations and measurements – to
probability distributions on the ontic space $\Lambda.$ The ontological model
reproduces the statistics of the theory by making use of the classical law of
total probability. We are here interested in experimental procedures that
correspond to lists of instructions to prepare a system in a given quantum
state. Such a preparation procedure $P$ of a quantum state $\rho$ is
represented by a probability distribution $\mu_{P}(\lambda)$ over the ontic
space, $\mu_{P}:\Lambda\rightarrow\mathbb{R}$ such that
$\int\mu_{P}(\lambda)d\lambda=1$ and $\mu_{P}(\lambda)\geq
0\;\;\forall\lambda\in\Lambda.$ We say that two preparation procedures, $P$
and $P^{\prime}$, in a prepare and measure scenario are operationally
equivalent, $P\simeq P^{\prime},$ if they provide the same statistics for any
measurement, i.e., $p(m|P,M)=p(m|P^{\prime},M)$ for every measurement $M$ and
any outcome $m.$ A simple example of operationally equivalent preparations in
quantum theory is given by any two decompositions of the completely mixed
state $\rho=\mathbb{I}/2$ of a qubit, e.g.,
$P=1/2\ket{0}\bra{0}+1/2\ket{1}\bra{1}$ and
$P^{\prime}=1/2\ket{+}\bra{+}+1/2\ket{-}\bra{-}.$

We here focus on prepare and measure scenarios. An ontological model of a
prepare and measure scenario in quantum theory is _preparation noncontextual_
if

$\mu_{P}(\lambda)=\mu_{P^{\prime}}(\lambda)\;\;\;\forall\;P\simeq P^{\prime}.$
(17)

We can now show, following [24], how preparation noncontextuality in the
prepare and measure scenario on Bob’s wing – let us choose Bob’s wing without
loss of generality – implies locality in the bipartite Bell scenario [2, 83].
Let us stress that this ultimately means that a proof of nonlocality in an XOR
game, cast in Bell scenario, implies, by virtue of our mapping, preparation
contextuality in an XOR* game treated as a prepare and measure scenario.

We start by focusing on the operational equivalences induced by Alice on Bob’s
side. Whenever she performs a measurement, that we denote with the POVM
$\\{E_{a}^{(s)}\\}_{a}$, and obtains the outcome associated with $E_{a}^{(s)}$
she steers, with probability $p(a|s)$, Bob’s system to the state
$\rho_{a|s}=\textrm{Tr}_{A}[(E_{a}^{(s)}\otimes\mathbb{I})\rho_{AB}]/p(a|s)$,
where $\rho_{AB}$ denotes the entangled state shared between Alice and Bob and
$p(a|s)=\textrm{Tr}_{AB}[(E_{a}^{(s)}\otimes\mathbb{I})\rho_{AB}]$. Because of
no-signalling, Bob can never infer the measurement setting of Alice $s$, and
therefore it holds that the different ensemble preparations labelled by $s$
will give the same state $\rho_{B}=\sum_{a}p(a|s)\rho_{a|s}$ for every $s$.
These are the operational equivalences that we consider. Let us now apply
preparation noncontextuality to the operationally equivalent preparations of
$\rho_{B}.$ It reads as

$\sum_{a}p(a|s)p(\lambda|s,a)=p(\lambda)\;\;\forall s.$

From the basic law for writing joint probabilities in terms of conditional
probabilities we notice that $p(a|s)p(\lambda|s,a)=p(a,\lambda|s)$ and, in
turn, $p(a,\lambda|s)=p(a|\lambda,s)p(\lambda|s).$ We can then write

$\sum_{a}p(a|s)p(\lambda|s,a)=\sum_{a}p(a|\lambda,s)p(\lambda|s)=p(\lambda|s)\sum_{a}p(a|\lambda,s)=p(\lambda|s),$

and so

$p(\lambda|s)=p(\lambda).$ (18)

At this point, let us consider the joint conditional probability in Bell
scenario $p(a,b|s,t).$ We want to show that it can be written as
$p(a,b|s,t)=\sum_{\lambda}p(a|s,\lambda)p(b|t,\lambda)p(\lambda)$, as this
defines the set of local correlations. First, we use the basic law for writing
joint probabilities as conditional probabilities,

$p(a,b|s,t)=p(a|s,t)p(b|s,t,a).$

We recall that no-signalling holds, and so $p(a|s,t)=p(a|s)$, thus yielding
$p(a,b|s,t)=p(a|s)p(b|s,t,a)$.

Let us focus on $p(b|s,t,a)$ and write it introducing $\lambda$ as

$p(b|s,t,a)=\sum_{\lambda}p(b,\lambda|s,t,a)=\sum_{\lambda}p(b,|\lambda,s,t,a)p(\lambda|s,t,a).$

We now impose two assumptions characterizing the ontological model framework
[59]. The first is known as measurement independence (usually justified as an
assumption of no-retrocausality) and, in the prepare and measure scenario on
Bob’s wing where the measurement settings are denoted with $t$, it reads as
$p(\lambda|s,a,t)=p(\lambda|s,a).$ The second is known as $\lambda-$mediation
(i.e., the ontic state $\lambda$ mediates any correlation between preparation
and measurement) and, in the prepare and measure scenario on Bob’s wing where
the preparations are associated with $(s,a)$ and the measurement settings with
$t$, it reads as $p(b,|\lambda,s,t,a)=p(b|\lambda,t).$ Therefore we obtain

$p(b|s,t,a)=\sum_{\lambda}p(b,|\lambda,t)p(\lambda|s,a),$

and so

$p(a,b|s,t)=\sum_{\lambda}p(a|s)p(b,|\lambda,t)p(\lambda|s,a).$

By exploiting again the fact proven above that
$p(a|s)p(\lambda|s,a)=p(a|\lambda,s)p(\lambda|s)$ we have that

$p(a,b|s,t)=\sum_{\lambda}p(b,|\lambda,t)p(a|\lambda,s)p(\lambda|s),$

and, by using preparation noncontextuality as in Eq. (18), we end the proof,

$p(a,b|s,t)=\sum_{\lambda}p(a|s,\lambda)p(b|t,\lambda)p(\lambda).$

Let us conclude by stressing how the proof just provided does not connect an
XOR game to the corresponding dual XOR* game, as the inputs considered in the
preparation stage of the prepare and measure scenario associated with the XOR*
game are $(s,a)$ and not just $s$. As a consequence, this proof does not apply
to the CHSH* game, that indeed cannot involve a proof of preparation
contextuality due to its too low cardinality of the inputs.