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

Haar random codes attain the quantum Hamming bound, approximately

Fermi Ma, Xinyu Tan, John Wright

Published Oct 8, 2025• 9 citations
arXivHTMLPDF

Abstract

We study the error correcting properties of Haar random codes, in which a $K$-dimensional code space $\boldsymbol{C} \subseteq \mathbb{C}^N$ is chosen at random from the Haar distribution. Our main result is that Haar random codes can approximately correct errors up to the quantum Hamming bound, meaning that a set of $m$ Pauli errors can be approximately corrected so long as $mK \ll N$. This is the strongest bound known for any family of quantum error correcting codes (QECs), and continues a line of work showing that approximate QECs can significantly outperform exact QECs [LNCY97, CGS05, BGG24]. Our proof relies on a recent matrix concentration result of Bandeira, Boedihardjo, and van Handel.

DOI
10.48550/arxiv.2510.07158

Related papers

Random Error Models in Quantum Error Correction

Matthew Coudron, C. A. Pasternak

We examine the performance of quantum error correcting codes subjected to random Haar distribution transformations of weight t. Rather than requiring correction of all errors, we require some high probability that a random error is corrected. We find that, for any integer i and arbitrarily high probability p < 1, there are codes which perfectly correct errors up to weight t and can correct errors up to weight t + i with probability at least p. We also find an analog to the quantum Hamming bound for the new error model. Lastly, we prove that codes generated from classical Reed-Muller codes can correct errors of weight up to 3d/4 with a probability approaching 1 as the length of the code increases, whereas they can only correct up to weight d/2 perfectly.

•Jan 1, 2013•0 citations

Spectral Properties and Coding Transitions of Haar-Random Quantum Codes

Grace M. Sommers, J. Alexander Jacoby, Zack Weinstein +2 more

A quantum error-correcting code with a nonzero error threshold undergoes a mixed-state phase transition when the error rate reaches that threshold. We explore this phase transition for Haar-random quantum codes, in which the logical information is encoded in a random subspace of the physical Hilbert space. We focus on the spectrum of the encoded system density matrix as a function of the rate of uncorrelated, single-qudit errors. For low error rates, this spectrum consists of well-separated bands, representing errors of different weights. As the error rate increases, the bands for high-weight errors merge. The evolution of these bands with increasing error rate is well described by a simple analytic ansatz. Using this ansatz, as well as an explicit calculation, we show that the threshold for Haar-random quantum codes saturates the hashing bound, and thus coincides with that for random codes. For error rates that exceed the hashing bound, typical errors are uncorrectable, but postselected error correction remains possible until a much higher threshold. Postselection can in principle be implemented by projecting onto subspaces corresponding to low-weight errors, which remain correctable past the hashing bound.

arXiv:2510.07396•PRX Quantum•Apr 3, 2026•3 citations

The Quantum Hamming Bound in Arbitrary Local Dimension

Yu-Xuan Zhang, Jing-Ling Chen

The quantum Hamming bound arises from a direct dimension estimate for exact quantum error-correcting codes. For nondegenerate codes, distinct correctable errors map the code space into orthogonal subspaces, so dimension counting directly gives the bound; degeneracy allows these subspaces to overlap and invalidates the argument. Although linear-programming, asymptotic, and structural approaches have advanced the problem from several directions, the general local-dimension case has remained open. Here we prove the quantum Hamming bound for every local dimension $q\ge3$. Building on the exact two-center Fourier reduction, we develop new overlap estimates for nonbinary Hamming spaces. For $q\ge4$, Jacobi estimates and monotonicity give a uniform gap; qutrits form the boundary case where the gap vanishes and are handled by a filtered correction. This completes the finite-length nonbinary case; together with the existing qubit result, it establishes the quantum Hamming bound for arbitrary local dimension.

quant-pharXiv:2606.22538•Jun 23, 2026•2 citations

Approximate quantum error correction can lead to better codes

Debbie Leung, Michael A. Nielsen, Isaac L. Chuang +1 more

We present relaxed criteria for quantum error correction that are useful when the specific dominant quantum noise process is known. As an example, we provide a four-bit code that corrects for a single amplitude damping error. This code violates the usual Hamming bound calculated for a Pauli description of the error process and has no simple explanation in terms of the usual Pauli basis GF(4) codes.

arXiv:quant-ph/9704002•Physical Review A•Oct 1, 1997•233 citations

Approximate quantum error correction, random codes, and quantum channel capacity

Rochus Klesse

We work out a theory of approximate quantum error correction that allows us to derive a general lower bound for the entanglement fidelity of a quantum code. The lower bound is given in terms of Kraus operators of the quantum noise. This result is then used to analyze the average error correcting performance of codes that are randomly drawn from unitarily invariant code ensembles. Our results confirm that random codes of sufficiently large block size are highly suitable for quantum error correction. Moreover, employing a lemma of Bennett, Shor, Smolin, and Thapliyal, we prove that random coding attains information rates of the regularized coherent information.

arXiv:quant-ph/0701102•Physical Review A•Jun 13, 2007•43 citations

Trade-off between the tolerance of located and unlocated errors in nondegenrate quantum

Henry L. Haselgrove, Peter P. Rohde

