Fault-tolerant quantum computation

TLDR

Quantum computing promises dramatic speedups, but decoherence and cumulative gate errors threaten long computations, limiting practical implementation. The authors argue that these obstacles are less severe than previously thought. They demonstrate that quantum operations can be executed directly on data encoded with error‑correcting codes without decoding. They construct polynomial‑size circuits that tolerate O(1/log^c t) error per gate for t‑gate computations, improving the prior O(1/t) bound.

Abstract

It has recently been realized that use of the properties of quantum mechanics might speed up certain computations dramatically. Interest in quantum computation has since been growing. One of the main difficulties in realizing quantum computation is that decoherence tends to destroy the information in a superposition of states in a quantum computer making long computations impossible. A further difficulty is that inaccuracies in quantum state transformations throughout the computation accumulate, rendering long computations unreliable. However, these obstacles may not be as formidable as originally believed. For any quantum computation with t gates, we show how to build a polynomial size quantum circuit that tolerates O(1/log/sup c/t) amounts of inaccuracy and decoherence per gate, for some constant c; the previous bound was O(1/t). We do this by showing that operations can be performed on quantum data encoded by quantum error-correcting codes without decoding this data.