Approximating the quantum value of an LCS game is RE-hard

This paper generalizes Håstad's long-code test to entangled provers and, by combining it with recent results establishing $\MIP^*=\RE$, proves that approximating the quantum value of a specific linear constraint satisfaction (LCS) game is RE-hard.

The Gist

The Big Picture: The Ultimate "Impossible" Puzzle

Imagine you are a judge trying to solve a mystery. You have two suspects (let's call them Alice and Bob) who are in separate rooms and cannot talk to each other. You ask them questions, and they give answers. Your goal is to figure out if they are telling the truth or if they are cheating by having a secret plan.

In the world of computer science, this is called a Nonlocal Game.

• Classical Suspects: They can only share a secret notebook written before the game starts.
• Quantum Suspects: They can share a "magic" entangled state (like a pair of dice that always roll the same number, no matter how far apart they are). This allows them to coordinate their answers in ways that seem impossible to classical physics.

The Main Discovery:
This paper proves that if you try to figure out the best possible score the Quantum Suspects can get in a specific type of puzzle (called an LCS Game), it is impossible for any computer to solve it perfectly.

In fact, it's not just "hard" (like a difficult Sudoku); it is RE-Hard.

• What is RE? Think of "RE" (Recursively Enumerable) as the class of problems that include the famous "Halting Problem." The Halting Problem asks: "Will this computer program run forever, or will it eventually stop?" Alan Turing proved in the 1930s that no computer can answer this question for every possible program.
• The Result: The authors show that figuring out the quantum score of this game is just as impossible as solving the Halting Problem. If you could build a computer to solve this game, you could also solve the Halting Problem, which means you could break the fundamental laws of computation.

---

The Metaphor: The "Long-Code" Lie Detector

To prove this, the authors had to upgrade an old tool used to catch classical liars so it could catch quantum liars.

1. The Old Tool: Håstad's Long-Code Test

Imagine a detective (the Verifier) trying to catch a liar. The detective asks the suspect to recite a long list of numbers (a "Long Code").

• The Trick: The detective asks three slightly different questions about the list. If the suspect is telling the truth, the answers must fit a specific mathematical pattern (like a linear equation).
• The Catch: If the suspect is lying, the answers will usually clash.
• The Problem: This old test was designed for people using normal logic (Classical Provers). The authors asked: "Does this test still work if the suspects are using quantum magic?"

2. The Upgrade: The Quantum Lie Detector

The authors (Aviv Taller and Thomas Vidick) took Håstad's test and reinforced it. They proved that even if Alice and Bob use quantum entanglement (the "magic dice"), they still cannot cheat the test effectively.

• The Analogy: Imagine the suspects are trying to coordinate their answers using a secret quantum signal. The authors showed that the "Long-Code Test" is so sensitive that even quantum magic cannot hide the fact that they are lying. If they try to cheat, the test catches them with high probability.

---

The Three Pillars of the Proof

To get from "Quantum Liars" to "Impossible to Solve," the authors combined three massive pieces of a puzzle:

1. The Quantum Lie Detector (Their Contribution):
   They proved the Long-Code test works against quantum suspects. This is the "new" part of the paper. They showed that the test remains "sound" (it catches liars) even in the quantum world.

2. The "Halting Problem" Connection (Dong et al.):
   Another group of scientists recently proved that if you give quantum suspects enough time and space, they can solve any problem that is solvable by a computer (including the Halting Problem). This is the MIP = RE* result.

   • Analogy: Think of this as finding a "Universal Key" that can open any locked door in the universe of computation, provided you have quantum suspects.

3. The "Parallel Repetition" (Dinur et al.):
   This is a rule that says: "If you play a game many times in a row, the chance of cheating on all of them drops to almost zero."

   • Analogy: If you flip a coin and get heads, it's luck. If you get heads 1,000 times in a row, you are definitely cheating. The authors used this to amplify the "lie detection" power.

Putting it together:

1. Take the Halting Problem (which is impossible to solve).
2. Turn it into a game where quantum suspects try to win (using the Dong et al. result).
3. Use the Parallel Repetition to make the game very strict.
4. Use the new Quantum Lie Detector to translate that game into an LCS Game (the specific puzzle the paper focuses on).
5. Conclusion: If you could calculate the winning score of this LCS Game, you could solve the Halting Problem. Since the Halting Problem is impossible, calculating the LCS score is also impossible.

---

Why Does This Matter?

You might ask, "Who cares about a math puzzle with Alice and Bob?"

This result connects two very different worlds:

1. Computer Science (Complexity Theory): It tells us the absolute limits of what computers can calculate.
2. Quantum Physics & Math (Group Theory): It touches on a deep mystery about "Non-Hyperlinear Groups."

The "Non-Hyperlinear Group" Mystery:
There is a famous open question in math: "Do there exist certain weird mathematical structures (groups) that cannot be approximated by finite matrices?"

• If the answer is Yes, it means there are quantum strategies that are fundamentally different from anything we can simulate on a computer.
• The authors show that if we could solve their LCS game perfectly (with zero error), we would prove these weird groups exist.
• Since we can't solve the game (it's RE-hard), we are stuck in a limbo where we can't easily prove or disprove the existence of these exotic mathematical objects.

