Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.20780

Asymptotically Good Quantum Locally Testable Codes

William Gay, Fernando Granha Jeronimo

quant-phSubmitted Sep 17, 2026• Announced Sep 18, 2026• 9 citations
arXivHTMLPDF

Abstract

We construct explicit families of asymptotically good quantum locally testable codes over qubits. More precseily, we construct explicit quantum LDPC CSS codes over qubits having constant rate, constant relative distance and constant weight local testers with constant soundness.

AI Summary

The paper addresses whether quantum local testability can coexist with constant rate, linear distance, and bounded check weight and qubit incidence. It constructs families of binary CSS codes with $N\to\infty$, parameters $[[N,\Omega(N),\Omega(N)]]$, and constant-soundness testers. Soundness uses quantum Hamming distance: the normalized check Hamiltonian satisfies $\mathsf H\succeq(\sigma/N)\mathsf D_{\mathscr Q}$ for a constant $\sigma>0$. The construction uses the middle degree of a four-dimensional cubical complex, extending the Dinur–Lin–Vidick framework. Arithmetic quotients of products of trees provide Ramanujan bounds for parallel-face walks without losses depending on the quotient size. Equivariant projective Reed–Solomon codes supply compatible incidence maps despite noncommuting geometric labels. A local-code theorem establishes uniform product expansion on unequal norm-one evaluation sets, including dual codes and coefficient-field extensions. Product expansion gives local filling inequalities; face-walk mixing then yields cohomological distance and syndrome-repair bounds. A double-complex argument transfers these estimates to homology, while an Euler-characteristic calculation supplies positive rate. Restriction of scalars produces qubit codes with constant parameter losses. A fixed instantiation has rate at least $2^{-5}$, relative distance at least $2^{-2^{18}}$, soundness at least $2^{-2^{20}}$, and check weight and qubit incidence at most $2^{2^{17}}$. Thus the stated guarantees are asymptotic, with very large locality bounds and very small distance and soundness bounds. The paper explicitly distinguishes this result from the quantum PCP conjecture: good qLTCs alone do not provide the reductions that conjecture requires.

Little sign of AI-generated textAI use disclosed
ChatGPT 6 Pro was used as an editorial assistant.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Asymptotically Good Quantum and Locally Testable Classical LDPC Codes

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

We study classical and quantum LDPC codes of constant rate obtained by the lifted product construction over non-abelian groups. We show that the obtained families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. Moreover, we show that the produced classical LDPC codes are also asymptotically good and locally testable with constant query and soundness parameters, which proves a well-known conjecture in the field of locally testable codes.

arXiv:2111.03654•Nov 5, 2021•129 citations

Asymptotically good Quantum and locally testable classical LDPC codes

Pavel Panteleev, Gleb Vyacheslavovich Kalachev

We study classical and quantum LDPC codes of constant rate obtained by the lifted product construction over non-abelian groups. We show that the obtained families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. Moreover, we show that the produced classical LDPC codes are also asymptotically good and locally testable with constant query and soundness parameters, which proves a well-known conjecture in the field of locally testable codes.

ACM Symposium on Theory of Computing (STOC)•Jun 9, 2022•315 citations

Good Quantum Locally Testable Codes from Product Expansion

Mitali Bafna, Anqi Li, Quynh T. Nguyen

We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick for constructing quantum LTCs, instantiated with the non-Abelian cubical complexes of Rungtanapirom, Stix and Vdovina. Our code is obtained by equipping the complex with carefully chosen Reed-Solomon local codes whose symmetries are compatible with those of the complex.

quant-pharXiv:2609.26735•Sep 23, 2026•5 citations

Asymptotically good families of quantum and locally testable classical LDPC codes

Gleb Vyacheslavovich Kalachev, Pavel Panteleev

In this paper we study classical and quantum LDPC codes with constant rate obtained using tensor product operation over noncommutative group algebra for chain complexes. It is shown that these families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. The existence of asymptotically good families of locally testable codes with constant parameters of locality and soundness is also shown, which gives the solution of the known conjecture in the field of classical locally testable codes.

Mathematical Problems of Cybernetics•Jan 1, 2023•0 citations

Constant Rate Codes with Fully Addressable Transversal T: Good Codes, Sparse Checks

Alexander Meiburg

Recent work by Wills constructed codes with constant rate and transversal $T$. Extending this line of work, we construct asymptotically good CSS codes with \textbf{fully addressable} transversal $T$, permitting selective control over which logical qubits receive a $T$ gate. We also give Pauli-LDPC codes with transversal $T$ and growing distance at vanishing rate; and a protected-subsystem construction with fully addressable transversal $T$, constant protected rate, distance $Ω(\sqrt n)$, and sparse (non-Pauli) checks. More generally, we obtain asymptotically good binary codes with full transversal addressability for every fixed finite-order one-qubit gate, retaining CSS realizations for dyadic phase gates such as $\sqrt T$ and using generally nonadditive codes for rotations such as $R_z(π/7)$. The remaining challenge is to construct asymptotically good Pauli-LDPC codes with fully addressable transversal non-Clifford one-qubit gates.

