home | literature reviews

## "Good quantum error-correcting codes exist", Robert Calderbank, Peter Shor, 1996

*Reviewed March 14, 2024*

*Citation:* Calderbank, A. Robert, and Peter W. Shor. "Good quantum error-correcting codes exist." Physical Review A 54.2 (1996): 1098.

*Web:* https://arxiv.org/abs/quant-ph/9512032

*Tags:* Computer-scientific, Foundational, Error-correcting-code, Information-theory

This is the paper which introduced CSS (Calderbank-Shor-Steane) codes. The work
by Steane was done independently of Calderbank and Shor, and was published
around the same time:

> Steane, Andrew M. "Error correcting codes in quantum theory." Physical Review Letters 77.5 (1996): 793.

These codes work by taking two orthogonal classical error correcting codes,
and making a new quantum code whose Tanner graph is the hypergraph product
of the Tanner graphs of the two classical codes. One of the classical
codes has its parity checks become X-checks, and the other classical
code has its parity checks become Z-checks. In a CSS code, all of
the stabilizers are Pauli. Moreover, all of the checks either include
all Xs or all Zs - there are no mixed terms or Ys. The best
example of CSS codes is the toric code, which is a hypergraph
product of two repetition codes. A more modern treatment
of CSS codes can be found here:

> Tillich, Jean-Pierre, and Gilles ZĂ©mor. "Quantum LDPC codes with positive rate and minimum distance proportional to the square root of the blocklength." IEEE Transactions on Information Theory 60.2 (2013): 1193-1202.

A key thing to remember is that finding good quantum codes is easy
and was done in this original work by Shor and Calderbank. The hard
part is doing it while using low density checks, which is
required by the locality of physics.

As with many of these LDPC papers, the authors
are very concerned with the implications for
quantum information theory. The last section
of this paper is a discussion of
noise in quantum channels. This
is the paper where the idea of
a noisy quantum channel was introduced,
and the important first observations were made.