Perfect play with spatial quantum strategies is Σ⁰₂-complete
In plain wordsNo computer can tell from a finite win-or-lose game’s rules whether two players sharing an entangled state of two possibly infinite quantum systems can win it every time, not even a computer that could solve the halting problem; with earlier results, each of four ways of asking for certainty in such games now has its exact level of difficulty.
The result
As the paper states it, in briefDeciding whether a finite nonlocal game admits perfect spatial quantum play is complete for the second existential level of the arithmetical hierarchy, Σ⁰₂; the same classification holds when a perfect strategy must have finite marginal entropy, and hardness persists among games whose finite-dimensional value is one and which have no finite-dimensional perfect strategy. Exact attainment of a rational Bell bound, of an unspecified supremum, and of a specified scalar value is also Σ⁰₂-complete.
How this was checked
- Audits
- An audit of the final manuscript
- Fix-checks
- A targeted check of the fixes.
- Verification
- The derivations of the upper bound, compiler, rooted computation, clock, reduction, value-one argument and Bell attainment checked by a model from another developer
- Independent computation
- Exact finite checks, among them 2,000 operator checks by a separate implementation and a compiled game with 27,991 questions per party
- Lean
- None.
- Peer review
- Not yet.
Every check here is internal. How we check results.
Label checked .
Novelty and credit
- Novelty
- New, with named prior work. To our knowledge, the first -completeness classifications of these spatial attainment problems; the paper calls this priority statement provisional. The other entries of its table are due to Ji, Natarajan, Vidick, Wright and Yuen (finite-dimensional perfection, ), Slofstra, with the account of Mousavi, Nezhadi and Yuen (commuting perfection, ), and Mousavi, Nezhadi and Yuen (value one, ). The bridge geometry is Mančinska’s flagged magic-square construction, and the toolkit extends the authors’ entropy-game paper.
Versionsone, each with its own DOI
| Version | Date | DOI | Notes |
|---|---|---|---|
| 1.0.0 | 10.5281/zenodo.23910987 | PDF hosted here. |
Paper, code and links
papers/spatial-perfection-v1.0.0.pdf, version 1.0.0, 674,490 bytes, 31 pages.SHA-256 4a126ac0b0e2f9ea8dce28f864ac77cb5e15c399e7f0e6718cc51750abbe6c0b
- DOI
10.5281/zenodo.23910987; all versions 10.5281/zenodo.23910986
Corrections
None so far.
All corrections, and what counts as one.
Cite
@misc{douglas2026spatialperfection,
author = {Douglas, Seth and Mghirbi, Nidhal},
title = {Perfect play with spatial quantum strategies is $\Sigma^0_2$-complete},
year = {2026},
version = {1.0.0},
doi = {10.5281/zenodo.23910987},
url = {https://doi.org/10.5281/zenodo.23910987}
}