Parallel repetition of entangled games
From MaRDI portal
Abstract: We consider one-round games between a classical referee and two players. One of the main questions in this area is the parallel repetition question: Is there a way to decrease the maximum winning probability of a game without increasing the number of rounds or the number of players? Classically, efforts to resolve this question, open for many years, have culminated in Raz's celebrated parallel repetition theorem on one hand, and in efficient product testers for PCPs on the other. In the case where players share entanglement, the only previously known results are for special cases of games, and are based on techniques that seem inherently limited. Here we show for the first time that the maximum success probability of entangled games can be reduced through parallel repetition, provided it was not initially 1. Our proof is inspired by a seminal result of Feige and Kilian in the context of classical two-prover one-round interactive proofs. One of the main components in our proof is an orthogonalization lemma for operators, which might be of independent interest.
Recommendations
- A parallel repetition theorem for all entangled games
- A parallel repetition theorem for entangled projection games
- Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
- scientific article; zbMATH DE number 6829293
- Quantum repeated games
- Quantum repeated games revisited
- Anchored parallel repetition for nonlocal games
- Games of entangled agents
- Parallel Repetition for the GHZ Game: A Simpler Proof.
- Cooperative quantum Parrondo's games
Cited in
(22)- Unique games with entangled provers are easy
- Parallel repetition and concentration for (sub-)no-signalling games via a flexible constrained de Finetti reduction
- scientific article; zbMATH DE number 6829293 (Why is no real title available?)
- Spatial Isolation Implies Zero Knowledge Even in a Quantum World
- The Hilbertian tensor norm and entangled two-prover games
- Parallel repetition of two-prover one-round games: an exposition
- scientific article; zbMATH DE number 7250160 (Why is no real title available?)
- Rank-one quantum games
- Entangled games are hard to approximate
- Information value of two-prover games
- A parallel repetition theorem for all entangled games
- A parallel repetition theorem for entangled projection games
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Anchored parallel repetition for nonlocal games
- Almost synchronous quantum correlations
- Parallel Repetition of the Odd Cycle Game
- Three-player entangled XOR games are NP-hard to approximate
- Parallel repetition via fortification: analytic view and the quantum case
- A monogamy-of-entanglement game with applications to device-independent quantum cryptography
- Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost
- Orthogonalization of positive operator valued measures
- Parallel repetition: simplification and the no-signaling case
This page was built for publication: Parallel repetition of entangled games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419105)