In a recent study [Rohde et al., quant-ph/0603130 (2006)] of several quantum error correcting protocols designed for tolerance against qubit loss, it was shown that these protocols have the undesirable effect of magnifying the effects of depolarization noise. This raises the question of which general properties of quantum error-correcting codes might explain such an apparent trade-off between tolerance to located and unlocated error types. We extend the counting argument behind the well-known quantum Hamming bound to derive a bound on the weights of combinations of located and unlocated errors which are correctable by nondegenerate quantum codes. Numerical results show that the bound gives an excellent prediction to which combinations of unlocated and located errors can be corrected {\em with high probability} by certain large degenerate codes. The numerical results are explained partly by showing that the generalized bound, like the original, is closely connected to the information-theoretic quantity the {\em quantum coherent information}. However, we also show that as a measure of the exact performance of quantum codes, our generalized Hamming bound is provably far from tight.

arXiv:quant-ph/0605183•Quantum Information and Computation•May 1, 2008•6 citations
We study the error correcting properties of Haar random codes, in which a KKK-dimensional code space C⊆CN\boldsymbol{C} \subseteq \mathbb{C}^NC⊆CN is chosen at random from the Haar distribution. Our main result is that Haar random codes can approximately correct errors up to the quantum Hamming bound, meaning that a set of mmm Pauli errors can be approximately corrected so long as mK≪NmK \ll NmK≪N. This is the strongest bound known for any family of quantum error correcting codes (QECs), and continues a line of work showing that approximate QECs can significantly outperform exact QECs [LNCY97, CGS05, BGG24]. Our proof relies on a recent matrix concentration result of Bandeira, Boedihardjo, and van Handel.
We examine the performance of quantum error correcting codes subjected to random Haar distribution transformations of weight t. Rather than requiring correction of all errors, we require some high probability that a random error is corrected. We find that, for any integer i and arbitrarily high probability p < 1, there are codes which perfectly correct errors up to weight t and can correct errors up to weight t + i with probability at least p. We also find an analog to the quantum Hamming bound for the new error model. Lastly, we prove that codes generated from classical Reed-Muller codes can correct errors of weight up to 3d/4 with a probability approaching 1 as the length of the code increases, whereas they can only correct up to weight d/2 perfectly.
A quantum error-correcting code with a nonzero error threshold undergoes a mixed-state phase transition when the error rate reaches that threshold. We explore this phase transition for Haar-random quantum codes, in which the logical information is encoded in a random subspace of the physical Hilbert space. We focus on the spectrum of the encoded system density matrix as a function of the rate of uncorrelated, single-qudit errors. For low error rates, this spectrum consists of well-separated bands, representing errors of different weights. As the error rate increases, the bands for high-weight errors merge. The evolution of these bands with increasing error rate is well described by a simple analytic ansatz. Using this ansatz, as well as an explicit calculation, we show that the threshold for Haar-random quantum codes saturates the hashing bound, and thus coincides with that for random codes. For error rates that exceed the hashing bound, typical errors are uncorrectable, but postselected error correction remains possible until a much higher threshold. Postselection can in principle be implemented by projecting onto subspaces corresponding to low-weight errors, which remain correctable past the hashing bound.
The quantum Hamming bound arises from a direct dimension estimate for exact quantum error-correcting codes. For nondegenerate codes, distinct correctable errors map the code space into orthogonal subspaces, so dimension counting directly gives the bound; degeneracy allows these subspaces to overlap and invalidates the argument. Although linear-programming, asymptotic, and structural approaches have advanced the problem from several directions, the general local-dimension case has remained open. Here we prove the quantum Hamming bound for every local dimension q≥3q\ge3q≥3. Building on the exact two-center Fourier reduction, we develop new overlap estimates for nonbinary Hamming spaces. For q≥4q\ge4q≥4, Jacobi estimates and monotonicity give a uniform gap; qutrits form the boundary case where the gap vanishes and are handled by a filtered correction. This completes the finite-length nonbinary case; together with the existing qubit result, it establishes the quantum Hamming bound for arbitrary local dimension.
We work out a theory of approximate quantum error correction that allows us to derive a general lower bound for the entanglement fidelity of a quantum code. The lower bound is given in terms of Kraus operators of the quantum noise. This result is then used to analyze the average error correcting performance of codes that are randomly drawn from unitarily invariant code ensembles. Our results confirm that random codes of sufficiently large block size are highly suitable for quantum error correction. Moreover, employing a lemma of Bennett, Shor, Smolin, and Thapliyal, we prove that random coding attains information rates of the regularized coherent information.
In a recent study [Rohde et al., quant-ph/0603130 (2006)] of several quantum error correcting protocols designed for tolerance against qubit loss, it was shown that these protocols have the undesirable effect of magnifying the effects of depolarization noise. This raises the question of which general properties of quantum error-correcting codes might explain such an apparent trade-off between tolerance to located and unlocated error types. We extend the counting argument behind the well-known quantum Hamming bound to derive a bound on the weights of combinations of located and unlocated errors which are correctable by nondegenerate quantum codes. Numerical results show that the bound gives an excellent prediction to which combinations of unlocated and located errors can be corrected {\em with high probability} by certain large degenerate codes. The numerical results are explained partly by showing that the generalized bound, like the original, is closely connected to the information-theoretic quantity the {\em quantum coherent information}. However, we also show that as a measure of the exact performance of quantum codes, our generalized Hamming bound is provably far from tight.