On p490 of Nielsen and Chuang, 2010 the authors say that the preparation of the 'cat' state ($|000\ldots 0\rangle+|111\ldots 1\rangle$) is not Fault Tolerant. Below is my mock up of the diagram they draw for the preparation ($H$ and $C$-not-not *) and one part of the verification (the next two C-nots):

enter image description here

They then explain that this is not fault tolerant because a $Z$ error in the 'extra qubit' (i.e. that at the bottom of the diagram) propagates into two Z-errors in the ancilla qubits (the top three).

They they go onto say that this will not affect the Encoded data (I have not shown this in my diagram).

There are a couple of things that confuse me here. Firstly I cannot see how we get two $Z$-errors on the axillary qubits, Secondly even if we did get two $Z$-errors, surely this is a good thing as it will take our cat state back to the cat state? More the the crux of the issue - I cannot see what criterion they are using for fault tolerance here (I know what it means in the general case - i.e. unrecoverable error with probability no greater then $Cp^2$) and how there example violates it - Please can someone explain this to me.

*Not technical name - I couldn't find what it was actually called.

  • $\begingroup$ I don't think we have a special name for c-not-not. It's just two controlled nots with the same control. $\endgroup$
    – DaftWullie
    Commented Apr 21, 2018 at 16:20

2 Answers 2


First of all, the two conditions for fault tolerant measurements are:

  1. A single error gives no more than one error per block of qubits
  2. The measurement result needs to be correct with probability $1-\mathcal O\left(p^2\right)$

The preparation step creates the state $\frac{1}{\sqrt{2}}\left(\left|000\right>+\left|111\right>\right)$ (the three qubit 'cat state', also known as the three qubit GHZ state).

The 'ancilla verification' step is then applying two CNOTs on extra qubits (starting in the state $\left|0\right>$) to check the parities $Z_iZ_j$ to see if a bit flip has occurred.

So, assuming no errors, checking $Z_2Z_3$:

  • The state after preparation, before verification is $\frac{1}{\sqrt{2}}\left(\left|000\right>+\left|111\right>\right)\left|0\right>$
  • After the first CNOT on the extra qubit: $\frac{1}{\sqrt{2}}\left(\left|000\right>\left|0\right>+\left|111\right>\left|1\right>\right)$
  • After the second CNOT: $\frac{1}{\sqrt{2}}\left(\left|000\right>+\left|111\right>\right)\left|0\right>$
  • The extra qubit is now measured and returns $0$, showing no bit flip has occurred. There is a possibility, with probability $\mathcal O\left(p^2\right)$ of two bit flips occurring, where the probability of a single error is $p$.

Instead of the above, let's have a $Z$ error after the first CNOT. The state after this error (and before the second CNOT) is $\frac{1}{\sqrt{2}}\left(\left|000\right>\left|0\right>-\left|111\right>\left|1\right>\right)$. Applying the second CNOT then gives $\frac{1}{\sqrt{2}}\left(\left|000\right>-\left|111\right>\right)\left|0\right>$, which is the same as before, only now with a $Z$ error on the second ancilla qubit.

A controlled-$M$ operation on the encoded data (in the state $\left|\psi\right> = \alpha\left|0_L\right> + \beta\left|1_L\right>$), putting the system in the state $\frac{1}{\sqrt{2}}I_1Z_2I_3\left(\left|000\right>\left|\psi\right>+\left|111\right>M\left|\psi\right>\right) = \frac{1}{\sqrt{2}}\left(\left|000\right>\left|\psi\right>-\left|111\right>M\left|\psi\right>\right)$.

The decoding operation (C-NOT-NOT, followed by $H_1$ on the ancilla qubits) is then performed. The decoding C-NOT-NOT gives the state $$\frac{1}{\sqrt{2}}\left(\left|000\right>\left|\psi\right>-\left|100\right>M\left|\psi\right>\right) = \frac{1}{\sqrt{2}}Z_1Z_2I_3\left(\left|000\right>\left|\psi\right>+\left|100\right>M\left|\psi\right>\right)$$ and the $Z$ error is now on the first qubit, directly affecting the measurement result.

While it isn't necessarily clear that this is the case, it can be shown that $Z$ errors propagate 'backwards' through CNOT gates by starting with the state $\left|++\right> = \frac{1}{2}\left(\left|0\right>+\left|1\right>\right)\left(\left|0\right>+\left|1\right>\right)$ and applying a CNOT to return the same state. However, a $Z$ error on the second qubit returns the state $\left|--\right> = ZZ\left|++\right>$, showing the $Z$ error has propagated backwards.

