Reducing the impractical constant-factor runtime of provably correct decoders for asymptotically good quantum LDPC codes and characterizing their flip-set search space

The first provably correct decoder for quantum Tanner codes (Gu–Pattison–Tang, 2022) runs in time linear in the blocklength but with constant prefactors on the order of $2^{\Delta^2}$, arising from exhaustively enumerating subsets of the $\Delta^2$-sized local views, which its authors state renders the decoder impractical in reality; they asked for ways to reduce the absolute runtime and for a combinatorial characterization of the candidate flip-sets searched at each step. The companion transfer question — efficient provable decoding of the Panteleev–Kalachev lifted-product codes — was resolved shortly afterwards by the greedy decoders of Leverrier–Zémor, but those decoders likewise leave their numerical constants unoptimized, and every known provably correct decoder for asymptotically good quantum LDPC codes retains an exhaustive search over a space exponential in the local view size, while all practical decoders for these codes lack any correctness guarantee. The open problem is to bring provably correct decoding of asymptotically good quantum LDPC codes to a practically implementable absolute runtime and to develop the combinatorial understanding of the flip-set search space needed to do so.

Background

Quantum low-density parity-check (qLDPC) codes are quantum stabilizer codes in which every stabilizer generator acts on a bounded number of qubits and every qubit is involved in a bounded number of generators; this constant locality is what makes qLDPC codes the natural vehicle for constant-overhead fault-tolerant quantum computation. A qLDPC family is called asymptotically good if it has constant encoding rate and minimum distance growing linearly with the blocklength $n$. After a long line of constructions whose distance stagnated at $O(\sqrt{n})$, Panteleev and Kalachev proved in 2021 that asymptotically good qLDPC codes exist, using the lifted product (a variant of the balanced product of two classical codes) over non-abelian groups, and Leverrier and Zémor introduced the closely related quantum Tanner codes. Quantum Tanner codes are CSS codes (codes built from two mutually commuting sets of $X$-type and $Z$-type checks) obtained from a left-right Cayley complex — a square complex whose vertices are four copies of a group $G$ and whose squares are indexed by pairs of generators from two self-inverse subsets of size $\Delta$ — with qubits on squares and checks defined by two small classical codes $C_A$ and $C_B$ of length $\Delta$. In these constructions the parity checks have weight $\Delta^2$, where $\Delta$ is a fixed constant (the degree of the underlying Cayley graphs), and correctness rests on the robustness of the tensor code $C_A \otimes C_B$ — the property that every low-weight word of the tensor code splits into few low-weight codewords of the component codes.

Gu, Pattison, and Tang gave the first provably correct decoder for quantum Tanner codes: a local-search algorithm in the lineage of the small-set-flip decoder for quantum expander codes, which at each step inspects constant-sized local views (the $\Delta^2$ qubits incident to a vertex) and applies a constant-sized correction that decreases a globally defined potential function, a locally computable proxy for the weight of the remaining error. The decoder runs in time linear in $n$ and provably corrects every error of weight up to a constant fraction of the blocklength (specifically $|e| \lesssim \delta n / \Delta^{7/2+\varepsilon}$), but its practical defect, emphasized by the authors, is the constant prefactor: naively finding the best local correction requires checking all subsets of a $\Delta^2$-sized local view, giving per-step work on the order of $2^{\Delta^2}$, which the authors state renders the decoder impractical in reality. They therefore posed the questions that define this problem: how to reduce the absolute runtime, for example by reducing the $\Delta^2$ check weights of the underlying construction or by finding more structured candidate flip-sets (the local corrections the decoder searches over), and how to obtain a better combinatorial characterization of the flip-sets, which they connect directly to lowering the runtime. A subordinate question is whether a tighter analysis, for instance via a stronger low-overlap property or more robust local codes, could eliminate the need to check local views of both vertex types $V_0$ and $V_1$ of the complex. They also asked whether efficient provable decoding extends to the Panteleev–Kalachev codes, for which no efficient decoder was known at the time, and more generally to balanced-product constructions with non-trivial local codes.

That last transfer question has since been answered at the level of its scientific objective: Leverrier and Zémor constructed greedy weight-decreasing local-search decoders that provably correct adversarial errors of linear weight for quantum Tanner codes in linear time (logarithmic time in a parallel variant), and showed by an explicit reduction that the same decoders apply to the asymptotically good lifted-product codes of Panteleev and Kalachev, correcting all errors of weight below $\kappa n / \Delta^6$ — thereby solving an open problem posed by Panteleev and Kalachev themselves. Further asymptotically good families with linear-time decoders are now known (Dinur–Hsieh–Lin–Vidick 2022; Lin–Hsieh 2022, conditionally on lossless expanders). However, none of this improves the practical picture: the Leverrier–Zémor analysis explicitly leaves its numerical constants unoptimized, and every known provably correct decoder for good qLDPC codes still performs, in effect, an exhaustive search over a space whose size is exponential in the local view size $\Delta^2$. Conversely, all decoders for these codes that are fast in practice — belief propagation (an iterative message-passing algorithm that computes approximate marginal likelihoods) in its many variants — carry no provable correction guarantee, and recent work on practical quantum Tanner code decoding explicitly notes that practical algorithms leveraging the codes' structure remain limited. The unresolved target is therefore provably correct decoding of asymptotically good qLDPC codes at a practically implementable absolute runtime, supported by a genuine combinatorial understanding of the flip-set search space.

Problem Statement

