What is it about?
Quantum stabilizer codes are the most foundational object driving the development of fault-tolerant quantum computers. They are the natural analog to classical linear codes, the object used by virtually all methods of protecting our computers from noise in the classical world. Almost all quantum stabilizer codes are incredibly good at shielding fragile quantum computers from noise. That is, for a typical quantum stabilizer code, it is possible in principle to recover from most errors. However, actually executing this recovery in practice has seemed to be incredibly costly in time. Is this fundamental? Can we design algorithms that actually can efficiently decode a typical quantum stabilizer code? We prove that the answer is no: unless widely believed cryptographic assumptions are broken, almost all quantum codes are fundamentally impossible to decode efficiently and are thus useless in practice, despite their otherwise excellent protective abilities.
Featured Image
Photo by A Chosen Soul on Unsplash
Why is it important?
The present frontier of quantum computing rests on our ability to make our quantum devices resistant to errors. A great deal of research has been dedicated towards designing extremely structured and specific quantum stabilizer codes, alongside carefully constructed decoding algorithms executing error recovery, which are often highly tailored to that specific code. This work proves that such highly tailored efforts are in fact necessary, as we cannot build a decoder which both runs efficiently and succeeds on most codes.
Perspectives
An interesting view of this result is that, perhaps contrary to intuition, the space of quantum stabilizer codes still "embeds" the space of classical linear codes. An important reason why the average-case complexity of quantum stabilizer decoding has remained open for some time is because, while we understand that classical linear codes are hard to decode on average, the set of classical linear codes takes up only a negligible amount of space in the larger world of quantum stabilizer codes—they are a tiny special case. Hence, it could have in principle been possible that classical linear codes constituted the hardest decoding problems, and "truly quantum" codes were otherwise somehow easy. In this work, we give an explicit proof that if we could decode a typical quantum code, we could decode a typical classical linear code. Consequently, despite the negligible space taken up by classical codes in the space of quantum codes, most quantum codes still hide a hard classical decoding problem within itself.
Jonathan Lu
Read the Original
This page is a summary of: Average-Case Complexity of Quantum Stabilizer Decoding, June 2026, ACM (Association for Computing Machinery),
DOI: 10.1145/3798129.3800800.
You can read the full text:
Contributors
The following have contributed to this page
