tilted-xor-games

name	tilted-xor-games
description	Tilted XOR games methodology — variant of XOR nonlocal games where winning condition depends on XOR plus one output bit. Shows quantum value approximation is RE-complete, dramatically increasing expressive power over standard XOR games.

Tilted XOR Games

Description

Tilted XOR games extend the standard XOR nonlocal game model by allowing the winning condition to additionally depend on only one player's output bit. This seemingly minor change dramatically increases computational complexity: while standard XOR games are polynomial-time approximable, tilted XOR games are RE-complete. Extends to succinct versions with polynomial-length question strings.

arXiv: 2607.06876 Authors: Richard Cleve, Eric Culf, Aviv Taller

Activation Keywords

• tilted XOR games
• binary nonlocal games hardness
• XOR game quantum value
• nonlocal game computational complexity
• RE-complete quantum games
• linear system games reduction
• 量子博弈 复杂性
• 倾斜XOR博弈
• quantum game complexity

Core Concepts

1. Tilted XOR Game Definition

• Standard XOR game: winning condition depends only on XOR of two output bits
• Tilted XOR game: winning condition additionally depends on one output bit
• This extension is quantum-sound (reduction preserves quantum properties)

2. Complexity Separation

• Classical: Both XOR and tilted XOR games are NP-complete to approximate (Håstad 2001)
• Quantum: XOR games = polynomial time; Tilted XOR games = RE-complete
• The distinction is dramatic only in the quantum setting

3. Reduction from Linear System Games

• Classical: Håstad reduces from linear systems to XOR games
• Quantum: Same reduction is quantum-sound when applied to tilted XOR games
• Extends to succinct versions with polynomial-length binary string questions

Usage Patterns

Pattern 1: Complexity Analysis of Nonlocal Games

When analyzing the computational complexity of quantum nonlocal games:

1. Determine if game is standard XOR or tilted variant
2. Check if winning condition depends on individual output bits
3. Apply polynomial-time algorithm for standard XOR
4. Recognize RE-completeness for tilted variants

Pattern 2: Quantum-Classical Complexity Gap

When demonstrating quantum-classical complexity separations:

1. Identify games where classical approximation has same complexity
2. Show quantum approximation complexity differs dramatically
3. Use as proof technique for quantum advantage in computation

Pattern 3: Succinct Game Extensions

For games with long question strings:

1. Generate questions via polynomial-time verifier
2. Apply tilted XOR framework to succinct versions
3. Complexity remains RE-complete even for succinct games

Mathematical Framework

Standard XOR Game

Winning condition: a ⊕ b = f(x, y) where a,b are outputs, x,y are inputs

Tilted XOR Game

Winning condition: a ⊕ b = f(x, y, a) or a ⊕ b = f(x, y, b)

• Additional dependence on one output bit
• This single change makes quantum value RE-complete

Complexity Classification

• Classical approximation: NP-complete (both XOR and tilted)
• Quantum approximation: P-time (XOR), RE-complete (tilted)

Instructions for Agents

Step 1: Identify Game Type

• Examine winning condition structure
• Check dependence on individual output bits
• Classify as standard XOR or tilted variant

Step 2: Apply Correct Complexity Framework

• Standard XOR: use polynomial-time approximation algorithm
• Tilted XOR: recognize RE-completeness, no efficient approximation

Step 3: Reduction Verification

• For hardness proofs: reduce from linear system games
• Verify quantum-soundness of reduction
• Extend to succinct versions if needed

Error Handling

Misclassification

• If game appears XOR-like but has individual bit dependence → tilted
• Default to harder complexity class when uncertain

Succinct vs Non-Succinct

• Both have same RE-completeness for tilted games
• Succinct version: questions are poly-length strings generated by verifier

Related Skills

• quantum-game-theory-economics - quantum game theory applications
• quantum-cognition - quantum models of decision making
• quantum-probability-statistics - quantum probability framework
• no-signaling-quantum-games-operator-algebra - operator algebra for quantum games

Resources

• arXiv: 2607.06876 - "XOR Games at Full Tilt: The Hardness of Binary Nonlocal Games"
• Håstad (J. ACM, 2001) - classical NP-completeness of XOR games