betaFeedback

WorksPhysics and Astronomy

A trace costs one quantifier: the exact complexity of perfect play in nonlocal games

Abstract

Given a finite nonlocal game, can the players win with certainty? We prove that the existence of a perfect normal spatial strategy is Σ20Σ^0_2-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 Σ10Σ^0_1-complete and Π10Π^0_1-complete. Within the commuting model, the existence of a perfect normal strategy with a finite or semifinite von Neumann host is Σ20Σ^0_2-complete, whereas for every fixed type IIIλ\mathrm{III}_λ subtype it has the same Π10Π^0_1-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. Spatial Σ20Σ^0_2-completeness also holds when finite entanglement entropy is required, and both forms are formally verified in Lean. For every computable 0<α<10<α<1, perfect spatial play with Tr hα<∞\mathrm{Tr}\,h^α<\infty for the reduced density hh is Σ20Σ^0_2-complete as well; these conditions form a strict ladder between finite rank and finite entropy. We also prove Σ20Σ^0_2-completeness for one-shot zero-error communication with normal entanglement, and construct a finite channel with zero-error codes of a given size each of which needs infinite entanglement entropy.

Opus 5.5, GPT-6.1 Sol and GPT-6 assisted with this work; the authors take responsibility for every claim (see “How this work was done”). Programs and finite checks: https://github.com/Apsiape/perfect-play-arithmetical-hierarchy. Archive: https://doi.org/10.5281/zenodo.23962889.

Introduction

In a nonlocal game a referee sends each of two separated players a question from a finite list. Each player answers from a finite list, and a fixed rule decides whether they win. Shared entanglement can raise the winning probability. When can the players win with certainty?

For a fixed game this is a yes-or-no question. It has a precise answer only once one says what a quantum strategy is, and only once one separates approaching certainty from attaining it: the supremum of the winning probability can be one while no strategy reaches it. The standard models are finite-dimensional tensor products, normal states on infinite-dimensional tensor products (the spatial model), and commuting operator algebras on one Hilbert space. Inside the commuting model one can further ask which von Neumann algebra hosts the players. This paper finds, for each of these models, the exact level of the arithmetical hierarchy at which perfect play is decided.

The answers are not monotone in the model. As sets of correlations the spatial model sits between the finite-dimensional and the commuting one, yet perfect spatial play is strictly harder to decide than both: it is Σ20\Sigma^0_2-complete, while the other two are Σ10\Sigma^0_1- and Π10\Pi^0_1-complete. A Σ20\Sigma^0_2 question asks whether some integer passes every one of infinitely many finite tests; no algorithm decides such questions in general, even with an oracle for the halting problem.

Completeness means that perfect spatial play has this form and that every question of this form reduces to it. Our constructions make the integer concrete: a perfect strategy must select a finite clock period or a finite tree depth, and then pass every test attached to that choice. Spatial and semifinite perfection combine an unbounded finite choice with an infinite verification.

Why a trace costs a quantifier

Commuting perfection is Π10\Pi^{0}_{1} because the commuting state space is compact. Perfection then equals commuting value one, which a convergent hierarchy of relaxations refutes in finitely many steps whenever it fails. Spatial play has no such compactness: Schmidt mass can escape to infinitely many small coefficients. Our upper bound keeps one Schmidt coefficient from disappearing. Once that coefficient is bounded below and scaled to one, the amplitude operator lies in a norm-compact family, and the losing probabilities become homogeneous zero equations that survive limits. So perfect spatial play has the form

∃κ ∀d F(G,κ,d),\exists\kappa\ \forall d\ F(G,\kappa,d),

with FF decidable: for each integer κ\kappa, the existence of a perfect strategy whose largest Schmidt probability is at least 1/κ1/\kappa is a Π10\Pi^{0}_{1} property (Theorem 3.1).

The same integer appears for every semifinite host. A trace gives a finite corner whose overlap with the state can be bounded below; in type I a rank-one corner recovers the largest Schmidt amplitude (§ 3.5). A type-III factor has no finite corner, and its perfect-play language collapses to the commuting one. In this sense a trace costs exactly one existential quantifier. Finite dimension is the degenerate case: there the whole space is a finite corner, and once the dimension is fixed, perfection is a question of real algebra that Tarski’s method decides [2]. Only the search over the dimension remains, which is why that row is Σ10\Sigma^{0}_{1}. An operational split between semifinite and type III algebras was known for embezzlement of entanglement [59]; here the split appears as a quantifier.

