Quantum Locally Testable Code with Constant Soundness

Andrew Cross; Zhiyang He; Anand Natarajan; Mario Szegedy; Guanyu Zhu

doi:10.22331/q-2024-10-18-1501

Quantum Locally Testable Code with Constant Soundness

Andrew Cross¹, Zhiyang He^1,2, Anand Natarajan³, Mario Szegedy⁴, and Guanyu Zhu¹

¹IBM Quantum, IBM T.J. Watson Research Center, Yorktown Heights, NY, United States.
²Department of Mathematics, Massachusetts Institute of Technology.
³Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology.
⁴Rutgers, The State University of New Jersey, New Brunswick, NJ, United States.

Published:	2024-10-18, volume 8, page 1501
Eprint:	arXiv:2209.11405v3
Doi:	https://doi.org/10.22331/q-2024-10-18-1501
Citation:	Quantum 8, 1501 (2024).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

In this paper, we present two constructions of quantum locally testable codes (QLTC) with constant soundness. In the first approach, we introduce an operation called check product, and show how this operation gives rise to QLTCs of constant soundness, constant rate, and distance scaling with locality. In the second approach, we consider hypergraph product of a quantum code and a classical repetition code, and observe a special case in which the soundness of component codes is preserved. This insight leads us to construct QLTCs of constant soundness, scalable rate and distance, and constant average locality. Our work marks a step towards constructing QLTCs of high soundness and distance, which would give a different construction to the No Low-Energy Trivial States (NLTS) theorem.

► BibTeX data

@article{Cross2024quantumlocally,
  doi = {10.22331/q-2024-10-18-1501},
  url = {https://doi.org/10.22331/q-2024-10-18-1501},
  title = {Quantum {L}ocally {T}estable {C}ode with {C}onstant {S}oundness},
  author = {Cross, Andrew and He, Zhiyang and Natarajan, Anand and Szegedy, Mario and Zhu, Guanyu},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {8},
  pages = {1501},
  month = oct,
  year = {2024}
}

► References

[1] Dorit Aharonov, Itai Arad, and Thomas Vidick, ``Guest column: the quantum PCP conjecture'' SIGACT News 44, 47-79 (2013).
https://doi.org/10.1145/2491533.2491549

[2] Anurag Anshu, Nikolas P. Breuckmann, and Chinmay Nirkhe, ``NLTS Hamiltonians from Good Quantum Codes'' (2023).
https://doi.org/10.1145/3564246.3585114

[3] Dorit Aharonovand Lior Eldar ``Quantum Locally Testable Codes'' SIAM Journal on Computing 44, 1230–1262 (2015).
https://doi.org/10.1137/140975498

[4] Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy, ``Proof verification and the hardness of approximation problems'' 45 (1998).
https://doi.org/10.1145/278298.278306

[5] Nikolas P. Breuckmannand Jens N. Eberhardt ``Balanced Product Quantum Codes'' IEEE Transactions on Information Theory 67, 6653–6674 (2021).
https://doi.org/10.1109/TIT.2021.3097347

[6] M. Blum, M. Luby, and R. Rubinfeld, ``Self-testing/correcting with applications to numerical problems'' Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing 73–83 (1990).
https://doi.org/10.1145/100216.100225

[7] Earl T Campbell ``A theory of single-shot error correction for adversarial noise'' Quantum Science and Technology 4, 025006 (2019).
https://doi.org/10.1088/2058-9565/aafc8f

[8] Irit Dinur, Shai Evra, Ron Livne, Alexander Lubotzky, and Shahar Mozes, ``Locally testable codes with constant rate, distance, and locality'' Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 357–374 (2022).
https://doi.org/10.1145/3519935.3520024

[9] Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, and Thomas Vidick, ``Good Quantum LDPC Codes with Linear Time Decoders'' Proceedings of the 55th Annual ACM Symposium on Theory of Computing 905–918 (2023).
https://doi.org/10.1145/3564246.3585101

[10] Irit Dinur ``The PCP theorem by gap amplification'' J. ACM 54, 12–es (2007).
https://doi.org/10.1145/1236457.1236459

[11] L. Eldarand A. W. Harrow ``Local Hamiltonians Whose Ground States Are Hard to Approximate'' 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS) 427–438 (2017).
https://doi.org/10.1109/FOCS.2017.46

