Approximating the quantum value of an LCS game is RE-hard
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912993922514944 |
|---|---|
| author | Taller, Aviv Vidick, Thomas |
| author_facet | Taller, Aviv Vidick, Thomas |
| contents | 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. \cite{Dong25}, which establishes that $\MIP^*=\RE$ with constant-length answers, we derive that $\LIN^*_{1-ε,s}=\RE$, for some $1/2< s<1$ and for every sufficiently small $ε>0$, where LIN refers to linearity (over $\mathbb{F}_2$) of the verifier predicate. Achieving the same result with $ε=0$ would imply the existence of a non-hyperlinear group. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_22444 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Approximating the quantum value of an LCS game is RE-hard Taller, Aviv Vidick, Thomas Computational Complexity Mathematical Physics Quantum Physics 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. \cite{Dong25}, which establishes that $\MIP^*=\RE$ with constant-length answers, we derive that $\LIN^*_{1-ε,s}=\RE$, for some $1/2< s<1$ and for every sufficiently small $ε>0$, where LIN refers to linearity (over $\mathbb{F}_2$) of the verifier predicate. Achieving the same result with $ε=0$ would imply the existence of a non-hyperlinear group. |
| title | Approximating the quantum value of an LCS game is RE-hard |
| topic | Computational Complexity Mathematical Physics Quantum Physics |
| url | https://arxiv.org/abs/2507.22444 |