A Caltech Library Service

Quantum soundness of testing tensor codes

Ji, Zhengfeng and Natarajan, Anand and Vidick, Thomas and Wright, John and Yuen, Henry (2022) Quantum soundness of testing tensor codes. In: 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 586-597. ISBN 978-1-6654-2056-3.

[img] PDF (7 Feb 2022) - Submitted Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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.

Item Type:Book Section
Related URLs:
URLURL TypeDescription Paper
Ji, Zhengfeng0000-0002-7659-3178
Natarajan, Anand0000-0003-3648-3844
Vidick, Thomas0000-0002-6405-365X
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.
Group:Institute for Quantum Information and Matter
Funding AgencyGrant Number
Australian Research CouncilDP200100950
Air Force Office of Scientific Research (AFOSR)FA9550-18-1-0161
Institute for Quantum Information and Matter (IQIM)UNSPECIFIED
Gordon and Betty Moore FoundationGBMF-12500028
Natural Sciences and Engineering Research Council of Canada (NSERC)UNSPECIFIED
Air Force Office of Scientific Research (AFOSR)FA9550-21-1-0040
Subject Keywords:codes; locally testable codes; low-degree test; quantum interactive proofs
Record Number:CaltechAUTHORS:20220202-191902193
Persistent URL:
Official Citation:Z. Ji, A. Natarajan, T. Vidick, J. Wright and H. Yuen, "Quantum soundness of testing tensor codes," 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 586-597, doi: 10.1109/FOCS52979.2021.00064
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:113223
Deposited By: George Porter
Deposited On:02 Feb 2022 23:41
Last Modified:05 Apr 2022 20:20

Repository Staff Only: item control page