A monogamy-of-entanglement game for subspace coset states

Eric Culf; Thomas Vidick

doi:10.22331/q-2022-09-01-791

A monogamy-of-entanglement game for subspace coset states

Eric Culf¹ and Thomas Vidick²

¹Department of Mathematics and Statistics, University of Ottawa, Canada
²Department of Computing and Mathematical Sciences, California Institute of Technology, USA

Published:	2022-09-01, volume 6, page 791
Eprint:	arXiv:2107.13324v5
Doi:	https://doi.org/10.22331/q-2022-09-01-791
Citation:	Quantum 6, 791 (2022).

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

Abstract

We establish a strong monogamy-of-entanglement property for subspace coset states, which are uniform superpositions of vectors in a linear subspace of $\mathbb{F}_2^n$ to which has been applied a quantum one-time pad. This property was conjectured recently by [Coladangelo, Liu, Liu, and Zhandry, Crypto'21] and shown to have applications to unclonable decryption and copy-protection of pseudorandom functions. We present two proofs, one which directly follows the method of the original paper and the other which uses an observation from [Vidick and Zhang, Eurocrypt'20] to reduce the analysis to a simpler monogamy game based on BB'84 states. Both proofs ultimately rely on the same proof technique, introduced in [Tomamichel, Fehr, Kaniewski and Wehner, New Journal of Physics '13].

Featured image: A diagram representing the interactions in the strong monogamy game

Popular summary

Quantum entanglement allows for correlations between two non-communicating systems that are classically impossible, a property that may be quantified using Bell inequalities or nonlocal games. The situation gets more involved when there are more parties. For example, correlations as strong as maximal entanglement are not possible between three quantum systems. This is a particular case of monogamy-of-entanglement — limitations on the strength of quantum multipartite correlations. One way to quantify this property is via monogamy-of-entanglement (MoE) games. An MoE game is played cooperatively by two players Bob and Charlie, who each hold a quantum system but do not communicate, against a referee Alice, who has fixed actions. The players win if they can both simultaneously guess the result of Alice's measurement, chosen at random from a predetermined set of possible measurements, on a state they have prepared, each using their own local quantum system. Monogamy-of-entanglement appears in the fact that the maximal winning probability may be low while, using a maximally entangled state, either one of the players could have guessed the result with certainty.

In this work, we study the winning probability of an MoE game called the strong monogamy game. In this game, Alice measures her $n$-qubit system in a basis of subspace coset states, which is a basis that arises from a linear subspace of the finite vector space of $n$ bits. An important property of this basis is that it is naturally indexed by two indices, one corresponding to a coset of the subspace and the other to a coset of its orthogonal complement. To win the game, Bob is only required to guess the first index correctly and Charlie is only required to guess the second. Nevertheless, we show that the optimal winning probability is exponentially small in the number of qubits. The bound also holds for a version of the game where Alice sends subspace coset states rather than measuring in a basis; this version has applications to uncloneable quantum cryptography, where the no-cloning property of quantum states, closely related to MoE, is exploited to achieve classically impossible security.

► BibTeX data

@article{Culf2022monogamyof,
  doi = {10.22331/q-2022-09-01-791},
  url = {https://doi.org/10.22331/q-2022-09-01-791},
  title = {A monogamy-of-entanglement game for subspace coset states},
  author = {Culf, Eric and Vidick, Thomas},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {6},
  pages = {791},
  month = sep,
  year = {2022}
}

► References

[1] V. V. Albert, J. P. Covey, and J. Preskill. Robust encoding of a qubit in a molecule. Physical Review X, 10(3), 2020. DOI: 10.1103/physrevx.10.031050.
https://doi.org/10.1103/physrevx.10.031050

[2] A. Coladangelo, J. Liu, Q. Liu, and M. Zhandry. Hidden cosets and applications to unclonable cryptography. In T. Malkin and C. Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 556–584, Cham, 2021. Springer International Publishing. DOI: 10.1007/978-3-030-84242-0_20.
https://doi.org/10.1007/978-3-030-84242-0_20

[3] N. Johnston, R. Mittal, V. Russo, and J. Watrous. Extended non-local games and monogamy-of-entanglement games. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 472(2189): 20160003, 2016. DOI: 10.1098/rspa.2016.0003.
https://doi.org/10.1098/rspa.2016.0003

[4] M. Koashi. Unconditional security of quantum key distribution and the uncertainty principle. In Journal of Physics: Conference Series, volume 36, page 016. IOP Publishing, 2006. DOI: 10.1088/1742-6596/36/1/016.
https://doi.org/10.1088/1742-6596/36/1/016

[5] M. Tomamichel, S. Fehr, J. Kaniewski, and S. Wehner. A monogamy-of-entanglement game with applications to device-independent quantum cryptography. New Journal of Physics, 15(10): 103002, 2013. DOI: 10.1088/1367-2630/15/10/103002.
https://doi.org/10.1088/1367-2630/15/10/103002

[6] M. Tomamichel and A. Leverrier. A largely self-contained and complete security proof for quantum key distribution. Quantum, 1: 14, 2017. DOI: 10.22331/q-2017-07-14-14.
https://doi.org/10.22331/q-2017-07-14-14

[7] T. Vidick and T. Zhang. Classical proofs of quantum knowledge. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 630–660. Springer, 2021. DOI: 10.1007/978-3-030-77886-6_22.
https://doi.org/10.1007/978-3-030-77886-6_22

Cited by

[1] Fuyuki Kitagawa and Ryo Nishimaki, Lecture Notes in Computer Science 13794, 569 (2022) ISBN:978-3-031-22971-8.

[2] Shweta Agrawal, Fuyuki Kitagawa, Ryo Nishimaki, Shota Yamada, and Takashi Yamakawa, Lecture Notes in Computer Science 14004, 581 (2023) ISBN:978-3-031-30544-3.

[3] Jiahui Liu, Qipeng Liu, Luowen Qian, and Mark Zhandry, Lecture Notes in Computer Science 13747, 294 (2022) ISBN:978-3-031-22317-4.

[4] Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry, Lecture Notes in Computer Science 13508, 212 (2022) ISBN:978-3-031-15978-7.

[5] Andrea Coladangelo, Jiahui Liu, Qipeng Liu, and Mark Zhandry, "Hidden Cosets and Applications to Unclonable Cryptography", arXiv:2107.05692, (2021).

[6] Prabhanjan Ananth, Fatih Kaleoglu, and Qipeng Liu, "Cloning Games: A General Framework for Unclonable Primitives", arXiv:2302.01874, (2023).

[7] Anne Broadbent and Eric Culf, "Rigidity for Monogamy-of-Entanglement Games", arXiv:2111.08081, (2021).

[8] Prabhanjan Ananth, Fatih Kaleoglu, Xingjian Li, Qipeng Liu, and Mark Zhandry, "On the Feasibility of Unclonable Encryption, and More", arXiv:2207.06589, (2022).

[9] Anne Broadbent and Eric Culf, "Uncloneable Cryptographic Primitives with Interaction", arXiv:2303.00048, (2023).

[10] Fuyuki Kitagawa and Ryo Nishimaki, "Functional Encryption with Secure Key Leasing", arXiv:2209.13081, (2022).

[11] Or Sattath and Uriel Shinar, "Quantum Amnesia Leaves Cryptographic Mementos: A Note On Quantum Skepticism", arXiv:2212.08750, (2022).

The above citations are from Crossref's cited-by service (last updated successfully 2023-06-05 13:45:49) and SAO/NASA ADS (last updated successfully 2023-06-05 13:45:49). The list may be incomplete as not all publishers provide suitable and complete citation data.

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.