In this sense, a single uncorrectable $Z$ error on an extra qubit eventually ends up causing $Z$ errors on multiple ancilla qubits (at a point where multiple $Z$ errors don't cancel) before the measurement and so, this part of the procedure is not fault tolerant as an error on multiple qubits happens with probability $p$ and the probability of a successful measurement outcome is $1-p$, so the whole process has to be repeated multiple times to achieve a better measurement outcome.

  • $\begingroup$ Ok thanks for your answer. In the state after the decoding C-NOT-NOT you have written: $\frac{1}{\sqrt{2}}Z_1Z_2I_3\left(\left|000\right>\left|\psi\right>+\left|100\right>M\left|\psi\right>\right)$ but this state is equal to $\frac{1}{\sqrt{2}}Z_1I_2I_3\left(\left|000\right>\left|\psi\right>+\left|100\right>M\left|\psi\right>\right)$ given this I am having problems interpreting your last paragraph. $\endgroup$ Commented Apr 22, 2018 at 8:58
  • $\begingroup$ @Quantumspaghettification It is, and that's a valid point that makes the whole thing a bit less clear. On the other hand, the probability that the measurement is correct is $1-p$, which is not good enough for fault tolerance, which requires the measurement to be correct with probability $1-\mathcal O\left(p^2\right)$. I've make an edit saying this $\endgroup$
    – Mithrandir24601
    Commented Apr 22, 2018 at 9:03
  • $\begingroup$ Ok thanks, given that I can see no other way of this making sense - I guess this is the intended meaning of the authors. $\endgroup$ Commented Apr 22, 2018 at 9:15

First a matter of terminology. I don't have my copy of Nielsen & Chuang to hand, but I would have thought that the bottom, extra qubit, is the one that is the ancilla. I am also not entirely convinced that the errors you're talking about can be correct. You seem to be talking about $Z$ errors, but giving results that correspond to $X$ errors. (If a $Z$-gate happens on the ancilla, it makes no difference, up to a global phase, because that qubit is always in a basis state and, as you state, 2 $Z$-errors on your original state give back the original state, so no harm done.)

What the ancilla qubit is doing here is comparing qubits 2 and 3; if they are in the same state (as they should be), you get a 0 answer. If they are in a different state, you get a 1 answer. Thus, if you get a 1 answer, you know something has gone wrong on one of your 3 main qubits, and needs correction. Let's say you've already tested to see that qubits 1 and 2 are the same, and they are. So, having found that qubits 2 and 3 are different, it must be that qubit 3 has the error (assuming the error occurred on one of the main qubits). So, you apply a bit-flip gate to qubit 3.

However, let me show you what could go wrong. Here, $X$ represents a bit-flip error. EC circuit with error This is the full syndrome circuit, where $|\psi\rangle$ is the cat state you produced before (also called a GHZ state).

Here, qubit 3 has the error, but you detect it on qubit 1. So, you correct it on qubit 1, and thus your state has 2 errors in it.

What does this have to do with fault-tolerance? Proofs of fault-tolerance are usually based around the idea of tracking the errors in each error correcting code (of which there are many, one for each logical qubit that you want). You can prove that provided each logical gate that you apply (preceded and followed by a round of error correction) only causes single errors on each logical qubit, then there is a threshold error probability below which these errors can be corrected away through the use of concatenated error correcting codes. So, the point is that the structure we've just talked about doesn't obey this. There is a place where a single error actually causes 2 errors on the error correcting code. Thus, the usual argument for fault tolerance does not apply. (Technically, this does not show that there aren't other arguments that could be made, it's just that the standard route doesn't work.)

  • $\begingroup$ (1:2) Thanks for this answer - it is very helpful. I note on you first paragraph: the circuit I drew was connected to another circuit (which I did not draw) in which the top three qubits did act as 'ancilla' (according the the authors). I also forgot to mention that the authors said the $Z$-error happened in between the C-nots on the extra qubit - thus it is not quite a global phase (sorry for forgetting this). Nevertheless the second part of your answer explains a lot - just one question: ... $\endgroup$ Commented Apr 21, 2018 at 16:33
  • $\begingroup$ (2:2) Is it generally take to not be Fault-Tolerant if a second error is introduced in this way i.e. by the error correcting procedure - could we not use a different set of error corrections where this does not occur? $\endgroup$ Commented Apr 21, 2018 at 16:35
  • $\begingroup$ @Quantumspaghettification I suspect in some situations you could compensate for this in a different way. As I tried to convey, the "one error per block" rule is a way that we know works. It doesn't mean there aren't others. Although I guess that when you're just doing small cases like the 3-bit repetition code, you probably can't. $\endgroup$
    – DaftWullie
    Commented Apr 21, 2018 at 16:46

Your Answer

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

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