home | literature reviews

## "Fault-tolerant quantum computation", Peter Shor, 1996

*Reviewed January 14, 2024*

*Citation:* Shor, Peter W. "Fault-tolerant quantum computation." Proceedings of 37th conference on foundations of computer science. IEEE, 1996.

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

*Tags:* Foundational, Error-correcting-codes, Universal-scheme

This is the first paper to prove that fault-tolerant quantum computation is possible.
Shor's scheme is as follows. If the algorithm is supposed to run on n-qubits, then
one chooses a "nice" n-qubit classical code. Constructing the associated quantum CSS code,
properties of the well-chosen n-qubit classical code allow for fault tolerant gates to be implemented.

This first approach to quantum computation is certainly non-topological,
and is very clearly unpractical to implement on a real machine. Even worse,
to perform a polynomial-length algorithm the error rate needs to
scale like a reciprocal polylog. To achieve constant threshold
we would need to wait for Kitaev to introduce his topological methods:

> Kitaev, A. Yu. "Quantum error correction with imperfect gates." Quantum communication, computing, and measurement. Boston, MA: Springer US, 1997. 181-188.