Summary in One Sentence

The authors built a super-sensitive "quantum lie detector" and used it to prove that calculating the best possible score for a specific quantum puzzle is as impossible as predicting whether a computer program will ever stop running, effectively linking the limits of quantum physics to the deepest unsolved problems in mathematics.

Technical Summary

1. Problem Statement

The paper addresses the computational complexity of approximating the quantum value (maximum winning probability using entangled provers) of Linear Constraint System (LCS) games.

• Context: In a seminal 2001 result, Håstad proved that approximating the classical value of LCS games is NP-hard. This was achieved by reducing 3SAT to a "long-code test" involving linear equations over $\mathbb{F}_2$.
• The Quantum Challenge: With the recent breakthrough establishing $MIP^* = RE$ (the class of languages decidable by multi-prover interactive proofs with entangled provers equals the class of recursively enumerable languages), it became known that approximating the quantum value of general nonlocal games is RE-hard. However, it remained an open question whether this hardness holds specifically for LCS games (games where the verifier checks linear equations) with two provers.
• Goal: The authors aim to prove that approximating the quantum value of an LCS game is RE-hard, specifically showing that the class $LIN\text{-}MIP^*_{1-\varepsilon, s} = RE$ for certain constants.

2. Methodology

The authors construct a reduction from the Halting Problem to an LCS game by generalizing Håstad's classical long-code test to the quantum setting. The proof strategy involves adapting three classical components of Håstad's proof to the quantum realm:

1. The Long-Code Test (Main Contribution):

   • The authors generalize Håstad's long-code test, which relies on a "distorted linear test" on three bits.
   • They prove that this test remains complete (if a solution exists, quantum provers can win with high probability) and sound (if no solution exists, even entangled provers cannot win with high probability).
   • Technical Innovation: The proof requires handling entangled provers (quantum strategies) rather than classical randomized algorithms. This involves analyzing the behavior of binary observables (unitary involutions) acting on a shared entangled state. A key technical hurdle is that the standard "folding" and "conditioning" techniques used in classical proofs must be adapted to preserve the algebraic structure of quantum operators (specifically, ensuring the observables commute or analyzing their non-commutativity via trace inequalities).

2. Replacement of the PCP Theorem:

   • Instead of the classical PCP theorem, the authors utilize the result by Dong et al. [Da22] that $MIP^* = RE$ with constant-length answers. This provides a starting point: a protocol for the Halting Problem where the verifier asks polynomial-length questions and receives constant-length answers.

