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:2608.09347

Binary code rate bounds via classical--quantum channels

Omar Alrabiah, Venkatesan Guruswami

cs.ITmath.COquant-phSubmitted Aug 10, 2026• Announced Aug 11, 2026• 8 citations
arXivHTMLPDF

Abstract

We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below $δ$, then every length-$n$ binary code, linear or nonlinear, of relative distance $δ$ has rate at most the channel's capacity, up to an $O(n^{-1/2})$ correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly. This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every $0 < δ< \frac{1}{2}$, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.

Comments
77 pages, 4 figures

Related papers

Comments on the recent improvements of the MRRW bounds

Alexander Barg

The asymptotic McEliece--Rodemich--Rumsey--Welch bound (1977) limits the largest attainable rate of binary codes as a function of the relative distance. After a nearly half-century hiatus, this result was recently improved in two concurrent works, by OpenAI and by O. Alrabiah and V. Guruswami. The two arguments look entirely different, a Delsarte certificate on the one hand, a classical-quantum channel and the pretty good measurement on the other, and they yield the same bound. The purpose of this note is to explain why: in both proofs, a subspace is attached to every codeword and moved with it, and the bound counts how many such subspaces fit in the ambient space, exactly in the first case and in the probabilistic sense of typicality in the second. We also present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.

cs.ITCross-listedarXiv:2609.01860•Sep 3, 2026

On the Duality Between the BSC and Quantum PSC

Narayanan Rengaswamy, Henry D. Pfister

In 2018, Renes [IEEE Trans. Inf. Theory, vol. 64, no. 1, pp. 577-592 (2018)] developed a general theory of channel duality for classical-input quantum-output channels. His result shows that a number of well-known duality results for linear codes on the binary erasure channel can be extended to general classical channels at the expense of using dual problems which are intrinsically quantum mechanical. One special case of this duality is a connection between coding for error correction on the quantum pure-state channel (PSC) and coding for wiretap secrecy on the classical binary symmetric channel (BSC). Similarly, coding for error correction on the BSC is related to wire-tap secrecy on the PSC. While this result has important implications for classical coding, the machinery behind the general duality result is rather challenging for researchers without a strong background in quantum information theory. In this work, we leverage prior results for linear codes on PSCs to give an alternate derivation of the aforementioned special case by computing closed-form expressions for the performance metrics. The noted prior results include the optimality of square-root measurement for linear codes on the PSC and the Fourier duality of linear codes.

IEEE International Symposium on Information Theory (ISIT)•Jul 12, 2021•2 citations

Reed–Muller Codes on CQ Channels via a New Correlation Bound for Quantum Observables

Avijit Mandal, Henry D. Pfister

The question of whether Reed-Muller (RM) codes achieve capacity on binary memoryless symmetric (BMS) channels has drawn attention since it was resolved positively for the binary erasure channel by Kudekar et al. in 2016. In 2021, Reeves and Pfister extended this to prove the bit-error probability vanishes on BMS channels when the code rate is less than capacity. In 2023, Abbe and Sandon improved this to show the block-error probability also goes to zero. These results analyze decoding functions using symmetry and the nested structure of RM codes. In this work, we focus on binary-input symmetric classicalquantum (BSCQ) channels and the Holevo capacity. For a BSCQ, we consider observables that estimate the channel input in the sense of minimizing the mean-squared error (MSE). Using the orthogonal decomposition of these observables under a weighted inner product, we establish a recursive relation for the minimum MSE estimate of a single bit in the RM code. Our results show that any set of$2^{o(\sqrt{\log N})}$bits can be decoded with high probability when the code rate is less than the Holevo capacity.

arXiv:2502.03785•IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•2 citations

Lower Bounds on Error Exponents via a New Quantum Decoder

Salman Beigi, Marco Tomamichel

We introduce a new quantum decoder based on a variant of the pretty good measurement, but defined via an alternative matrix quotient. We then use this novel decoder to derive new lower bounds on the error exponent both in the one-shot and asymptotic regimes for the classical-quantum and the entanglement-assisted channel coding problems. Our bounds are expressed in terms of measured (for the one-shot bounds) and sandwiched (for the asymptotic bounds) channel Rényi mutual information of order between 1/2 and 1. The bounds are not comparable with some previously established bounds for general channels, yet they are tight (for rates close to capacity) when the channel is classical. Finally, we also use our new decoder to rederive Cheng’s recent tight bound on the decoding error probability, which implies that most existing asymptotic results also hold for the new decoder.

arXiv:2310.09014•IEEE Transactions on Information Theory•Aug 20, 2024•10 citations

Quantum channel bounds for constant-composition codes

A. R. Akhiiarov, Peter Boyvalenkov, Danila Dmitrievich Cherkashin +1 more

