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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- 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)
- Abstract: 'titled XOR games' should be 'tilted XOR games' (appears twice in the abstract, last sentence).
- Abstract: 'H{åstad}' should render as 'Håstad' (likely a LaTeX encoding issue in the abstract metadata).
- 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').
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
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
free parameters (2)
- δ (soundness gap) =
≈ 10^-8
- ε (completeness parameter) =
arbitrarily small > 0
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+ε)
- domain assumption MIP* = RE
- standard math Slofstra's XOR game structure theorem (Theorem 2.6)
- standard math Araki-Yamagami inequality for Frobenius norm continuity of operator absolute value
- domain assumption Near-perfect strategies for projection games can be rounded to tracial strategies
invented entities (2)
-
Tilted XOR game
independent evidence
-
Tilted cube game G□
independent evidence
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
Reference graph
Works this paper leans on
-
[1]
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]
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]
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]
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]
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]
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),
work page Pith review arXiv doi:10.1109/ccc.2004.1313847 2004
-
[7]
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,
work page 2014
-
[8]
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
-
[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,
2025 doi
-
[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,
2024 doi
-
[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,
-
[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,
1971 doi
-
[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,
-
[14]
[JNV+20] Z
DOI: 10.1145/2049697.2049704. [JNV+20] Z. Ji, A. Natarajan, T. Vidick, J. Wright, and H. Yuen. MIP∗= RE,
-
[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,
2001 arXiv
-
[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,
-
[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,
2019 doi
-
[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,
2024 doi
-
[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,
2025 doi
-
[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,
2025 doi
-
[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,
-
[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,
-
[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,
2018 doi
-
[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,
-
[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,
-
[26]
[TV25] A
DOI: 10.1137/S0097539797328847. [TV25] A. Taller and T. Vidick. Approximating the quantum value of anLCS game is RE-hard,
-
[27]
Preprint
Online: https://arxiv.org/abs/2507.22444. Preprint. [Vid22] T. Vidick. Almost synchronous quantum correlations.Journal of Mathematical Physics, 63(2),
-
[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,
-
[29]
DOI: 10.1007/11672142_12. 44
Reviewed July 9, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.