Entangled Games Are Hard to Approximate

DOI10.1137/090751293zbMath1226.81048arXiv0704.2903OpenAlexW1997685871WikidataQ56675303 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

zbMATH Keywords

entanglementquantum computinginteractive proofsalmost-commuting matrices

Mathematics Subject Classification ID

Quantum computation (81P68) (n)-person games, (n>2) (91A06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (17)

Quantum de Finetti theorems under local measurements with applications ⋮ Grothendieck-Type Inequalities in Combinatorial Optimization ⋮ Spatial Isolation Implies Zero Knowledge Even in a Quantum World ⋮ Geometry of information structures, strategic measures and associated stochastic control topologies ⋮ Heralded channel Holevo superadditivity bounds from entanglement monogamy ⋮ Unbounded violations of bipartite Bell inequalities via operator space theory ⋮ Classical, quantum and nonsignalling resources in bipartite games ⋮ On symmetric nonlocal games ⋮ Nonlocal Games with Noisy Maximally Entangled States are Decidable ⋮ 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 ⋮ Large violation of Bell inequalities with low entanglement ⋮ Dimension Reduction for Polynomials over Gaussian Space and Applications ⋮ Tsirelson’s problem and an embedding theorem for groups arising from non-local games ⋮ Three-Player Entangled XOR Games are NP-Hard to Approximate ⋮ Rank-one quantum games

This page was built for publication: Entangled Games Are Hard to Approximate