We extend the quantum-channel optimization of Alrabiah and Guruswami to $q$-ary constant-composition codes. We study explicit channel and flag constructions that recover selected classical asymptotic upper bounds, including the Ben-Haim--Litsyn, moving-subspace and Horn-channel bounds. We give two equivalent formulations, Gram and flag, and prove stability of the obtained upper bounds under permutation transport and generalized shortening. A hierarchy defined by bounding the output-state ranks within each flag improves strictly between consecutive levels at every composition and every positive distance below the Plotkin threshold. We provide finite matrix parametrizations of these bounds (i.e., the number of variables does not depend on the length of codes under consideration). Numerical optimization rapidly produces improvements over the known asymptotic upper bounds throughout all tested nonbinary parameter ranges. For rational input data, each finite level admits near-optimal feasible rational descriptions of polynomial length. Their feasibility can be checked exactly and their objective values computed to any prescribed accuracy in polynomial time; the associated threshold problem with a prescribed gap belongs to $\mathsf{PromiseNP}$.

arXiv:2611.10827•Nov 7, 2026•0 citations

The minimum distance problem for two-way entanglement purification

Andris Ambainis, Daniel Gottesman

Entanglement purification takes a number of noisy EPR pairs |00>+|11> and processes them to produce a smaller number of more reliable pairs. If this is done with only a forward classical side channel, the procedure is equivalent to using a quantum error-correcting code (QECC). We instead investigate entanglement purification protocols with two-way classical side channels (2-EPPs) for finite block sizes. In particular, we consider the analog of the minimum distance problem for QECCs, and show that 2-EPPs can exceed the quantum Hamming bound and the quantum Singleton bound. We also show that 2-EPPs can achieve the rate k/n=1-(t/n)log/sub 2/3-h(t/n)-O(1/n) (asymptotically reaching the quantum Hamming bound), where the EPP produces at least k good pairs out of n total pairs with up to t arbitrary errors, and h(x)=-xlog/sub 2/x-(1-x)log/sub 2/(1-x) is the usual binary entropy. In contrast, the best known lower bound on the rate of QECCs is the quantum Gilbert-Varshamov bound k/n/spl ges/1-(2t/n)log/sub 2/3-h(2t/n). Indeed, in some regimes, the known upper bound on the asymptotic rate of good QECCs is strictly below our lower bound on the achievable rate of 2-EPPs.

