We study monogamy of entanglement, a fundamental constraint on how entanglement can be distributed across multipartite systems, through the framework of extended nonlocal quantum games. We analyze and compare three classes of strategies and their success probabilities: classical, quantum, and non-signaling. Our results demonstrate how the values of these strategies change in higher-dimensional games as well as with multiple repetitions. In particular, we demonstrate that the ratio between the non-signaling and quantum value can be made arbitrarily large with sufficient game repetitions. These games are subsequently incorporated into one-sided device-independent quantum key distribution protocols, with specific parameters such as key rate clearly defined. Finally, a simulation of a monogamy of entanglement game using IBM's Quantum Information Software Kit demonstrates monogamy of entanglement on real quantum hardware.
In this work, we consider "decision" variants of a monogamy-of-entanglement game by Tomamichel, Fehr, Kaniewski, and Wehner [New Journal of Physics '13]. In its original "search" variant, Alice prepares a (possibly entangled) state on registers
ABC; register
A, consisting of
n qubits, is sent to a Referee, while
B and
C are sent to Bob and Charlie; the Referee then measures each qubit in the standard or Hadamard basis (chosen uniformly at random). The basis choices are sent to Bob and Charlie, whose goal is to simultaneously guess the Referee's
n-bit outcome string
x. Tomamichel et al. show that the optimal winning probability is
cos2n(8π), following a perfect parallel repetition theorem. We consider the following "decision" variants of this game: - Variant 1, "XOR repetition": Bob and Charlie's goal is to guess the XOR of all the bits of
x. Ananth et al. [Asiacrypt '24] conjectured that the optimal advantage over random guessing decays exponentially in
n. Surprisingly, we show that this conjecture is false, and, in fact, there is no decay at all: there exists a strategy that wins with probability
cos2(8π)≈0.85 for any
n. - Variant 2, "Goldreich-Levin": The Referee additionally samples a uniformly random
n-bit string
r that is sent to Bob and Charlie along with the basis choices. Their goal is to guess the parity of
r⋅x. We show that the optimal advantage over random guessing decays exponentially in
n for the restricted class of adversaries that do not share entanglement. A similar result was already shown by Champion et al. and Çakan et al.; we give a more direct proof. Additionally, we put forward a reasonably concrete conjecture that is equivalent to exponential decay for general adversaries.
Abstract This paper considers the decidability of fully quantum nonlocal games with noisy maximally entangled states. Fully quantum nonlocal games are a generalization of nonlocal games, where both questions and answers are quantum and the referee performs a binary POVM measurement to decide whether they win the game after receiving the quantum answers from the players. The quantum value of a fully quantum nonlocal game is the supremum of the probability that they win the game, where the supremum is taken over all the possible entangled states shared between the players and all the valid quantum operations performed by the players. The seminal work
MIP∗=RE~\cite{JNVWY'20,JNVWYuen'20} implies that it is undecidable to approximate the quantum value of a fully nonlocal game. This still holds even if the players are only allowed to share (arbitrarily many copies of) maximally entangled states. This paper investigates the case that the shared maximally entangled states are noisy. We prove that there is a computable upper bound on the copies of noisy maximally entangled states for the players to win a fully quantum nonlocal game with a probability arbitrarily close to the quantum value. This implies that it is decidable to approximate the quantum values of these games. Hence, the hardness of approximating the quantum value of a fully quantum nonlocal game is not robust against the noise in the shared states. This paper is built on the framework for the decidability of non-interactive simulations of joint distributions~\cite{7782969,doi:10.1137/1.9781611975031.174,Ghazi:2018:DRP:3235586.3235614} and generalizes the analogous result for nonlocal games in~\cite{qin2021nonlocal}. We extend the theory of Fourier analysis to the space of super-operators and prove several key results including an invariance principle and a dimension reduction for super-operators. These results are interesting in their own right and are believed to have further applications.
Abstract In a variant of communication tasks, players cooperate in choosing their local strategies to compute a given task later, working separately. Utilizing quantum bits for communication and sharing entanglement between parties is a recognized method to enhance performance in these situations. In this work, we introduce the game for which three parties, Alice, Bob and Charlie, would like to discover the hidden order in which they make the moves. We show the advantage of quantum strategies that use shared entanglement and local operations over classical setups for discriminating operations’ composition order. The role of quantum resources improving the probability of successful discrimination is also investigated. Our research provides a basis for examining computational model featuring a specific gate set while examining the diverse operations achievable through permutations of its elements.
By leveraging the no-cloning principle of quantum mechanics, unclonable cryptography enables us to achieve novel cryptographic protocols that are otherwise impossible classically. Two most notable examples of unclonable cryptography are quantum copy-protection and unclonable encryption. Most known constructions rely on the quantum random oracle model (as opposed to the plain model), in which all parties have access in superposition to a powerful random oracle. Despite receiving a lot of attention in recent years, two important open questions still remain: copy-protection of point functions in the plain model, which is usually considered as feasibility demonstration, and unclonable encryption with unclonable indistinguishability security in the plain model. A core ingredient of these protocols is the so-called monogamy-of-entanglement property. Such games allow quantifying the correlations between the outcomes of multiple non-communicating parties sharing entanglement in a particular context. Specifically, we define the games between a challenger and three players in which the first player is asked to split and share a quantum state between the two others, who are then simultaneously asked a question and need to output the correct answer. In this work, by relying on previous works of Coladangelo, Liu, Liu, and Zhandry (Crypto'21) and Culf and Vidick (Quantum'22), we establish a new monogamy-of-entanglement property for subspace coset states, which allows us to progress towards the aforementioned goals. However, it is not sufficient on its own, and we present two conjectures that would allow first to show that copy-protection of point functions exists in the plain model, with different challenge distributions (including arguably the most natural ones), and then that unclonable encryption with unclonable indistinguishability security exists in the plain model. We believe that our new monogamy-of-entanglement to be of independent interest, and it could be useful in other applications as well. To highlight this last point, we leverage our new monogamy-of-entanglement property to show the existence of a tokenized signature scheme with a new security definition, called unclonable unforgeability.
In a recently introduced coset guessing game, Alice plays against Bob and Charlie, aiming to meet a joint winning condition. Bob and Charlie can only communicate before the game starts to devise a joint strategy. The game we consider begins with Alice preparing a 2m-qubit quantum state based on a random selection of three parameters. She sends the first m qubits to Bob and the rest to Charlie, and then reveals to them her choice for one of the parameters. Bob is supposed to guess one of the hidden parameters, Charlie the other, and they win if both guesses are correct. From previous work, we know that the probability of Bob’s and Charlie’s guesses being simultaneously correct goes to zero exponentially as m increases. We derive a tight upper bound on this probability and show how Bob and Charlie can achieve it. While developing an optimal strategy, we devised an encoding circuit using only and Hadamard gates, which builds CSS codes from EPR pairs using only local operations. We found that the role of quantum information that Alice communicates to Bob and Charlie is to make their responses correlated rather than improve their individual (marginal) correct guessing rates.