Entangled games are hard to approximate
From MaRDI portal
Abstract: We establish the first hardness results for the problem of computing the value of one-round games played by a verifier and a team of provers who can share quantum entanglement. In particular, we show that it is NP-hard to approximate within an inverse polynomial the value of a one-round game with (i) quantum verifier and two entangled provers or (ii) classical verifier and three entangled provers. Previously it was not even known if computing the value exactly is NP-hard. We also describe a mathematical conjecture, which, if true, would imply hardness of approximation to within a constant. We start our proof by describing two ways to modify classical multi-prover games to make them resistant to entangled provers. We then show that a strategy for the modified game that uses entanglement can be ``rounded to one that does not. The results then follow from classical inapproximability bounds. Our work implies that, unless P=NP, the values of entangled-prover games cannot be computed by semidefinite programs that are polynomial in the size of the verifier's system, a method that has been successful for more restricted quantum games.
Recommendations
Cited in
(32)- On symmetric nonlocal games
- Shannon-like games are difficult
- Quantum de Finetti theorems under local measurements with applications
- Unique games with entangled provers are easy
- Semi-definite programming and quantum information
- Parallelization of entanglement-resistant multi-prover interactive proofs
- Quantum advantage and CSP complexity
- Limitations of semidefinite programs for separable states and entangled games
- Quantum interactive proofs using quantum energy teleportation
- Spatial Isolation Implies Zero Knowledge Even in a Quantum World
- Dimension Reduction for Polynomials over Gaussian Space and Applications
- scientific article; zbMATH DE number 7250160 (Why is no real title available?)
- Compression of quantum multi-prover interactive proofs
- Quantum games: a review of the history, current state, and interpretation
- Rank-one quantum games
- A lower bound on the value of entangled binary games
- Tsirelson's problem and an embedding theorem for groups arising from non-local games
- Hardness amplification for entangled games via anchoring
- Grothendieck-type inequalities in combinatorial optimization
- Characterization of binary constraint system games
- Erratum to: ``Three-player entangled XOR games are NP-hard to approximate
- Classical, quantum and nonsignalling resources in bipartite games
- Geometry of information structures, strategic measures and associated stochastic control topologies
- Quantum advantage and CSP complexity
- The computational advantage of MIP* vanishes in the presence of noise
- The computational advantage of MIP* vanishes in the presence of noise
- Interactive proofs with approximately commuting provers
- Three-player entangled XOR games are NP-hard to approximate
- Unbounded violations of bipartite Bell inequalities via operator space theory
- Large violation of Bell inequalities with low entanglement
- Heralded channel Holevo superadditivity bounds from entanglement monogamy
- Nonlocal Games with Noisy Maximally Entangled States are Decidable
This page was built for publication: Entangled games are hard to approximate
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3093626)