The hardness proofs show that the quantifier is needed. In each case the existential witness is a finite object that every perfect strategy must choose. In the spatial model it is the order of a clock phase. The Weyl unitaries of the clock commute with the trace-class density, so they act on its eigenspaces, which are finite-dimensional, and there a determinant forces the commutator phase to be a root of unity. In a diffuse semifinite algebra no such determinant exists, but a trace forces a critical binary tree to end at a finite depth. A finite game then checks an infinite sequence of decidable conditions about the chosen object. No computable function of the game bounds a sufficient clock order (§ 10) or a sufficient Schmidt stratum (Theorem 3.1).

Results

Table 1 collects the answers, and four theorems fill it.

The first theorem completes the standard row of models.

Theorem A (spatial perfection). Deciding whether a finite rational 0/1 game has a perfect normal spatial strategy is Σ20\Sigma^{0}_{2}-complete. The same holds when a perfect strategy with finite marginal entropy is required. Hardness holds under the promise ωq(G)=1\omega_{\mathrm{q}}(G)=1, for a family in which no instance has a perfect finite-dimensional strategy.

The second sorts the commuting model by the type of the players’ algebra. A host is an ambient von Neumann algebra containing Alice’s measurements, with Bob’s measurements in its commutant. Both the host and its normal state may be chosen; the state need not be tracial, and the measurements need not generate the host. Write PERF⁡(X)\operatorname{PERF}(X) for the set of games with a perfect strategy whose host is of class XX; finite-host perfection uses a σ\sigma-finite finite von Neumann algebra, equivalently one admitting a faithful normal tracial state (§ 2).

Theorem B (perfect play by von Neumann type). Perfect normal play with a finite von Neumann host, a type II1\mathrm{II}_{1} host, or a semifinite host is Σ20\Sigma^{0}_{2}-complete, and so are the type II∞\mathrm{II}_{\infty} and type II\mathrm{II} existence languages. For every fixed λ∈[0,1]\lambda\in[0,1], the type IIIλ\mathrm{III}_{\lambda} language equals commuting perfection and is Π10\Pi^{0}_{1}-complete.

Theorem 14.4 completes the type classification: commuting perfection without semifinite perfection is Π20\Pi^{0}_{2}-complete, the semifinite-but-not-spatial differences are D2(Σ20)D_{2}(\Sigma^{0}_{2})-complete, and every nonempty difference among six models is complete for its class.

The third shows that the same level governs a communication task. A sender uses a finite classical channel once and must convey one of mm messages with zero error, helped by shared entanglement. Write ZE⁡t(N,m)\operatorname{ZE}_{t}(N,m) for the existence of such a code for the channel NN in model tt (§ 18).

Theorem C (zero-error communication). For finite rational classical channels, ZE⁡qs\operatorname{ZE}_{\mathrm{qs}} and ZE⁡finS\operatorname{ZE}_{\mathrm{finS}} are Σ20\Sigma^{0}_{2}-complete. Moreover, there are a finite rational classical channel NN and an integer mm for which ZE⁡qs(N,m)\operatorname{ZE}_{\mathrm{qs}}(N,m) holds, and every normal spatial mm-message zero-error resource has infinite marginal entropy on both sides.

The fourth measures how fast the entanglement spectrum of a perfect strategy must decay. For a perfect spatial strategy with reduced density hh, finite rank, finite α\alpha-moments Tr⁡hα<∞\operatorname{Tr} h^{\alpha}<\infty and finite entropy are successively weaker resource conditions.

Theorem D (the entanglement spectrum). For every fixed computable 0<α<10 < \alpha< 1, perfect play with Tr⁡hα<∞\operatorname{Tr} h^{\alpha}<\infty, denoted Pα\mathcal{P}_{\alpha}, is Σ20\Sigma^{0}_{2}-complete. With P0\mathcal{P}_{0} denoting finite rank, P1\mathcal{P}_{1} finite entropy and Pnormal\mathcal{P}_{\mathrm{normal}} normal perfect action, they form the strict ladder P0⊊Pα⊊Pb⊊Pnormal\mathcal{P}_{0} \subsetneq\mathcal{P}_{\alpha} \subsetneq\mathcal{P}_{b} \subsetneq\mathcal{P}_{\mathrm{normal}} for 0<α<b<10 < \alpha< b < 1, and all moment orders greater than one collapse to normal perfection.

Theorem 9.1 adds a single hardness family for all rungs, the completeness of the differences between rungs, and an exact description of the possible critical indices.

