The DOI matches its Crossref record; 28 of the 29 references it cites were found in a registry or an index.
Quantum Tanner codes
Open accessAbstract
Tanner codes are long error correcting codes obtained from short codes and a graph, with bits on the edges and parity-check constraints from the short codes enforced at the vertices of the graph. Combining good short codes together with a spectral expander graph yields the celebrated expander codes of Sipser and Spielman, which are asymptotically good classical LDPC codes. In this work we apply this prescription to the left-right Cayley complex that lies at the heart of the recent construction of a c3locally testable code by Dinur et at. Specifically, we view this complex as two graphs that share the same set of edges. By defining a Tanner code on each of those graphs we obtain two classical codes that together define a quantum code. This construction can be seen as a simplified variant of the Panteleev and Kalachev asymptotically good quantum LDPC code, with improved estimates for its minimum distance. This quantum code is closely related to the Dinur et at. code in more than one sense: indeed, we prove a theorem that simultaneously gives a linearly growing minimum distance for the quantum code and recovers the local testability of the Dinur et at. code.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
The cited source says what the claim attributes to it.
In the citing paper
“The latter were shown39,40 to be asymptotically ‘good’ in the sense of offering a constant encoding rate and linear distance: a parameter quantifying the number of correctable errors.”
From High-threshold and low-overhead fault-tolerant quantum memory (2024) · cites this paper as [40]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Low-density parity-check codes
Gallager, R. G. (1962) · IEEE Transactions on Information Theory · doi:10.1109/tit.1962.1057683 · Cited by 10,727
Fault-tolerant quantum computation by anyons
Kitaev, A. Y. (2003) · Annals of Physics · doi:10.1016/s0003-4916(02)00018-0 · Cited by 7,238
A recursive approach to low complexity codes
Tanner, R. M. (1981) · IEEE Transactions on Information Theory · doi:10.1109/tit.1981.1056404 · Cited by 3,176
Error Correcting Codes in Quantum Theory
Steane, A. M. (1996) · Physical Review Letters · doi:10.1103/physrevlett.77.793 · Cited by 2,677
Good quantum error-correcting codes exist
Calderbank, A. R., & Shor, P. W. (1996) · Physical Review A · doi:10.1103/physreva.54.1098 · Cited by 2,516
Expander graphs and their applications
Hoory, S., Linial, N., & Wigderson, A. (2006) · Bulletin of the American Mathematical Society · doi:10.1090/s0273-0979-06-01126-8 · Cited by 1,679
Sipser, M., & Spielman, D. A. (1996) · IEEE Transactions on Information Theory · doi:10.1109/18.556667 · Cited by 945
Checking computations in polylogarithmic time
Babai, L., Fortnow, L., Levin, L. A., & Szegedy, M. (1991) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/103418.103428 · Cited by 627
Tillich, J., & Zémor, G. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2013.2292061 · Cited by 418
Quantum Low-Density Parity-Check Codes
Breuckmann, N. P., & Eberhardt, J. N. (2021) · PRX Quantum · doi:10.1103/prxquantum.2.040101 · Cited by 328
Asymptotically good Quantum and locally testable classical LDPC codes
Panteleev, P., & Kalachev, G. (2022) · Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing · doi:10.1145/3519935.3520017 · Cited by 222
Balanced Product Quantum Codes
Breuckmann, N. P., & Eberhardt, J. N. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3097347 · Cited by 217
Nearly-linear size holographic proofs
Polishchuk, A., & Spielman, D. A. (1994) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/195058.195132 · Cited by 191
Quantum LDPC Codes With Almost Linear Minimum Distance
Panteleev, P., & Kalachev, G. V. (2021) · IEEE Transactions on Information Theory · doi:10.1109/tit.2021.3119384 · Cited by 172
Locally testable codes and PCPs of almost-linear length
Goldreich, O., & Sudan, M. (2006) · Journal of the ACM · doi:10.1145/1162349.1162351 · Cited by 152
Aharonov, D., Arad, I., & Vidick, T. (2013) · ACM SIGACT News · doi:10.1145/2491533.2491549 · Cited by 137
Fiber bundle codes: breaking the n 1/2 polylog( n ) barrier for Quantum LDPC codes
Hastings, M. B., Haah, J., & O’Donnell, R. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451005 · Cited by 125
Local Hamiltonians Whose Ground States Are Hard to Approximate
Eldar, L., & Harrow, A. W. (2017) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2017.46 · Cited by 58
Z2-systolic freedom and quantum codes
Freedman, M. H., Meyer, D., & Luo, F. (2002) · Computational matematics series/Computational mathematics series · doi:10.1201/9781420035377.ch12 · Cited by 58
On Quantum Weight ReductionPreprint
Hastings, M. B. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2102.10030 · Cited by 57
Locally testable codes with constant rate, distance, and locality
Dinur, I., Evra, S., Livné, R., Lubotzky, A., & Mozes, S. (2022) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3519935.3520024 · Cited by 55
Quantum Locally Testable Codes
Aharonov, D., & Eldar, L. (2015) · SIAM Journal on Computing · doi:10.1137/140975498 · Cited by 34
Evra, S., Kaufman, T., & Zémor, G. (2020) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs46700.2020.00029 · Cited by 34
Trivial low energy states for commuting Hamiltonians, and the quantum PCP conjecture
Hastings, M. B. (2013) · Quantum Information and Computation · doi:10.26421/qic13.5-6-3 · Cited by 33
Quantum Codes from High-Dimensional ManifoldsPreprint
Hastings, M. B. (2016) · arXiv (Cornell University) · doi:10.4230/lipics.itcs.2017.25 · Cited by 27
Short Locally Testable Codes and Proofs: A Survey in Two Parts
Goldreich, O. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-16367-8_6 · Cited by 22
Towards local testability for quantum coding
Leverrier, A., Londe, V., & Zémor, G. (2022) · Quantum · doi:10.22331/q-2022-02-24-661 · Cited by 17
Self-citationKaufman, T., & Tessler, R. J. (2021) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3406325.3451029 · Cited by 16
Research works printed but not linked: 2
- Lin, 2022, c3-local testable codes from lossless expanders, arXiv preprint arXiv:2201.11369 · arXiv
- Gottesman, 1997, Stabilizer codes and quantum error correction
Cited by
Sorted by citations
High-threshold and low-overhead fault-tolerant quantum memory
Bravyi, S., Cross, A. W., Gambetta, J. M., Maslov, D., Rall, P., & Yoder, T. J. (2024) · Nature · doi:10.1038/s41586-024-07107-7 · Cited by 456
“The latter were shown [37, 38] to be asymptotically “good” in the sense of offering a constant encoding rate and linear distance – a parameter quantifying the number of correctable errors.”
BackgroundConstant-overhead fault-tolerant quantum computation with reconfigurable atom arrays
Xu, Q., Ataides, J. P. B., Pattison, C. A., Raveendran, N., Bluvstein, D., Wurtz, J., Vasic, B. V., Lukin, M. D., Jiang, L., & Zhou, H. (2024) · Nature Physics · doi:10.1038/s41567-024-02479-z · Cited by 245
IBM quantum computers: evolution, performance, and future directions
AbuGhanem, M. (2025) · The Journal of Supercomputing · doi:10.1007/s11227-025-07047-7 · Cited by 266
Good Quantum LDPC Codes with Linear Time Decoders
Dinur, I., Hsieh, M.-H., Lin, T.-C., & Vidick, T. (2023) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3564246.3585101 · Cited by 153
Decoding algorithms for surface codes
deMarti iOlius, A., Fuentes, P., Orús, R., Crespo, P. M., & Etxezarreta Martinez, J. (2024) · Quantum · doi:10.22331/q-2024-10-10-1498 · Cited by 60
Metadata
- Authors
- Leverrier, A., & Zemor, G.
- Affiliations
- Institut national de recherche en sciences et technologies du numérique (FR)
- Institut de Mathématiques de Bordeaux,Bordeaux,France,UMR 5251
- ORCID
- Leverrier, Anthony
- Venue
- 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
- Publisher
- IEEE
- Published
- 2022-10
- Pages
- 872-883
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W4226180919
- Cited by
- 140
- References
- 29
- Citations by year
- 2026: 25 · 2025: 48 · 2024: 40 · 2023: 21 · 2022: 6
- FWCI
- 15.86
- Type
- conference paper
- Language
- en
- Open access
- green
- arxiv.org
- Locations
- Annual Symposium on Foundations of Computer Science (publishedVersion)
- arXiv (Cornell University) (submittedVersion)
- HAL (submittedVersion, other-oa)
- HAL (submittedVersion, cc-by)
- Oskar-Bordeaux (Universite de Bordeaux) (submittedVersion)
- arXiv (Cornell University) (cc-by)
- Funders
- Agence Nationale de la Recherche
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
- Physical Sciences › Mathematics › Discrete Mathematics and Combinatorics › Coding theory and cryptography
- Physical Sciences › Computer Science › Computer Networks and Communications › Error Correcting Code Techniques
- Keywords
- quantum LDPC codes, expander codes, locally testable codes, minimum distance, quantum error-correcting codes
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
