When does a finite nonlocal game admit perfect spatial quantum play? We prove that this decision problem is complete for the second existential level of the arithmetical hierarchy. The same classification holds when a perfect strategy must have finite marginal entropy. Hardness persists among games whose finite-dimensional value is one and which have no finite-dimensional perfect strategy. A finite clock-phase order supplies the existential witness: normality forces a finite order on a nonzero sector, while the strategy chooses the order. For the upper bound, we normalize the largest Schmidt coefficient and use compact operator sandwiches. Fixing a lower bound on the largest Schmidt probability gives a co-recursively enumerable stratum. No computable bound selects a sufficient stratum for every game. Exact attainment of a rational Bell bound, of an unspecified supremum, and of a specified scalar value is also Sigma^0_2-complete. The hardness proof extends the modular-shift and rational-row toolkit of our earlier entropy-game paper to four calibrated bridges and a deterministic computation on rooted finite squares.
When does a finite nonlocal game admit perfect spatial quantum play? We prove that this decision problem is complete for the second existential level of the arithmetical hierarchy. The same classification holds when a perfect strategy must have finite marginal entropy. Hardness persists among games whose finite-dimensional value is one and which have no finite-dimensional perfect strategy. A finite clock-phase order supplies the existential witness: normality forces a finite order on a nonzero sector, while the strategy chooses the order. For the upper bound, we normalize the largest Schmidt coefficient and use compact operator sandwiches. Fixing a lower bound on the largest Schmidt probability gives a co-recursively enumerable stratum. No computable bound selects a sufficient stratum for every game. Exact attainment of a rational Bell bound, of an unspecified supremum, and of a specified scalar value is also Sigma^0_2-complete. The hardness proof extends the modular-shift and rational-row toolkit of our earlier entropy-game paper to four calibrated bridges and a deterministic computation on rooted finite squares.
Given a finite nonlocal game, can the players win with certainty? We prove that the existence of a perfect normal spatial strategy is Σ⁰₂-complete, even when restricted to games of value one, so it cannot be decided even with an oracle for the halting problem. This is strictly harder than perfect play in the finite-dimensional and commuting-operator models, which are Σ⁰₁-complete and Π⁰₁-complete. Within the commuting model, the existence of a perfect normal strategy with a finite or semifinite von Neumann host is Σ⁰₂-complete, whereas for every fixed type III_λ subtype it has the same Π⁰₁-complete language as unrestricted commuting play. A trace thus costs one existential number quantifier: the hardness constructions force every perfect strategy to choose a finite clock period or a finite tree depth. The spatial classification persists when finite entanglement entropy is required, and it is formally verified in Lean, assuming only a special case of Tarski's decision theorem. We also prove Σ⁰₂-completeness for one-shot zero-error communication with normal entanglement, and construct a finite channel with zero-error codes of a given size every one of which needs infinite entanglement entropy.
How much infinity can a finite nonlocal game require? We construct a finite two-player game with classical questions, classical answers and a Boolean winning rule. It has a perfect strategy on a tensor product of separable Hilbert spaces. Every perfect normal spatial strategy contains, under local isometries, the same pure entangled state with infinite entropy. For mixed strategies, both marginal entropies are infinite and the pure state remains a tensor factor. Thus infinite dimension can be strengthened to infinite entropy without losing spatial attainment. The proof constructs a rational Bell functional whose perfect strategies contain a state with Catalan Schmidt multiplicities, and compiles it into Boolean tests. For either construction, the minimum marginal entropy at loss ε is Θ(log(1/ε)). The lower bound holds for every normal spatial strategy, including mixed states and POVMs. It follows from polynomial decoding on the actual state and a finite-strip entropy estimate. Height and size cutoffs give the matching upper order. The sharp leading constant remains open.
We construct a finite rational two-player nonlocal game with a binary winning predicate that has a perfect strategy on ℓ²⊗ℓ² and no perfect finite-dimensional strategy. The game has ten questions for Alice, eleven for Bob, at most six answers per question, and a uniform distribution on fifty-two question pairs. We glue two copies of Mančinska's Flagged Magic-Square game along complementary labels, adding a boundary answer to the second copy. An inverse-free sector argument forces every perfect strategy to contain a Schmidt-coefficient chain closed under halving, which rules out finite rank. An explicit normalized spatial strategy has twenty coefficients at each geometric level. Its compression to 20K dimensions has loss exactly 1/[624(4^K−1)], giving D(ε) ≤ 10 log2(1/ε) + 20 for general local POVMs and 0 < ε < 1. We prove a weaker algebraic lower bound and state a matching logarithmic lower bound as an open problem. Thus a binary-scoring game distinguishes spatial from finite-dimensional perfect attainment even though both values are one.
A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile DΓ(ε)=10log2(1/ε)+O(loglog(1/ε)). Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, 5.362740278498934 ebits, and least mean occupation, 275/18 per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II1 factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit Δ∗=ln(7/6)−ln(2)/7. Type-II∞ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.
A finite rational binary-scoring game can require infinite dimension for perfect play while admitting finite energy and finite entanglement entropy. Our game has ten Alice questions, eleven Bob questions, at most six answers, and 52 uniform question pairs. It is spatially perfect and never finitely perfect, with sharp dimension profile DΓ(ε)=10log2(1/ε)+O(loglog(1/ε)). Among pure perfect strategies, the displayed strategy attains the least entanglement entropy, 5.362740278498934 ebits, and least mean occupation, 275/18 per oscillator. We classify all perfect normal type-I marginal spectra and prove that this spectrum is the unique majorization maximum. These constants are also the small-loss limits of the entropy and one-sided oscillator energy prices. In the massive free scalar field we construct a pure perfect state in two strictly separated bounded regions, equal to the vacuum outside a bounded containing region and with every polynomial energy moment finite. In contrast, every fixed faithful split state has a positive loss floor; the complementary-wedge vacuum has supremum one without attainment. Energy-analytic states, bounded-region invertible vacuum preparations and product-Kraus preparations cannot be perfect. Every perfect pure spatial strategy has infinite Schmidt rank; finite entropy is attained but not forced. In every type-II1 factor the normalized trace has a loss floor, while bounded faithful prepared densities win perfectly with sharp trace-entropy deficit Δ∗=ln(7/6)−ln(2)/7. Type-II∞ permits every finite trace entropy. A graded modular ladder gives a normal semifinite hosting criterion. Its scalar fingerprint has sharp capacity and entropy-gap bounds; the capacity floor is approached but not attained in type I, and attained in type II.
We identify a structural mechanism by which perfect play in a nonlocal game requires and self-tests a specific non-maximally entangled state. To this end, we construct a Flagged Magic-Square game by extending the standard Magic-Square game with an additional ``flag'' outcome and two additional questions for each player. The game admits a perfect strategy using a state with Schmidt coefficients proportional to (1,2,2,2,2). We give a direct algebraic proof that maximally entangled strategies have winning probability bounded away from one, independently of dimension. Moreover, the game self-tests this state, providing an example of a two-party pseudo-telepathy game that certifies a specific non-maximally entangled state. Our construction illustrates how adding suitable constraints to a rigid measurement geometry can enforce specific Schmidt ratios and provides a modular route to further self-tests based on other rigid pseudo-telepathy games.
We establish a general game-to-channel reduction that transfers separations in the game model to one-shot zero-error communication over classical channels. Applied to the Flagged Magic-Square game, it yields a classical channel for which entanglement permits the zero-error transmission of ten messages in a single use, whereas any finite-dimensional maximally entangled resource permits at most nine. Thus, maximally entangled states are not a universally optimal entanglement resource for zero-error communication over classical noisy channels.