Approaching the Quantum Singleton Bound with Approximate Error Correction

It is well known that no quantum error correcting code of rate R can correct adversarial errors on more than a (1 -R)/4 fraction of symbols. But what if we only require our codes to approximately recover the message?

In this work, we construct efficiently-decodable approximate quantum codes against adversarial error rates approaching the quantum Singleton bound of (1 -R)/2, for any constant rate R. Specifically, for every R ∈ (0, 1) and γ > 0, we construct codes of rate R, message length k, and alphabet size 2 O(1/γ 5 ) , that are efficiently decodable against a (1-R-γ)/2 fraction of adversarial errors and recover the message up to inverse-exponential error 2 -Ω(k) .

At a technical level, we use classical robust secret sharing and quantum purity testing to reduce approximate quantum error correction to a suitable notion of quantum list decoding. We then instantiate our notion of quantum list decoding by (i) defining and constructing folded quantum Reed-Solomon codes, and (ii) applying a new, quantum version of distance amplification.