arXiv:quant-ph/0310097•IEEE Transactions on Information Theory•Jan 25, 2006•31 citations
We derive the four principal asymptotic rate-distance tradeoffs for binary codes---Plotkin, Elias--Bassalygo, and the two McEliece--Rodemich--Rumsey--Welch (MRRW) bounds---from one theorem, the ``pretty good criterion.'' If the bit error rate under the pretty good measurement (PGM)---the quantum analog of posterior sampling---of a binary-input output-symmetric classical--quantum (cq) channel lies below δδδ, then every length-nnn binary code, linear or nonlinear, of relative distance δδδ has rate at most the channel's capacity, up to an O(n−1/2)O(n^{-1/2})O(n−1/2) correction. Rate--distance bounds thereby reduce to a channel design problem, wherein the task is to minimize channel capacity subject to the posterior bit error rate constraint. Via the pretty good criterion, the binary erasure channel (BEC) yields Plotkin, the binary symmetric channel (BSC) yields Elias--Bassalygo, the pure-state channel (PSC) yields the first MRRW bound, and a masked PSC yields the second MRRW bound exactly.
This framework is then instantiated with new channels to improve upon the MRRW bounds. Specifically, the mixed-qubit channel (MQC), a mixed-state version of PSC, strictly improves the first MRRW bound at every 0<δ<120 < δ< \frac{1}{2}0<δ<21​, while the masked mixed-qubit channel (2MQC) strictly improves the second MRRW bound throughout the same interval.
The asymptotic McEliece--Rodemich--Rumsey--Welch bound (1977) limits the largest attainable rate of binary codes as a function of the relative distance. After a nearly half-century hiatus, this result was recently improved in two concurrent works, by OpenAI and by O. Alrabiah and V. Guruswami. The two arguments look entirely different, a Delsarte certificate on the one hand, a classical-quantum channel and the pretty good measurement on the other, and they yield the same bound. The purpose of this note is to explain why: in both proofs, a subspace is attached to every codeword and moved with it, and the bound counts how many such subspaces fit in the ambient space, exactly in the first case and in the probabilistic sense of typicality in the second. We also present the OpenAI proof in the language and context of coding theory, as an extension of the spectral method in which the single vector attached to a codeword is replaced by a subspace.
In 2018, Renes [IEEE Trans. Inf. Theory, vol. 64, no. 1, pp. 577-592 (2018)] developed a general theory of channel duality for classical-input quantum-output channels. His result shows that a number of well-known duality results for linear codes on the binary erasure channel can be extended to general classical channels at the expense of using dual problems which are intrinsically quantum mechanical. One special case of this duality is a connection between coding for error correction on the quantum pure-state channel (PSC) and coding for wiretap secrecy on the classical binary symmetric channel (BSC). Similarly, coding for error correction on the BSC is related to wire-tap secrecy on the PSC. While this result has important implications for classical coding, the machinery behind the general duality result is rather challenging for researchers without a strong background in quantum information theory. In this work, we leverage prior results for linear codes on PSCs to give an alternate derivation of the aforementioned special case by computing closed-form expressions for the performance metrics. The noted prior results include the optimality of square-root measurement for linear codes on the PSC and the Fourier duality of linear codes.
The question of whether Reed-Muller (RM) codes achieve capacity on binary memoryless symmetric (BMS) channels has drawn attention since it was resolved positively for the binary erasure channel by Kudekar et al. in 2016. In 2021, Reeves and Pfister extended this to prove the bit-error probability vanishes on BMS channels when the code rate is less than capacity. In 2023, Abbe and Sandon improved this to show the block-error probability also goes to zero. These results analyze decoding functions using symmetry and the nested structure of RM codes. In this work, we focus on binary-input symmetric classicalquantum (BSCQ) channels and the Holevo capacity. For a BSCQ, we consider observables that estimate the channel input in the sense of minimizing the mean-squared error (MSE). Using the orthogonal decomposition of these observables under a weighted inner product, we establish a recursive relation for the minimum MSE estimate of a single bit in the RM code. Our results show that any set of2o(log⁡N)2^{o(\sqrt{\log N})}2o(logN​)bits can be decoded with high probability when the code rate is less than the Holevo capacity.
We introduce a new quantum decoder based on a variant of the pretty good measurement, but defined via an alternative matrix quotient. We then use this novel decoder to derive new lower bounds on the error exponent both in the one-shot and asymptotic regimes for the classical-quantum and the entanglement-assisted channel coding problems. Our bounds are expressed in terms of measured (for the one-shot bounds) and sandwiched (for the asymptotic bounds) channel Rényi mutual information of order between 1/2 and 1. The bounds are not comparable with some previously established bounds for general channels, yet they are tight (for rates close to capacity) when the channel is classical. Finally, we also use our new decoder to rederive Cheng’s recent tight bound on the decoding error probability, which implies that most existing asymptotic results also hold for the new decoder.
We extend the quantum-channel optimization of Alrabiah and Guruswami to qqq-ary constant-composition codes. We study explicit channel and flag constructions that recover selected classical asymptotic upper bounds, including the Ben-Haim--Litsyn, moving-subspace and Horn-channel bounds. We give two equivalent formulations, Gram and flag, and prove stability of the obtained upper bounds under permutation transport and generalized shortening. A hierarchy defined by bounding the output-state ranks within each flag improves strictly between consecutive levels at every composition and every positive distance below the Plotkin threshold. We provide finite matrix parametrizations of these bounds (i.e., the number of variables does not depend on the length of codes under consideration). Numerical optimization rapidly produces improvements over the known asymptotic upper bounds throughout all tested nonbinary parameter ranges. For rational input data, each finite level admits near-optimal feasible rational descriptions of polynomial length. Their feasibility can be checked exactly and their objective values computed to any prescribed accuracy in polynomial time; the associated threshold problem with a prescribed gap belongs to PromiseNP\mathsf{PromiseNP}PromiseNP.
Entanglement purification takes a number of noisy EPR pairs |00>+|11> and processes them to produce a smaller number of more reliable pairs. If this is done with only a forward classical side channel, the procedure is equivalent to using a quantum error-correcting code (QECC). We instead investigate entanglement purification protocols with two-way classical side channels (2-EPPs) for finite block sizes. In particular, we consider the analog of the minimum distance problem for QECCs, and show that 2-EPPs can exceed the quantum Hamming bound and the quantum Singleton bound. We also show that 2-EPPs can achieve the rate k/n=1-(t/n)log/sub 2/3-h(t/n)-O(1/n) (asymptotically reaching the quantum Hamming bound), where the EPP produces at least k good pairs out of n total pairs with up to t arbitrary errors, and h(x)=-xlog/sub 2/x-(1-x)log/sub 2/(1-x) is the usual binary entropy. In contrast, the best known lower bound on the rate of QECCs is the quantum Gilbert-Varshamov bound k/n/spl ges/1-(2t/n)log/sub 2/3-h(2t/n). Indeed, in some regimes, the known upper bound on the asymptotic rate of good QECCs is strictly below our lower bound on the achievable rate of 2-EPPs.