SpringerLink
Log in

Quantum strategies for simple two-player XOR games

  • Published:
Quantum Information Processing Aims and scope Submit manuscript

Abstract

The non-local game scenario provides a powerful framework to study the limitations of classical and quantum correlations, by studying the upper bounds of the wining probabilities those correlations offer in cooperation games where communication between players is prohibited. Building upon results presented in the seminal work of Cleve et al. (in: 19th IEEE annual conference on computational complexity, 2004), a straightforward construction to compute the Tsirelson bounds for simple two-player XOR games is presented. The construction is applied explicitly to some examples, including the Entanglement Assisted Orientation in Space (EAOS) game of Brukner et al. (Int J Quant Inf 4(2):365–370), proving for the first time that their proposed quantum strategy is in fact the optimal, as it reaches the Tsirelson bound.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Germany)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Notes

  1. These strictly speaking are the stages of just one round of a game and some games could have more than one round - since this work deals exclusively with one round games this description fully characterizes the evolution of such games.

  2. Note that \(Q^{x}\) does not mean the set of all possible questions for the xth player, like \(Q_i\) meant for the ith player. It means the xth element of Q, whatever it might be according to some arbitrary order. Likewise \(A^{y}\) means the yth element of A.

  3. This is equivalent to saying that the average over a set of positive numbers is never greater than the highest number of the set.

  4. We make the implicit assumption that Alice and Bob always try to win the game with the highest possible probability.

  5. The quantum/classical bias is the difference between the quantum/classical value and the winning probability offered by a trivial random answer - it is a standard way to measure the quantum over classical advantage in non-local games.

  6. It is this exact rule that makes this a simple two-player XOR game. If there would be no restrictions on the questions, then (26) would be ever harder to solve for increasing values of n.

References

  1. Cleve, R., Høyer, P., Toner, B., Watrous, J.: Consequences and limits of non-local strategies. In: Proceedings. 19th IEEE Annual Conference on Computational Complexity, (2004)

  2. Brukner, Č., Paunković, N., Rudolph, T., Vedral, V.: Entanglement assisted orientation in space. Int. J. Quant. Inf. 04(02), 365–370 (2006)

    Article  Google Scholar 

  3. Buhrman, H., Cleve, R., Massar, S., de Wolf, R.: Nonlocality and communication complexity. Int. Rev. Mod. Phys. 82, 665 (2010)

    Article  ADS  Google Scholar 

  4. Broadbent, A.: André Allan Méthot, on the power of non-local boxes -. Theor. Comput. Sci. 358(1), 3–14 (2006)

    Article  MathSciNet  Google Scholar 

  5. Brassard, G., Broadbent, A., Tapp, A.: Multi-party pseudo-telepathy. Algorithms and Data Structures. WADS 2003. Lecture Notes in Computer Science, Vol. 2748. Springer, Berlin (2003)

  6. Aravind, P.K.: Quantum mysteries revisited again. Am. J. Phys. 72, 1303 (2004)

    Article  ADS  MathSciNet  Google Scholar 

  7. Ambainis, A., Kravchenko, D., Nahimovs, N., Rivosh, A.: Nonlocal quantum XOR Games for Large Number of Players—Theory and Applications of Models of Computation. TAMC 2010. Lecture Notes in Computer Science, Vol. 6108. Springer, Berlin (2010)

  8. Briet, J., Vidick, T.: Explicit lower and upper bounds on the entangled value of multiplayer XOR games. Commun. Math. Phys. 321(1), 1 (2013). Presented as a contributed talk at QIP’12

    Article  MathSciNet  Google Scholar 

  9. Regev, O., Vidick, T.: Quantum XOR games. ACM Tran. Comput. Theory (TOCT) 7, 4 (2015)

    MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The author would like to thank N. Paunković, who first introduced him to the EAOS game, and also the support of SQIG (Security and Quantum Information Group), the Instituto de Telecomunicações (IT) Research Unit, Ref. UID/EEA/50008/2019, funded by Fundação para a Ciência e Tecnologia (FCT). The author acknowledges funding from FCT through the DP-PMI Grant PD/BD/128636/2017.

Author information

Authors and Affiliations

  1. Instituto de Telecomunicações and Departamento de Matemática, Instituto Superior Técnico, Avenida Rovisco Pais, 1049-001, Lisboa, Portugal

    Ricardo Faleiro

Authors
  1. Ricardo Faleiro
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ricardo Faleiro.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Faleiro, R. Quantum strategies for simple two-player XOR games. Quantum Inf Process 19, 229 (2020). https://doi.org/10.1007/s11128-020-02717-2

Download citation

  • Received:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s11128-020-02717-2

Keywords

Search

Navigation