Connecting XOR and XOR games Lorenzo Catani1Ricardo Faleiro2Pierre-Emmanuel Emeriau3 Shane Mansfield3 and Anna Pappa1 1Electrical Engineering and Computer Science Department

2025-04-27 1 0 728.74KB 15 页 10玖币

侵权投诉

Connecting XOR and XOR* games

Lorenzo Catani1,∗Ricardo Faleiro2,†Pierre-Emmanuel Emeriau3, Shane Mansﬁeld3, and Anna Pappa1

1Electrical Engineering and Computer Science Department,

Technische Universitat Berlin, 10587 Berlin, Germany

2Instituto de Telecomunicações,

Avenida Rovisco Pais 1,049-001, Lisboa, Portugal

3Quandela, 7 Rue Léonard de Vinci, 91300 Massy, France

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 ﬁnal measurement.

Examples of XOR* games are 2→1quantum 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.

I. 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 ques-

tions (arithmetic is modulo 2). The bound on the perfor-

mances of classical strategies is known as the Bell bound,

while in the quantum case the maximum winning prob-

ability 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 phys-

ical theories. Scenarios that involve violations of the Bell

bound are said to manifest “nonlocality” (meaning that

the statistics they show are inconsistent with a descrip-

tion in terms of a local hidden variable model [2]), and

the Tsirelson bound can be interpreted as a quantiﬁer

of how nonlocal quantum theory is within the broader

landscape of all possible no-signaling theories. Nonlocal-

ity is also known to be a useful resource for applications

∗lorenzo.catani@tu-berlin.de

†ricardofaleiro@tecnico.ulisboa.pt

in quantum technology, e.g., in device-independent cryp-

tography [4–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 advan-

tage and speedups in a variety of settings [9–35].

Inspired by the CHSH game, broad classes of nonlo-

cal cooperative games have been proposed. These in-

volve, in their simplest formulation, two spatially sepa-

rated parties performing operations on some shared re-

source system, while being forbidden from communicat-

ing. Moreover, there also exist games cast in diﬀerent

setups that show the same classical and quantum bounds

as the CHSH game [9, 36–38]. 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 transforma-

tions 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 quan-

tiﬁer of the nonlocality of quantum theory and it be-

comes 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 particu-

lar classes of nonlocal and monopartite sequential games

that include various known games studied in the liter-

ature. More precisely, we focus on a subclass of non-

local games – XOR games [39] – where the goal is to

satisfy the condition that a (possibly nonlinear) func-

tion of the inputs equals the XOR (or sum modulo 2)

of the output bits. Via Theorem 1, we relate a sub-

set of these to a class of monopartite sequential games –

the XOR* games – where the goal is to obtain, as sin-

gle output, the (possibly nonlinear) function of the in-

arXiv:2210.00397v4 [quant-ph] 5 Feb 2024

puts. 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 [40, 41] where Alice and Bob have to compute a

Kronecker-delta function of the input trits. Regarding

XOR* games, examples are the 2→1quantum random

access codes (QRACs)[36], 2→1parity oblivious multi-

plexing (POM) [9] and CHSH* [38] games. By virtue of

our categorisation, the CHSH* game emerges as the nat-

ural XOR* version of the CHSH game and the QRACs

read as the XOR* versions of an XOR game which is dif-

ferent from the CHSH game. This may sound surprising,

as the 2→1QRAC is usually associated to the CHSH

game in that it shares the same values for the Bell and

Tsirelson bounds [42].

Crucial in our work is Theorem 1: it allows us to con-

nect 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. [39]) 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

III C and, as a consequence of our framework, we also

deﬁne the XOR versions of known XOR* games such as

the 2→1QRAC [36], the binary output Torpedo game

[33], and the Gallego et al. [43] 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 [44] 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 clas-

sical strategies in XOR nonlocal games can be mapped

to proofs of preparation contextuality in monopartite se-

quential games (interpreted as prepare and measure sce-

narios) via the mapping of the theorem. However, this

argument does not apply to all the XOR* games that

mimic the quantum over classical computational advan-

tages of the XOR games and, crucially, does not apply to

what we deﬁne 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 outlin-

ing 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 II we describe nonlocal games and monopar-

tite sequential games, focusing speciﬁcally on XOR and

XOR* games. In section III we relate XOR and XOR*

games via Theorem 1, which establishes a mapping be-

tween these two classes. In particular, we prove Theo-

rem 1 using a diagrammatic approach according to the

formalism of process theories [45], and we give various

examples of games within these classes. In section IV we

discuss why the typical features employed to explain the

quantum computational advantage in information pro-

cessing tasks do not apply in the case of XOR* games

and we advance a proposal to overcome this problem. In

section V we discuss the signiﬁcance of the results and we

outline future challenges. Finally, we relegate all proofs

of the stated lemmas to A.

II. XOR NONLOCAL GAMES AND XOR*

SEQUENTIAL GAMES

Acooperative game consists of a protocol involving

some number of agents (players) that cooperate to per-

form a certain task. In order to win the game the play-

ers 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 condi-

tion as a predicate that equates the task function with

a function of the outputs. A game is also speciﬁed by

the setup it is played in. The setup is deﬁned 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 deﬁnes a strategy for the game. Each

strategy has to obey possible restrictions that, given the

speciﬁcation of the setup, the protocol posits. The typi-

cal example of such a restriction, in the context of nonlo-

cal games where the players are spatially separated and

cannot communicate, is the principle of no-signaling. No-