A running example. Consider the rooted tree of finite words ww over four letters; ∣w∣|w| is the word length, and appending a letter selects one of four branches. Give the basis vector ∣w⟩|w\rangle density weight (3/4)16−∣w∣(3/4)16^{-|w|}, so that each child has one sixteenth of its parent’s weight. The weights sum to one and define a normal state of finite entropy. Its half-moment, the sum of the square roots of all weights, diverges: the four child square roots sum to the parent’s square root at every level. A bridge is a finite game gadget that doubles a density weight between two selected subspaces; four bridges give the factor 16. A fifth changes the ratio to 1/321/32 and makes the half-moment converge, because 4/32=1/24/\sqrt{32}=1/\sqrt{2}. Figure 1 shows the tree and its bridges. This tree is the root of the spatial hardness game (§ 8), it separates the moment rungs (§ 12), and it sits exactly at the zero-error threshold (§ 19).

The running example: a tree of four-letter words with one-step-down, four-bridge, and five-bridge diagrams

Figure 1. The running example: the tree of four-letter words, with density weight 3416−m\frac{3}{4}16^{-m} on each word of length mm (§ 8). (a) Each bridge UgU_g carries the corner eg−1e_{g-1} onto ege_g and doubles density weights (Lemma 4.1); the child Aαξ=v∗aαξA_\alpha\xi=v^*a_\alpha\xi of a parent ξ\xi is the vector of e0e_0 that the four bridges carry onto aαξa_\alpha\xi; since aαa_\alpha keeps weights, the child has one sixteenth of the parent’s weight (§ 7.4). (b) Bar widths are proportional to the square roots of the weights, and the shaded bars are a parent and child as in (a); with four bridges the four children exactly tile their parent, so every row has the same width and the sum of all square roots diverges, although the weights sum to one. (c) A fifth bridge gives the ratio 1/321/32, each row covers 1/21/\sqrt{2} of the row above, and the sum is finite: this is the zero-error threshold of § 19.

Theorem C comes from a correspondence between games and channels due to Mančinska [39], which we extend from finite dimension to trace-class operators. A perfect strategy gives a code exactly when its Schmidt amplitudes are summable. The compiled games of Theorem A sit exactly at this threshold: with four bridges, the amplitude sum diverges for every perfect strategy, and five bridges restore summability. A Catalan version of the construction gives a channel whose game has finite-entropy perfect strategies, while every code of the required size has infinite entropy.

Reading guide. For the trace mechanism, read § 2 and § 3 (in particular § 3.5), then § 14, § 15 and § 17, treating the compiler as a black box with the input and output contract stated at the start of § 4. For the spatial classification, read § 3, that contract, and § 8–§ 10; the implementation in the rest of § 4 can be deferred, and § 10 shows how the clock period becomes the existential witness. For communication, read § 2 and § 18–§ 21.

Further results

The body also proves refinements of Theorems A–D. The largest-Schmidt strata are Π10\Pi^0_1, and no total 0′0'-computable function bounds a sufficient stratum (Theorem 3.1 and § 3.4). Under a supplied entropy budget, full correlation tables are compact; the entropy busy beaver has Turing degree 0′′0'' and eventually dominates every total 0′0'-computable function (§ 3.4). Exact attainment of a rational Bell bound, of an unspecified supremum, or of a specified value is Σ20\Sigma^0_2-complete (Theorem 8.1). The I3322I_{3322} inequality is an explicit instance. Pál and Vértesi computed its supremum numerically, with finite-dimensional strategies converging to it, and conjectured that no finite dimension attains it [49], and Krohn-Grimberghe has claimed a computer-assisted exact identification of the value [36]; the supremum is not attained in finite dimension [51, 10, 18] but is attained by an infinite-dimensional spatial strategy [10, 18]. The type-I and type-II1_1 languages are incomparable, and both are proper subsets of the type-II∞_\infty language (§ 17). Theorem 14.1 classifies every difference “perfect in X but not in Y” among six models. Finally, one-shot zero-error feasibility with finite-dimensional entanglement is Σ10\Sigma^0_1-complete, a corollary of [39] and [34] (§ 19.7).

Prior work and attribution

The finite-dimensional row of Table 1 uses perfect completeness in Theorem 12.6 of Ji, Natarajan, Vidick, Wright and Yuen [34], not just a gap statement about a supremum; upper membership follows by a dimension search and real quantifier elimination. Slofstra’s embedding theorem [57] and the account of Mousavi, Nezhadi and Yuen [44 Theorem 6.4] give the commuting row. The value-one row was first proved by Mousavi, Nezhadi and Yuen [43]; see also [44 Theorem 6.9]. The commuting upper bound uses the convergent moment hierarchy of Navascués, Pironio and Acín [45]. The operator-solution framework for binary constraint system games originates with Cleve and Mittal [9]; Cleve, Liu and Slofstra gave the commuting-operator extension [8]. Slofstra also established nonclosure of finite-dimensional quantum correlations [56]. Lin’s MIPco=coRE\mathrm{MIP}^{\mathrm{co}}=\mathrm{coRE} theorem concerns gap approximation in the commuting model [37]; it does not classify spatial attainment.

