Quantum soundness of testing tensor codes
Abstract
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.
Additional Information
© 2021 IEEE. We thank the anonymous reviewers for their feedback. We thank William Slofstra and Vern Paulsen for their explanations regarding synchronous strategies. Z.l. was supported by Australian Research Council (DP200100950), and conducted this work while at the University of Technology, Sydney. T.V. was supported by MURI Grant FA9550-18-1-0161, NSF QLCI Grant OMA-2016245, and the IQIM, an NSF Physics Frontiers Center (NSF Grant PHY-1125565) with support of the Gordon and Betty Moore Foundation (GBMF-12500028). H.Y. was supported by an NSERC Discovery Grant, a Google Research Award, and AFOSR award FA9550-21-1-0040.Attached Files
Submitted - 2111.08131.pdf
Files
| Name | Size | Download all |
|---|---|---|
|
md5:d69e8d7172a98bb00b02830fac48be90
|
735.7 kB | Preview Download |
Additional details
- Eprint ID
- 113223
- Resolver ID
- CaltechAUTHORS:20220202-191902193
- DP200100950
- Australian Research Council
- FA9550-18-1-0161
- Air Force Office of Scientific Research (AFOSR)
- OMA-2016245
- NSF
- Institute for Quantum Information and Matter (IQIM)
- PHY-1125565
- NSF
- GBMF-12500028
- Gordon and Betty Moore Foundation
- Natural Sciences and Engineering Research Council of Canada (NSERC)
- FA9550-21-1-0040
- Air Force Office of Scientific Research (AFOSR)
- Created
-
2022-02-02Created from EPrint's datestamp field
- Updated
-
2022-04-05Created from EPrint's last_modified field
- Caltech groups
- Institute for Quantum Information and Matter