# Concatenated quantum code

I seem to running into a contradiction when trying to understand concatenated quantum codes.

Consider for concreteness the Shor code which is a $$[[9,1,3]]$$ stabilizer code. Let's concatenate it with itself, to form a $$[[81,1,9]]$$ code. According to the theory of stabilizer codes I should be able to correct up to $$\lfloor (9-1)/2 \rfloor = 4$$ errors. (See these slides (pdf file), slide 6 for the claim for a different code)

But I seem to be able to convince myself it can only correct up to 3 errors. My argument is as follows. Consider the arrangement of the 81 physical qubits in a line and consider blocks of 9; the first block of 9 qubits encode the first qubit of the inner Shor code, the second block of 9 qubits encode the second qubit of the inner Shor code etc. (The inner Shor code in turn encodes a single logical qubit).

Now consider two errors on the first block of 9 and two errors on the second block of 9 physical qubits. Since a single layer of Shor can only protect a single qubit error, these two errors on the first block can't be corrected by the outer Shor and get pushed to the inner Shor; similarly the two errors on the second block get pushed to the inner Shor. Thus the inner Shor gets faced with two errors and I would conclude we can't error correct overall. An explicit error that one may consider which is of this form could be $$X_1 X_2 X_{10} X_{11}$$.

But this is contradictory to the claim that 4 errors should be correctable. What is wrong with my line of reasoning?

More generally, since multiple $$(m)$$ concatenations of a stabilizer code generate a $$[[n^m, k, d^m]]$$ code (right? how to see this?), what is the best way to see that it can correct $$\lfloor (d^m-1)/2 \rfloor$$ errors?

• It might help to consider the same scenario, but with a concatenation of a three bit repetition code into itself. What happens there? Mar 25, 2023 at 17:57