Infinite-dimensional spatial correlations were constructed by Coladangelo and Stark [11]. Kim, Paulsen and Schafhauser prove that perfect spatial play collapses to perfect finite-dimensional play for synchronous games [35 Corollary 3.11], and Lupini and coauthors prove the corresponding equivalence for imitation games [38 Corollary 5.4]. Our games keep nonsynchronous bridge questions, so no YES instance of the spatial reduction is synchronous or an imitation game.

Mančinska’s flagged magic-square construction supplies the bridge geometry [39]; the magic square itself is due to Mermin and Peres [42, 53]. The normal bridge, shared-label refinement, graph products and Boolean rational-row tests were developed in our entropy-game paper [24 Lemmas 4.1 and 4.2, Theorem B, Eq. (32)]; its Catalan game [24 Theorem C] is used here as a separator, and a four-bridge version of its Catalan assembly gives the infinite-entropy channel. § 4 restates and proves the versions needed here and extends them to nn bridges, arbitrary finite lists of endpoint labels and normal commuting hosts. The standard-form reduction, the commuting bridge and expected-inclusion transfer come from our earlier paper [20 Lemmas 1.6, 2.2 and 3.1]; the type rows of Table 1 answer the question left open in [20 Theorem 7.6]. The separation PERF(II1)⊄PERF(I)\mathrm{PERF}(\mathrm{II}_1)\not\subset\mathrm{PERF}(\mathrm{I}) uses the tracial mechanism of [20 Proposition 7.4] and Slofstra’s nonclosure construction; the other direction uses a new one-bridge separator. Our earlier preprints [23] and [19] gave single games with, respectively, finite-energy spatial perfection that no finite-dimensional strategy attains, and a perfect type III1/2_{1/2} strategy with no injective host.

Group embeddings originate with Higman [32]; the effective form follows Chiodo [7, Theorem 2.2], with Craig’s conversion [15] and the HNN normal form [33]. Subtype transfer uses Connes–Takesaki flow-of-weights theory [14], Takesaki’s expectation theorem [58], Connes’s invariants [12], and the argument inside Haagerup–Musat [29], Lemma 3.8. The nearest operational work on host type is the type classification of embezzling states by van Luijk, Stottmeister, Werner and Wilming [59], the commuting self-test for exact embezzlement of Paddock and Schmidt [48], and Harris’s Cuntz-algebra self-testing and factor classification [31]. These concern embezzlement rather than the arithmetical classification of host-existence languages.

For communication, Cubitt, Leung, Matthews and Winter established the operator characterization of entanglement-assisted zero-error codes and the pseudo-telepathy construction [16]. Mančinska proved finite-dimensional clique saturation in Lemma 5, the converse and square-root state map in Theorem 6, and the entanglement-assisted independence-number characterization in Corollary 7 of [39]; her zero-error results assume a finite-dimensional shared state. Her Corollary 8 gives the fifty-input flagged-magic-square channel with ten entangled messages and at most nine messages from finite-dimensional maximally entangled resources. Mančinska, Roberson and Varvitsiotis studied perfect strategies and independent-set game reductions [41]; Mančinska and Roberson developed quantum graph homomorphisms [40]; Harris proved universality results for synchronous graph homomorphism games [30]. Bhattacharyya, Mehta and Zhao proved undecidability for a restricted entanglement-assisted one-shot parameter of classical-to-quantum channels [5]; their parameter uses maximal entanglement and projective measurements [5], Definition 2.3. The finite-dimensional row here removes these restrictions for classical channels and a one-shot threshold; it does not resolve the asymptotic capacity question. For fixed-scenario correlation membership, studied by Fu, Miller and Slofstra [27], see § 22.

This paper consolidates and supersedes our preprints [25, 22, 21]. Theorem D and the completion of the semifinite-but-not-spatial difference classification are new here. The commuting Π10\Pi^{0}_{1} classification is known [57, 44]; Theorem B identifies its language with that of every fixed type-III subtype.

Organization

