Let us ground ourselves in a simple example to understand what error propagation looks like and how it can cause havoc. Suppose we have a single logical qubit that we want to store unchanged for some period of time. For this purpose, we encode it using some error-correction code into $n$ physical qubits. Periodically, we do syndrome measurements and if an error is detected, we correct it.
Assume that we are using the Steane code, which has (non-fault-tolerant) syndrome measurements of the following form.
Let's assume that an $X$ error occurs on qubit 7 after the $H$ and the first $CX$. The qubits 0-3,7 look like this.
It should be clear that this single error propagates to qubits 1,2,3 due to the $CX$. So, this very act to trying to detect errors can cause 3 errors in the data qubits. As we know the Steane code can correct at most one error, so our logical qubit is now destroyed.
If instead consider an error that occurs a bit later.
This only causes one additional error in the data qubits and will be corrected in the next round of error-correction.
We learn that the syndrome measurement circuit is not very tolerant of faults/errors within it if the error occurs in the wrong location. So we need to design better circuits that don't collapse so catastrophically.
To move towards a better design, we need to define what condition that design obeys.
Def: A block of qubits is the $n$ physical qubits required for one error-correction code.
Ex. In the Steane code, the 7 data qubits form one block. They are augmented by 6 ancilla qubits. If we have two logical qubits in our circuits, then we will have two blocks of qubits (each consisting of 7 qubits), augmented by a total of 12 ancilla qubits.
Suppose now we have $B$ blocks in our circuit.
Def: A fault-tolerant circuit is one in which if an error occurs on one of the physical qubits (data or ancilla), then that error propagates to at most one data qubit in each of the $B$ blocks.
This definition implies many things.
- If an error occurs on an ancilla qubit for block $i$, then it can propagate to a data qubit in block $i$.
- But if an error occurs on a data qubit in block $i$, then it can't propagate at all to any other data qubit in block $i$.
- If errors occurs on two physical qubits, then we can allow them propagate to $2B$ data qubits in the circuit, with a maximum of 2 per block.
This is a very strong definition. We can ask, why don't we tolerate more errors if the code we are using can correct multiple errors. For instance, if instead of the Steane code, we were using a $[[n,k,7]]$, code above, which can correct three errors. Then those three propagated errors would have been fixed in the next round of error-correction. But as it turns out, we don't need to allow it. We can prove that even with a max-one-error-propagation limit, that quantum error-correction can be used to suppress errors enough to do useful computation. I am referring to the so called fault-tolerance threshold theorem.
Perhaps, someone can prove that even with a higher limit, one can prove the theorem, but to my knowledge, it has not been done yet.
Reference: Gaitan 2008
