3
$\begingroup$

If we have two quantum error-correcting qubit $[[n_1, 1, d_1]]$ and $[[n_2,1,d_2]]$ codes then the notes of Preskill says that the concatenation of the codes is a code of distance at least $d_1d_2.$

Could someone prove it mathematically?

By concatenation, I mean the code given by the encoding map $\phi_2^{\otimes n_1}\circ \phi_1,$ where $\phi_i$ is the encoding map of $[[n_i, 1, d_i]]$ code.

$\endgroup$
1
  • $\begingroup$ How do the logical operators map through the concatenation operation? $\endgroup$
    – DaftWullie
    Commented Oct 2, 2023 at 6:33

2 Answers 2

1
$\begingroup$

Distance of concatenated codes without assumptions on their structure is at least $d_1 d_2 /2$.

Another way to think about the distance is as how many qubits one should fault to trick the code's decoder. Let $C_{1},C_{2}$, not necessary liner/stabilizer/quantum/classic/whatever, codes and let $D_{1},D_{2}$ be their decoders. One can easily build the following decoder for the concatenated code $ C_{1} \circ C_{2}$ by decoding first each of the $n_{2}$-tuples (disjoint partition of $n_1 \cdot n_2$) by $D_{2}$ and then apply $D_{1}$ while treating any of the tuple, which each encodes a logical qubit, as physical qubit.

To trick that decoder, one has to construct a fault such that after the decoding step of $D_{2}$, the remaining state will be seen in the $n_1$-logical qubit space as a fault that tricks $D_1$. Therefore, at least $d_{1}/2$ of the $n_2$-tuples have to be corrupted such $D_2$ will fail to correct them, and for that, at least $d_2/2$ qubits of each tuple have to be corrupted. In over all we obtain that $d_{1}d_{2}/4$ have to be corrupted, so the new distance is $d_{1}d_{2}/2$.

Assuming that the codes are CSS codes, distance is at least $d_{1}d_{2}$.

In the context of CSS codes defined by $C_{X},C_{Z} \rightarrow C = C_{X}/C_{Z}^\perp$, the distance equals the minimum hamming weight of codeword in the code. Using that definition, one can repeat the above, but instead of constructing a fault, construct a non-trivial code word. At least $d_{1}$ of $n_{2}$-logical tuples have to encode a non-zero bit, so each of them contributes at least $d_{2}$ for the hamming weight. Thus, the total hamming weight must be at least $d_{1}d_{2}$. For getting a complete picture, it is left to prove that a concatenation of CSS codes gives a CSS code.

$\endgroup$
2
  • $\begingroup$ I am confused. Is the claim by Preskill false then? $\endgroup$
    – SiOn
    Commented Oct 3, 2023 at 3:26
  • $\begingroup$ Not necessarily, the distance still might be $ d_1 d_2 $, but it is just hard to prove without assuming structure. Yet, in the context of threshold theorems, when the decoders are exactly as defined above, the statement is "wrong" (for any code) in the sense that $d_1 d_2 /4 $ is a fault. $\endgroup$
    – Dudu Ponar
    Commented Oct 4, 2023 at 7:54
0
$\begingroup$

This is not proof the question is asking for, but a comment on the other answer, that the result about distances is much more general than that. However, it is too large for a comment.


Concatenating two codes $[\![n_1,k_1,d_1]\!]$ (as outer layer) and $[\![n_2,k_2,d_2]\!]$(as inner layer) gives you a resultant code $[\![n,k,d]\!]$ where

Case(1):

  • $n = n_1 n_2\,,$
  • $k = k_1 k_2 \,,$
  • $d \geq d_1 d_2\,,$

holds true if $n_1 (\text{mod } {k_2}) \neq 0\,.$

Case(2):

  • $n = \frac{n_1 n_2}{k_2}\,,$
  • $k = k_1 \,,$
  • $d \geq \frac{d_1 d_2}{k_2}\,,$

holds true if $n_1(\text{mod } {k_2}) =0\,.$

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