Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Quantum soundness of testing tensor codes
 
conference paper

Quantum soundness of testing tensor codes

Ji, Zhengfeng
•
Natarajan, Anand
•
Vidick, Thomas  orcid-logo
Show more
2022
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

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.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/FOCS52979.2021.00064
Scopus ID

2-s2.0-85127148295

Author(s)
Ji, Zhengfeng

Tsinghua University

Natarajan, Anand

Massachusetts Institute of Technology

Vidick, Thomas  orcid-logo

California Institute of Technology

Wright, John

The University of Texas at Austin

Yuen, Henry

Columbia

Date Issued

2022

Publisher

IEEE Computer Society

Published in
2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)
ISBN of the book

9781665420556

Book part number

2022-February

Volume

2022

Start page

586

End page

597

Subjects

locally testable codes

•

low-degree test

•

quantum interactive proofs

•

Tensor codes

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
Event nameEvent acronymEvent placeEvent date
62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS)

ELECTR NETWORK

2022-02-07 - 2022-02-07

FunderFunding(s)Grant NumberGrant URL

Google

AFOSR

FA9550-21-1-0040

MURI

FA9550-18-1-0161

Show more
Available on Infoscience
November 21, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/256157
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés