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. Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes
 
conference paper

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes

Dinur, Irit
•
Lin, Ting-Chun
•
Vidick, Thomas  orcid-logo
October 27, 2024
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024)
65th Annual Symposium on Foundations of Computer Science

We introduce a high-dimensional cubical complex, for any dimension t∈N, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case t=2), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes h1,…,ht as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. For t=4 our construction gives a new family of “almost-good” quantum LTCs - with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.

  • Details
  • Metrics
Type
conference paper
DOI
10.1109/FOCS61266.2024.00031
Author(s)
Dinur, Irit
Lin, Ting-Chun
Vidick, Thomas  orcid-logo

Weizmann Institute of Science

Date Issued

2024-10-27

Publisher

IEEE

Published in
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS 2024)
DOI of the book
https://doi.org/10.1109/FOCS61266.2024
Published in
2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS)
Start page

379

End page

385

Editorial or Peer reviewed

REVIEWED

Written at

OTHER

EPFL units
Non-EPFL  
Event nameEvent acronymEvent placeEvent date
65th Annual Symposium on Foundations of Computer Science

FOCS 2024

Chicago, United States

2024-10-27 - 2024-10-30

FunderGrant Number

ERC

772839

Available on Infoscience
November 12, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/255808
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