**Encoding-decoding:** Quantum error correction codes work by *encoding* quantum states in a special way and then *decoding* when it is required to recover the original state without error. Clearly, this assumption is vulnerable if the quantum gates used in the process are themselves noisy. Fortunately, the quantum fault-tolerance theorem mentioned earlier comes to our rescue. In fact, error correction can be implemented fault-tolerantly, i.e., in such a way that it is insensitive to errors that occur during the error detection operations themselves.

Finally, there is the *threshold theorem that says that provided the noise in individual quantum gates is below a certain constant threshold it is possible to efficiently perform an arbitrarily large quantum computation.* There are caveats. Nevertheless, it is a remarkable theorem indicating that noise likely poses no fundamental barrier to the performance of large-scale quantum computations. Error correction codes related to this theorem are called *concatenated quantum codes.* In these codes, each qubit is itself further encoded in a hierarchical tree of entangled qubits. In this way, concatenated codes allow correctable quantum computations of unlimited duration!

The key idea is that if we wish to protect a message against the effects of noise, then we should encode the message by adding some redundant information to the message. That way, even if some bits of the message get corrupted, there will be enough redundancy in the encoded message to recover the message completely by decoding. This redundancy is essential. The amount of redundancy required depends on the severity of noise.

**Steps of error correction:** The steps are encoding, error detection, and recovery.

*Encoding*: Quantum states are encoded by unitary operations into a quantum error-correcting code, formally defined as a subspace *C* of some larger Hilbert space. This code may subsequently be affected by noise.

*Error detection*: A syndrome^{16} measurement is made to diagnose the type of error which occurred. In effect, the measured value tells us what procedure to use to recover the original state of the code.

*Recovery*: Post-syndrome measurement, a recovery operation returns the quantum system to the original state of the code.

We assume that all errors are the result of quantum interactions between a set of qubits and the environment. In addition, the possible errors for each single qubit considered are linear combinations of the following: no errors (*I*), bit flip errors (*X*), phase errors (*Z*), and bit flip phase errors (*Y*). Note that these are describable by Pauli matrices. A general form of a single-bit error is thus

^{16}Syndrome: a group or pattern of symptoms that together is indicative of a particular disease, disorder, or condition.