CS Paper Radar

Area Theorems for Quantum Error Correction

Avijit Mandal, Mert Gökduman, Henry D. Pfister

cs.IT quant-ph ·submitted 2026-10-15 22:27 UTC · v1
theory

Abstract

The extrinsic information transfer (EXIT) and generalized EXIT (GEXIT) area theorems provide fundamental conservation laws that connect the rate of classical codes to the performance of maximum-a-posteriori decoding on binary memoryless channels. In this work, we generalize these area theorems to quantum error correction. We first develop a coset-entropy formalism for nested linear codes, where the message specifies a coset and encoder randomization selects a codeword within that coset. The area under the resulting coset (G)EXIT function equals the normalized dimension of the quotient. For stabilizer codes, the measured syndrome restricts the Pauli error but does not always determine its logical effect, and the remaining uncertainty is an entropy over logical correction classes. We show that this entropy equals a classical coset entropy associated with the stabilizer group and the Pauli operators that commute with it. The resulting quantum GEXIT function has area equal to the number of encoded qubits per channel use for any stabilizer code, and this applies to the depolarizing channel through its joint four-valued Pauli-error distribution. For CSS codes on the quantum erasure channel and under independent bit- and phase-flip noise, the logical correction problem separates into two binary coset-decoding problems. On the quantum erasure channel, the duality between the stabilizer group and the Pauli operators that commute with it gives a folding identity at complementary erasure probabilities. Using this and the area theorem, we derive an upper bound on the rate of code families with vanishing logical error probability that matches the capacity of the quantum erasure channel. For the depolarizing channel, we also derive a rate-dependent converse, using a connection between correction-class entropy and coherent information to establish an inequality involving the complementary channel.

Comment
This work will be presented in part at ITW 2026 in Tempe, Arizona

Closest papers

Nearest neighbours by meaning across the whole index.

Quantum codes in the Lee metric

cs.IT quant-phmath.COmath.MG ·2026-10-04 ·Jinkang Guo, Yiqiu Han, Aranya Chakraborty, Shubham P. Jain, Tianhao Liu +2 more
theory similarity 0.68
Abstract

We introduce a quantum coding framework for discrete small-shift noise, in which errors on qudits are modeled as low-weight $X$- and $Z$-type Pauli shifts, analogous to small phase-space displacements in continuous-variable systems. This structure is approximately respected by nuclear-spin noise and captured by the Lee metric, motivating a quantum extension of classical Lee-metric coding theory. We develop such a formalism for stabilizer codes over $\mathbb{Z}_q$ for arbitrary $q$, using joint and separate Lee metrics for the $X$- and $Z$-components of errors. For qubits, the joint metric counts $Y$ errors twice and can yield codes that detect and correct $X$ and $Z$ errors with fewer physical qubits than codes designed for the conventional Hamming metric. We discuss Lee-weight spreading under Clifford gates and qubitize codes over $\mathbb{Z}_4$ via the Gray map, finding codes with two-fold transversal non-qubit-Clifford gates. For quantum CSS Lee-LDPC codes on $n$ qudits, we prove that the Lee distance cannot exceed $O(n)$, uniformly in $q$, demonstrating an unexpected obstruction to using the large internal Hilbert space of a large-$q$ qudit to make high-Lee-distance codes. Under local Metropolis dynamics, certain classical $q$-ary ``helical repetition codes'' have exponentially long memory times at fixed temperature for sufficiently large $q$ (that grows with system length), which can be understood as spontaneous symmetry breaking at finite temperature, even in local one-dimensional models. Hypergraph products of these helical repetition codes provide local two-dimensional quantum codes that inherit self-correction for $Z$ errors, but self-correction for $X$ errors remains an open question.

0.49

Random Quantum LDPC Codes Approaching the Gilbert-Varshamov Bound

cs.IT quant-ph ·2026-10-02 ·Tushant Mittal, Shashank Srivastava, Madhur Tulsiani, Mary Wootters
similarity 0.68
Abstract

