Quantum XOR games
From MaRDI portal
Publication:2828211
DOI10.1145/2799560zbMATH Open1348.81177DBLPjournals/toct/RegevV15arXiv1207.4939OpenAlexW2232305496WikidataQ59792609 ScholiaQ59792609MaRDI QIDQ2828211FDOQ2828211
Authors: Thomas Vidick, Oded Regev 
Publication date: 24 October 2016
Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)
Abstract: We introduce quantum XOR games, a model of two-player one-round games that extends the model of XOR games by allowing the referee's questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a wide range of behaviors that are known not to exist for standard XOR games, such as cases in which the use of entanglement leads to an arbitrarily large advantage over the use of no entanglement. By invoking two deep extensions of Grothendieck's inequality, we present an efficient algorithm that gives a constant-factor approximation to the best performance players can obtain in a given game, both in case they have no shared entanglement and in case they share unlimited entanglement. As a byproduct of the algorithm we prove some additional interesting properties of quantum XOR games, such as the fact that sharing a maximally entangled state of arbitrary dimension gives only a small advantage over having no entanglement at all.
Full work available at URL: https://arxiv.org/abs/1207.4939
Recommendations
- Quantum games
- Quantum strategies for simple two-player XOR games
- Quantum Parrondo's games
- QUANTUM OCTAL GAMES
- scientific article; zbMATH DE number 2103535
- Quantum game simulation
- Algorithms, bounds, and strategies for entangled XOR games
- Nonlocal Quantum XOR Games for Large Number of Players
- Connes' embedding problem and winning strategies for quantum XOR games
- Classical versus quantum communication in XOR games
Applications of game theory (91A80) Quantum computation (81P68) Quantum coherence, entanglement, quantum correlations (81P40)
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Proposed experiment to test local hidden-variable theories
- Approximating the Cut-Norm via Grothendieck's Inequality
- Quantum analogues of the Bell inequalities. The case of two spatially separated domains
- Proof verification and the hardness of approximation problems
- Near-optimal and explicit Bell inequality violations
- Probabilistic checking of proofs
- Interactive proofs and the hardness of approximating cliques
- Grothendieck’s Theorem, past and present
- Some optimal inapproximability results
- Generalizing the Singular Value Decomposition
- Title not available (Why is that?)
- On the power of unique 2-prover 1-round games
- Non-deterministic exponential time has two-prover interactive protocols
- A new upper bound for the complex Grothendieck constant
- Grothendieck's theorem for operator spaces
- Lower bounds on the entanglement needed to play XOR non-local games
- Efficient rounding for the noncommutative Grothendieck inequality
- Unbounded violation of tripartite Bell inequalities
- Title not available (Why is that?)
- Explicit lower and upper bounds on the entangled value of multiplayer XOR games
- Unique games with entangled provers are easy
- The Grothendieck Constant is Strictly Smaller than Krivine's Bound
- Unbounded violations of bipartite Bell inequalities via operator space theory
- Large violation of Bell inequalities with low entanglement
- Towards a Generalized Singular Value Decomposition
- Title not available (Why is that?)
- A framework for bounding nonlocality of state discrimination
- Grothendieck's theorem for noncommutative \(C^*\)-algebras, with an appendix on Grothendieck's constants
- Comparison of quantum statistical models: Equivalent conditions for sufficiency
- The Grothendieck inequality for bilinear forms on \(C^*\)-algebras
- Elementary proofs of Grothendieck theorems for completely bounded norms
- The Effros-Ruan conjecture for bilinear forms on \(C^{*}\)-algebras
- Perfect parallel repetition theorem for quantum XOR proof systems
- Title not available (Why is that?)
- Constantes de Grothendieck et fonctions de type positif sur les sphères
- Title not available (Why is that?)
- On the Completely Bounded Map of a C* -Algebra to its Dual Space
- Title not available (Why is that?)
Cited In (23)
- Universal gaps for XOR games from estimates on tensor norm ratios
- Synchronicity for quantum non-local games
- Dimensionality distinguishers
- Unbounded entanglement can be needed to achieve the optimal success probability
- The Hilbertian tensor norm and entangled two-prover games
- Rank-one quantum games
- Lower bounds on the entanglement needed to play XOR non-local games
- 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- A lower bound on the value of entangled binary games
- Failure of the trilinear operator space Grothendieck theorem
- The quantum-to-classical graph homomorphism game
- Synchronous values of games
- On the relation between completely bounded and \((1,{cb})\)-summing maps with applications to quantum XOR games
- On the power of quantum entanglement in multipartite quantum XOR games
- Geometry of Banach spaces: a new route towards position based cryptography
- Quantum strategies are better than classical in almost any XOR game
- Quantum strategies for simple two-player XOR games
- Hadamard's matrices, Grothendieck's constant, and root two
- The set of quantum correlations is not closed
- Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting)
- Connes' embedding problem and winning strategies for quantum XOR games
- Extended non-local games and monogamy-of-entanglement games
This page was built for publication: Quantum XOR games
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2828211)
