A Caltech Library Service

Unbounded entanglement in nonlocal games

Mančinska, Laura and Vidick, Thomas (2015) Unbounded entanglement in nonlocal games. Quantum Information and Computation, 15 (15-16). pp. 1317-1332. ISSN 1533-7146.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Quantum entanglement is known to provide a strong advantage in many two-party distributed tasks. We investigate the question of how much entanglement is needed to reach optimal performance. For the first time we show that there exists a purely classical scenario for which no finite amount of entanglement suffices. To this end we introduce a simple two-party nonlocal game H, inspired by Lucien Hardy’s paradox. In our game each player has only two possible questions and can provide bit strings of any finite length as answer. We exhibit a sequence of strategies which use entangled states in increasing dimension d and succeed with probability 1 - O(d^(-c)) for some c ≥ 0.13. On the other hand, we show that any strategy using an entangled state of local dimension d has success probability at most 1 - Ω (d^(-2)). In addition, we show that any strategy restricted to producing answers in a set of cardinality at most d has success probability at most 1 - Ω (d^(-2)). Finally, we generalize our construction to derive similar results starting from any game G with two questions per player and finite answers sets in which quantum strategies have an advantage.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2015 Rinton Press. The first author thanks the anonymous referees of QIP 2014 for pointing out a mistake in an earlier proof of the non-quantitative part of Theorem 5, Aleksandrs Belovs for suggesting the proof of Lemma 2 as well Richard Cleve, David Roberson, Stephanie Wehner, Harry Buhrman and his group at CWI for helpful discussions. Both authors are grateful to Oded Regev who prompted us to generalize our initial results, which were restricted to Hardy’s game, by suggesting that the same construction might also apply for the CHSH game. Both authors are supported by the Ministry of Education, Singapore under the Tier 3 grant MOE2012-T3-1-009. Thomas Vidick is also supported by the Newton Institute, Cambridge. Parts of this work was completed during a workshop at the Institute for Mathematical Sciences, Singapore.
Funding AgencyGrant Number
Ministry of Education (Singapore)MOE2012-T3-1-009
Newton InstituteUNSPECIFIED
Issue or Number:15-16
Record Number:CaltechAUTHORS:20160818-080941623
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:69743
Deposited By: Tony Diaz
Deposited On:18 Aug 2016 16:49
Last Modified:03 Oct 2019 10:25

Repository Staff Only: item control page