More Web Proxy on the site http://driver.im/

research-article

Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH

Authors:

Mohammad Bavarian,

Peter W. ShorAuthors Info & Claims

ITCS '15: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science

Pages 123 - 132

https://doi.org/10.1145/2688073.2688112

Published: 11 January 2015 Publication History

Abstract

n this work, we consider the following family of two prover one-round games. In the CHSH_q game, two parties are given x,y in F_q uniformly at random, and each must produce an output a,b in F_q without communicating with the other. The players' objective is to maximize the probability that their outputs satisfy a+b=xy in F_q. This game was introduced by Buhrman and Massar (PRA 2005) as a large alphabet generalization of the celebrated CHSH game---which is one of the most well-studied two-prover games in quantum information theory, and which has a large number of applications to quantum cryptography and quantum complexity.

Our main contributions in this paper are the first asymptotic and explicit bounds on the entangled and classical values of CHSH_q, and the realization of a rather surprising connection between CHSH_q and geometric incidence theory. On the way to these results, we also resolve a problem of Pawlowski and Winter about pairwise independent Information Causality, which, beside being interesting on its own, gives as an application a short proof of our upper bound for the entangled value of CHSH_q.

References

[1]

J. S. Bell. On the Einstein-Podolsky-Rosen paradox. Physics, 1(3), 1964.

[2]

M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the twentieth annual ACM symposium on Theory of computing(STOC), 1988.

Digital Library

[3]

J. Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1(01):1--32, 2005.

[4]

J. Bourgain, N. Katz, and T. Tao. A sum-product estimate in finite fields, and applications. Geometric & Functional Analysis, 14(1), 2004.

[5]

J. Briët and T. Vidick. Explicit lower and upper bounds on the entangled value of multiplayer XOR games. Communications in Mathematical Physics, 321(1):181--207, 2013.

[6]

N. Brunner, D. Cavalcanti, S. Pironio, V. Scarani, and S. Wehner. Bell nonlocality. quant-ph:1303.2849, 2013.

[7]

H. Buhrman and S. Massar. Causality and Tsirel'son bounds. Physical Review A, 72(5), 052103, 2005.

[8]

H. Buhrman, O. Regev, G. Scarpa, and R. de Wolf. Near-optimal and explicit Bell inequality violations. In IEEE 26th Annual Conference on Computational Complexity (CCC), pages 157--166, 2011.

Digital Library

[9]

J. F. Clauser, M. A. Horne, A. Shimony, and R. A. Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23(15):880--884, 1969.

[10]

W. v. Dam. Implausible consequences of superstrong nonlocality. Natural Computing, 12(1), 2013.

Digital Library

[11]

I. Dinur and D. Steurer. Analytical approach to parallel repetition. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC, pages 624--633, 2014.

Digital Library

[12]

A. K. Ekert. Quantum cryptography based on Bell's theorem. Physical Review Letters, 67(6):661--663, 1991.

[13]

N. Gisin. Bell inequalities: Many questions, a few answers. The Western Ontario Series in Philosophy of Science, 73, 2009.

[14]

S.-W. Ji, J. Lee, J. Lim, K. Nagata, and H.-W. Lee. Multisetting Bell inequality for qudits. Physical Review A, 78(5):052103, 2008.

[15]

T. G. Jones. Explicit incidence bounds over general finite fields. arXiv preprint arXiv:1009.3899, 2010.

[16]

T. G. Jones. New quantitative estimates on the incidence geometry and growth of finite sets. PhD Thesis, University of Bristol. arXiv:1301.4853, 2013.

[17]

M. Junge and C. Palazuelos. Large violation of Bell inequalities with low entanglement. Communications in Mathematical Physics, 306(3):695--746, 2011.

[18]

R. Kasher and J. Kempe. Two-source extractors secure against quantum adversaries. Theory of Computing, 8(21), 2012.

[19]

J. Kempe, O. Regev, and B. Toner. Unique games with entangled provers are easy. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE, 2008.

Digital Library

[20]

Y.-C. Liang, C.-W. Lim, and D.-L. Deng. Reexamination of a multisetting Bell inequality for qudits. Physical Review A, 80(5), 2009.

[21]

N. Linden, S. Popescu, A. J. Short, and A. Winter. Quantum nonlocality and beyond: limits from nonlocal computation. Physical Review Letters, 99(18):180502, 2007.

[22]

M. Navascués, S. Pironio, and A. Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10(7), 2008.

[23]

M. Pawłowski, T. Paterek, D. Kaszlikowski, V. Scarani, A. Winter, and M. Zukowski. Information causality as a physical principle. Nature, 461, 2009.

[24]

M. Pawłowski and A. Winter. Hyperbits: The information quasiparticles. Physical Review A, 85(2), 2012.

[25]

S. Popescu and D. Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24(3):379--385, 1994.

[26]

A. Rao. An exposition of Bourgain's 2-source extractor. Electronic Colloquium on Computational Complexity (ECCC), 14(034), 2007.

[27]

R. Raz. A counterexample to strong parallel repetition. SIAM Journal on Computing, 40(3):771--777, 2011.

Digital Library

[28]

B. W. Reichardt, F. Unger, and U. Vazirani. A classical leash for a quantum system: command of quantum systems via rigidity oftextrmCHSH games. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science (ITCS), 2013.

Digital Library

[29]

E. Szemerédi and W. T. Trotter Jr. Extremal problems in discrete geometry. Combinatorica, 3(3--4):381--392, 1983.

[30]

B. S. Tsirel'son. Quantum generalizations of Bell's inequality. Letters in Mathematical Physics, 4(2), 1980.

[31]

