Citation: Crepeau, Claude, Daniel Gottesman, and Adam Smith. "Approximate quantum error-correcting codes and secret sharing schemes." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 2005.
Web: https://arxiv.org/abs/quant-ph/0503139
Tags: Error-correcting-codes, Approximate-structure, Computer-scientific
In this lovely article, the authors show a discrepancy between the behavior of exact quantum error correcting codes and approximate quantum error correcting codes. This discrepancy has to do with the ability to correct arbitrary errors. For an exact code storing information spread between n registers, it is known that it is impossible to correct arbitrary errors on n/4 of the registers. This is because the Knill-Laflamme condition implies that correcting arbitrary errors on n/4 of the registers is equivalence to being able to correct n/2 erasure errors, which would allow you to clone the state by splitting into two copies, which is impossible by the no-cloning theorem. However, the authors show that there are approximate error correcting codes which can approximately fix (n-1)/2 arbitrary errors. To make the approximation better, one needs to work with larger on-register Hilbert space dimensions. This has no contradiction with the Knill-Laflamme condition, because the implication between correcting arbitrary errors and erasure errors breaks down in the approximate setting.
As a special case, they show that there is a 3-register code that can correct arbitrary errors on any one of the registers. Again, to make the correction increasingly good, one needs increasingly larger on-register Hilbert spaces. This is in contrast to the exact case, where there are not codes which can protect all of the registers.
At first, it is unclear whether this paper can be used for any sort of asymptotic advantage because one needs increasingly larger on-register Hilbert spaces. The fantastic update paper is
> Bergamaschi, Thiago, Louis Golowich, and Sam Gunn. "Approaching the quantum singleton bound with approximate error correction." Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024.
There, they show that using a constant size alphabet, and the error of the recovery maps decreases exponentially with system size. Their construction can work with codes of arbitrarily high rates. This hints that approximate codes might be have some practical advantage.