Restricted decidability of nonlocal games
Identify natural restricted families of finite nonlocal games whose finite-dimensional tensor-product value admits two-sided additive approximation with a certified stopping rule; separately determine efficient algorithms and finite-level NPA certificates.
Problem statement
Identify natural restricted families of finite nonlocal games whose finite-dimensional tensor-product value admits two-sided additive approximation with a certified stopping rule; separately determine efficient algorithms and finite-level NPA certificates.
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
For a finitely specified game, the quantum value is a supremum over finite-dimensional tensor-product strategies. MIP*=RE rules out a general algorithm approximating this value to prescribed accuracy. Enumerating finite-dimensional strategies already supplies lower semicomputability; this is weaker than a two-sided computable value or a terminating threshold decision.
XOR games have an SDP characterization. The Navascués–Pironio–Acín hierarchy supplies decreasing upper bounds converging to the commuting-operator value, which need not equal the tensor-product value. Restricted symmetries, game algebras, input/output patterns and noisy-resource assumptions can yield tractable islands, including computable bounds in the Qin–Yao setting.
Preprint progress (July 2026): Pakhunov's two manuscripts claim nonexactness of any fixed NPA level throughout suitable neighborhoods of the doubly-tilted CHSH critical point, with a finite-certification phase boundary. Chaturvedi claims that no finite standard NPA level equals the entire quantum set in the two-input/two-output scenario. These are statements about fixed levels and sets or neighborhoods. They do not mean every individual inequality lacks a finite certificate, or that values in this small scenario are uncomputable.
N9's former generic solver request is archived here; dimensional aspects are treated in N5. The active target is a precisely described restricted family with a certified algorithm, not a universal solver.
Progress & source assessment
Source catalogue review: 4 September 2026. Improved indicates partial progress, including qualified preprint claims.
preprint: Nonexactness of fixed NPA levels near a critical doubly-tilted CHSH point, not universal noncomputability in the smallest Bell scenario. Evidence
preprint: No finite standard NPA level describes the complete (2,2,2) behavior set; particular functionals can still have finite certificates. Evidence
- [1]Ji et al., 'MIP*=RE' link
- [2]Qin & Yao, 'Decidability of fully quantum nonlocal games with noisy maximally entangled states' (2023 revision) link
- [3]Cleve, Høyer, Toner, Watrous, 'Consequences and limits of nonlocal strategies', CCC 2004 link
- [4]Pakhunov, 'No finite level of the NPA hierarchy is exact for the doubly-tilted CHSH functional near the critical tilt' (2026 preprint) link
- [5]Pakhunov, 'A phase transition in the exactness of the NPA hierarchy at the critical doubly-tilted CHSH functional' (2026 preprint) link
- [6]Chaturvedi, 'No Finite NPA Level Characterizes the Complete Quantum Set in the Simplest Bell Scenario' (2026 preprint) link
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.
No machine attempts recorded.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.
No notes yet.
Sign in to add a note.