[12] Michael Freedmanand Matthew Hastings ``Quantum Systems on Non-$k$-Hyperfinite Complexes: A Generalization of Classical Statistical Mechanics on Expander Graphs'' Quantum Information and Computation 14 (2013).
https://doi.org/10.26421/QIC14.1-2-9

[13] Mathew B. Hastings ``Weight reduction for quantum codes'' Quant. Inf. Comput. 17, 1307–1334 (2017).
https://doi.org/10.26421/QIC17.15-16-4

[14] Matthew B. Hastings ``Quantum Codes from High-Dimensional Manifolds'' 8th Innovations in Theoretical Computer Science Conference (ITCS 2017) 67, 25:1–25:26 (2017).
https://doi.org/10.4230/LIPIcs.ITCS.2017.25

[15] Matthew B. Hastings, Jeongwan Haah, and Ryan O'Donnell, ``Fiber bundle codes: breaking the $n^{1/2}$ polylog(n) barrier for Quantum LDPC codes'' Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 1276–1288 (2021).
https://doi.org/10.1145/3406325.3451005

[16] Anthony Leverrier, Vivien Londe, and Gilles Zémor, ``Towards local testability for quantum coding'' Quantum 6, 661 (2022).
https://doi.org/10.22331/q-2022-02-24-661

[17] A. Leverrierand G. Zemor ``Quantum Tanner codes'' 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) 872–883 (2022).
https://doi.org/10.1109/FOCS54457.2022.00117

[18] Pavel Panteleevand Gleb Kalachev ``Asymptotically good Quantum and locally testable classical LDPC codes'' Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing 375–388 (2022).
https://doi.org/10.1145/3519935.3520017

[19] Pavel Panteleevand Gleb Kalachev ``Quantum LDPC Codes With Almost Linear Minimum Distance'' IEEE Transactions on Information Theory 68, 213–229 (2022).
https://doi.org/10.1109/TIT.2021.3119384

Cited by

[1] Adam Wills, Ting-Chun Lin, and Min-Hsiu Hsieh, "Tradeoff Constructions for Quantum Locally Testable Codes", IEEE Transactions on Information Theory 71 1, 426 (2025).

[2] Alexander Cowtan, Zhiyang He, Dominic J. Williamson, and Theodore J. Yoder, "Parallel Logical Measurements via Quantum Code Surgery", PRX Quantum 7 2, 020325 (2026).

[3] Victor V. Albert and Philippe Faist, "Handbook of Error-Correcting Codes", arXiv:2606.11484, (2026).

[4] Shouzhen Gu, Eugene Tang, Libor Caha, Shin Ho Choe, Zhiyang He, and Aleksander Kubica, "Single-Shot Decoding of Good Quantum LDPC Codes", Communications in Mathematical Physics 405 3, 85 (2024).

[5] Alexander Cowtan, Zhiyang He, Dominic J. Williamson, and Theodore J. Yoder, "Fast and fault-tolerant logical measurements: Auxiliary hypergraphs and transversal surgery", arXiv:2510.14895, (2025).

[6] Alexander Cowtan, Zhiyang He, Dominic J. Williamson, and Theodore J. Yoder, "Parallel Logical Measurements via Quantum Code Surgery", arXiv:2503.05003, (2025).

[7] Yiming Li, Zimu Li, Zi-Wen Liu, and Quynh T. Nguyen, "Poincaré Duality and Multiplicative Structures on Quantum Codes", arXiv:2512.21922, (2025).

[8] Eric Sabo, Lane G. Gunderman, Benjamin Ide, Michael Vasmer, and Guillaume Dauphinais, "Weight-Reduced Stabilizer Codes with Lower Overhead", PRX Quantum 5 4, 040302 (2024).

[9] Adam Wills, Ting-Chun Lin, and Min-Hsiu Hsieh, "General Distance Balancing for Quantum Locally Testable Codes", arXiv:2305.00689, (2023).

[10] Zhiyang He and Chinmay Nirkhe, "NLTS Hamiltonians from classical LTCs", arXiv:2210.02999, (2022).

[11] Adam Wills, Ting-Chun Lin, and Min-Hsiu Hsieh, "Tradeoff Constructions for Quantum Locally Testable Codes", arXiv:2309.05541, (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-15 04:43:06) and SAO/NASA ADS (last updated successfully 2026-07-14 16:39:15). The list may be incomplete as not all publishers provide suitable and complete citation data.

Could not fetch ADS cited-by data during last attempt 2026-07-15 04:43:06: Cannot retrieve data from ADS due to rate limitations.

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.