Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography

Llorenç Escolà-Farràs; Florian Speelman

doi:10.22331/q-2025-04-18-1712

Lossy-and-Constrained Extended Non-Local Games with Applications to Quantum Cryptography

Llorenç Escolà-Farràs and Florian Speelman

QuSoft, CWI Amsterdam, Science Park 123, 1098 XG Amsterdam, The Netherlands
Multiscale Networked Systems (MNS), Informatics Institute, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, The Netherlands

Published:	2025-04-18, volume 9, page 1712
Editor:	Christos Gagatsos
Eprint:	arXiv:2405.13717v2
Doi:	https://doi.org/10.22331/q-2025-04-18-1712
Citation:	Quantum 9, 1712 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Extended non-local games are a generalization of monogamy-of-entanglement games, played by two quantum parties and a quantum referee that performs a measurement on their local quantum system. Along the lines of the NPA hierarchy, the optimal winning probability of those games can be upper bounded by a hierarchy of semidefinite programs (SDPs) converging to the optimal value. Here, we show that if one extends such games by considering $constraints$ and $loss$, motivated by experimental errors and loss through quantum communication, the convergence of the SDPs to the optimal value still holds. We give applications of this result, and we compute SDPs that show tighter security of protocols for relativistic bit commitment, quantum key distribution, and quantum position verification.

Featured image: Bounds on the normalized optimal winning probabilities (𝜔) for the lossy-BB84 game —played by two distant parties— as a function of the transmission rate of a quantum channel (𝜂). The bounds, obtained using our methods, are tight and illustrate that greater losses (smaller values of 𝜂) allow parties to achieve higher winning probabilities. These results are used to show security for the BB84 quantum position verification protocol.

Popular summary

We provide a general framework to obtain bounds on quantum nonlocal correlations when the involved parties can exploit losses in quantum communication and errors in measurement devices. To determine these limits, it is sufficient to provide a description of the experimental setup and compute a semidefinite program on a computer. We show that the obtained results can be used to prove security in various quantum cryptographic protocols, such as quantum key distribution, relativistic bit commitment, and quantum position verification.

► BibTeX data

@article{EscolaFarras2025lossyconstrained,
  doi = {10.22331/q-2025-04-18-1712},
  url = {https://doi.org/10.22331/q-2025-04-18-1712},
  title = {Lossy-and-{C}onstrained {E}xtended {N}on-{L}ocal {G}ames with {A}pplications to {Q}uantum {C}ryptography},
  author = {Escol{\`{a}}-Farr{\`{a}}s, Lloren{\c{c}} and Speelman, Florian},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1712},
  month = apr,
  year = {2025}
}

► References

[1] J. S. Bell. ``On the Einstein Podolsky Rosen paradox''. Physics Physique Fizika 1, 195–200 (1964).
https://doi.org/10.1103/PhysicsPhysiqueFizika.1.195

[2] Antonio Acín, Nicolas Brunner, Nicolas Gisin, Serge Massar, Stefano Pironio, and Valerio Scarani. ``Device-independent security of quantum cryptography against collective attacks''. Physical Review Letters 98, 230501 (2007).
https://doi.org/10.1103/PhysRevLett.98.230501

[3] S. Pironio, A. Acín, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe. ``Random numbers certified by Bell's theorem''. Nature 464, 1021–1024 (2010).
https://doi.org/10.1038/nature09008

[4] Harry Buhrman, Richard Cleve, Serge Massar, and Ronald de Wolf. ``Nonlocality and communication complexity''. Reviews of Modern Physics 82, 665–698 (2010).
https://doi.org/10.1103/RevModPhys.82.665

[5] Dominic Mayers and Andrew Yao. ``Self testing quantum apparatus''. Quantum Info. Comput. 4, 273–286 (2004).
https://doi.org/10.26421/QIC4.4-3

[6] Ivan Šupić and Joseph Bowles. ``Self-testing of quantum systems: a review''. Quantum 4, 337 (2020).
https://doi.org/10.22331/q-2020-09-30-337

[7] Janet Anders and Dan E. Browne. ``Computational power of correlations''. Physical Review Letters 102, 050502 (2009).
https://doi.org/10.1103/PhysRevLett.102.050502

[8] 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 (1969).
https://doi.org/10.1103/PhysRevLett.23.880

[9] Richard Cleve, Peter Hoyer, Ben Toner, and John Watrous. ``Consequences and limits of nonlocal strategies'' (2010). arXiv:quant-ph/0404076.
arXiv:quant-ph/0404076

[10] Stephanie Wehner. ``Tsirelson bounds for generalized Clauser-Horne-Shimony-Holt inequalities''. Physical Review A 73 (2006).
https://doi.org/10.1103/physreva.73.022110

[11] Yeong-Cherng Liang and Andrew C. Doherty. ``Bounds on quantum correlations in bell-inequality experiments''. Phys. Rev. A 75, 042103 (2007).
https://doi.org/10.1103/PhysRevA.75.042103

[12] Miguel Navascués, Stefano Pironio, and Antonio Acín. ``Bounding the set of quantum correlations''. Phys. Rev. Lett. 98, 010401 (2007).
https://doi.org/10.1103/PhysRevLett.98.010401

[13] Miguel Navascués, Stefano Pironio, and Antonio Acín. ``A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations''. New Journal of Physics 10, 073013 (2008).
https://doi.org/10.1088/1367-2630/10/7/073013

[14] Oded Regev and Thomas Vidick. ``Quantum XOR games'' (2012). arXiv:1207.4939.
arXiv:1207.4939

[15] T. Cooney, M. Junge, C. Palazuelos, and D. Pérez-García. ``Rank-one quantum games'' (2013). arXiv:1112.3563.
arXiv:1112.3563

[16] Nathaniel Johnston, Rajat Mittal, Vincent Russo, and John Watrous. ``Extended non-local games and monogamy-of-entanglement games''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 472, 20160003 (2016).
https://doi.org/10.1098/rspa.2016.0003

[17] Marco Tomamichel, Serge Fehr, Jedrzej Kaniewski, and Stephanie Wehner. ``A monogamy-of-entanglement game with applications to device-independent quantum cryptography''. New Journal of Physics 15, 103002 (2013).
https://doi.org/10.1088/1367-2630/15/10/103002

[18] Vincent Russo and John Watrous. ``Extended nonlocal games from quantum-classical games'' (2017). arXiv:1709.01837.
arXiv:1709.01837

[19] Llorenç Escolà-Farràs and Florian Speelman. ``Single-qubit loss-tolerant quantum position verification protocol secure against entangled attackers''. Physical Review Letters 131 (2023).
https://doi.org/10.1103/physrevlett.131.140802

[20] Llorenç Escolà-Farràs. ``https://github.com/llorensescola/LossyAndConstrainedGames''.
https://github.com/llorensescola/LossyAndConstrainedGames

[21] Adrian Kent. ``Unconditionally secure bit commitment by transmitting measurement outcomes''. Physical Review Letters 109 (2012).
https://doi.org/10.1103/physrevlett.109.130501

[22] Charles H. Bennett and Gilles Brassard. ``Quantum cryptography: Public key distribution and coin tossing''. Proc. IEEE Int. Conf. on Computers, Systems, and Signal Process (Bangalore) (Piscataway, NJ: IEEE) (1984).

[23] Jedrzej Kaniewski, Marco Tomamichel, Esther Hanggi, and Stephanie Wehner. ``Secure bit commitment from relativistic constraints''. IEEE Transactions on Information Theory 59, 4687–4699 (2013).
https://doi.org/10.1109/tit.2013.2247463

[24] Damián Pitalúa-García and Iordanis Kerenidis. ``Practical and unconditionally secure spacetime-constrained oblivious transfer''. Physical Review A 98 (2018).
https://doi.org/10.1103/physreva.98.032327

[25] Monique Laurent and Franz Rendl. ``Semidefinite programming and integer programming''. In K. Aardal, G.L. Nemhauser, and R. Weismantel, editors, Discrete Optimization. Volume 12 of Handbooks in Operations Research and Management Science, pages 393–514. Elsevier (2005).
https://doi.org/10.1016/S0927-0507(05)12008-8

[26] Stephen Boyd and Lieven Vandenberghe. ``Convex optimization''. Cambridge University Press. (2004).

[27] Vincent Russo. ``Extended nonlocal games'' (2017). arXiv:1704.07375.
arXiv:1704.07375

[28] Leon Alaoglu. ``Weak topologies of normed linear spaces''. Annals of Mathematics 41, 252–267 (1940).

[29] Anne Broadbent and Eric Culf. ``Rigidity for Monogamy-Of-Entanglement Games''. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Volume 251 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1–28:29. Dagstuhl, Germany (2023). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2023.28

[30] Hoi-Kwong Lo and H. F. Chau. ``Is quantum bit commitment really possible?''. Phys. Rev. Lett. 78, 3410–3413 (1997).
https://doi.org/10.1103/PhysRevLett.78.3410

[31] Dominic Mayers. ``Unconditionally secure quantum bit commitment is impossible''. Phys. Rev. Lett. 78, 3414–3417 (1997).
https://doi.org/10.1103/PhysRevLett.78.3414

[32] Charles H. Bennett, Gilles Brassard, and N. David Mermin. ``Quantum cryptography without Bell's theorem''. Phys. Rev. Lett. 68, 557–559 (1992).
https://doi.org/10.1103/PhysRevLett.68.557

[33] Nishanth Chandran, Vipul Goyal, Ryan Moriarty, and Rafail Ostrovsky. ``Position based cryptography''. In Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference. Volume 5677 of Lecture Notes in Computer Science, pages 391–407. Springer (2009).
https://doi.org/10.1007/978-3-642-03356-8_23

[34] W. K. Wootters and W. H. Zurek. ``A single quantum cannot be cloned''. Nature 299, 802–803 (1982).
https://doi.org/10.1038/299802a0

[35] Adrian Kent, William J. Munro, and Timothy P. Spiller. ``Quantum tagging: Authenticating location via quantum information and relativistic signaling constraints''. Physical Review A 84 (2011).
https://doi.org/10.1103/physreva.84.012326

[36] Robert A. Malaney. ``Location-dependent communications using quantum entanglement''. Phys. Rev. A 81, 042319 (2010).
https://doi.org/10.1103/PhysRevA.81.042319

[37] Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, and Christian Schaffner. ``Position-based quantum cryptography: Impossibility and constructions''. SIAM Journal on Computing 43, 150–178 (2014).
https://doi.org/10.1137/130913687

[38] Salman Beigi and Robert König. ``Simplified instantaneous non-local quantum computation with applications to position-based cryptography''. New Journal of Physics 13, 093036 (2011).
https://doi.org/10.1088/1367-2630/13/9/093036

[39] Adrian Kent, William Munro, Timothy Spiller, and Raymond Beausoleil. ``Tagging systems. us patent nr 2006/0022832'' (2006).

[40] Hoi-Kwan Lau and Hoi-Kwong Lo. ``Insecurity of position-based quantum-cryptography protocols against entanglement attacks''. Physical Review A 83 (2011).
https://doi.org/10.1103/physreva.83.012322

[41] Jérémy Ribeiro and Frédéric Grosshans. ``A tight lower bound for the BB84-states quantum-position-verification protocol'' (2015).

[42] Kaushik Chakraborty and Anthony Leverrier. ``Practical position-based quantum cryptography''. Physical Review A 92 (2015).
https://doi.org/10.1103/physreva.92.052304

[43] Florian Speelman. ``Instantaneous Non-Local Computation of Low T-Depth Quantum Circuits''. In Anne Broadbent, editor, 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Volume 61 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1–9:24. Dagstuhl, Germany (2016). Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.TQC.2016.9

[44] Kfir Dolev. ``Constraining the doability of relativistic quantum tasks'' (2022). arXiv:1909.05403.
arXiv:1909.05403

[45] Kfir Dolev and Sam Cree. ``Non-local computation of quantum circuits with small light cones'' (2022). arXiv:2203.10106.
arXiv:2203.10106

[46] Alvin Gonzales and Eric Chitambar. ``Bounds on instantaneous nonlocal quantum computation''. IEEE Transactions on Information Theory 66, 2951–2963 (2020).
https://doi.org/10.1109/tit.2019.2950190

[47] Joy Cree and Alex May. ``Code-routing: a new attack on position verification''. Quantum 7, 1079 (2023).
https://doi.org/10.22331/q-2023-08-09-1079

[48] Kirsten Kanneworff, Mio Poortvliet, Dirk Bouwmeester, Rene Allerstorfer, Philip Verduyn Lunel, Florian Speelman, Harry Buhrman, Petr Steindl, and Wolfgang Löffler. ``Towards experimental demonstration of quantum position verification using true single photons'' (2025). arXiv:2502.04125.
arXiv:2502.04125

Cited by

[1] Kirsten Kanneworff, Mio Poortvliet, Dirk Bouwmeester, Rene Allerstorfer, Philip Verduyn Lunel, Florian Speelman, Harry Buhrman, Petr Steindl, and Wolfgang Löffler, "Towards experimental demonstration of quantum position verification using single photons", Quantum Science and Technology 10 4, 045004 (2025).

[2] Ian George, Rene Allerstorfer, Philip Verduyn Lunel, and Eric Chitambar, "Orthogonality broadcasting and quantum position verification", New Journal of Physics 27 5, 054511 (2025).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-12 23:37:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

On Crossref's cited-by service no data on citing works was found (last attempt 2026-08-13 17:08:26). Could not fetch ADS cited-by data during last attempt 2026-08-13 17:08:26: cURL error 28: Operation timed out after 10001 milliseconds with 0 bytes received

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.