The NPA hierarchy does not always attain the commuting operator value

2025/10/06 by Marco Fanizza, Fanizza, Marco, Larissa Kroell +11 · 2 citations
Computer Science · #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2510.04943

openalex publication_date 2025/10/06 · openalex created_date 2025/10/09 · openalex updated_date 2026/07/28

Abstract

We show that it is undecidable to determine whether the commuting operator value of a nonlocal game is strictly greater than 1/2. Specifically, there is a computable mapping from Turing machines to /boolean constraint system (BCS) nonlocal games in which the halting property of the machine is encoded as a decision problem for the commuting operator value of the game. As a corollary, there is a BCS game for which the value of the Navascués-Pironio-Acín (NPA) hierarchy does not attain the commuting operator value at any finite level.

Citations

• Quantitative Quantum Soundness for Bipartite Compiled Bell Games via the Sequential NPA Hierarchy
• Robust self-testing for nonlocal games with robust game algebras
• RE-completeness of entangled constraint satisfaction problems
• Self-testing in the compiled setting via tilted-CHSH inequalities
• A Computational Tsirelson's Theorem for the Value of Compiled XOR Games
• Positivity is undecidable in tensor products of free algebras
• Satisfiability problems and algebras of boolean constraint system games
• Almost synchronous correlations and Tomita-Takesaki theory
• Bounding the quantum value of compiled nonlocal games: from CHSH to BQP verification
• Quantum Advantage from Any Non-Local Game
• Rounding near-optimal quantum strategies for nonlocal games to strategies using maximally entangled states
• Synchronous Values of Games
• On the complexity of zero gap MIP*
• Quantum proof systems for iterated exponential time, and beyond
• Generalized Satisfiability Problems via Operator Assignments
• The set of quantum correlations is not closed
• Algebras, Synchronous Games and Chromatic Numbers of Graphs
• Compression of Quantum Multi-Prover Interactive Proofs
• Classical Verification of Quantum Proofs
• Algorithms in Real Algebraic Geometry: A Survey
• Binary Constraint System Games and Locally Commutative Reductions
• Three-player entangled XOR games are NP-hard to approximate
• Characterization of Binary Constraint System Games
• A multi-prover interactive proof for NEXP sound against entangled provers
• Oracularization and Two-Prover One-Round Interactive Proofs against Nonlocal Strategies
• Semidefinite programming relaxations for semialgebraic problems

Cited by

• On the undecidability of quantum channel capacities
• Fejér--Riesz factorization for positive noncommutative trigonometric polynomials

Related

• Characterization of Binary Constraint System Games
• Complexity lower bounds for computing the approximately-commuting operator value of non-local games to high precision
• Binary Constraint System Games and Locally Commutative Reductions
• Topics in Non-local Games: Synchronous Algebras, Algebraic Graph Identities, and Quantum NP-hardness Reductions
• Weihrauch degrees of finding equilibria in sequential games