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) introducing folded quantum Reed-Solomon codes, and (ii) applying a new, quantum version of distance amplification.

Authors

• Thiago Bergamaschi
• Louis Golowich
• Sam Gunn

Keywords

• Quantum Error Correction
• Quantum Secret Sharing