Pith. sign in

REVIEW 1 major objections 10 minor 29 references

XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games

T0 review · 1 major / 10 minor · reviewed 2026-07-09 · glm-5.2

Pith's one-line read One bit of tilt makes quantum games undecidable

desk verdict Letter re: arXiv:2607.06876 read the letter →

arxiv 2607.06876 v1 pith:SJI23X6C submitted 2026-07-08 quant-ph cs.CC

classification quant-phcs.CC PACS 03.67.-a03.67.Mn
keywords nonlocalgamesXORtiltedbinaryquantumvalueRE-hardnesslinearconstraintsystemsemidefiniteprogramming
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

XOR games — where two players win or lose based on the XOR of their output bits — are the one class of nonlocal games whose quantum value can be computed efficiently, by a semidefinite program. This paper introduces a minimal modification: allow the winning condition to depend on just one player's bit for a single distinguished question type, rather than always on the XOR of both. For classical strategies this changes nothing. But for quantum strategies, this single tweak pushes the problem from polynomial-time solvable to RE-complete, the hardest class of undecidable problems. The reduction works by taking Håstad's classical gadget — a cube of XOR constraints that tests whether three variables satisfy a linear equation — and reinterpreting it as a tilted XOR game. The key insight is that the cube gadget, when tilted, forces optimal quantum strategies to produce observables that satisfy the linear equation exactly (A_i A_j A_k = I), and near-optimal strategies satisfy it approximately with error O(√ε). This quantum soundness property, combined with the known RE-hardness of approximating linear system games, yields the result. Since tilted XOR games are a special case of binary games (each player outputs a single bit), the full hardness of general nonlocal games is already present in the binary setting.

What carries the argument

The proof chain runs: E3-LIN games (known RE-hard to approximate quantumly) → Håstad's cube gadget reinterpreted as tilted XOR games → Slofstra's XOR game structure theorem (optimal strategies satisfy eigenvector equations) → a tightened average-case version (Lemma 4.4, exploiting equal row/column biases) → robust product relation (Proposition 4.5) → rounding to commuting observables (Lemma 4.6, using Araki-Yamagami inequality) → gap preservation yielding δ ≈ 10^{-8}.

What would settle it

A quantum strategy for the tilted cube game G_⊥ that achieves value strictly greater than 3/4, or a near-optimal strategy (value 3/4 - ε for small ε) whose observables violate the product relation A_{011}·A_{101}·A_{110} ≈ I by substantially more than 68√(13ε), would break the reduction chain. More fundamentally, any strategy for the full reduced game achieving value ≥ 3/4 - δ for a NO instance of the halting problem would falsify the soundness claim.

Watch

Extended reading notes

Core claim

The central mechanism is the tilted cube game: a four-vertex bipartite graph gadget where three of Alice's vertices carry variables and the fourth is a distinguished question ⊥ on which Alice's answer is fixed to 0. For this game, both classical and quantum optimal values equal 3/4, and the structure theorem for XOR games (due to Slofstra) forces any optimal quantum strategy's observables A_{011}, A_{101}, A_{110} to commute and satisfy A_{011}·A_{101}·A_{110} = I. The paper proves a robust version of this: an ε-optimal strategy yields observables satisfying the product relation up to error 68√(13ε). This robustness, propagated through Håstad's reduction from E3-LIN games, converts a gap in

Load-bearing premise

The soundness argument depends on a chain of approximation bounds: near-optimal strategies for the tilted cube game yield observables satisfying a product relation up to error O(√ε), which are then rounded to commuting observables satisfying a linear constraint up to error O(ε). The accumulated constants through this chain determine the gap δ ≈ 10^{-8}. If any of these norm bounds is loose by orders of magnitude, the gap could shrink to zero and the reduction would fail.

Editorial extensions