$$\newcommand{\ket}[1]{|#1\rangle}$$

The short answer is given on the same slide "optimal decoding must pass information between the levels"

### Preparation calculations

To understand, let us work out some details by hand. Consider, the encoded basis states for the Shor code $$\ket{\bar{0}} = (\ket{000} + \ket{111})(\ket{000} + \ket{111})(\ket{000} + \ket{111}), \\ \ket{\bar{1}} = (\ket{000} - \ket{111})(\ket{000} - \ket{111})(\ket{000} - \ket{111}).$$ Let's compute the impact of various errors followed by corrections. If the error is $$X_1X_2$$, then $$X_1X_2\ket{\bar{1}} = (\ket{110} - \ket{001})(\ket{000} - \ket{111})(\ket{000} - \ket{111}).$$ The correction process will, identify (incorrectly) the error $$X_3$$ and correct to $$-(\ket{000} - \ket{111})(\ket{000} - \ket{111})(\ket{000} - \ket{111}) = -\ket{\bar 1}$$

Similarly, here are some sample results

Initial state Error State after correction
$$\ket{\bar 0}$$ $$X_1X_2$$ $$\ket{\bar 0}$$
$$\ket{\bar 1}$$ $$X_1X_2$$ -$$\ket{\bar 1}$$
$$\ket{\bar 0}$$ $$X_1X_2X_3$$ $$\ket{\bar 0}$$
$$\ket{\bar 1}$$ $$X_1X_2X_3$$ -$$\ket{\bar 1}$$
$$\ket{\bar 0}$$ $$X_1X_2X_4X_5$$ $$\ket{\bar 0}$$
$$\ket{\bar 1}$$ $$X_1X_2X_4X_5$$ $$\ket{\bar 1}$$

As you can see, the Shor code is quite remarkable. A worst case two-qubit or three-qubit bit flip only causes a phase error, instead of sending the state completely out of the code space. The example four qubit bit flip doesn't even cause an error.

### Example error $$X_1X_2X_{10}X_{11}$$

Armed with these results, let's work out when we have a doubly encoded Shor code. Some terminology for this code is as follows.

• There are 81 physical qubits, divided into 9 level 1 blocks.
• Each block is encoded via Shor code, leading to 9 level 1 encoded qubits (barred qubits).
• These 9 level 1 qubits are encoded once again with Shor code to yield one level 2 encoded qubit.

This level 2 encoded qubit has basis states $$\ket{\bar{\bar{0}}} = (\ket{\overline{000}} + \ket{\overline{111}})(\ket{\overline{000}} + \ket{\overline{111}})(\ket{\overline{000}} + \ket{\overline{111}}), \\ \ket{\bar{\bar{1}}} = (\ket{\overline{000}} - \ket{\overline{111}})(\ket{\overline{000}} - \ket{\overline{111}})(\ket{\overline{000}} - \ket{\overline{111}}),$$ where we have already identified the single-bar states above as the level 1 encoded qubits. I will refer to the three sets of three level 1 qubits above as 1st, 2nd and 3rd level-2 subblocks [1, 2].

In your example, we have the error $$X_1X_2X_{10}X_{11}$$. These are the two-qubit errors on the 1st and 2nd level-1/barred qubits. As we calculated in the table, these errors only yield a phase error after error-detection and correction at level 1. Explicitly $$X_1X_2$$ creates a phase error (after correction) on the 1st barred qubit, and $$X_{10}X_{11}$$ creates a phase error on the 2nd barred qubit. So after the level 1 error correction, the basis states go to $$\ket{\bar{\bar{0}}} \to (\ket{\overline{000}} + (-1)^2\ket{\overline{111}})(\ket{\overline{000}} + \ket{\overline{111}})(\ket{\overline{000}} + \ket{\overline{111}}), \\ \ket{\bar{\bar{1}}} \to (\ket{\overline{000}} - (-1)^2\ket{\overline{111}})(\ket{\overline{000}} - \ket{\overline{111}})(\ket{\overline{000}} - \ket{\overline{111}}).$$ This four-qubit error was completely corrected at level 1, and no errors will be detected or corrected at level 2 (inner code)!

### Example error $$X_1X_2X_{28}X_{29}$$

However, we can figure out errors that cause more trouble. Let's think about the error $$X_1X_2X_{28}X_{29}$$. This as you can note, impacts the 1st and 4th blocks at level 1. This time the phase flips don't cancel each other out, and we get $$\ket{\bar{\bar{0}}} \to (\ket{\overline{000}} - \ket{\overline{111}})(\ket{\overline{000}} - \ket{\overline{111}})(\ket{\overline{000}} + \ket{\overline{111}}), \\ \ket{\bar{\bar{1}}} \to (\ket{\overline{000}} + \ket{\overline{111}})(\ket{\overline{000}} + \ket{\overline{111}})(\ket{\overline{000}} - \ket{\overline{111}}).$$ Now, we seem to be in trouble. Naively running error detection at level 2, will identify a phase error in the 3rd level-2 sublock (the last parenthesis in the barred states above). Which if we correct, will distort our logical state - particularly, the effect is equivalent to a logical $$\bar{\bar{X}}$$ on the logical state. This is not what we wanted.

So with concatenated codes, we have to be smarter. Remember the short answer from above. We just ran level-1 error detection. We did not detect any errors in qubits 55-81 (the last three blocks at level 1 and the 3rd subblock at level 2). So, why would be think now that it is the 3rd level-2 subblock which has an error?

Going back, we remember that our error-detection on the 1st level-1 block we did some syndrome measurements. These measurements were consistent with either the error $$X_3$$ or $$X_1X_2$$. We choose to do corrections according to $$X_3$$ because one-qubit error is more likely than a two-qubit error. Similarly, for the 4th level 1 block we did the correction $$X_{30}$$ instead of $$X_{28}X_{29}$$. It seems like both of these choices were incorrect. The correct choice back then should have been $$X_1X_2X_{28}X_{29}$$. Therefore, its actually the 1st and 2nd subblocks at level 2, which have phase errors! Hence, we apply $$\bar{Z}_0\bar{Z}_1$$ as our correction. Which is correct.

In summary, being dumb would result in the correction $$X_3X_{30}$$ (at level 1) followed by $$\bar{Z_3}$$ (at level 2). Being smart is to realize that the correction $$X_3X_{30}$$ (at level 1) should be followed by $$\bar{Z}_0\bar{Z}_1$$ (at level 2).

### Other four-qubit error possibilities

One possibility is three flips inside one level 1 qubit, and one flip in another subblock entirely. For example, $$X_1X_2X_3X_{10}$$. It should be easy to see from the table that this will result in a phase error in the 1st level-2 subblock. This will be corrected without trouble at level 2.

Another possibility is all four flips in one level-1 qubit. For instance, $$X_1X_2X_3X_4$$. This is easy, as from the table we note that this results in no error.

I will let you figure out how things work out in the case of four-qubit $$Z$$ errors on the physical qubits.

By hand, the Shor code, due to being made up of two repetition codes, is easy to reason about. However, other codes such as non-CSS ones (eg. $$[[5,1,3]]$$) might be more difficult to reason about verbally.
[1] This is necessitated by the fact that the Shor code itself is a concatentated code. Other doubly encoded codes such as the $$[[7,1,3]]$$ won't have these subblocks.