Unique Games with Entangled Provers Are Easy
From MaRDI portal
Publication:5390593
DOI10.1137/090772885zbMath1244.68040arXiv0710.0655MaRDI QIDQ5390593
Ben Toner, Oded Regev, Julia Kempe
Publication date: 4 April 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0710.0655
68Q25: Analysis of algorithms and problem complexity
90C22: Semidefinite programming
81P40: Quantum coherence, entanglement, quantum correlations
Related Items
Generalized XOR non-locality games with graph description on a square lattice, Anchored Parallel Repetition for Nonlocal Games, Nonlocal Games with Noisy Maximally Entangled States are Decidable, Linear game non-contextuality and Bell inequalities—a graph-theoretic approach, Explicit lower and upper bounds on the entangled value of multiplayer XOR games, Linear conic formulations for two-party correlations and values of nonlocal games, Unbounded violations of bipartite Bell inequalities via operator space theory, Large violation of Bell inequalities with low entanglement, Random constructions in Bell inequalities: a survey, Geometry of information structures, strategic measures and associated stochastic control topologies, Rank-one quantum games, Quantum de Finetti theorems under local measurements with applications, Survey on nonlocal games and operator space theory, SDP Relaxations for Non-Commutative Polynomial Optimization, Three-Player Entangled XOR Games are NP-Hard to Approximate, Quantum XOR Games, Quantum Bilinear Optimization, Interactive Proofs with Approximately Commuting Provers