B. S. Tsirel'son. Quantum analogues of the Bell inequalities. the case of two spatially separated domains. Journal of Soviet Mathematics, 36(4), 1987.

[32]

G. Wang. Functional boxes, communication complexity and information causality. arXiv preprint arXiv:1109.4988, 2011.

[33]

R. F. Werner and M. M. Wolf. Bell inequalities and entanglement. Quantum Information and Computation (QIC), (3), 2001.

Digital Library

Cited By

Botteron PBroadbent AChhaibi RNechita IPellegrini C(2024)Algebra of Nonlocal Boxes and the Collapse of Communication ComplexityQuantum10.22331/q-2024-07-10-14028(1402)Online publication date: 10-Jul-2024
https://doi.org/10.22331/q-2024-07-10-1402
Cui DMehta AMousavi HNezhadi S(2020)A generalization of CHSH and the algebraic structure of optimal strategiesQuantum10.22331/q-2020-10-21-3464(346)Online publication date: 21-Oct-2020
https://doi.org/10.22331/q-2020-10-21-346
Kaniewski JŠupić ITura JBaccari FSalavrakos AAugusiak R(2019)Maximal nonlocality from maximal entanglement and mutually unbiased bases, and self-testing of two-qutrit quantum systemsQuantum10.22331/q-2019-10-24-1983(198)Online publication date: 24-Oct-2019
https://doi.org/10.22331/q-2019-10-24-198
Show More Cited By

Index Terms

Information Causality, Szemerédi-Trotter and Algebraic Variants of CHSH
1. Theory of computation

Recommendations

Characterizing multipartite entanglement by violation of CHSH inequalities
Abstract
Entanglement of high-dimensional and multipartite quantum systems offer promising perspectives in quantum information processing. However, the characterization and measure of such kind of entanglement is of great challenge. Here, we consider the ...
Generalizations of the Szemerédi---Trotter Theorem

We generalize the Szemerédi---Trotter incidence theorem, to bound the number of complete flags in higher dimensions. Specifically, for each $$i=0,1,\ldots ,d-1$$i=0,1, ,d-1, we are given a finite set $$S_i$$Si of i-flats in $${\mathbb {R}}^d$$Rd or in $$...
Bound on genuine multipartite correlations from the principle of information causality

Quantum mechanics is not the unique no-signaling theory which is endowed with stronger-than-classical correlations, and there exists a broad class of no-signaling theories allowing even stronger-than-quantum correlations. The principle of information ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ITCS '15: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science

January 2015

404 pages

ISBN:9781450333337

DOI:10.1145/2688073

Program Chair:
Tim Roughgarden
Stanford University

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 January 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation

Conference

ITCS'15

Sponsor:

SIGACT

ITCS'15: Innovations in Theoretical Computer Science

January 11 - 13, 2015

Rehovot, Israel

Acceptance Rates

ITCS '15 Paper Acceptance Rate 45 of 159 submissions, 28%;

Overall Acceptance Rate 172 of 513 submissions, 34%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
170
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)0

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Botteron PBroadbent AChhaibi RNechita IPellegrini C(2024)Algebra of Nonlocal Boxes and the Collapse of Communication ComplexityQuantum10.22331/q-2024-07-10-14028(1402)Online publication date: 10-Jul-2024
https://doi.org/10.22331/q-2024-07-10-1402
Cui DMehta AMousavi HNezhadi S(2020)A generalization of CHSH and the algebraic structure of optimal strategiesQuantum10.22331/q-2020-10-21-3464(346)Online publication date: 21-Oct-2020
https://doi.org/10.22331/q-2020-10-21-346
Kaniewski JŠupić ITura JBaccari FSalavrakos AAugusiak R(2019)Maximal nonlocality from maximal entanglement and mutually unbiased bases, and self-testing of two-qutrit quantum systemsQuantum10.22331/q-2019-10-24-1983(198)Online publication date: 24-Oct-2019
https://doi.org/10.22331/q-2019-10-24-198
Rey APalazuelos CVillanueva I(2019)Optimal non-signalling violations via tensor normsRevista Matemática Complutense10.1007/s13163-019-00329-8Online publication date: 12-Oct-2019
https://doi.org/10.1007/s13163-019-00329-8
Ostrev DVidick T(2018)Entanglement of approximate quantum strategies in XOR gamesQuantum Information & Computation10.5555/3370256.337026218:7-8(617-631)Online publication date: 1-Jun-2018
https://dl.acm.org/doi/10.5555/3370256.3370262
Bricout RChailloux A(2017)Recursive Cheating Strategies for the Relativistic FQ Bit Commitment ProtocolCryptography10.3390/cryptography10200141:2(14)Online publication date: 24-Aug-2017
https://doi.org/10.3390/cryptography1020014
Fehr SFillinger M(2016)On the Composition of Two-Prover Commitments, and Applications to Multi-round Relativistic CommitmentsProceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 966610.5555/3081738.3081755(477-496)Online publication date: 8-May-2016
https://dl.acm.org/doi/10.5555/3081738.3081755
Pivoluska MPlesch M(2016)An explicit classical strategy for winning a ${\mathrm{CHSH}}_{q}$ gameNew Journal of Physics10.1088/1367-2630/18/2/02501318:2(025013)Online publication date: 12-Feb-2016
https://doi.org/10.1088/1367-2630/18/2/025013
Fehr SFillinger M(2016)On the Composition of Two-Prover Commitments, and Applications to Multi-round Relativistic CommitmentsAdvances in Cryptology – EUROCRYPT 201610.1007/978-3-662-49896-5_17(477-496)Online publication date: 28-Apr-2016
https://doi.org/10.1007/978-3-662-49896-5_17

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents