Quantum strategies are better than classical in almost any XOR game

Andris Ambainis; Arturs Bačkurs; Kaspars Balodis; Dmitrijs Kravčenko; Raitis Ozols; Juris Smotrovs; Madars Virza

doi:10.1007/978-3-642-31594-7_3

Quantum strategies are better than classical in almost any XOR game

Andris Ambainis
, Arturs Bačkurs
, Kaspars Balodis
, Dmitrijs Kravčenko
, Raitis Ozols
, Juris Smotrovs
, Madars Virza

Massachusetts Institute of Technology

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

9 Citations (Scopus)

Abstract

We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1 - o(1) fraction of all 2-player XOR games.

Original language	English
Title of host publication	Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings
Pages	25-37
Number of pages	13
Edition	PART 1
DOIs	https://doi.org/10.1007/978-3-642-31594-7_3
Publication status	Published - 2012
Event	39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 - Warwick, United Kingdom Duration: 9 Jul 2012 → 13 Jul 2012

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Number	PART 1
Volume	7391 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	39th International Colloquium on Automata, Languages, and Programming, ICALP 2012
Country/Territory	United Kingdom
City	Warwick
Period	9/07/12 → 13/07/12

Access to Document

10.1007/978-3-642-31594-7_3

Cite this

Ambainis, A., Bačkurs, A., Balodis, K., Kravčenko, D., Ozols, R., Smotrovs, J., & Virza, M. (2012). Quantum strategies are better than classical in almost any XOR game. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings (PART 1 ed., pp. 25-37). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7391 LNCS, No. PART 1). https://doi.org/10.1007/978-3-642-31594-7_3

Ambainis, Andris ; Bačkurs, Arturs ; Balodis, Kaspars et al. / Quantum strategies are better than classical in almost any XOR game. Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1. ed. 2012. pp. 25-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1).

@inproceedings{cc3cc23c04414ab3b2f5096b6c1b2a41,

title = "Quantum strategies are better than classical in almost any XOR game",

abstract = "We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1 - o(1) fraction of all 2-player XOR games.",

author = "Andris Ambainis and Arturs Ba{\v c}kurs and Kaspars Balodis and Dmitrijs Krav{\v c}enko and Raitis Ozols and Juris Smotrovs and Madars Virza",

year = "2012",

doi = "10.1007/978-3-642-31594-7\_3",

language = "English",

isbn = "9783642315930",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

number = "PART 1",

pages = "25--37",

booktitle = "Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings",

edition = "PART 1",

note = "39th International Colloquium on Automata, Languages, and Programming, ICALP 2012 ; Conference date: 09-07-2012 Through 13-07-2012",

}

Ambainis, A, Bačkurs, A, Balodis, K , Kravčenko, D, Ozols, R, Smotrovs, J & Virza, M 2012, Quantum strategies are better than classical in almost any XOR game. in Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), no. PART 1, vol. 7391 LNCS, pp. 25-37, 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012, Warwick, United Kingdom, 9/07/12. https://doi.org/10.1007/978-3-642-31594-7_3

Quantum strategies are better than classical in almost any XOR game. / Ambainis, Andris; Bačkurs, Arturs; Balodis, Kaspars et al.
Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1. ed. 2012. p. 25-37 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 7391 LNCS, No. PART 1).

Research output: Chapter in Book/Report/Conference proceeding › Conference paper › Research › peer-review

TY - GEN

T1 - Quantum strategies are better than classical in almost any XOR game

AU - Ambainis, Andris

AU - Bačkurs, Arturs

AU - Balodis, Kaspars

AU - Kravčenko, Dmitrijs

AU - Ozols, Raitis

AU - Smotrovs, Juris

AU - Virza, Madars

PY - 2012

Y1 - 2012

N2 - We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1 - o(1) fraction of all 2-player XOR games.

AB - We initiate a study of random instances of nonlocal games. We show that quantum strategies are better than classical for almost any 2-player XOR game. More precisely, for large n, the entangled value of a random 2-player XOR game with n questions to every player is at least 1.21... times the classical value, for 1 - o(1) fraction of all 2-player XOR games.

UR - https://www.scopus.com/pages/publications/84873844360

U2 - 10.1007/978-3-642-31594-7_3

DO - 10.1007/978-3-642-31594-7_3

M3 - Conference paper

AN - SCOPUS:84873844360

SN - 9783642315930

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 25

EP - 37

BT - Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings

T2 - 39th International Colloquium on Automata, Languages, and Programming, ICALP 2012

Y2 - 9 July 2012 through 13 July 2012

ER -

Ambainis A, Bačkurs A, Balodis K , Kravčenko D, Ozols R, Smotrovs J et al. Quantum strategies are better than classical in almost any XOR game. In Automata, Languages, and Programming - 39th International Colloquium, ICALP 2012, Proceedings. PART 1 ed. 2012. p. 25-37. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); PART 1). doi: 10.1007/978-3-642-31594-7_3

Quantum strategies are better than classical in almost any XOR game

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this