Perfect quantum play hides a second quantifier

Can the players win every time?

In a nonlocal game, a referee sends questions to two separated players, who answer according to a fixed rule. The players may share entanglement, and the referee awards a win or loss. A natural question is whether they can win with certainty. But “the best possible score is one” does not always mean that any strategy actually reaches one: a sequence of strategies might get closer and closer without ever being perfect.

In their November 2026 preprint, Seth Douglas and Nidhal Mghirbi study the decision problem for finite games with rational rules. Their central result is that perfect play depends not just on the game but on which mathematical model is allowed to represent the players’ shared quantum resources.

Three models, three levels of difficulty

The paper compares finite-dimensional strategies, normal spatial strategies, and commuting-operator strategies. In the first, the players’ systems have finite dimensions. A spatial strategy allows a normal state on an infinite-dimensional tensor product; “normal” here means that the state can be represented by a trace-class density operator. In the commuting model, both players’ measurements act on one space and commute with each other.

To describe the decision difficulty, the authors use the arithmetical hierarchy, which classifies questions by the number and order of searches over natural numbers and algorithmic checks. The finite-dimensional perfect-play problem is Σ₁⁰-complete: it can be framed as searching for a finite-dimensional strategy. Commuting perfect play is Π₁⁰-complete, a universal sequence of checks. By contrast, perfect normal spatial play is Σ₂⁰-complete. In plain terms, it has the form “there exists an integer such that every one of infinitely many finite tests succeeds.” Completeness means not only that this form describes the problem, but that every problem of the same class can be translated into it.

The result holds even for a restricted family of games whose value is one—the supremum of attainable winning probabilities is already one—while no perfect finite-dimensional strategy exists in that family. Spatial perfection, which is strictly between the other two models in the sets of correlations they allow, is therefore harder to decide than perfect play in either model. This is a statement about the worst-case computability of a precisely encoded mathematical problem, not a practical running-time estimate for a particular game.

Why does a trace add a quantifier?

The paper’s title points to a technical resource: a trace, which assigns a finite size to suitable parts of an operator algebra. The upper-bound argument for spatial play isolates a nonzero Schmidt coefficient—the weight of one paired component in the players’ shared state—and asks whether some integer can bound its inverse. For any fixed bound, the remaining question becomes an infinite sequence of finite tests. Searching over the bound adds the existential number quantifier.

The hardness construction makes that integer meaningful. Depending on the model, a perfect strategy must choose a finite period for a mathematical clock or a finite depth for a branching tree, then satisfy every check attached to that choice. A trace supplies a finite corner that can witness nonzero overlap; without that finite witness, the authors show a different complexity pattern. In the fixed type-III commuting submodels, perfect play has the same Π₁⁰-complete language as unrestricted commuting play. Finite and semifinite hosts instead yield Σ₂⁰-complete problems. These are existence results: the host algebra and normal state may be chosen as part of the strategy.

Beyond certainty in games

The preprint also finds Σ₂⁰-completeness when spatial perfect strategies are required to have finite entanglement entropy, or—under each fixed computable exponent between zero and one—a finite spectral moment of the reduced state. These resource conditions form a strict ladder between finite rank and finite entropy. The authors extend the complexity result to one-shot zero-error communication with normal entanglement: a sender uses a finite classical channel once and must transmit one of a specified number of messages without error.

These results concern exact attainment and resource-constrained existence, not whether a noisy experiment can distinguish two scores, nor the typical difficulty of games used in laboratories. The classifications range over all finite scenarios rather than fixing the numbers of questions and answers. The paper also distinguishes a game’s value, a supremum, from a perfect strategy that attains it; conflating the two would change the decision problem. It is a mathematical preprint, and its classifications should be read within those formal definitions. The authors report formal verification in Lean for the spatial completeness results.