Rank-one quantum games

DOI10.1007/S00037-014-0096-XMaRDI QIDQ2353189zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Marius Junge, Carlos Palazuelos, David Pérez-García, Tom Cooney

Publication date 8 July 2015

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.3563, http://eprints.ucm.es/30050/7/PerezGarcia107-1.pdf

zbMATH Keywords

combinatorial optimizationquantum gamesoperator spacesparallel repetitionefficient approximationmodels for rank one gamequantum informations

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Operator spaces (= matricially normed spaces) (47L25) Quantum coherence, entanglement, quantum correlations (81P40) Quantum information, communication, networks (quantum-theoretic aspects) (81P45)

Abstract: In this work we study rank-one quantum games. In particular, we focus on the study of the computability of the entangled value $omeg{a}^{\ast }$. We show that the value $omeg{a}^{\ast }$ can be efficiently approximated up to a multiplicative factor of 4. We also study the behavior of $omeg{a}^{\ast }$ under the parallel repetition of rank-one quantum games, showing that it does not verify a perfect parallel repetition theorem. To obtain these results, we first connect rank-one games with the mathematical theory of operator spaces. We also reprove with these new tools essentially known results about the entangled value of rank-one games with one-way communication $omeg{a}_{qow}$. In particular, we show that $omeg{a}_{qow}$ can be computed efficiently and it satisfies a perfect parallel repetition theorem.

Recommendations

• Quantum XOR games
• Towards a general theory of quantum games
• Survey on nonlocal games and operator space theory
• scientific article
• QUANTUM OCTAL GAMES

Cites work

• scientific article; zbMATH DE number 1216173 (Why is no real title available?)
• scientific article; zbMATH DE number 1993745 (Why is no real title available?)
• scientific article; zbMATH DE number 1849957 (Why is no real title available?)
• scientific article; zbMATH DE number 6292749 (Why is no real title available?)
• A Parallel Repetition Theorem
• Completely Bounded Maps between C^∗ -Algebras
• Completely bounded and ideal norms of multiplication operators and Schur multipliers
• Computing stabilized norms for quantum operations via the theory of completely bounded maps
• Connes' embedding problem and Tsirelson's problem
• Elementary proofs of Grothendieck theorems for completely bounded norms
• Embedding of the operator space OH and the logarithmic `little Grothendieck inequality'
• Entangled games are hard to approximate
• Facial structure of the trace class
• Geometric algorithms and combinatorial optimization.
• Grothendieck's theorem for operator spaces
• Grothendieck’s Theorem, past and present
• Large violation of Bell inequalities with low entanglement
• Minimal and maximal operator spaces and operator systems in entanglement theory
• Multiplicativity of completely bounded p-norms implies a new additivity result
• On the best constants in noncommutative Khintchine-type inequalities
• On the power of quantum, one round, two prover interactive proof systems
• PSPACE has constant-round quantum interactive proof systems
• Parallel repetition of entangled games
• Parallelization, amplification, and exponential time simulation of quantum interactive proof systems
• Perfect parallel repetition theorem for quantum XOR proof systems
• Pointwise domination of matrices and comparison of \(F_ p\) norms
• Position-based quantum cryptography: impossibility and constructions
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Quantum XOR games
• Quantum computations: algorithms and error correction
• Quantum multi-prover interactive proof systems with limited prior entanglement.
• Quantum multiprover interactive proofs with communicating provers
• Representation of certain homogeneous Hilbertian operator spaces and applications
• Semidefinite programs for completely bounded norms
• The Effros-Ruan conjecture for bilinear forms on \(C^{*}\)-algebras
• The Grothendieck-Pietsch and Dvoretzky-Rogers theorems for operator spaces
• Three-player entangled XOR games are NP-hard to approximate
• Unbounded violation of tripartite Bell inequalities
• Unbounded violations of bipartite Bell inequalities via operator space theory
• Unique games with entangled provers are easy

Cited in

(10)

• Quantum no-signalling correlations and non-local games
• Synchronicity for quantum non-local games
• Complexity limitations on one-turn quantum refereed games
• A lower bound on the value of entangled binary games
• Failure of the trilinear operator space Grothendieck theorem
• Extended nonlocal games from quantum-classical games
• On the relation between completely bounded and \((1,{cb})\)-summing maps with applications to quantum XOR games
• Explicit lower and upper bounds on the entangled value of multiplayer XOR games
• Survey on nonlocal games and operator space theory
• The connected wedge theorem and its consequences

This page was built for publication: Rank-one quantum games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2353189)