In the book "Quantum Computation and Quantum Information," one of the definitions for fault-tolerant measurement is mentioned as "any single component in the procedure results in an error in at most one qubit in each encoded block of qubits at the output of the procedure."

There are a few things I don't understand about this definition. Firstly, regarding the term "single component," does it refer only to errors occurring on a single qubit or does it also include two-qubit errors that occur on a single two-qubit gate? If it includes such two-qubit errors, I don't understand why it treat a single component containing 1 qubit error and 2 qubit errors as an error occurring, rather than the number of errors?

Additionally, I'm having trouble understanding what it means to be fault-tolerant when there is "at most one qubit in each encoded block of qubits at the output of the procedure". If the definition of being fault-tolerant is that if there's a one qubit error in the input, and if after the syndrome measurement process there's at most one qubit error, then I can understand the concept of fault tolerance in the sense that the error that should have been correctable within the capacity of the code will not become an error that's uncorrectable.

However, I don't quite understand the intention of defining fault tolerance in terms of the relationship between the error of a single component and the number of errors at the output of the procedure.


1 Answer 1


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.

Steane code syndrome measurements

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.