A Caltech Library Service

Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability

Mančinska, Laura and Vidick, Thomas (2014) Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability. In: Automata, Languages, and Programming. Lecture Notes in Computer Science. No.8572. Springer , Berlin, pp. 835-846. ISBN 978-3-662-43947-0.

Full text is not posted in this repository. Consult Related URLs below.

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 a paradox of Lucien Hardy. In our game each player has only two possible questions and can provide answers in a countable set. 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⁻²). 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⁻²).

Item Type:Book Section
Related URLs:
URLURL TypeDescription ReadCube access
Vidick, Thomas0000-0002-6405-365X
Additional Information:© 2014 Springer-Verlag Berlin Heidelberg. 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 1, Aleksandrs Belovs, Richard Cleve, David Roberson, Stephanie Wehner, Harry Buhrman and his group at CWI for helpful discussions. 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
Subject Keywords:nonlocal game; value of the game; entanglement; dimension witness
Series Name:Lecture Notes in Computer Science
Issue or Number:8572
Record Number:CaltechAUTHORS:20200805-153500961
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:104767
Deposited By: Tony Diaz
Deposited On:05 Aug 2020 23:10
Last Modified:16 Nov 2021 18:34

Repository Staff Only: item control page