Why or how is 'cat' state preparation via a C-not-not operation not fault tolerant?

Question

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):

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.}

Answer 1

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.

Answer 2

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. 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.)