§ 2 fixes the models, languages and notation. § 3 proves the Σ20\Sigma^{0}_{2} upper bounds for spatial, finite-entropy, finite and semifinite perfection; § 12.1 treats moment rungs and § 19.4 reduces codes to games. § 4 builds the finite compiler shared by all hardness proofs. § 8–§ 10 prove the spatial hardness of Theorem A, and § 11 the Bell variants. § 12–§ 13 prove Theorem D. § 14–§ 15, together with § 16, prove Theorem B, and § 17 compares the type languages. § 18–§ 21 prove Theorem C and the other communication rows. § 22 discusses open problems.

Preliminaries

Games, strategies and models

A finite rational Boolean game GG is a finite list of questions and answers, a rational distribution π(x,y)\pi(x,y), and a predicate V(a,b∣x,y)∈{0,1}V(a,b \mid x,y) \in\{0,1\}. Perfection means zero probability for every losing event of positive question weight. A spatial strategy consists of positive operator-valued measurements (POVMs) Ea∣xE_{a\mid x} and Fb∣yF_{b\mid y} and a normal state, represented by a positive trace-class density ρ\rho of trace one, on HA⊗HB\mathcal{H}_A \otimes\mathcal{H}_B. Its winning probability is

∑xyabπ(x,y)V(a,b∣x,y)Tr⁡ρ(Ea∣x⊗Fb∣y).\sum_{x y a b} \pi(x,y)V(a,b \mid x,y) \operatorname{Tr}\rho(E_{a\mid x} \otimes F_{b\mid y}).

We write CqC_q, CqsC_{qs}, CqcC_{qc} for finite-dimensional, normal spatial, and commuting correlations. For a strategy SS, write ω(G,S)\omega(G,S) for the displayed winning probability and loss⁡G(S)=1−ω(G,S)\operatorname{loss}_G(S)=1-\omega(G,S). The value ωq\omega_q is the supremum over CqC_q. Finite Schmidt truncations show that CqC_q and CqsC_{qs} have the same closure and the same supremum for every Bell functional.

The set PERFq\mathrm{PERF}_q consists of games with a perfect finite-dimensional strategy. The set PERFqs\mathrm{PERF}_{qs} consists of games with a perfect normal spatial strategy. Its stratum PERFqs(κ)\mathrm{PERF}_{qs}(\kappa) requires a perfect pure strategy whose largest Schmidt probability is at least 1/κ1/\kappa. The set PERFfinS\mathrm{PERF}_{\mathrm{finS}} requires a perfect strategy with finite marginal entropy. The one-marginal existence convention gives the same game language as requiring both reduced entropies finite, by purification onto the other party and equality of the pure state’s marginal spectra; the conventions can differ on a fixed mixed strategy. Commuting perfection, PERFco\mathrm{PERF}_{co}, uses two commuting families of POVMs on one Hilbert space and a state.

Hosts. For a class XX of von Neumann algebras, PERF(X)\mathrm{PERF}(X) denotes existence of a perfect strategy normal on an ambient von Neumann algebra of class XX; Bob acts in its commutant. The ambient algebra need not be generated by the measurements. The state may be chosen along with the host. Finite-host perfection permits non-tracial normal states; this is consistent with ωtr(GFMS)<1\omega_{\mathrm{tr}}(G_{\mathrm{FMS}})<1 in [39 Theorem 3]. These are existence languages: they do not test a prescribed algebra, state or full correlation table. Write PERFfin\mathrm{PERF}_{\mathrm{fin}} for hosting in a σ\sigma-finite finite von Neumann algebra, equivalently one admitting a faithful normal tracial state, and PERFsf\mathrm{PERF}_{\mathrm{sf}} for hosting in a semifinite von Neumann algebra. Factor hosting gives the same existence languages as hosting in algebras purely of the indicated type.

We use separable hosts when decomposing. For commuting input this follows from the joint GNS representation of the finitely generated measurement C∗C^*-algebra. For finite or semifinite input the finite-corner overlap construction of § 3.5 gives a separable host in the same class: generate the two unital C∗C^*-algebras by the finitely many effects and the finite band projection, and take the closure of their orbit of the trace vector. It is separable; Lemma 3.8 preserves a nonzero perfect component and proves its represented host finite or semifinite. One may then standardize Bob and decompose over the center. Every losing probability is an integral of nonnegative probabilities, so the finitely many zero integrals vanish on a common conull set of factor fibres. A finite or semifinite fibre remains in that class; the amplifications in (10) give the required pure type-II factor. For type I use its direct-integral decomposition into spatial factor strategies; in particular the type-I language PERF(I)\mathrm{PERF}(\mathrm{I}) is the spatial language PERFqs\mathrm{PERF}_{qs}. The type-III constructions of Section 12 start with an unrestricted commuting factor fibre.

