Document Open Access Logo

Algorithms, Bounds, and Strategies for Entangled XOR Games

Authors Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, Anand Natarajan

PDF

File

Thumbnail PDF
PDF
LIPIcs.ITCS.2019.10.pdf
  • Filesize: 0.52 MB
  • 18 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Quantum complexity theory
Keywords
  • Nonlocal games
  • XOR Games
  • Pseudotelepathy games
  • Multipartite entanglement

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Entangled games are a quantum analog of constraint satisfaction problems and have had important applications to quantum complexity theory, quantum cryptography, and the foundations of quantum mechanics. Given a game, the basic computational problem is to compute its entangled value: the supremum success probability attainable by a quantum strategy. We study the complexity of computing the (commuting-operator) entangled value omega^* of entangled XOR games with any number of players. Based on a duality theory for systems of operator equations, we introduce necessary and sufficient criteria for an XOR game to have omega^* = 1, and use these criteria to derive the following results: 
1) An algorithm for symmetric games that decides in polynomial time whether omega^* = 1 or omega^* < 1, a task that was not previously known to be decidable, together with a simple tensor-product strategy that achieves value 1 in the former case. The only previous candidate algorithm for this problem was the Navascués-Pironio-Acín (also known as noncommutative Sum of Squares or ncSoS) hierarchy, but no convergence bounds were known. 
2) A family of games with three players and with omega^* < 1, where it takes doubly exponential time for the ncSoS algorithm to witness this. By contrast, our algorithm runs in polynomial time. 
3) Existence of an unsatisfiable phase for random (non-symmetric) XOR games. We show that there exists a constant C_k^{unsat} depending only on the number k of players, such that a random k-XOR game over an alphabet of size n has omega^* < 1 with high probability when the number of clauses is above C_k^{unsat} n. 
4) A lower bound of Omega(n log(n)/log log(n)) on the number of levels in the ncSoS hierarchy required to detect unsatisfiability for most random 3-XOR games. This is in contrast with the classical case where the (3n)^{th} level of the sum-of-squares hierarchy is equivalent to brute-force enumeration of all possible solutions.

Cite As Get BibTex

Adam Bene Watts, Aram W. Harrow, Gurtej Kanwar, and Anand Natarajan. Algorithms, Bounds, and Strategies for Entangled XOR Games. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.ITCS.2019.10

Author Details

Adam Bene Watts
  • MIT Center for Theoretical Physics, 77 Massachusetts Ave, 6-304, Cambridge, MA, USA
Aram W. Harrow
  • MIT Center for Theoretical Physics, 77 Massachusetts Ave, 6-304, Cambridge, MA, USA
Gurtej Kanwar
  • MIT Center for Theoretical Physics, 77 Massachusetts Ave, 6-304, Cambridge, MA, USA
Anand Natarajan
  • California Institute of Technology, 1200 E. California Blvd, Pasadena, CA, USA

Funding

  • Bene Watts, Adam: ABW was supported by NSF grant CCF-1729369.
  • Harrow, Aram W.: AWH was funded by NSF grants CCF-1452616, CCF-1729369, ARO contract W911NF-17-1-0433 and the MIT-IBM Watson AI Lab under the project Machine Learning in Hilbert space.
  • Kanwar, Gurtej: GK was supported by DOE grant DE-SC0011090.
  • Natarajan, Anand: AN was supported by NSF grant CCF-1452616.

