Open problems on explicit parallel decoding, exact rate-distance tradeoffs, and fault-tolerant encoders for linear-time encodable and decodable quantum error-correcting codes

A 2026 construction by Wills, Lin, Zhang, and Hsieh (arXiv:2603.04543) gave the first asymptotically good quantum error-correcting codes that can be encoded, unencoded, and decoded by low-depth, low-complexity circuits in the channel-capacity (code-capacity) setting, using new expander objects called lossless Z-graphs; the randomized variant admits logarithmic-depth parallel classical decoding with $O(n\log n)$ gates, while the explicit variant does not. The paper explicitly poses three open problems: (1) construct explicit asymptotically good quantum codes whose classical decoding runs in logarithmic depth and $O(n\log n)$ gates, currently blocked by the lack of explicit two-sided lossless expanders with expansion deficit $\varepsilon=O(1/\Delta)$ and quadratic degree separation; (2) characterize the exact rate/distance tradeoff achievable by explicit or randomized asymptotically good quantum codes with low-depth, low-complexity encoders and decoders, the quantum analogue of the classical linear-time Gilbert-Varshamov program; and (3) determine whether asymptotically good quantum codes admit low-depth, low-complexity encoders that are fault tolerant against gate faults during encoding, and whether fundamental tradeoffs bind code parameters, encoder depth/complexity, and maximum check weight, a question open even for classical LDPC codes. As of August 2026, all three problems remain open.

Background

A quantum stabilizer code encodes $k$ logical qubits into $n$ physical qubits as the joint +1 eigenspace of a commuting set of $n$ -qubit Pauli operators (the stabilizers); a CSS code is a stabilizer code whose stabilizers are each products of only $I$ and $X$ , or only $I$ and $Z$ , so the code is specified by two binary parity-check matrices $H_X$ and $H_Z$ with $H_X H_Z^T=0$ over $\mathbb{F}_2$ . The rate is $k/n$ and the distance $d$ is the minimum number of qubits on which an undetectable logical error can act; a code family is asymptotically good if both $k/n$ and $d/n$ stay bounded below by positive constants as $n\to\infty$ . A low-density parity-check (LDPC) code has parity checks each acting on few qubits, but here the relevant complexity measures are the depth and gate count of circuits that implement encoding, unencoding, and decoding. This is the channel-capacity setting: a noise channel acts between perfect encoding and perfect unencoding/decoding operations, the setting relevant for communication between fault-tolerant quantum computers, and no faults occur inside the encoder or decoder themselves. Classically, Spielman (1996) constructed linear-time encodable and decodable codes of good rate and distance, and a subsequent line of work culminated in linear-time encodable binary codes achieving the Gilbert-Varshamov (GV) bound, the best rate-versus-distance tradeoff known to be achievable by general random codes, with linear-time encodable duals also at GV (Brehm and Resch 2025). In the quantum setting, good LDPC code families with linear-time classical decoders were constructed from lossless expanders (Lin and Hsieh 2022) and as quantum Tanner codes (Leverrier and Zemor 2022), but these address only decoding complexity, not the complexity of the encoding and unencoding circuits. Wills, Lin, Zhang, and Hsieh (2026) closed that gap: they build quantum error-reduction codes from lossless Z-graphs, a two-sided lossless expander of mixed degrees $\Delta_1,\Delta_2$ between vertex classes $L_1,L_2,R_1,R_2$ in which small subsets of $L_1\cup L_2$ have nearly $\Delta_i$ -fold-distinct neighborhoods in $R_2$ (within a deficit $\varepsilon_i$ ), and similarly through the $R$ -side, and then convert error-reduction codes into full quantum codes. A lossless expander is a bipartite graph in which every small set of left vertices expands to almost the maximum possible number, $(1-\varepsilon)\Delta$ times its size, of distinct right neighbors. Their randomized construction of lossless Z-graphs works with high probability and yields asymptotically good CSS-type quantum codes with encoding, unencoding, and decoding of linear complexity, logarithmic-depth parallel quantum circuits for encoding/unencoding, and classical decoding in logarithmic depth with $O(n\log n)$ total gates. Their explicit construction (a white-box modification of the explicit constant-degree lossless vertex expanders of Hsieh, Lubotzky, Mohanty, Reiner, and Zhang 2025) retains linear-complexity and logarithmic-depth encoding/unencoding but loses the parallel classical decoder, because the parallel error-reduction analysis requires expansion deficits $\varepsilon_i=O(1/\Delta_i)$ and a degree separation making $\Delta_1^2/\Delta_2$ small (intuitively $\Delta_2$ quadratically larger than $\Delta_1$ ), while current explicit two-sided lossless expanders are proved only for constant $\varepsilon$ and make $\Delta_1/\Delta_2$ (not $\Delta_1^2/\Delta_2$ ) small.

Problem Statement