We show that for any $R,ε>0$ and any prime $p\geq 2$, there exists an infinite family of $p$-ary quantum low-density parity-check (QLDPC) codes, rate $R$, checks of weight $O_ε(1)$, and normalized distance at least $δ_{\mathrm{GV}}(p,R)-ε$. Here, $δ_{\mathrm{GV}}(p,R)$ denotes the quantum Gilbert-Varshamov (GV) bound for $p$-ary stabilizer codes. In fact, we construct an ensemble of such QLDPC codes, such that a random code from this ensemble is close to the GV bound with high probability. Moreover, this ensemble matches the performance of random stabilizer codes on several quantum channels. Specifically, it approaches the quantum capacity of the erasure channel and the hashing bound for memoryless Pauli channels, including the depolarizing channel. A significant challenge in working with QLDPC codes is that they are necessarily \emph{degenerate}, i.e., contain many low-weight stabilizers. A key contribution of our work is a construction of QLDPC codes with quantitative control on their degeneracy. These codes are obtained by combining known constructions of asymptotically good QLDPC codes with the expander-based distance amplification procedure of Alon, Edmonds, and Luby [FOCS'95]. Our random ensemble is constructed by starting with these low-degeneracy QLDPC codes near the quantum Singleton bound and concatenating each coordinate with a random inner code. This can be viewed as a quantum analogue of Thommesen's construction, and as an LDPC version of a result of Ouyang, with an appropriately designed outer code.

0.39

Lifting an $[n,k,d]$ Binary Linear Code to an $[[n,k,d]]$ Quantum Stabilizer Code

cs.IT quant-ph ·2026-10-09 ·Thamadathil Aswanth, Navin Kashyap
theory similarity 0.67
Abstract · 6 pages, Submitted to ITW 2027

The codeword stabilized (CWS) framework provides a systematic method for constructing quantum error correcting codes from a simple undirected graph and a classical code. When the underlying classical code is linear, the resulting quantum code is a stabilizer code. In this work, we investigate the conditions under which an arbitrary $[n,k,d]$ classical binary linear code can be lifted to an $[[n,k,d]]$ quantum stabilizer code using the CWS framework. We analyze the random CWS code constructed from a given $[n,k,d]$ binary linear code $\mathcal{C}$ and an Erdős-Rényi random graph $\mathrm{G}(n, \frac12)$. We establish a lower bound on the probability that the resulting quantum code preserves the minimum distance $d$ of the classical code. This probabilistic analysis yields a Gilbert-Varshamov-type condition on the $n,k,d$ parameters of the classical code that guarantees the existence of a graph resulting in a quantum code with the same $n,k,d$ parameters.

0.09

From Random Quantum Codes to Explicit qLDPC Codes via Local Properties

cs.IT quant-ph ·2026-09-30 ·Fernando Granha Jeronimo, Xiaojuan Ma, Nikhil Shagrithaya
theory similarity 0.66
Abstract

Constructing explicit codes matching the parameters of random codes has been a central and largely elusive question in coding theory. The quantum setting is even more challenging since it is highly desirable that the quantum code be an LDPC code. Local coordinate-wise linear (LCL) [Levi, Mosheiff, and Shagrithaya, FOCS 2025] witnesses provide a unifying language for many coding-theoretic properties, from distance to list decoding and list recovery. In particular, it provides a framework to study properties of random linear codes, which achieve optimal parameters for many properties of linear codes. For CSS quantum codes, however, a local witness has two distinct ranks: its physical rank before quotienting by stabilizers and its logical rank after quotienting. We develop a quantum version of the LCL framework for nested spaces $S \subseteq C$, in which local constraints are imposed on physical representatives while independence is measured in the logical quotient $C/S$. The resulting theory gives a threshold theorem for random CSS codes, and as a consequence shows that the per-sector rate threshold is equal to the classical rate threshold. We also define a quantum analogue of subspace design [Guruswami and Xing, STOC 2013] and show that they can be described in a natural manner within the quantum-LCL framework. Finally, we give explicit constructions for arbitrary folded quantum-LCL properties, in a manner similar to the LCL derandomization of [Jeronimo and Shagrithaya, STOC 2026]. As a consequence, we obtain the first explicit constructions of quantum list-decodable codes and list-recoverable codes that have optimal list sizes, in addition to explicit quantum subspace design codes. We note that all our explicit constructions are qLDPC codes, an important property for quantum error-correcting codes.

0.42

Quantum List Recovery and Decoding: Achievability and Limitations

cs.IT quant-ph ·2026-09-30 ·Fernando Granha Jeronimo, Xiaojuan Ma
theory similarity 0.66
Abstract

Quantum list recovery (QLR) and quantum list decoding (QLD) seek short lists of logically distinct Pauli corrections consistent with a syndrome and prescribed error constraints. For CSS codes, two issues arise: treating the \(X\)- and \(Z\)-sectors separately can multiply their output list sizes, while distinct classical candidates can collapse after stabilizer quotienting. We study combinatorial upper and lower bounds for balanced folded quantum Reed--Solomon (FQRS) codes and balanced random CSS codes, both studied by Bergamaschi, Golowich, and Gunn (STOC 24). Let \(R\in(0,1)\) be the quantum rate and \(R_1=(1+R)/2\) the common component rate. As the radius \(ρ=(1-R)/2-γ\) approaches the quantum Singleton bound, we have, deterministically for FQRS codes and w.h.p. for balanced random CSS codes, \[ L^\star_{\rm QLR} = \ell^{Θ(R_1/γ)}, \qquad L^\star_{\rm QLD} = Θ\!\left(\frac{1-R}γ\right) \qquad (γ\downarrow0). \] The asymptotically exact QLD radius tradeoff is \[ ρ_L^\star = \frac{L}{L+1}\frac{1-R}{2}. \] These conclusions extend to the average-radius setting. For achievability, building on the work of Brakensiek, Chen, Dhar, and Zhang (STOC 2026), we establish a pairing lemma for joint \(X/Z\) candidate lists that preserves the one-sector coefficient and avoids a product loss in list size. For the QLD converse, we prove a quantum generalized Singleton bound based on the classical projection-and-patching argument with stabilizer distinctness. For the QLR lower bounds, we adapt the folded Reed--Solomon construction of Chen and Zhang (STOC 2025) so that the candidates remain stabilizer distinct. For random CSS codes, we show classical bad lists survive the stabilizer quotient with high probability.

0.35

Universality Sacrifices Reliability in Classical-Quantum Channel Coding

cs.IT quant-ph ·2026-10-01 ·Kaito Watanabe, Masahito Hayashi, Takaya Matsuura, Hao-Chung Cheng
similarity 0.66
Abstract · 5+23 pages

Universal channel coding enables communication without a complete description of the channel. For classical channels, universal codes can attain both capacity and the optimal high-rate reliability. We show that this compatibility fails for classical-quantum channels in general; that is, the optimal reliability in the channel-aware scenario is not always achievable with universal coding due to the ignorance of the unitary rotation of the output system. We exhibit a family of classical-quantum channels for which one cannot achieve the channel-aware optimal reliability by a fixed coding scheme. We further derive a converse bound on the reliability for unitary-invariant decoders, a natural assumption for the universal coding scheme, that can be strictly smaller than the optimal channel-aware error exponent. Conversely, we construct a channel-independent encoder-decoder pair and establish a universally achievable bound on the reliability that matches this converse bound in the high-rate regime, thereby characterizing the optimal universal reliability. Specifically, the channel-aware and universal exponents are governed by the Petz and sandwiched Rényi divergences, respectively. These divergences coincide for commuting outputs but differ for noncommuting ones, explaining why universality preserves optimal reliability classically but can reduce it quantumly. Our results showcase the fundamental reliability cost of performing the classical-quantum channel coding task universally.

0.30

Finite-blocklength classical communication over the quantum erasure channel with and without classical feedback

cs.IT quant-ph ·2026-09-30 ·Mark M. Wilde
similarity 0.65
Abstract · 46 pages, 11 figures

We determine the optimal success probability for transmitting a fixed number of classical messages through a finite number of uses of the quantum erasure channel, assisted by noiseless classical feedback and without initial shared entanglement. For an input dimension $d$, an erasure probability $p$, a blocklength $n$, and $M$ equiprobable messages, the optimal success probability is equal to $E[\min\{1,d^K/M\}]$, where $K$ is binomial with parameters $n$ and $1-p$. The converse allows arbitrary adaptive quantum encoders, quantum memories, and receiver instruments. Its main ingredient is an elementary dimension bound for noiseless quantum communication with classical feedback, proved by fixing the classical controls without conditioning the sender's state on the observed transcript. A classical protocol that transmits the base-$d$ digits of an integer representing the message, repeating each digit until the receiver acknowledges its reception or the prescribed blocklength is reached, attains the bound for every integer $M$. We also establish a relative-majorization property of erasure-channel outputs and exactly evaluate a hypothesis-testing converse, recovering the same numerical bound without feedback. That converse need not be achievable without feedback: four uses of the qubit erasure channel and four messages give a strict gap. A product-state code employing tetrahedral qubit states nevertheless outperforms every classical binary erasure code with these parameters. We give an explicit message-size formula and show that the bounded-remainder normal approximation and the average-success strong-converse exponent are unchanged without feedback. We also determine the feedback-assisted error exponent below capacity, prove that it agrees with the no-feedback exponent above a critical rate, and give no-feedback bounds at lower rates.

0.47

Universal recovery in approximate quantum error correction

cs.IT quant-ph ·2026-08-29 ·Dor Elimelech, Victor V. Albert, Alexander Barg
similarity 0.64
Abstract · v2: 40pp, 4 figures. Added experimental data to support the theory

Universal recovery -- the existence of a single recovery map that corrects an entire family of error channels -- is a central feature of quantum error correction (QEC). In exact QEC, linearity guarantees that a code correcting a given error set also corrects every channel whose Kraus operators lie in its linear span, and that a single recovery map suffices for all such channels. Approximate quantum error correction (AQEC), which relaxes perfect recovery to recovery with controlled error, has traditionally lacked this structure. In a recent paper (arXiv:2607.22995), we developed a theory of approximate quantum error correction showing that a restricted form of linearity persists in the approximate setting, yielding uniform AQEC guarantees for the family of channels controlled by a given error set. In this work, we complete the picture by establishing the second half of universal recovery in the approximate setting: a single recovery map can simultaneously correct every channel controlled by a given error set. The error-set theory we proposed quantifies approximate correctability through two parameters: the environment-leakage distance, governing worst-case performance, and the Knill--Laflamme Hellinger distance, governing average-case performance. We show here that both quantities also control universal decoding. We further study the Petz map naturally associated with an error set as an explicit universal recovery, and obtain uniform average- and worst-case guarantees across the entire family of channels.

0.40