If this is right

  • Binary nonlocal games — the simplest output structure possible — already capture the full computational hardness of MIP*=RE, so no richer answer alphabets are needed for undecidability.
  • The boundary between easy and hard quantum approximation is razor-thin: XOR games are in P, but allowing the verifier to sometimes check one player's bit directly (rather than the XOR) crosses into undecidability.
  • Noncommutative Max-Cut with a single constraint X_1 = I becomes RE-hard, even though unconstrained noncommutative Max-Cut is in P — one linear constraint on a quadratic optimization over hermitian unitaries suffices for undecidability.
  • The result extends to commuting-operator strategies (coRE-complete for the gapless version), tracial strategies, and oracularisable strategies, showing the hardness is robust to the entanglement model.
  • Even XOR games themselves become RE-hard when restricted to oracularisable strategies, connecting to the quantum unique games conjecture.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The gap δ ≈ 10^{-8} is determined by the accumulation of constants through the reduction chain (C = 301814 in Lemma 4.6, then squared and multiplied through the soundness argument). Whether this gap can be substantially improved likely depends on tightening the Frobenius norm bounds in the rounding step, which currently lose several orders of magnitude.
  • The fact that classical strategies are unaffected by the tilt (Lemma 3.3) while quantum strategies jump to RE-hardness suggests that the tilt exploits a specifically quantum resource — the ability to maintain non-classical correlations that cannot be realized as product observables. The boundary between P and RE-hard may be characterizable by which types of marginal constraints break the SDP formu
  • The obstacle for oracularised tilted XOR games (Proposition 6.7) — where the quantum value of the tilted cube's oracularisation drops below the XOR bound — suggests that the cube gadget's power depends on the specific bipartite question structure, and alternative gadgets may be needed for the oracularised setting.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

1 major / 10 minor

Summary. This paper introduces 'tilted XOR games,' a minimal modification of XOR games where the winning condition for one distinguished question depends on a single output bit rather than the XOR. While XOR game quantum values are polynomial-time approximable via SDP, the authors show that tilted XOR game quantum values are RE-complete to approximate to constant precision. The reduction proceeds from E3-LIN games (known RE-complete by Taller–Vidick [TV25]) using Håstad's classical cube gadget, reinterpreted in the tilted framework. The key technical contribution is a robust version (Proposition 4.5) of an exact structural lemma (Lemma 3.7) for the tilted cube game, showing that near-optimal strategies yield observables approximately satisfying the E3-LIN constraints. The result implies RE-hardness for general binary nonlocal games. Extensions to commuting-operator, oracularisable, and tracial models, and to noncommutative Max-Cut, are also presented.

Significance. The paper resolves a natural and previously open question about the complexity of approximating quantum values of binary nonlocal games. The contrast with standard XOR games (polynomial-time via SDP) is striking and well-motivated. The methodology—showing that Håstad's classical reduction is 'quantum-sound' when reinterpreted with a tilt—is elegant and conceptually clean. The improved XOR game structure theorem (Lemma 4.4) is a useful standalone tightening of Slofstra's Theorem 2.6. The extensions to commuting-operator, oracularisable, and tracial strategies, and the connection to noncommutative Max-Cut, add substantial breadth. The constants are explicit and verifiable, which is a strength of the presentation.

major comments (1)
  1. Proof of Theorem 4.2 (Section 4.2.2, soundness paragraph): The text states 'ω(G(S,π),p′) ≥ 1 − 4·10⁶·δ', but the final reduction formula and the constant C = 301814 from Lemma 4.6 indicate the multiplier should be approximately 4·10⁵ (specifically, 4·C ≈ 1.2×10⁶, or C itself ≈ 3×10⁵). If 4·10⁶ were correct, the resulting gap δ would be roughly 2×10⁻⁹, contradicting the stated δ ≈ 10⁻⁸. This is a load-bearing constant in the soundness analysis. The authors should correct this to the intended value and verify consistency with the stated gap δ ≈ 10⁻⁸ throughout the paper (including Theorem 4.3 and Section 5).