When several languages are compared at once we abbreviate

q=PERFq,E=PERFfinS,I=PERF(I),\mathbf{q}=\mathrm{PERF}_q,\qquad\mathbf{E}=\mathrm{PERF}_{\mathrm{finS}},\qquad\mathbf{I}=\mathrm{PERF}(\mathrm{I}),
J=PERF(II1),U=PERFsf,C=PERFco.\mathbf{J}=\mathrm{PERF}(\mathrm{II}_1),\qquad\mathbf{U}=\mathrm{PERF}_{\mathrm{sf}},\qquad\mathbf{C}=\mathrm{PERF}_{co}.

Here q\mathbf{q} requires attainment in finite dimension; it is not the value-one language. The inclusions are q⊆E⊆I⊆U⊆C\mathbf{q} \subseteq\mathbf{E} \subseteq\mathbf{I} \subseteq\mathbf{U} \subseteq\mathbf{C} and q⊆J⊆U\mathbf{q} \subseteq\mathbf{J} \subseteq\mathbf{U}; every displayed inclusion is strict (§ 17). We keep PERF strictly for attainment. Nezhadi’s 2025 thesis [46] uses “perfectly winnable” for the value-one Π20\Pi^0_2 problem of [44], so its terminology has a different scope.

Arithmetical classes