tice that these restrictions are theory-independent, in the

sense that they must be obeyed independently of the pre-

cise operational theory (e.g., classical or quantum theory)

that the strategies of the players are formulated in.1

Finally, a game, in general, can also be speciﬁed by ex-

tra constraints that do not emerge from the setup, but are

artiﬁcial constraints that are imposed on the set of pos-

sible strategies. Examples of these are the parity oblivi-

ousness in the parity oblivious multiplexing game [9], the

dimensional constraint in quantum random access codes

1The term “theory-independent” is standard in the literature of

device-independent protocols (see for example [46]). 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).

[36, 47] and, more recently, the information restriction

on the communication channel in the protocols consid-

ered in [46]. The purpose of introducing these artiﬁcial

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 perfor-

mances of the strategies depending on the operational

theory they are formulated in. In particular, they al-

low to observe performance gaps between classical and

quantum strategies. Given some game G, such a gap

is characterised by a positive quantum-over-classical ad-

vantage,2Ω(G) := ωq(G)−ωc(G)>0, where ωq(G)and

ωc(G)denote the highest probabilities to win Gby means

of quantum and a classical strategy, respectively called

the quantum value and classical value of the game. No-

tice that when we say “classical” and “quantum” strate-

gies we mean strategies that employ systems that are

prepared, transformed and measured according to the

rules of the respective theory. Furthermore, when re-

ferring to the quantum-over-classical advantage and/or

the classical and quantum values for games bearing ar-

tiﬁcial constraints, we will explicitly write the type of

constraint in the notation. For instance, XOR* games re-

stricted to two-dimensional resources and reversible op-

erations, which we will extensively deal with later on,

have their quantum-over-classical advantage written as

Ω(XOR∗|Rev

2D) := ωq(XOR∗|Rev

2D)−ωc(XOR∗|Rev

2D).

In summary, a game is formally deﬁned by a speciﬁca-

tion of a setup, predicate, restrictions and possible arti-

ﬁcial constraints. In this section we are interested in two

broad classes of games: nonlocal games and monopartite

sequential games, which we now deﬁne in the case of two

players (ﬁgure 1).

Deﬁnition 1 (Two-player Nonlocal game).

•Setup: the two players, Alice and Bob, receive in-

puts s∈ S and t∈ T , respectively, sampled from a

known probability distribution p(s, t), where Sand

Tdenote tuples of dits of ﬁnite dimension. Be-

fore 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 lo-

cal operations (transformations and measurements)

controlled by the values of their respective inputs.

Each player has to provide an output, denoted with

a∈ A for Alice and b∈ B for Bob, where Aand B

denote tuples of dits of ﬁnite dimension.

•Restriction: the restriction of the setup is the no-

signalling condition, that prevents Alice and Bob

2In the following, we will refer to the quantum-over-classical ad-

vantage also as “quantum-classical gap” or “performance gap”.

– in spatially separated locations – from communi-

cating during the game,

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

•Predicate:

Wg|f(a, b|s, t) = 1if f(s, t) = g(a, b)

0otherwise.(2)

The function f(s, t)is what we called the “task function”

at the beginning of the section.

Deﬁnition 2 (Two-player Monopartite Sequential

game).

•Setup: the two players, Alice and Bob, receive in-

puts s∈ S and t∈ T , respectively, sampled from

a known probability distribution p(s, t), where S

and Tdenote tuples of dits of ﬁnite dimension.

They are ordered in sequence, say Alice before Bob

( denoted as “A < B”). Alice is given a single re-

source system on which she applies one operation

controlled by the value of the input sshe receives.

The system is forwarded to Bob on which he also

applies one operation controlled by the value of the

input the receives. At the end the resource sys-

tem is subjected to a ﬁxed measurement. In this

way it is subjected to a ordered sequence of opera-

tions (transformations or measurements) controlled

by the inputs, and the strategy the players agree on

consists of choosing the resource system, the con-

trolled operations and the measurement. The out-

come m∈ M of the measurement is the output of

the game, where Mdenotes a tuple of dits of ﬁnite

dimension.

•Restriction: analogously to the principle of no-

signaling in nonlocal games, the physical restric-

tion on the game is here that the communication

between the players cannot violate the causal struc-

ture 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 ais the variable associated with Alice’s

choice of operation.

•Artiﬁcial constraints: They might be of various

types. For example, reversibility of operations, di-

mensional constraints on the resource, parity obliv-

iousness, informational restriction of the channels,

etc.

•Predicate:

Wf(m|s, t) = 1if f(s, t) = m

0otherwise.(4)

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

ConnectingXORandXOR*gamesLorenzoCatani1,∗RicardoFaleiro2,†Pierre-EmmanuelEmeriau3,ShaneMansfield3,andAnnaPappa11ElectricalEngineeringandComputerScienceDepartment,TechnischeUniversitatBerlin,10587Berlin,Germany2InstitutodeTelecomunicações,AvenidaRoviscoPais1,049-001,Lisboa,Portugal3Quandela,7RueLéona...

展开>> 收起<<

Connecting XOR and XOR games Lorenzo Catani1Ricardo Faleiro2Pierre-Emmanuel Emeriau3 Shane Mansfield3 and Anna Pappa1 1Electrical Engineering and Computer Science Department.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Connecting XOR and XOR games Lorenzo Catani1Ricardo Faleiro2Pierre-Emmanuel Emeriau3 Shane Mansfield3 and Anna Pappa1 1Electrical Engineering and Computer Science Department

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: