Parallel repetition of local simultaneous state discrimination

Llorenç Escolà-Farràs; Jaròn Has; Maris Ozols; Christian Schaffner; Mehrdad Tahmasbi

doi:10.22331/q-2025-04-15-1706

Parallel repetition of local simultaneous state discrimination

Llorenç Escolà-Farràs^1,2, Jaròn Has³, Maris Ozols^1,3,4, Christian Schaffner^1,2, and Mehrdad Tahmasbi⁵

¹QuSoft, Amsterdam, The Netherlands
²Informatics Institute, University of Amsterdam, The Netherlands
³Korteweg-de Vries Institute (KdVI), University of Amsterdam, The Netherlands
⁴Institute for Logic, Language, and Computation (ILLC), University of Amsterdam, The Netherlands
⁵Tufts University, Medford, MA, USA

Published:	2025-04-15, volume 9, page 1706
Editor:	Anurag Anshu
Eprint:	arXiv:2211.06456v2
Doi:	https://doi.org/10.22331/q-2025-04-15-1706
Citation:	Quantum 9, 1706 (2025).

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

Abstract

Local simultaneous state discrimination (LSSD) is a recently introduced problem in quantum information processing. Its classical version is a non-local game played by non-communicating players against a referee. Based on a known probability distribution, the referee generates one input for each of the players and keeps one secret value. The players have to guess the referee's value and win if they all do so. For this game, we investigate the advantage of no-signalling strategies over classical ones. We show numerically that for three players and binary values, no-signalling strategies cannot provide any improvement over classical ones. For a certain LSSD game based on a binary symmetric channel, we show that no-signalling strategies are strictly better when multiple simultaneous instances of the game are played. Good classical strategies for this game can be defined by codes, and good no-signalling strategies by list-decoding schemes. We expand this example game to a class of games defined by an arbitrary channel, and extend the idea of using codes and list decoding to define strategies for multiple simultaneous instances of these games. Finally, we give an expression for the limit of the exponent of the classical winning probability, and show that no-signalling strategies based on list-decoding schemes achieve this limit.

Featured image: Optimal classical (blue) and no-signalling (red) winning probabilities for the two-fold parallel repetition of the binary-symmetric-channel game as a function of the noise parameter α. The light blue area represents the values below the optimal classical winning probability, and the blue dots represent the optimal quantum winning probability.

Popular summary

Non-local games are played by two collaborating players against a referee who supplies questions to the players and checks the consistency of their answers. While the players cannot communicate during the game, they are allowed to correlate their answers using either pre-shared randomness or entanglement. We study a particular game – the binary-symmetric-channel game – in which the two players receive two noisy versions of the same bit and must both output the original bit. We investigate the winning probability for 2 and 3 parallel repetitions of this game and show that for most values of the noise parameter α quantum strategies do not outperform classical ones. We also relate the n-fold parallel repetition of this game to error correction.

► BibTeX data

@article{EscolaFarras2025parallelrepetition,
  doi = {10.22331/q-2025-04-15-1706},
  url = {https://doi.org/10.22331/q-2025-04-15-1706},
  title = {Parallel repetition of local simultaneous state discrimination},
  author = {Escol{\`{a}}-Farr{\`{a}}s, Lloren{\c{c}} and Has, Jar{\`{o}}n and Ozols, Maris and Schaffner, Christian and Tahmasbi, Mehrdad},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1706},
  month = apr,
  year = {2025}
}

► References

[1] Richard E. Blahut. ``Hypothesis testing and information theory''. IEEE Transactions on Information Theory 20, 405–417 (1974).
https://doi.org/10.1109/TIT.1974.1055254

[2] Yury Polyanskiy, H. Vincent Poor, and Sergio Verdu. ``Channel coding rate in the finite blocklength regime''. IEEE Transactions on Information Theory 56, 2307–2359 (2010).
https://doi.org/10.1109/TIT.2010.2043769

[3] Ueli Maurer. ``Authentication theory and hypothesis testing''. IEEE Transactions on Information Theory 46, 1350–1356 (2000).
https://doi.org/10.1109/18.850674

[4] Larry Wasserman. ``All of statistics: A concise course in statistical inference''. Springer Texts in Statistics. Springer. New York (2004). 1st edition.
https://doi.org/10.1007/978-0-387-21736-9

[5] Carl W. Helstrom. ``Quantum detection and estimation theory''. Journal of Statistical Physics 1, 231–252 (1969).
https://doi.org/10.1007/BF01007479

[6] Joonwoo Bae and Leong-Chuan Kwek. ``Quantum state discrimination and its applications''. Journal of Physics A: Mathematical and Theoretical 48, 083001 (2015).
https://doi.org/10.1088/1751-8113/48/8/083001

[7] Charles H. Bennett, David P. DiVincenzo, Christopher A. Fuchs, Tal Mor, Eric Rains, Peter W. Shor, John A. Smolin, and William K. Wootters. ``Quantum nonlocality without entanglement''. Physical Review A 59, 1070–1091 (1999).
https://doi.org/10.1103/physreva.59.1070

[8] Andrew M. Childs, Debbie Leung, Laura Mančinska, and Maris Ozols. ``A framework for bounding nonlocality of state discrimination''. Communications in Mathematical Physics 323, 1121–1153 (2013).
https://doi.org/10.1007/s00220-013-1784-0

[9] Christian Majenz, Maris Ozols, Christian Schaffner, and Mehrdad Tahmasbi. ``Local simultaneous state discrimination''. Physical Review A 109 (2024).
https://doi.org/10.1103/physreva.109.052217

[10] Anne Broadbent and Sébastien Lord. ``Uncloneable quantum encryption via oracles''. In Steven T. Flammia, editor, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Volume 158 of Leibniz International Proceedings in Informatics (LIPIcs), pages 4:1–4:22. Dagstuhl, Germany (2020). Schloss Dagstuhl–Leibniz-Zentrum für Informatik. arXiv:1903.00130.
https://doi.org/10.4230/LIPIcs.TQC.2020.4
arXiv:1903.00130

[11] Christian Majenz, Christian Schaffner, and Mehrdad Tahmasbi. ``Limitations on uncloneable encryption and simultaneous one-way-to-hiding'' (2021). arXiv:2103.14510.
arXiv:2103.14510

[12] Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry. ``On the feasibility of unclonable encryption, and more''. In Yevgeniy Dodis and Thomas Shrimpton, editors, Advances in Cryptology – CRYPTO 2022. Pages 212–241. Springer Nature (2022).
https://doi.org/10.1007/978-3-031-15979-4_8

[13] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry. ``Hidden cosets and applications to unclonable cryptography''. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – Crypto 2021. Pages 556–584. Springer (2021). arXiv:2107.05692.
https://doi.org/10.1007/978-3-030-84242-0_20
arXiv:2107.05692

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

[15] Abbas El Gamal and Young-Han Kim. ``Network information theory''. Cambridge University Press. (2011).
https://doi.org/10.1017/cbo9781139030687

[16] Alexander S. Holevo. ``Quantum systems, channels, information''. De Gruyter. (2019).
https://doi.org/10.1515/9783110642490

[17] Omar Fawzi and Paul Fermé. ``Beating the sum-rate capacity of the binary adder channel with non-signaling correlations''. In 2022 IEEE International Symposium on Information Theory (ISIT). Pages 2750–2755. (2022).
https://doi.org/10.1109/ISIT50566.2022.9834699

[18] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, and Stephanie Wehner. ``Bell nonlocality''. Rev. Mod. Phys. 86, 419–478 (2014). arXiv:1303.2849.
https://doi.org/10.1103/RevModPhys.86.419
arXiv:1303.2849

[19] Jaron Has, Llorenç Escolà Farràs, and Maris Ozols. ``Parallel repetition of LSSD (GitHub repository)''. https://github.com/JaronHas/ParallelRepetitionOfLSSD (2024).
https://github.com/JaronHas/ParallelRepetitionOfLSSD

[20] 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). arXiv:0803.4290.
https://doi.org/10.1088/1367-2630/10/7/073013
arXiv:0803.4290

[21] Richard W. Hamming. ``Error detecting and error correcting codes''. Bell System Technical Journal 29, 147–160 (1950).
https://doi.org/10.1002/j.1538-7305.1950.tb00463.x

[22] Harry Buhrman, Serge Fehr, and Christian Schaffner. ``On the parallel repetition of multi-player games: The no-signaling case''. In Steven T. Flammia and Aram W. Harrow, editors, 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Volume 27 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24–35. Dagstuhl, Germany (2014). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. arXiv:1312.7455.
https://doi.org/10.4230/LIPIcs.TQC.2014.24
arXiv:1312.7455

[23] Thomas M. Cover and Joy A. Thomas. ``Elements of information theory''. Wiley. (2005).
https://doi.org/10.1002/047174882x

[24] Imre Csiszár and János Körner. ``Information theory: coding theorems for discrete memoryless systems''. Cambridge University Press. (2011).
https://doi.org/10.1017/cbo9780511921889

[25] Claude E. Shannon. ``A mathematical theory of communication''. The Bell System Technical Journal 27, 379–423 (1948).
https://doi.org/10.1002/j.1538-7305.1948.tb01338.x

[26] Suguru Arimoto. ``On the converse to the coding theorem for discrete memoryless channels (corresp.)''. IEEE Transactions on Information Theory 19, 357–359 (1973).
https://doi.org/10.1109/TIT.1973.1055007

[27] Gunter Dueck and János Körner. ``Reliability function of a discrete memoryless channel at rates above capacity (corresp.)''. IEEE Transactions on Information Theory 25, 82–85 (1979).
https://doi.org/10.1109/tit.1979.1056003

[28] John Watrous. ``Lecture 8: The hierarchy of Navascués, Pironio, and Acín''. Lecture notes of ``Advanced topics in quantum information theory'', https://johnwatrous.com/wp-content/uploads/2023/08/QIT-notes.08.pdf (2021).
https://johnwatrous.com/wp-content/uploads/2023/08/QIT-notes.08.pdf

[29] Jonathan Barrett, Noah Linden, Serge Massar, Stefano Pironio, Sandu Popescu, and David Roberts. ``Nonlocal correlations as an information-theoretic resource''. Physical Review A 71, 022101 (2005). arXiv:quant-ph/0404097.
https://doi.org/10.1103/physreva.71.022101
arXiv:quant-ph/0404097

[30] Komei Fukuda. https://people.inf.ethz.ch/fukudak/cdd_home/ (2022).
https://people.inf.ethz.ch/fukudak/cdd_home/

[31] Stefano Pironio, Jean-Daniel Bancal, and Valerio Scarani. ``Extremal correlations of the tripartite no-signaling polytope''. Journal of Physics A: Mathematical and Theoretical 44, 065303 (2011). arXiv:1101.2477.
https://doi.org/10.1088/1751-8113/44/6/065303
arXiv:1101.2477

Cited by

[1] Prabhanjan Ananth, Fatih Kaleoglu, and Henry Yuen, "Simultaneous Haar Indistinguishability with Applications to Unclonable Cryptography", arXiv:2405.10274, (2024).

[2] Christian Majenz, Maris Ozols, Christian Schaffner, and Mehrdad Tahmasbi, "Local simultaneous state discrimination", Physical Review A 109 5, 052217 (2024).

The above citations are from SAO/NASA ADS (last updated successfully 2026-08-09 03:07:20). 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-09 03:07:12).

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.