minor comments (10)
  1. Abstract: 'titled XOR games' should be 'tilted XOR games' (appears twice in the abstract, last sentence).
  2. Abstract: 'H{åstad}' should render as 'Håstad' (likely a LaTeX encoding issue in the abstract metadata).
  3. Section 1.1, paragraph containing 'approximately 10⁻⁸': The sentence 'A natural open question for further investigation is whether RE-hardness holds for larger values of δ, and more generally to deterrmine the computational complexity within the unclassified (white) regions in Fig. 1' has a typo ('deterrmine').
  4. Lemma 4.4: The statement uses β∗(G) in the bound but the proof writes β = β∗(G) and uses nα = β. It would help the reader to note that β = nα follows from the equal-bias assumption, since this is used implicitly.
  5. Proposition 4.5: The proof involves several intermediate norm bounds with specific constants (e.g., 32√26ε, 136√13ε). A brief remark summarizing how these aggregate to the final 68√(13ε) bound would improve readability.
  6. Lemma 4.6: The constant C = 301814 is stated without derivation of its exact value. A short parenthetical noting that it arises from summing the three error contributions (approximately 6656ε, 260(417+272√2)ε, and 15028ε) would help readers verify the bound.
  7. Figure 1: The caption mentions the RE-complete region 'is not to scale' but the text in Section 5 states the maximum width is δ ≈ 10⁻⁸. A note on the approximate aspect ratio or a log-scale alternative would make the figure more informative, though this is not essential.
  8. Section 6.1, Theorem 6.1: The theorem states the distinguished variable is asked to Bob 'for reasons of convenience,' but the main definition (Definition 3.1) places it in Alice's question set. A brief remark that the two formulations are equivalent by swapping players would prevent confusion.
  9. Section 6.4, Corollary 6.15: The reduction to noncommutative Max-Cut involves introducing auxiliary variables Y_i and a parameter Δ. The choice Δ = δ²/2 is somewhat opaque; a sentence motivating this choice would aid the reader.
  10. References: The citation [TV25] lists the year as 2025 and the URL as arXiv:2507.22444, while the paper's own arXiv ID is 2607.06876 (dated July 2026). This is consistent if [TV25] appeared in mid-2025, but the authors should verify the reference is complete and final.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity; one load-bearing self-citation to [TV25] that is independently grounded

full rationale

The paper's main theorem (RE-hardness of approximating tilted XOR game quantum values) is proved by a reduction from E3-LIN games, whose RE-hardness comes from [TV25] (co-author Taller). This self-citation is load-bearing but not circular: [TV25] is itself grounded in MIP*=RE [JNV+20] and Slofstra's undecidability [Slo19], neither involving the present authors. The present paper contributes substantial independent mathematical work — the quantum soundness of Håstad's gadget reduction (Proposition 4.5, Lemma 4.6, Lemma 4.7), the improved XOR game structure theorem (Lemma 4.4), and the exact characterization (Lemma 3.7) — none of which reduces to the cited hardness result by construction. The tilted XOR game model (Definition 3.1) is defined independently of E3-LIN games. The Håstad reduction [Hås01] and the XOR game structure theorem [Slo11] are by different authors. No fitted parameters are renamed as predictions, no uniqueness theorem from the authors' prior work is invoked, and no ansatz is smuggled through self-citation. The extensions in Section 6 each require additional argument beyond the main reduction. Score 1 reflects the one load-bearing self-citation that is independently grounded and does not create circularity.

Assumptions & free parameters 2 free parameters · 5 assumptions · 2 invented entities

The paper introduces two new game definitions (tilted XOR games, tilted cube game) but no new physical entities or postulated objects. The axioms are standard results in quantum information and operator algebras. The main external dependency is [TV25] for E3-LIN RE-hardness, which shares an author but is independently grounded in [JNV+20] and [Slo19].

