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

Aviv Taller and Thomas Vidick · 2025

Read Approximating the quantum value of an LCS game is RE-hard by Aviv Taller and Thomas Vidick (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-22444.txt.

Introduction

Aviv Taller and Thomas Vidick prove that even roughly estimating the quantum power of a certain family of games is as hard as the hardest problems computers can pose. The games, called LCS games, ask two players to satisfy a system of linear equations. Quantum players sharing entanglement can sometimes beat classical limits, and the best quantum score is called the game's quantum value.

The team extends a classic testing method from computer science and shows it stays sound even against entangled players. Chaining that result to a landmark theorem about quantum interactive proofs, they show that telling a near-perfect quantum score from a mediocre one is RE-hard. That class covers problems with no general solution procedure at all. A small strengthening of their result, they note, would settle a deep open question about groups in mathematics.

Catalog record

CREATORAviv Taller and Thomas Vidick
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE67 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2507-22444

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Approximating the quantum value of an LCS game is RE-hard Aviv Taller and Thomas Vidick Abstract . We generalize Håstad’s long-code test for projection games and show that it remains complete and sound against entangled provers. Combined with a result of Dong et al. [ Da22 ] , which establishes that MIP ∗ = RE \text{MIP}^{*}=\text{RE} with constant-length answers, we derive that LIN-MIP 1 − ϵ , s ∗ = RE \text{LIN-MIP}^{*}_{1-\epsilon,s}=\text{RE} , for some 1 / 2 < s < 1 1/2<s<1 and for every sufficiently small ϵ > 0 \epsilon>0 , where LIN refers to linearity (over 𝔽 2 \mathbb{F}_{2} ) of the verifier predicate. Achieving the same result with ϵ = 0 \epsilon=0 would imply the existence of a non-hyperlinear group. 1. Introduction In a seminal result [ Hås01 ] , Håstad established that the problem of approximating the maximum winning probability of two classical provers in the nonlocal game associated to a linear constraint system (LCS) is NP-hard. In this nonlocal game, or two-prover one-round interactive protocol, the verifier sends to one prover (Alice) a linear equation out of the system and one of the variables in that equation to the other prover (Bob). Unaware of the question posed to the other prover, each participant is required to provide an assignment for their respective variables. The provers, or players, win if Alice’s assignment satisfies the equation and agrees with Bob’s assignment for the selected variable. Håstad’s proof of hardness of approximation for the maximum winning probability in an LCS game, referred to as its classical game value , consists of three main components. The first component involves the association of a 3SAT formula with a long-code test, as constructed in [ Hås01 ] , which has been demonstrated to possess (imperfect) completeness and soundness. At the heart of the long-code test lies a distorted linear test on three bits. This results in the formulation of a linear system, and the subsequent hardness result is derived through its combination with the other two components, specifically the PCP theorem [ AS98 , Aro+98 ] and Raz’s parallel repetition theorem [ Raz98 ] . It is noted that the preceding discussion pertains to classical provers; specifically, these are two randomized algorithms which are permitted to share a mutual random seed. In this work, we establish that approximating the maximum winning probability of quantum provers in an LCS game, referred to as its quantum game value , is RE-hard. By quantum provers, we mean provers who are allowed to perform measurements on a finite dimensional shared entangled state. In other words, we show that \text{LIN-MIP}^{*}_{1-\epsilon,s}=\text{RE} for certain 1>s>1/2 and for every sufficiently small \epsilon>0 . In order to obtain this hardness result, we needed quantum analogs for the three classical components of the proof. The analog for the first component is provided in this work. Namely, we show that the long-code test is complete and sound against quantum provers. This is our main technical contribution. In place of the PCP theorem, we employ the equivalence of the classes \text{MIP}^{*}=\text{RE} , as formulated by Dong et al. [ Da22 ] . In that work, the authors refine the reduction of the halting problem as established in [ Ji+21 ] , guaranteeing that the resulting \text{MIP}^{*} protocols use polynomial length questions while maintaining answers of constant length. Finally, in lieu of the classical parallel repetition theorem, we utilize the parallel repetition theorem for entangled projection games by Dinur et al. [ DSV15 ] . Loosely speaking, projection games refer to games in which the response of Bob, which leads to a win, is uniquely determined by Alice’s response. Furthermore, a fourth component that we needed and which allowed us to combine the other three is an observation provided by [ CM25 ] . This observation states, roughly, that the reduction of [ Da22 ] gives rise to a reduction of the halting problem to projection Boolean constraint system games with equations of constant length. Informally, a Boolean constraint system (BCS) is defined as any system with binary equations. In the aforementioned reduction, YES instances are mapped to BCSs admitting a special type of perfect quantum strategies, while NO instances are sent to BCSs with quantum value bounded away from 1. We discuss the soundness parameter that is obtained through our reduction. The linear system induced by the test consists exclusively of equations that involve exactly three variables. Since any such system admits an assignment that satisfies at least half of the equations, this implies a lower bound of (2+1/2)/3=5/6 on the classical winning probability in the corresponding LCS game. Indeed, Bob may respond using such an assignment, and in at most half of the equations, Alice needs to modify at most one variable to ensure satisfiability. Following the analysis in [ Hås01 ] , this lower bound is in fact tight for classical provers. In contrast, the soundness bound we obtain for entangled provers is 35/36 , representing a square loss relative to the classical threshold. We do not know whether this bound is tight. Determining the minimal winning probability for entangled strategies in such LCS games, and whether it coincides with or exceeds the classical value, is left for future work. The following is a brief discussion concerning the imperfect completeness of the main result. This property is exhibited by both the original reduction from 3SAT in [ Hås01 ] and our reduction from the halting problem. In both cases, this is a direct consequence of introducing noise into the linearity test, which is a necessary component of the construction. However, beyond this, there are additional barriers to achieving perfect completeness using our methods. From the computational point of view, an efficient reduction with perfect completeness for classical strategies would imply \text{P}=\text{NP} , which is widely believed to be false. On top of that, there are also algebraic obstacles, which we now describe in more detail. Each BCS game B can be associated with a * -algebra, denoted {\mathcal{A}}(B) . Various notions of satisfiability for the game B , that is, different types of perfect strategies with winning probability 1, correspond to different types of * -representations of {\mathcal{A}}(B) . It was shown in [ PS23 ] that for LCS games, certain types of satisfiability are equivalent at the algebraic level, whereas this equivalence fails for general BCS games. In particular, it is not possible, in general, to associate with every BCS B an LCS B^{\prime} such that {\mathcal{A}}(B) admits a * -morphism into {\mathcal{A}}(B^{\prime}) . This fact presents a significant obstacle to reducing the known \text{MIP}^{*} protocols for the halting problem to LCS games with perfect completeness. Indeed, these protocols admit a presentation as BCS protocols. As a result, any attempt to generically reduce such protocols to LCS protocols, in a way that induces a * -embedding of the associated algebras, is ruled out by the aforementioned algebraic constraint. Further details on reductions of the halting problem to BCS protocols can be found in [ MS24 , CM25 , Fri20 , PS23 ] . One main motivation for pursuing perfect completeness lies in its connection to the longstanding open question concerning the existence of non-hyperlinear groups. Roughly speaking, these groups

Read the complete text