2
$\begingroup$

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?

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

1 Answer 1

5
$\begingroup$

$\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.

Final comments

I am not aware of a general algorithm to do this sort of clever error correction for concatenated codes. Though it shouldn't be that difficult.

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.

[2] The 1st subblock at level 2 is made of the 1st three blocks at level 1, which in turn are made of physical qubits 1-27.

$\endgroup$

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.