Abstract
In this work, we study rank-one quantum games. In particular, we focus on the study of the computability of the entangled value ω*. We show that the value ω* can be efficiently approximated up to a multiplicative factor of 4. We also study the behavior of ω* 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 ωqow. In particular, we show that ωqow can be computed efficiently and it satisfies a perfect parallel repetition theorem.
Original language | English (US) |
---|---|
Pages (from-to) | 133-196 |
Number of pages | 64 |
Journal | Computational Complexity |
Volume | 24 |
Issue number | 1 |
DOIs | |
State | Published - Mar 2015 |
Keywords
- Quantum games
- efficient approximation
- operator spaces
- parallel repetition
ASJC Scopus subject areas
- Theoretical Computer Science
- General Mathematics
- Computational Theory and Mathematics
- Computational Mathematics