2009/08/24 by Gus Gutoski, Gutoski, Gus
Computer Science · Physics and Astronomy · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Physics (quant-ph) #cs.CC #quant-ph
paper · pdf · doi:10.48550/arxiv.0908.3491
Withdrawn. I found a mistake in my proof. This one-page replacement note explains the problem in more detail. Sorry, everyone
openalex publication_date 2009/08/24 · arxiv created 2009/09/03 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.