free parameters (2)
  • δ (soundness gap) = ≈ 10^-8
    Not fitted but derived from the accumulated error constants in the reduction chain (Lemma 4.6 constant C = 301814, Proposition 4.5 constant 68√13). It is a consequence of the proof, not an input.
  • ε (completeness parameter) = arbitrarily small > 0
    Inherited from the E3-LIN reduction [TV25]; can be chosen arbitrarily small. Not a free parameter of this paper.
assumptions (5)
  • domain assumption E3-LIN games are RE-hard to approximate (E3-LIN*_{c,s} is RE-complete for c = 1−ε, s = 119/120+ε)
    Invoked in the proof of Theorem 4.2/4.3 as the source of hardness. This is [TV25, Theorem 4.2], an external result by overlapping author Taller and Vidick.
  • domain assumption MIP* = RE
    Background result [JNV+20] establishing that general nonlocal games are RE-complete. Used to contextualize the result; the reduction does not directly invoke it.
  • standard math Slofstra's XOR game structure theorem (Theorem 2.6)
    Used as the starting point for the improved structure theorem (Lemma 4.4). Proven in [Slo11, Theorem 3.1].
  • standard math Araki-Yamagami inequality for Frobenius norm continuity of operator absolute value
    Invoked in Lemma 4.6 to bound ‖[A_i, ψ_A^{1/2}]‖_F. Proven in [AY81].
  • domain assumption Near-perfect strategies for projection games can be rounded to tracial strategies
    Used in Theorem 6.14 for the tracial strategy extension. Cited to [Vid22, Cul26], where [Cul26] is by the present author Culf.
invented entities (2)
  • Tilted XOR game independent evidence
    purpose: A binary nonlocal game where the winning condition is XOR-based except for a distinguished question ⊥ where it depends only on one player's bit.
    The definition is a natural generalization of the tilted CHSH game [AMP12]. The paper proves its computational properties from first principles via the reduction.
  • Tilted cube game G□ independent evidence
    purpose: A specific 8-vertex gadget game used as the reduction gadget from E3-LIN to tilted XOR.
    Derived from Håstad's cube game [Hås01] with a tilt added. Its properties (Lemma 3.6, 3.7) are proven within the paper.

how reviews work

0 comments
Cite this review

Pith. "Pith review of XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games." pith.science (2026). https://pith.science/paper/SJI23X6C

@misc{pith2026260706876,
  author       = {Pith},
  title        = {Pith review of: XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SJI23X6C}},
  note         = {Machine review of arXiv:2607.06876}
}
read the original abstract

It is well known that the quantum value of an XOR nonlocal game, where the winning condition depends only on the XOR of the two players' output bits, may be approximated in polynomial time. We study a variant of the XOR game model, which we call tilted XOR games, where the winning condition can additionally depend on only one of the output bits. We show that this dramatically increases the expressive power: the computational complexity of the problem of approximating the quantum value of tilted XOR games to constant precision is RE-complete. Also, our result extends to succinct versions of tilted XOR games, where the questions can be polynomial-length binary strings, generated by a polynomial-time verifier. For classical strategies, the distinction between XOR games and tilted XOR games is inconsequential. H{\aa}stad (J. ACM, 2001) shows that they are both NP-complete to approximate, by using a reduction from linear systems to XOR games. Our approach is to show that this is also quantum-sound, but as a reduction from linear system games to tilted XOR games. Since titled XOR games are a special case of binary games (where each party outputs a single bit), our result implies that binary games are RE-hard to approximate.

Figures

Figures reproduced from arXiv: 2607.06876 by the authors.

