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 optimizationefficient approximationmodels for rank one gameoperator spacesparallel repetitionquantum gamesquantum informations

Mathematics Subject Classification ID

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

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.

Review text

The study of two-players one round games is a central topic in both theoretical computer science and quantum information theory (QIT). In theoretical computer science, they play a key role in analyzing the complexity of approximating some combinatorial optimization problems. As for quantum information theory, two-player one-round games are a natural setting in which to understand Bell inequalities. Quantum games are those in which the communication between the referee and players (the questions and answers) is transmitted using quantum states. A subclass of quantum games called rank-one quantum games. In this paper, the authors deal with one rank-one quantum games in which the projective measurements of the referee is defined by a rank-one projection. The authors introduce some examples of rank-one quantum games that have some interesting properties. They introduce also an approach to study those games via operator spaces. Operator space theory can be understood as a non-commutative version of Banach space theory and has been shown to be a natural mathematical tool in quantum information theory. There is a section devoted to the basic definitions and results from this theory (Section 2). The paper is well organized; in Section 1 we find summary of results, in Section 2 one finds operator spaces and in Section 3 we find the connections of rank-one quantum games to operator spaces. In Section 4 we find three different models of the entangled value of the game. The authors in Section 5 give computing and approximating the different values of rank-one games. In Section 6 the authors study the behavior of the different values of a rank-one quantum game with respect to the perfect parallel repetition theorem. Two families of games from operator space theory are given in Section 7.

Recommendations

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

Cites work

• A Parallel Repetition Theorem
• Completely bounded and ideal norms of multiplication operators and Schur multipliers
• Completely Bounded Maps between C^∗ -Algebras
• 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
• 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?)
• 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
• 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
• PSPACE has constant-round quantum interactive proof systems
• Quantum computations: algorithms and error correction
• Quantum multi-prover interactive proof systems with limited prior entanglement.
• Quantum multiprover interactive proofs with communicating provers
• Quantum XOR games
• 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

(11)

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

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)