Entangled games do not require much entanglement (withdrawn)
arXiv:0908.3491
Abstract
We prove an explicit upper bound on the amount of entanglement required by any strategy in a two-player cooperative game with classical questions and quantum answers. Specifically, we show that every strategy for a game with n-bit questions and n-qubit answers can be implemented exactly by players who share an entangled state of no more than 5n qubits--a bound which is optimal to within a factor of 5/2. Previously, no upper bound at all was known on the amount of entanglement required even to approximate such a strategy. It follows that the problem of computing the value of these games is in NP, whereas previously this problem was not known to be computable.
Withdrawn. I found a mistake in my proof. This one-page replacement note explains the problem in more detail. Sorry, everyone
References in corpus (5)
- A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
- A lower bound on the dimension of a quantum system given measured data
- Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems
- Two-message quantum interactive proofs are in PSPACE
- Quantum Multi Prover Interactive Proofs with Communicating Provers