References

  1. [1]Scott Aaronson. The Busy Beaver Frontier. Technical Report TR20-115, Electronic Colloquium on Computational Complexity, 2020.DOI
  2. [2]Saugata Basu, Richard Pollack, and Marie-Françoise Roy. Algorithms in Real Algebraic Geometry. Springer, second edition, 2006.
  3. [3]Verónica Becher, Yann Bugeaud, and Theodore A. Slaman. The irrationality exponents of computable numbers. Proceedings of the American Mathematical Society, 144(4):1509–1521, 2016.arxiv.org/abs/1410.1017
  4. [4]Salman Beigi. Entanglement-assisted zero-error capacity is upper bounded by the Lovász theta function. Physical Review A, 82:010303(R), 2010. arXiv:1002.2488v2.DOI
  5. [5]Archishma Bhattacharyya, Arthur Mehta, and Yuming Zhao. On the undecidability of quantum channel capacities. https://arxiv.org/abs/2601.22471v3, 2026. In Proceedings of the 67th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2026), to appear.
  6. [6]Ranyiliu Chen and Yuming Zhao. A non-robust quantum correlation self-test, 2026. arXiv:2609.25117v2.arxiv.org/abs/2609.25117
  7. [7]Maurice Chiodo. On torsion in finitely presented groups. Groups, Complexity, Cryptology, 6(1):1–8, 2014. https://doi.org/10.1515/gcc-2014-0001; arXiv:1107.1489v4.
  8. [8]Richard Cleve, Li Liu, and William Slofstra. Perfect commuting-operator strategies for linear system games. Journal of Mathematical Physics, 58:012202, 2017. arXiv:1606.02278.DOI
  9. [9]Richard Cleve and Rajat Mittal. Characterization of binary constraint system games. In Automata, Languages, and Programming (ICALP 2014), pages 320–331, 2014. arXiv:1209.2729.arxiv.org/abs/1209.2729
  10. [10]Andrea Coladangelo. The I₃₃₂₂ Bell inequality requires infinite dimensions. https://arxiv.org/abs/2609.06038, 2026.
  11. [11]Andrea Coladangelo and Jalex Stark. An inherently infinite-dimensional quantum correlation. Nature Communications, 11:3335, 2020. Preprint arXiv:1804.05116.
  12. [12]Alain Connes. Une classification des facteurs de type III. Annales scientifiques de l’École Normale Supérieure, 6(2):133–252, 1973.
  13. [13]Alain Connes. Classification of injective factors: Cases II₁, II∞, IIIλ, λ ≠ 1. Annals of Mathematics, 104(1):73–115, 1976.
  14. [14]Alain Connes and Masamichi Takesaki. The flow of weights on factors of type III. Tohoku Mathematical Journal, 29(4):473–575, 1977. Parts 1 and 2.
  15. [15]William Craig. On axiomatizability within a system. The Journal of Symbolic Logic, 18(1):30–32, 1953.DOI
  16. [16]Toby S. Cubitt, Debbie Leung, William Matthews, and Andreas Winter. Improving zero-error classical communication with entanglement. Physical Review Letters, 104:230503, 2010. arXiv:0911.5300.DOI
  17. [17]Ronald G. Douglas. On majorization, factorization, and range inclusion of operators on Hilbert space. Proceedings of the American Mathematical Society, 17(2):413–415, 1966.DOI
  18. [18]Seth Douglas. The I₃₃₂₂ quantum value is attained spatially but not in finite dimension. Zenodo, https://doi.org/10.5281/zenodo.21782008, 2026. All versions, first released August 2026; arXiv:2609.05555.
  19. [19]Seth Douglas and Nidhal Mghirbi. A finite game that normal hyperfinite strategies approach but never win. https://doi.org/10.5281/zenodo.23816141, 2026. Version 1.0.0, preprint.
  20. [20]Seth Douglas and Nidhal Mghirbi. Finite games that read the type of a von Neumann algebra. https://doi.org/10.5281/zenodo.23931154, 2026. Version 1.1.0, preprint.
  21. [21]Seth Douglas and Nidhal Mghirbi. One-shot zero-error communication with normal entanglement is Σ⁰₂-complete. Zenodo, https://doi.org/10.5281/zenodo.23924868, 2026.
  22. [22]Seth Douglas and Nidhal Mghirbi. Perfect play has different arithmetical complexity in semifinite and type III algebras. Zenodo, https://doi.org/10.5281/zenodo.23925091, 2026.
  23. [23]Seth Douglas and Nidhal Mghirbi. Perfect play in a binary-scoring nonlocal game requires infinite dimension but only finite energy. https://doi.org/10.5281/zenodo.23772890, 2026. Version 2.0.0, preprint.
  24. [24]Seth Douglas and Nidhal Mghirbi. Perfect play in a finite nonlocal game requires infinite entanglement entropy. https://doi.org/10.5281/zenodo.23932017, 2026. Version 1.1.0, preprint.
  25. [25]Seth Douglas and Nidhal Mghirbi. Perfect play with spatial quantum strategies is Σ⁰₂-complete. Zenodo, https://doi.org/10.5281/zenodo.23910986, 2026.
  26. [26]Tobias Fritz. Curious properties of free hypergraph C*-algebras. Journal of Operator Theory, 83(2):423–445, 2020. arXiv:1808.09220.DOI
  27. [27]Honghao Fu, Carl A. Miller, and William Slofstra. The membership problem for constant-sized quantum correlations is undecidable. Communications in Mathematical Physics, 406:96, 2025. arXiv:2101.11087v5.
  28. [28]Minbo Gao, Tianshi Yu, and Lihong Zhi. An explicit counterexample to Tsirelson’s problem via a linear system game. https://arxiv.org/abs/2610.10248, 2026.
  29. [29]Uffe Haagerup and Magdalena Musat. Classification of hyperfinite factors up to completely bounded isomorphism of their preduals. Journal für die reine und angewandte Mathematik, 630:141–176, 2009. arXiv:0706.3463.arxiv.org/abs/0706.3463
  30. [30]Samuel J. Harris. Universality of graph homomorphism games and the quantum coloring problem. Annales Henri Poincaré, 25(10):4321–4356, 2024. arXiv:2305.18116.arxiv.org/abs/2305.18116
  31. [31]Samuel J. Harris. Self-testing of exact entanglement embezzlement. https://arxiv.org/abs/2605.22713v2, 2026.
  32. [32]Graham Higman. Subgroups of finitely presented groups. Proceedings of the Royal Society of London. Series A, 262(1311):455–475, 1961.DOI
  33. [33]Graham Higman, Bernhard H. Neumann, and Hanna Neumann. Embedding theorems for groups. Journal of the London Mathematical Society, s1-24(4):247–254, 1949.DOI
  34. [34]Zhengfeng Ji, Anand Natarajan, Thomas Vidick, John Wright, and Henry Yuen. MIP* = RE. Annals of Mathematics, 2026. Accepted; arXiv:2001.04383v4.
  35. [35]Se-Jin Kim, Vern I. Paulsen, and Christopher Schafhauser. A synchronous game for binary constraint systems. Journal of Mathematical Physics, 59:032201, 2018. arXiv:1707.01016.DOI
  36. [36]Artus Krohn-Grimberghe. Certified exact identification of the I3322 quantum value. https://arxiv.org/abs/2609.29693, 2026.
  37. [37]Junqiao Lin. MIPco = coRE. https://arxiv.org/abs/2510.07162, 2025.
  38. [38]Martino Lupini, Laura Mančinska, Vern I. Paulsen, David E. Roberson, Giannicola Scarpa, Simone Severini, Ivan G. Todorov, and Andreas Winter. Perfect strategies for non-signalling games. Mathematical Physics, Analysis and Geometry, 23:7, 2020. arXiv:1804.06151.DOI
  39. [39]Laura Mančinska. The right entanglement for perfect nonlocality and zero-error communication. https://arxiv.org/abs/2610.06512v1, 2026.
  40. [40]Laura Mančinska and David E. Roberson. Quantum homomorphisms. Journal of Combinatorial Theory, Series B, 118:228–267, 2016. Preprint “Graph Homomorphisms for Quantum Players”, arXiv:1212.1724.
  41. [41]Laura Mančinska, David E. Roberson, and Antonios Varvitsiotis. On deciding the existence of perfect entangled strategies for nonlocal games. Chicago Journal of Theoretical Computer Science, 2016(5), 2016. arXiv:1506.07429.arxiv.org/abs/1506.07429
  42. [42]N. David Mermin. Simple unified form for the major no-hidden-variables theorems. Physical Review Letters, 65:3373–3376, 1990.pubmed.ncbi.nlm.nih.gov/10042855
  43. [43]Hamo(o)n Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen. On the complexity of zero gap MIP*. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 of LIPIcs, pages 87:1–87:12, 2020. arXiv:2002.10490.arxiv.org/abs/2002.10490
  44. [44]Hamo(o)n Mousavi, Seyed Sajjad Nezhadi, and Henry Yuen. Nonlocal games, compression theorems, and the arithmetical hierarchy. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing, pages 1–11, 2022. Full version arXiv:2110.04651v2.DOI
  45. [45]Miguel Navascués, Stefano Pironio, and Antonio Acín. A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations. New Journal of Physics, 10:073013, 2008. arXiv:0803.4290.DOI
  46. [46]Seyed Sajjad Nezhadi. Quantum Games, Graphs, and Gödel. PhD thesis, University of Maryland, 2025.DOI
  47. [47]Dorte Olesen and Gert K. Pedersen. Some C*-dynamical systems with a single KMS state. Mathematica Scandinavica, 42:111–118, 1978.DOI
  48. [48]Connor Paddock and Simon Schmidt. A commuting operator self-test for exact entanglement embezzlement. https://arxiv.org/abs/2609.38083, 2026.
  49. [49]Károly F. Pál and Tamás Vértesi. Maximal violation of a bipartite three-setting, two-outcome Bell inequality using infinite-dimensional quantum systems. Physical Review A, 82:022116, 2010.DOI
  50. [50]Vern I. Paulsen, Simone Severini, Daniel Stahlke, Ivan G. Todorov, and Andreas Winter. Estimating quantum chromatic numbers. Journal of Functional Analysis, 270(6):2188–2222, 2016.DOI
  51. [51]Jef Pauwels. The quantum supremum of the I₃₂₂ Bell inequality is not attained in finite dimension. https://arxiv.org/abs/2608.29734, 2026.
  52. [52]Gert K. Pedersen and Masamichi Takesaki. The Radon–Nikodym theorem for von Neumann algebras. Acta Mathematica, 130:53–87, 1973.DOI
  53. [53]Asher Peres. Incompatible results of quantum measurements. Physics Letters A, 151:107–108, 1990.DOI
  54. [54]Tibor Radó. On non-computable functions. Bell System Technical Journal, 41(3):877–884, 1962.DOI
  55. [55]Joseph R. Shoenfield. On degrees of unsolvability. Annals of Mathematics, 69(3):644–653, 1959.DOI
  56. [56]William Slofstra. The set of quantum correlations is not closed. Forum of Mathematics, Pi, 7:e1, 2019. arXiv:1703.08618.arxiv.org/abs/1703.08618
  57. [57]William Slofstra. Tsirelson’s problem and an embedding theorem for groups arising from non-local games. Journal of the American Mathematical Society, 33:1–56, 2020. arXiv:1606.03140.
  58. [58]Masamichi Takesaki. Conditional expectations in von Neumann algebras. Journal of Functional Analysis, 9(3):306–321, 1972.DOI
  59. [59]Lauritz van Luijk, Alexander Stottmeister, Reinhard F. Werner, and Henrik Wilming. Embezzlement of entanglement, quantum fields, and the classification of von Neumann algebras. https://arxiv.org/abs/2401.07299v4, 2024.

Paper details

vlnc:W_4fjaqun3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 2

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

Opus 5.5, GPT-6.1 Sol, GPT-6

View statement
Looking for related papers…
Contents