Quantum soundness of testing tensor codes
A locally testable code is an error-correcting code that admits very efficient probabilistic tests of membership. Tensor codes provide a simple family of combinatorial constructions of locally testable codes that generalize the family of Reed-Muller codes. The natural test for tensor codes, the axis-parallel line vs. point test, plays an essential role in constructions of probabilistically checkable proofs. We analyze the axis-parallel line vs. point test as a two-prover game and show that the test is sound against quantum provers sharing entanglement. Our result implies the quantum-soundness of the low individual degree test, which is an essential component of the MIP∗ = RE theorem. Our proof also generalizes to the infinite-dimensional commuting-operator model of quantum provers.
2-s2.0-85127148295
Tsinghua University
Massachusetts Institute of Technology
California Institute of Technology
The University of Texas at Austin
Columbia
2022
9781665420556
2022-February
2022
586
597
REVIEWED
OTHER
| Event name | Event acronym | Event place | Event date |
ELECTR NETWORK | 2022-02-07 - 2022-02-07 | ||
| Funder | Funding(s) | Grant Number | Grant URL |
AFOSR | FA9550-21-1-0040 | ||
MURI | FA9550-18-1-0161 | ||
| Show more | |||