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.
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.
We study the error correcting properties of Haar random codes, in which a K-dimensional code space C⊆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 m Pauli errors can be approximately corrected so long as mK≪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.
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.
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 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 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.
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.
Reed-Muller codes encode an m-variate polynomial of degree r by evaluating it on all points in {0,1}m. We denote this code by RM(m,r). The minimal distance of RM(m,r) is 2m−r and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this work we give an efficient algorithm (in the block length n=2m) for decoding random errors in Reed-Muller codes far beyond the minimal distance. Specifically, for low rate codes (of degree r=o(m)) we can correct a random set of (1/2−o(1))n errors with high probability. For high rate codes (of degree m−r for r=o(m/logm)), we can correct roughly mr/2 errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m,m−(2r+2)) for which the same erasure pattern can be corrected in RM(m,m−(r+1)). The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding Reed-Muller codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.