The problem, as posed by Gu, Pattison, and Tang (2022) and still open, is to make provably correct decoding of asymptotically good quantum LDPC codes practical, together with the combinatorial understanding of the decoder's search space that this requires. Concretely: construct a decoder for quantum Tanner codes, or for a modification of the construction (for example one with reduced check weights in place of the inherent $\Delta^2$), that still provably corrects every adversarial error up to a constant fraction of the blocklength in time linear (or near-linear) in the blocklength, but whose per-step work avoids the exhaustive enumeration of subsets of the $\Delta^2$-sized local views — the constant prefactors currently on the order of $2^{\Delta^2}$ that render the known decoders impractical in reality; and establish a combinatorial characterization of the candidate flip-sets (the local corrections searched at each step) precise enough to guide such runtime reductions. A subordinate part asks whether a tighter analysis, for instance via a stronger low-overlap property or more robust local codes, could eliminate the need to check local views of both vertex types $V_0$ and $V_1$ and thereby simplify and speed up decoding. These deliverables serve one overarching objective — an asymptotically good quantum LDPC code family equipped with a decoder that is simultaneously provably correct against adversarial noise up to a constant fraction of the blocklength and implementable at realistic block lengths — and partial progress (for example, the flip-set characterization alone, or a constants reduction for one concrete family) is a meaningful answer to the corresponding part. The companion question of whether efficient provable decoding extends to the Panteleev–Kalachev lifted-product codes and to balanced-product constructions in general is resolved by Leverrier and Zémor and is not part of what remains open.

References

1. Shouzhen Gu, Christopher A. Pattison, Eugene Tang, “An efficient decoder for a linear distance quantum LDPC code”, 2022, arXiv:2206.06557, DOI 10.48550/arXiv.2206.06557, https://arxiv.org/abs/2206.06557
2. Pavel Panteleev, Gleb Kalachev, “Asymptotically Good Quantum and Locally Testable Classical LDPC Codes”, 2021, STOC 2022, arXiv:2111.03654, DOI 10.48550/arXiv.2111.03654, https://arxiv.org/abs/2111.03654
3. Anthony Leverrier, Gilles Zémor, “Quantum Tanner codes”, 2022, FOCS 2022, arXiv:2202.13641, DOI 10.48550/arXiv.2202.13641, https://arxiv.org/abs/2202.13641
4. Anthony Leverrier, Gilles Zémor, “Efficient decoding up to a constant fraction of the code length for asymptotically good quantum codes”, 2022, SODA 2023, arXiv:2206.07571, DOI 10.48550/arXiv.2206.07571, https://arxiv.org/abs/2206.07571
5. Anthony Leverrier, Gilles Zémor, “Decoding quantum Tanner codes”, 2022, journal version in IEEE Transactions on Information Theory 69(8), pp. 5100–5115, 2023, DOI 10.1109/TIT.2023.3267945, arXiv:2208.05537, https://arxiv.org/abs/2208.05537
6. Irit Dinur, Min-Hsiu Hsieh, Ting-Chun Lin, Thomas Vidick, “Good Quantum LDPC Codes with Linear Time Decoders”, 2022, arXiv:2206.07750, DOI 10.48550/arXiv.2206.07750, https://arxiv.org/abs/2206.07750
7. Ting-Chun Lin, Min-Hsiu Hsieh, “Good quantum LDPC codes with linear time decoder from lossless expanders”, 2022, arXiv:2203.03581, DOI 10.48550/arXiv.2203.03581, https://arxiv.org/abs/2203.03581
8. Shouzhen Gu, Eugene Tang, Libor Caha, Shin Ho Choe, Zhiyang He, Aleksander Kubica, “Single-shot decoding of good quantum LDPC codes”, 2023, arXiv:2306.12470, DOI 10.48550/arXiv.2306.12470, https://arxiv.org/abs/2306.12470
9. Louis Golowich, Venkatesan Guruswami, “Decoding Quasi-Cyclic Quantum LDPC Codes”, 2024, arXiv:2411.04464, DOI 10.48550/arXiv.2411.04464, https://arxiv.org/abs/2411.04464
10. Olai Å. Mostad, Eirik Rosnes, Hsuan-Yin Lin, “Improved Decoding of Quantum Tanner Codes Using Generalized Check Nodes”, 2026, arXiv:2603.05486, DOI 10.48550/arXiv.2603.05486, https://arxiv.org/abs/2603.05486
11. Lukas Rapp, Muriel Médard, Eugene Tang, Ken R. Duffy, “Efficient Soft-Output Guessing for Enhanced Quantum Tanner Code Decoding”, 2026, arXiv:2603.18318, DOI 10.48550/arXiv.2603.18318, https://arxiv.org/abs/2603.18318
12. Zhuo-Yan Xiao, Sha Shi, Chen-Peng Huang, Dong-Sheng Wang, Yun-Jiang Wang, “LEAD: A Local Ensemble-Assisted Parallel Decoding Framework for Quantum Tanner Codes”, 2026, arXiv:2605.17796, DOI 10.48550/arXiv.2605.17796, https://arxiv.org/abs/2605.17796
13. Kuan Cheng, Minghui Ouyang, Chong Shangguan, Yuanting Shen, “When can an expander code correct Ω(n) errors in O(n) time?”, 2023, arXiv:2312.16087, DOI 10.48550/arXiv.2312.16087, https://arxiv.org/abs/2312.16087
14. Feroz Ahmed Mian, Vaishnavi L. Addala, Arman Meraj, Adhiraj Chadha, Stefan Krastanov, “Quantum Tanner Codes at Moderate Blocklength”, 2026, arXiv:2608.12509, DOI 10.48550/arXiv.2608.12509, https://arxiv.org/abs/2608.12509