Quantum Colloquium — 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. Moreover, the size of the alphabet is a constant independent of the message length and the recovery error is exponentially small in the message length.

Central to our construction is a notion of quantum list decoding and an implementation involving folded quantum Reed-Solomon codes.

Joint work with Thiago Bergamaschi (UC Berkeley) and Louis Golowich (UC Berkeley). 

Panel discussion: Steve Flammia (AWS), Venkatesan Guruswami (Simons Institute, UC Berkeley), Debbie Leung (University of Waterloo), Umesh Vazirani (Simons Institute, UC Berkeley)