Near-Optimal and Explicit Bell Inequality Violations

Harry Buhrman 1 Oded Regev 2 Scarpa Giannicola 1, 3 Ronald De Wolf 1
2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Abstract : Bell inequality violations correspond to behavior of entangled quantum systems that cannot be simulated classically. We give two new two-player games with Bell inequality violations that are stronger, fully explicit, and arguably simpler than earlier work.The first game is based on the Hidden Matching problem of quantum communication complexity, introduced by Bar-Yossef, Jayram, and Kerenidis. This game can be won with probability 1 by a quantum strategy using a maximally entangled state with local dimension n (e.g., log n EPR-pairs), while we show that the winning probability of any classical strategy differs from 1/2 by at most O(log n/√n).The second game is based on the integrality gap for Unique Games by Khot and Vishnoi and the quantum rounding procedure of Kempe, Regev, and Toner. Here n-dimensional entanglement allows to win the game with probability 1/(log n)2, while the best winning probability without entanglement is 1/n. This near-linear ratio ("Bell inequality violation'') is near-optimal, both in terms of the local dimension of the entangled state, and in terms of the number of possible outputs of the two players.
Type de document :
Communication dans un congrès
CCC 2011 - 26th Annual Conference on Computational Complexity, Jun 2011, San Jose, CA, United States. IEEE, pp.157-166, 〈10.1109/CCC.2011.30〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01110446
Contributeur : Brigitte Briot <>
Soumis le : mercredi 28 janvier 2015 - 11:17:38
Dernière modification le : vendredi 25 mai 2018 - 12:02:05

Lien texte intégral

Identifiants

Collections

Citation

Harry Buhrman, Oded Regev, Scarpa Giannicola, Ronald De Wolf. Near-Optimal and Explicit Bell Inequality Violations . CCC 2011 - 26th Annual Conference on Computational Complexity, Jun 2011, San Jose, CA, United States. IEEE, pp.157-166, 〈10.1109/CCC.2011.30〉. 〈hal-01110446〉

Partager

Métriques

Consultations de la notice

112