3. Replacement of Parallel Repetition:

   • To amplify the soundness gap, the authors employ the parallel repetition theorem for entangled projection games by Dinur, Steurer, and Vidick [DSV15].
   • They first map the general $MIP^*$ protocol (which may not be a projection game) to a projection game (where Bob's winning answer is uniquely determined by Alice's). This is done using a standard projection technique, followed by the parallel repetition theorem to exponentially suppress the winning probability of NO instances.

4. Integration via Boolean Constraint Systems (BCS):

   • The authors leverage a recent observation by Culf and Mastel [CM25] that reductions from the Halting Problem can be viewed as reductions to Boolean Constraint System (BCS) games.
   • They then construct a specific reduction from these BCS games to Linear Constraint System (LCS) games. This step is non-trivial because general BCS games cannot always be algebraically mapped to LCS games while preserving the structure of the associated $*$-algebras (a barrier to achieving perfect completeness).

3. Key Contributions

• Quantum Soundness of the Long-Code Test: The primary technical contribution is the proof that Håstad's long-code test is sound against entangled provers. They show that if the quantum winning probability of the test is close to 1, the provers must possess a strategy that correlates with a valid assignment to the underlying linear system.
• Hardness for Two-Prover LCS Games: The paper establishes that approximating the quantum value of LCS games with two provers is RE-hard. This is significant because previous hardness results for $MIP^*$ often required three or more provers or did not restrict the game type to linear equations.
• Soundness Parameters: The authors derive specific soundness parameters.
  • For classical provers, the soundness threshold is $5/6$.
  • For entangled provers, the derived soundness bound is $35/36$.
  • The result holds for completeness $1-\varepsilon$ and soundness $s$ (where $1/2 < s < 1$) for sufficiently small $\varepsilon$.
• Algebraic Obstacles to Perfect Completeness: The paper discusses why achieving perfect completeness (winning probability exactly 1 for YES instances) is difficult. It highlights an algebraic obstruction: general BCS games do not always admit a $*$-morphism into the algebra of an LCS game. This suggests that proving $LIN\text{-}MIP^*_{1, s} = RE$ (perfect completeness) would imply the existence of non-hyperlinear groups, a major open problem in operator algebras.

4. Main Results

• Theorem: There exist constants $1 > s > 1/2$ and for every sufficiently small $\varepsilon > 0$, the class $LIN\text{-}MIP^*_{1-\varepsilon, s}$ equals $RE$.
  • Here, $LIN$ refers to the linearity of the verifier's predicate (the game is an LCS game).
  • This implies that it is RE-hard to distinguish between an LCS game where the quantum value is at least $1-\varepsilon$ and one where it is at most $s$.
• Corollary: The problem of approximating the quantum value of an LCS game is undecidable (in the sense that the gap problem is RE-hard).

5. Significance

• Bridging Complexity and Operator Algebras: The result deepens the connection between quantum complexity theory ($MIP^*$) and the representation theory of groups (via the non-hyperlinear group conjecture). It shows that the difficulty of approximating LCS games is intimately tied to the existence of exotic mathematical objects (non-hyperlinear groups).
• Two-Prover Limitation: By achieving this with only two provers, the authors simplify the model compared to previous $MIP^*$ results that often relied on three provers to simplify algebraic manipulations. This makes the hardness result more robust and applicable to a wider range of quantum interactive proof scenarios.
• Limitations on Perfect Completeness: The paper provides strong evidence that achieving perfect completeness for LCS games with entangled provers is likely impossible unless major breakthroughs occur in group theory (proving non-hyperlinear groups exist). This sets a clear boundary for what can be achieved with current algebraic techniques.
• Technical Advancement: The extension of the long-code test to the quantum setting provides new tools for analyzing entangled strategies in nonlocal games, specifically handling the "folding" and "conditioning" of observables in a way that respects quantum mechanics.

In summary, Taller and Vidick successfully generalize Håstad's classical hardness proof to the quantum domain, proving that even restricted to linear equations and two entangled provers, the problem of determining the winning probability is as hard as the Halting Problem.