quant-pharXiv:2609.38996•Oct 1, 2026•1 citation

Local testability of distance-balanced quantum codes

Adam Wills, Ting-Chun Lin, Min-Hsiu Hsieh

In this paper, we prove a lower bound on the soundness of quantum locally testable codes under the distance balancing construction of Evra et al. Our technical contribution is that the soundness of the quantum code after this procedure is at least its soundness before the procedure divided by the length of the classical code used to perform distance balancing. This allows us to use any classical code when distance balancing, where previously only the repetition code had been considered for these codes. By using a good classical low-density parity check (LDPC) code, we are able to grow the dimension of the hypersphere product codes and the hemicubic codes while maintaining their distance and locality, but at the expense of soundness. From this, and also by distance balancing a chain complex of Cross et al., we obtain quantum locally testable codes of new parameters.

arXiv:2305.00689•npj Quantum Information•Nov 20, 2024•9 citations
The paper addresses whether quantum local testability can coexist with constant rate, linear distance, and bounded check weight and qubit incidence. It constructs families of binary CSS codes with N→∞N\to\inftyN→∞, parameters [[N,Ω(N),Ω(N)]][[N,\Omega(N),\Omega(N)]][[N,Ω(N),Ω(N)]], and constant-soundness testers. Soundness uses quantum Hamming distance: the normalized check Hamiltonian satisfies H⪰(σ/N)DQ\mathsf H\succeq(\sigma/N)\mathsf D_{\mathscr Q}H⪰(σ/N)DQ​ for a constant σ>0\sigma>0σ>0.
The construction uses the middle degree of a four-dimensional cubical complex, extending the Dinur–Lin–Vidick framework. Arithmetic quotients of products of trees provide Ramanujan bounds for parallel-face walks without losses depending on the quotient size. Equivariant projective Reed–Solomon codes supply compatible incidence maps despite noncommuting geometric labels. A local-code theorem establishes uniform product expansion on unequal norm-one evaluation sets, including dual codes and coefficient-field extensions. Product expansion gives local filling inequalities; face-walk mixing then yields cohomological distance and syndrome-repair bounds. A double-complex argument transfers these estimates to homology, while an Euler-characteristic calculation supplies positive rate. Restriction of scalars produces qubit codes with constant parameter losses.
A fixed instantiation has rate at least 2−52^{-5}2−5, relative distance at least 2−2182^{-2^{18}}2−218, soundness at least 2−2202^{-2^{20}}2−220, and check weight and qubit incidence at most 22172^{2^{17}}2217. Thus the stated guarantees are asymptotic, with very large locality bounds and very small distance and soundness bounds. The paper explicitly distinguishes this result from the quantum PCP conjecture: good qLTCs alone do not provide the reductions that conjecture requires.
We construct quantum locally testable codes (LTCs) with constant rate, distance, soundness and locality under a variant of a product expansion conjecture of Bafna and Vyas about Reed-Solomon codes. In particular, we use the high-dimensional expansion framework of Dinur, Lin and Vidick for constructing quantum LTCs, instantiated with the non-Abelian cubical complexes of Rungtanapirom, Stix and Vdovina. Our code is obtained by equipping the complex with carefully chosen Reed-Solomon local codes whose symmetries are compatible with those of the complex.
In this paper we study classical and quantum LDPC codes with constant rate obtained using tensor product operation over noncommutative group algebra for chain complexes. It is shown that these families of quantum LDPC codes are asymptotically good, which proves the qLDPC conjecture. The existence of asymptotically good families of locally testable codes with constant parameters of locality and soundness is also shown, which gives the solution of the known conjecture in the field of classical locally testable codes.
Recent work by Wills constructed codes with constant rate and transversal TTT. Extending this line of work, we construct asymptotically good CSS codes with \textbf{fully addressable} transversal TTT, permitting selective control over which logical qubits receive a TTT gate. We also give Pauli-LDPC codes with transversal TTT and growing distance at vanishing rate; and a protected-subsystem construction with fully addressable transversal TTT, constant protected rate, distance Ω(n)Ω(\sqrt n)Ω(n​), and sparse (non-Pauli) checks. More generally, we obtain asymptotically good binary codes with full transversal addressability for every fixed finite-order one-qubit gate, retaining CSS realizations for dyadic phase gates such as T\sqrt TT​ and using generally nonadditive codes for rotations such as Rz(π/7)R_z(π/7)Rz​(π/7). The remaining challenge is to construct asymptotically good Pauli-LDPC codes with fully addressable transversal non-Clifford one-qubit gates.
In this paper, we prove a lower bound on the soundness of quantum locally testable codes under the distance balancing construction of Evra et al. Our technical contribution is that the soundness of the quantum code after this procedure is at least its soundness before the procedure divided by the length of the classical code used to perform distance balancing. This allows us to use any classical code when distance balancing, where previously only the repetition code had been considered for these codes. By using a good classical low-density parity check (LDPC) code, we are able to grow the dimension of the hypersphere product codes and the hemicubic codes while maintaining their distance and locality, but at the expense of soundness. From this, and also by distance balancing a chain complex of Cross et al., we obtain quantum locally testable codes of new parameters.