Figure 1
Figure 1. Hardness of tilted XOR games. The P regions (green) are problems solvable in polynomial time, the triangular regions (red) are hard instances, and the white regions are where the complexity is unknown. The problem is undefined below the diagonal (gray). The RE-complete region is not to scale (though it is the interior of a triangle with positive area). The diagonal line labelled ̸∈R (purple) is a region where the pr… view at source ↗
Figure 2
Figure 2. The cube game depicted as a bipartite graph. The question pairs are the edges. The winning [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Gadgets for E3-LIN equations of the form [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: The tilted cube game as a bipartite graph. For question [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    [AMP12] A

    DOI: 10.1145/278298.278306. [AMP12] A. Acín, S. Massar, and S. Pironio. Randomness versus nonlocality and entanglement. Physical review letters, 108(10): 100402,

  2. [2]

    [AY81] H

    DOI: 10.1145/273865.273901. [AY81] H. Araki and S. Yamagami. An inequality for Hilbert-Schmidt norm. Communications in Mathematical Physics, 81(1): 89–96,

  3. [3]

    [Can88] J

    DOI: 10.1103/PhysRevA.91.052111. [Can88] J. Canny. Some algebraic and geometric computations in PSP ACE. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, page 460–467, New York, NY , USA,

  4. [4]

    DOI: 10.1145/62212.62257

    Association for Computing Machinery. DOI: 10.1145/62212.62257. [CG04] D. Collins and N. Gisin. A relevant two qubit Bell inequality inequivalent to the CHSH inequality. Journal of Physics A: Mathematical and General, 37(5): 1775–1787,

  5. [5]

    [CHTW04] R

    DOI: 10.1103/PhysRevLett.23.880. [CHTW04] R. Cleve, P. Høyer, B. Toner, and J. Watrous. Consequences and limits of nonlocal strategies. In Proceedings. 19th IEEE Annual Conference on Computational Complex- ity (CCC 04), pages 236–249,

  6. [6]

    Investigating the Effectiveness of Representations Based on Pretrained Transformer-based Language Models in Active Learning for Labelling Text Datasets

    DOI: 10.1109/CCC.2004.1313847. [CLS17] R. Cleve, L. Liu, and W. Slofstra. Perfect commuting-operator strategies for linear system games. Journal of Mathematical Physics, 58(1),

  7. [7]

    Cleve and R

    41 [CM14] R. Cleve and R. Mittal. Characterization of binary constraint system games. In J. Es- parza, P. Fraigniaud, T. Husfeldt, and E. Koutsoupias, editors,Automata, Languages, and Programming, ICALP 2014, pages 320–331. Springer Berlin Heidelberg,

  8. [8]

    [CM25] E

    DOI: 10.1007/978-3-662-43948-7_27. [CM25] E. Culf and K. Mastel. RE-completeness of entangled constraint satisfaction problems. In 2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS), pages 2194–2230,

Show all 29 references
  1. [9]

    [CMS24] E

    DOI: 10.1109/FOCS63196.2025.00116. [CMS24] E. Culf, H. Mousavi, and T. Spirig. Approximation algorithms for noncommutative CSPs. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 920–929,

  2. [10]

    [CSUU08] R

    DOI: 10.1109/FOCS61266.2024.00061. [CSUU08] R. Cleve, W. Slofstra, F. Unger, and S. Upadhyay. Perfect parallel repetition theorem for quantum XOR proof systems. Computational Complexity, 17(2): 282–299,

  3. [11]

    [DFN+25] Y

    Online: https://arxiv.org/abs/2603.14746. [DFN+25] Y . Dong, H. Fu, A. Natarajan, M. Qin, H. Xu, and P. Yao. The computational advantage of MIP* vanishes in the presence of noise. Journal of the ACM, 72(6): 1–78,

  4. [12]

    [Fro81] M

    DOI: 10.1142/S0129055X12500122. [Fro81] M. Froissart. Constructive generalization of Bell’s inequalities. Il Nuovo Cimento B (1971-1996), 64(2): 241–251,

  5. [13]

    [JJUW11] R

    DOI: 10.1145/502090.502098. [JJUW11] R. Jain, Z. Ji, S. Upadhyay, and J. Watrous. QIP = PSP ACE. Journal of the ACM, 58(6): 30,

  6. [14]

    [JNV+20] Z

    DOI: 10.1145/2049697.2049704. [JNV+20] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen. MIP∗= RE,

  7. [15]

    [KMV22] I

    arXiv: 2001.04383. [KMV22] I. Klep, V . Magron, and J. V olˇciˇc. Optimization over trace polynomials. Annales Henri Poincaré, 23(1): 67–100,

  8. [16]

    42 [Mer90] N

    arXiv: 2510.07162. 42 [Mer90] N. D. Mermin. Simple unified form for the major no-hidden-variables theorems. Physical Review Letters, 65(27): 3373–3376,

  9. [17]

    [MNY22] H

    DOI: 10.1103/PhysRevLett.65.3373. [MNY22] H. Mousavi, S. S. Nezhadi, and H. Yuen. Nonlocal games, compression theorems, and the arithmetical hierarchy. In 51st Annual ACM Symposium on Theory of Computing— STOC 2019, pages 1–11,

  10. [18]

    [MS24] K

    DOI: 10.1145/3519935.3519949. [MS24] K. Mastel and W. Slofstra. Two prover perfect zero knowledge for MIP∗. In Proceed- ings of the 56th Annual ACM Symposium on Theory of Computing (STOC 2024), pages 991–1002,

  11. [19]

    [MS25] H

    DOI: 10.1145/3618260.3649702. [MS25] H. Mousavi and T. Spirig. A quantum unique games conjecture. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025), pages 76–1. Schloss Dagstuhl– Leibniz-Zentrum für Informatik,

  12. [20]

    [NW19] A

    DOI: 10.4230/LIPIcs.ITCS.2025.76. [NW19] A. Natarajan and J. Wright. Neexp is contained in mip. In 2019 IEEE 60th annual symposium on foundations of computer science (FOCS), pages 510–518. IEEE,

  13. [21]

    [PNA10] S

    DOI: 10.1016/0375-9601(90)90172-K. [PNA10] S. Pironio, M. Navascués, and A. Acin. Convergent relaxations of polynomial op- timization problems with noncommuting variables. SIAM Journal on Optimization, 20(5): 2157–2180,

  14. [22]

    [Slo19] W

    DOI: 10.1063/1.3652924. [Slo19] W. Slofstra. The set of quantum correlations is not closed. Forum of Mathematics, Pi, 7: e1,

  15. [23]

    43 [Slo20] W

    DOI: 10.1017/fmp.2018.3. 43 [Slo20] W. Slofstra. Tsirelson’s problem and an embedding theorem for groups arising from non-local games. J. Amer. Math. Soc., 33(1): 1–56,

  16. [24]

    [Tsi87] B

    DOI: 10.1090/jams/929. [Tsi87] B. Tsirelson. Quantum analogues of the Bell inequalities. the case of two spatially separated domains. Journal of Soviet Mathematics, 36(4): 557–570,

  17. [25]

    [TSSW00] L

    Online: https://www.tau.ac.il/~tsirel/download/qbell87.html. [TSSW00] L. Trevisan, G. B. Sorkin, M. Sudan, and D. P. Williamson. Gadgets, approximation, and linear programming. SIAM Journal on Computing, 29(6): 2074–2097,

  18. [26]

    [TV25] A

    DOI: 10.1137/S0097539797328847. [TV25] A. Taller and T. Vidick. Approximating the quantum value of anLCS game is RE-hard,

  19. [27]

    Preprint

    Online: https://arxiv.org/abs/2507.22444. Preprint. [Vid22] T. Vidick. Almost synchronous quantum correlations.Journal of Mathematical Physics, 63(2),

  20. [28]

    [Weh06] S

    DOI: 10.1063/5.0056512. [Weh06] S. Wehner. Entanglement in interactive proof systems with binary answers. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), volume 3884 LNCS,

  21. [29]

    DOI: 10.1007/11672142_12. 44

Pith tools

Reviewed July 9, 2026 · model on record in the stance chip above.