Complete the low-complexity encoding/decoding program for asymptotically good quantum error-correcting codes by resolving the three independent open problems explicitly posed by Wills, Lin, Zhang, and Hsieh (arXiv:2603.04543, Section 1.2): (1) and (2) are posed in the code-capacity setting, in which no faults occur inside the encoder or decoder, while (3) is posed in the fault-tolerant setting, in which the encoder is subject to gate faults. These share the objective of determining what is constructible and optimal for quantum codes under provable low-depth, low-complexity encoding, unencoding, and decoding, but they are independently posed and all of the deliverables enumerated below are mandatory. (1) Explicit parallel decoding: construct explicit (uniformly computable, no randomness) and asymptotically good quantum error-correcting codes whose classical decoding admits a parallel algorithm of logarithmic depth and $O(n\log n)$ total gates, as the randomized construction already admits; the authors' identified route, an explicit construction of the required two-sided lossless expanders (lossless $Z$ -graphs) with expansion deficits $\varepsilon_i=O(1/\Delta_i)$ and degree separation making $\Delta_1^2/\Delta_2$ small (in particular $\Delta_2$ quadratically larger than $\Delta_1$ ), is permitted but not required. (2) Exact rate/distance tradeoff: characterize the exact rate/distance frontier achievable by explicit or randomized asymptotically good quantum codes whose encoders and decoders have low depth and low complexity, the quantum analogue of the classical program that produced linear-time encodable codes at the Gilbert-Varshamov bound with linear-time encodable duals. (3) Fault-tolerant encoders and parameter tradeoffs: (a) determine whether asymptotically good quantum codes exist whose low-depth, low-complexity encoders are fault tolerant, i.e. tolerate gate faults occurring during the encoding circuit while preserving the code's error-correction guarantees; and (b) determine whether there are fundamental tradeoffs between code parameters, encoder depth/complexity, and maximum stabilizer check weight, noting that the corresponding classical question for LDPC encoders is itself open.

References

arXiv:2603.04543, DOI 10.48550/arxiv.2603.04543 — Adam Wills, Ting-Chun Lin, Rachel Yun Zhang, Min-Hsiu Hsieh, 'Linear-Time Encodable and Decodable Quantum Error-Correcting Codes' (2026), https://arxiv.org/abs/2603.04543
DOI 10.1109/18.556668 — D. A. Spielman, 'Linear-time encodable and decodable error-correcting codes', IEEE Transactions on Information Theory 42(6) (1996), https://doi.org/10.1109/18.556668
arXiv:2203.03581, DOI 10.48550/arxiv.2203.03581 — Ting-Chun Lin, Min-Hsiu Hsieh, 'Good quantum LDPC codes with linear time decoder from lossless expanders' (2022), https://arxiv.org/abs/2203.03581
arXiv:2202.13641, DOI 10.48550/arxiv.2202.13641 — Anthony Leverrier, Gilles Zémor, 'Quantum Tanner codes' (2022), https://arxiv.org/abs/2202.13641
arXiv:2302.01212, DOI 10.48550/arxiv.2302.01212 — Jun-Ting Hsieh, Theo McKenzie, Sidhanth Mohanty, Pedro Paredes, 'Explicit two-sided unique-neighbor expanders' (2023, v2 2024), https://arxiv.org/abs/2302.01212
arXiv:2504.15087, DOI 10.48550/arxiv.2504.15087 — Jun-Ting Hsieh, Alexander Lubotzky, Sidhanth Mohanty, Assaf Reiner, Rachel Yun Zhang, 'Explicit Lossless Vertex Expanders' (2025, FOCS 2025), https://arxiv.org/abs/2504.15087
arXiv:2509.07639, DOI 10.48550/arxiv.2509.07639 — Martijn Brehm, Nicolas Resch, 'Linear time encodable binary code achieving GV bound with linear time encodable dual achieving GV bound' (2025, v2 2026), https://arxiv.org/abs/2509.07639
arXiv:2608.18536, DOI 10.48550/arxiv.2608.18536 — Emile Anand, Elia Gorokhovsky, Jennifer Hritz, Jingtong Sun, 'Good Stabilizer Codes from Shallow Clifford Circuits with Random Matchings' (2026), https://arxiv.org/abs/2608.18536
arXiv:2306.12470, DOI 10.48550/arxiv.2306.12470 — Shouzhen Gu, Eugene Tang, Libor Caha, Shin Ho Choe, Zhiyang He, Aleksander Kubica, 'Single-shot decoding of good quantum LDPC codes' (2023, v2 2024), https://arxiv.org/abs/2306.12470
arXiv:2405.07242, DOI 10.48550/arxiv.2405.07242 — Abhi Kumar Sharma, Shayan Srinivasa Garani, 'Fault-Tolerant Quantum LDPC Encoders' (2024), https://arxiv.org/abs/2405.07242
arXiv:2408.06299, DOI 10.48550/arxiv.2408.06299 — Yu Shi, Ashlesha Patil, Saikat Guha, 'Stabilizer Entanglement Distillation and Efficient Fault-Tolerant Encoders' (2024, v2 2025), https://arxiv.org/abs/2408.06299
arXiv:2603.20369, DOI 10.48550/arxiv.2603.20369 — Arman Sauliere, Guglielmo Lami, Pedro Ribeiro, Andrea De Luca, Jacopo De Nardis, 'Error-Correction Transitions in Finite-Depth Quantum Channels' (2026), https://arxiv.org/abs/2603.20369