Unique Games with Entangled Provers Are Easy

DOI10.1137/090772885zbMath1244.68040arXiv0710.0655OpenAlexW2105098759MaRDI 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

zbMATH Keywords

semidefinite programmingquantum entanglementparallel repetitiontwo-prover one-round games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Quantum coherence, entanglement, quantum correlations (81P40)

Related Items (18)

Quantum de Finetti theorems under local measurements with applications ⋮ Interactive Proofs with Approximately Commuting Provers ⋮ Generalized XOR non-locality games with graph description on a square lattice ⋮ Quantum Bilinear Optimization ⋮ Anchored Parallel Repetition for Nonlocal Games ⋮ Explicit lower and upper bounds on the entangled value of multiplayer XOR games ⋮ Geometry of information structures, strategic measures and associated stochastic control topologies ⋮ Unbounded violations of bipartite Bell inequalities via operator space theory ⋮ Nonlocal Games with Noisy Maximally Entangled States are Decidable ⋮ Random constructions in Bell inequalities: a survey ⋮ Linear conic formulations for two-party correlations and values of nonlocal games ⋮ Large violation of Bell inequalities with low entanglement ⋮ 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 ⋮ Linear game non-contextuality and Bell inequalities—a graph-theoretic approach ⋮ Rank-one quantum games

This page was built for publication: Unique Games with Entangled Provers Are Easy