Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision

DOI10.4230/LIPIcs.CCC.2019.25OpenAlexW2966029787MaRDI QIDQ5091777

Matthew Coudron, William Slofstra

Publication date: 27 July 2022

Full work available at URL: https://arxiv.org/abs/1905.11635

zbMATH Keywords

entanglementquantum complexity theorynon-local gamemulti-prover interactive proof

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (2)

Unnamed Item ⋮ 3XOR games with perfect commuting operator strategies have perfect tensor product strategies and are decidable in polynomial time

Cites Work

• Unnamed Item
• Unnamed Item
• Isoperimetric and isodiametric functions of groups
• Entanglement in non-local games and the hyperlinear profile of groups
• Perfect commuting-operator strategies for linear system games
• Proof verification and the hardness of approximation problems
• Interactive Proofs with Approximately Commuting Provers
• Probabilistic checking of proofs
• Compression of quantum multi-prover interactive proofs
• Characterization of Binary Constraint System Games
• Tsirelson’s problem and an embedding theorem for groups arising from non-local games
• Tsirelson's problem and asymptotically commuting unitary matrices

This page was built for publication: Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision