Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published November 2015 | Submitted
Journal Article Open

Unbounded entanglement in nonlocal games

Abstract

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.

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.

Attached Files

Submitted - 1402.4145.pdf

Files

1402.4145.pdf
Files (336.2 kB)
Name Size Download all
md5:0bf22efad33b508d623db16db087befa
336.2 kB Preview Download

Additional details

Created:
August 20, 2023
Modified:
October 20, 2023