Entangled Games Are Hard to Approximate
From MaRDI portal
Publication:3093626
DOI10.1137/090751293zbMath1226.81048arXiv0704.2903WikidataQ56675303 ScholiaQ56675303MaRDI QIDQ3093626
Thomas Vidick, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Julia Kempe
Publication date: 18 October 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0704.2903
81P68: Quantum computation
91A06: (n)-person games, (n>2)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Heralded channel Holevo superadditivity bounds from entanglement monogamy, Spatial Isolation Implies Zero Knowledge Even in a Quantum World, Nonlocal Games with Noisy Maximally Entangled States are Decidable, Dimension Reduction for Polynomials over Gaussian Space and Applications, Tsirelson’s problem and an embedding theorem for groups arising from non-local games, Classical, quantum and nonsignalling resources in bipartite games, On symmetric nonlocal games, Unbounded violations of bipartite Bell inequalities via operator space theory, Large violation of Bell inequalities with low entanglement, Limitations of semidefinite programs for separable states and entangled games, Quantum games: a review of the history, current state, and interpretation, Parallelization of entanglement-resistant multi-prover interactive proofs, Geometry of information structures, strategic measures and associated stochastic control topologies, Rank-one quantum games, Quantum de Finetti theorems under local measurements with applications, Three-Player Entangled XOR Games are NP-Hard to Approximate, Grothendieck-Type Inequalities in Combinatorial Optimization