References

  1. Jonathan Barrett, Lucien Hardy, and Adrian Kent. No signaling and quantum key distribution. Physical review letters, 95(1):010503, 2005. URL: http://arxiv.org/abs/quant-ph/0405101.
  2. Gilles Brassard, Anne Broadbent, and Alain Tapp. Recasting mermin’s multi-player game into the framework of pseudo-telepathy. ArXiv e-prints, 2004. URL: http://arxiv.org/abs/quant-ph/0408052.
  3. Jop Briët, Harry Buhrman, Troy Lee, and Thomas Vidick. Multipartite Entanglement in XOR Games. Quantum Info. Comput., 13(3-4):334-360, March 2013. URL: http://arxiv.org/abs/0911.4007.
  4. Jop Briët and Thomas Vidick. Explicit lower and upper bounds on the entangled value of multiplayer XOR games. Communications in Mathematical Physics, 321(1):181-207, 2013. URL: http://arxiv.org/abs/1108.5647.
  5. Anne Lise Broadbent. Quantum pseudo-telepathy games. Master’s thesis, Université de Montréal, 2004. Google Scholar
  6. Boris S Cirel’son. Quantum generalizations of Bell’s inequality. Letters in Mathematical Physics, 4(2):93-100, 1980. Google Scholar
  7. John F. Clauser, Michael A. Horne, Abner Shimony, and Richard A. Holt. Proposed Experiment to Test Local Hidden-Variable Theories. Phys. Rev. Lett., 23:880-884, October 1969. URL: http://dx.doi.org/10.1103/PhysRevLett.23.880.
  8. Richard Cleve, Peter Hoyer, Benjamin Toner, and John Watrous. Consequences and Limits of Nonlocal Strategies. In CCC '04, pages 236-249, 2004. URL: http://arxiv.org/abs/quant-ph/0404076.
  9. Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In International Colloquium on Automata, Languages, and Programming, pages 320-331. Springer, 2014. Google Scholar
  10. Roger Colbeck. Quantum And Relativistic Protocols For Secure Multi-Party Computation. PhD thesis, University of Cambridge, 2006. URL: http://arxiv.org/abs/0911.3814.
  11. Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner. The Quantum Moment Problem and Bounds on Entangled Multi-prover Games. In CCC '08, pages 199-210, 2008. URL: http://arxiv.org/abs/0803.4373.
  12. Olivier Dubois and Jacques Mandler. The 3-XORSAT threshold. Comptes Rendus Mathématique, 335(11):963-966, 2002. Google Scholar
  13. Artur K Ekert. Quantum cryptography based on Bell’s theorem. Physical review letters, 67(6):661, 1991. Google Scholar
  14. Joseph Fitzsimons, Zhengfeng Ji, Thomas Vidick, and Henry Yuen. Quantum proof systems for iterated exponential time, and beyond. arXiv, 2018. URL: http://arxiv.org/abs/1805.12166.
  15. Tobias Fritz, Tim Netzer, and Andreas Thom. Can you compute the operator norm? Proceedings of the American Mathematical Society, 142(12):4265-4276, 2014. URL: http://arxiv.org/abs/1207.0975.
  16. Daniel M Greenberger, Michael A Horne, Abner Shimony, and Anton Zeilinger. Bell’s theorem without inequalities. American Journal of Physics, 58(12):1131-1143, 1990. Google Scholar
  17. Dima Grigoriev. Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity. Theoretical Computer Science, 259:613-622, 2001. URL: http://dx.doi.org/10.1016/S0304-3975(00)00157-2.
  18. Johan Håstad. Some optimal inapproximability results. Journal of the ACM (JACM), 48(4):798-859, 2001. Google Scholar
  19. Zhengfeng Ji. Classical verification of quantum proofs. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 885-898. ACM, 2016. Google Scholar
  20. Zhengfeng Ji. Compression of Quantum Multi-Prover Interactive Proofs. arXiv, 2016. URL: http://arxiv.org/abs/1610.03133.
  21. Anand Natarajan and Thomas Vidick. Low-degree testing for quantum states, and a quantum entangled games PCP for QMA. arXiv, 2018. URL: http://arxiv.org/abs/1801.03821v2.
  22. Miguel Navascués, Stefano Pironio, and Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New J. Phys., 10(7):073013, 2008. URL: http://arxiv.org/abs/0803.4290.
  23. Dimiter Ostrev and Thomas Vidick. Entanglement of approximate quantum strategies in XOR games, 2016. URL: http://arxiv.org/abs/1609.01652.
  24. C. Palazuelos and T. Vidick. Survey on nonlocal games and operator space theory. Journal of Mathematical Physics, 57(1):015220, January 2016. URL: http://dx.doi.org/10.1063/1.4938052.
  25. David Pérez-García, Michael M Wolf, Carlos Palazuelos, Ignacio Villanueva, and Marius Junge. Unbounded violation of tripartite Bell inequalities. Communications in Mathematical Physics, 279(2):455-486, 2008. URL: http://arxiv.org/abs/quant-ph/0702189.
  26. Ben W Reichardt, Falk Unger, and Umesh Vazirani. Classical command of quantum systems. Nature, 496(7446):456-460, 2013. Google Scholar
  27. William Slofstra. Tsirelson’s problem and an embedding theorem for groups arising from non-local games, 2016. URL: http://arxiv.org/abs/1606.03140.
  28. Boris S Tsirel’son. Quantum analogues of the Bell inequalities. The case of two spatially separated domains. Journal of Mathematical Sciences, 36(4):557-570, 1987. Google Scholar
  29. Umesh Vazirani and Thomas Vidick. Fully device-independent quantum key distribution. Physical review letters, 113(14):140501, 2014. Google Scholar
  30. Thomas Vidick. Three-Player Entangled XOR Games Are NP-Hard to Approximate. In Proceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS '13, pages 766-775. IEEE Computer Society, 2013. URL: http://dx.doi.org/10.1109/FOCS.2013.87.
  31. Reinhard F Werner and Michael M Wolf. All-multipartite Bell-correlation inequalities for two dichotomic observables per site. Physical Review A, 64(3):032112, 2001. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact