The Anti-Infinity Parade

Oct 30, 2022

Algorithms for code concatenation

My goal is to compute fault-tolerance thresholds for stabililzer codes. To this end, we need to understand how to concatenate quantum codes. Briefly, code concatenation is when a state is encoded first by one code, then the encoded qubits again by same or another code. The resultant qubits may be encoded again by another code, and so on. The entire concatenation of codes can be treated as a single code, which has a larger number of physical qubits than any of the individual codes but also a larger a distance.

In our study of code concatenation, we are interested in the following:

  • What are the generators of the concatenated code?
  • How to perform encoding and logical operations of the code?
  • How to do error correction.

Today, I will be mostly interested in the first question. My development will follow the algorithms presented by Gaitan [1], though I have made significant advances in the clarity of the arguments.

First foray: a two layer concatenation

Suppose, we encode k1k_1 qubits using the code C1[[n1,k1,d1]]C_1 \sim [[n_1,k_1,d_1]]. This yields n1n_1 encoded qubits. We then take each of these qubits, and encode each one separately using C2[[n2,k2=1,d2]]C_2 \sim [[n_2, k_2 = 1, d_2]]. We will refer to the concatenated code as C=C2C1C = C_2 \circ C_1.

This process can be visualized as follows. The numbers indicate how many elements are in the box to their right.

"k2=1 concatenation"

Let's first consider the question of generators. The generators of C1C_1 are {gi1,i=0,,n1k11}\{g_i^1, i=0,\dots,n_1-k_1-1\} and C2C_2 are {gi2,i=0,,n22}\{g_i^2, i=0,\dots,n_2-2\}. What are the generators of CC? To answer this, let ψk1\ket{\psi}_{k_1} be a state of k1k_1 qubits that is to be encoded. The first encoding is written as ψk1C1ψˉn1.\ket{\psi}_{k_1} \stackrel{C_1}{\to} \ket{\bar\psi}_{n_1}. We note for now that for all ii, gi1ψˉ=ψˉ.g_i^1\ket{\bar\psi} = \ket{\bar\psi}.

Now, for the second round of encoding, we will separate each of the n1n_1 qubits and encode each one using C1C_1. To write this, let λ=(λ0,λ1,,λn11)\lambda = (\lambda_0, \lambda_1,\dots, \lambda_{n_1-1}). Then ψˉ=λi=0,1αλλ01λ11λn111.\ket{\bar\psi} = \sum_{\lambda_i = 0,1} \alpha_\lambda \ket{\lambda_0}_1 \otimes \ket{\lambda_1}_1 \otimes \cdots \otimes \ket{\lambda_{n_1-1}}_1. When we encode each qubit, we obtain, ψˉC2ψˉˉ=λi=0,1αλλˉ0n2λˉ1n2λˉn11n2,\ket{\bar\psi} \stackrel{C_2}{\to} \ket{\bar{\bar\psi}} = \sum_{\lambda_i = 0,1} \alpha_\lambda \ket{\bar\lambda_0}_{n_2} \otimes \ket{\bar\lambda_1}_{n_2} \otimes \cdots \otimes \ket{\bar\lambda_{n_1-1}}_{n_2}, where the bars in λˉin2\ket{\bar\lambda_i}_{n_2} indicate that it is an encoded state, and the subscript indicates that it has n2n_2 qubits. To summarize, let us call each block of n2n_2 qubits E(b)E(b), where b=0,,n11b=0,\dots,n_1-1 because there are n1n_1 such blocks.


In this way, our doubly encoded state is a n1n2n_1n_2 qubit state. Overall, we have encoded k1k_1 qubits into n=n1n2n=n_1n_2 qubits. This means that the concatenated code must have n1n2k1n_1n_2-k_1 generators. Let's find them.

(1) Consider a generator gl2g^2_l of C2C_2, which is a n2n_2 qubit operator, but we have to be careful over which qubits it acts. For instance, we can write gl2Inn2g^2_l \otimes I_{n-n_2} to obtain an operator that acts on the first n2n_2 qubits of nn total qubits. Similarly, we can write In2gl2In2n2I_{n_2} \otimes g^2_l \otimes I_{n-2n_2} to obtain an operator that acts on the next n2n_2 qubits. This notation will get tedious fast, so let's just write gl2[i,j]g^2_l[i,j] to indicate that gl2g^2_l acts on qubits i,i+1,,j1i, i+1, \dots, j-1, where ji=n2j-i = n_2.

Now, it's quite easy to see from definition that for all ii, gl2[n2i,n2(i+1)]λˉin2=λˉin2,g^2_l[n_2 i, n_2 (i+1)] \ket{\bar\lambda_i}_{n_2} = \ket{\bar\lambda_i}_{n_2}, i.e. if gl2g^2_l is made to act on the ii-th block of n2n_2 qubits in the final block, it will be a stabilizer operation. In other words, we have discovered that the set {gl2[n2i,n2(i+1)],l=0,,n22,i=0,,n11}\{g^2_l[n_2 i, n_2(i+1)], l=0,\dots,n_2-2, i=0, \dots, n_1-1\} stabilizes the state ψˉˉ\ket{\bar{\bar\psi}}. We can count that there are n1(n21)n_1(n_2-1) such operators.

(2) But wait, there are more operators that stabilize the state ψˉˉ\ket{\bar{\bar\psi}}. Let ξ2\xi_2 be the encoding operation for C2C_2. Then ξ2n1\xi_2^{\otimes n_1} is the encoding operations for the second step. Conversely, (ξ2n1)\left(\xi_2^{\otimes n_1}\right)^\dagger is the decoding operation. Then, (ξ2n1)ψˉˉ=ψˉ\left(\xi_2^{\otimes n_1}\right)^\dagger\ket{\bar{\bar\psi}} = \ket{\bar\psi}. We noted earlier that gl1g^1_l stabilizes this state. Hence, ξ2n1gl1(ξ2n1)ψˉˉ=ψˉˉ.\xi_2^{\otimes n_1}g^1_l\left(\xi_2^{\otimes n_1}\right)^\dagger\ket{\bar{\bar\psi}} = \ket{\bar{\bar\psi}}.

Hence, the set {ξ2n1gl1(ξ2n1),l=0,,n1k11}\{\xi_2^{\otimes n_1}g^1_l\left(\xi_2^{\otimes n_1}\right)^\dagger, l = 0, \dots, n_1-k_1-1\} must also stabilize the doubly encoded state. There are n1k1n_1-k_1 such operators.

In total, we have n1(n21)+(n1k1)=n1n2k1n_1(n_2-1) + (n_1-k_1) = n_1n_2-k_1 stabilizers. As we have found sufficient number of stabilizers, we are done.

How to put this mathematics into practice

Let's try to construct the algorithm that creates the generators of the concatenated code. We will depend on the vector representation of the Pauli operators.

(1) Constructing the first set of generators is very simple. We just have to do some shifting. Note that gl2g^2_l, an operator on n2n_2 qubits, is represented by a vector of length 2n22n_2. We have to construct, gl2[n2i,n2(i+1)]g^2_l[n_2 i, n_2(i+1)], an operator over nn qubits, which is represented by a vector of length 2n2n. The code is right there is the notation.

Call g=gl2g=g^2_l. Then

# for each of the E(b) blocks
for b in range(n_1):
    for each g:
        encoded_g = zeros((1,2*n))
        # for the X part
        encoded_g[n_2*b: n_2*(b+1)] = g[:n2]
        # for the Z part
        encoded_g[n + n_2*b: n + n_2*(b+1)] = g[n2:]

(2) For the second set, we have to do a little bit of work to understand encoding. If we use C2C_2 to encode a qubit, it takes the logical operators X,ZX, Z of the qubit and maps them to the encoded Xˉ=ξ2Xξ2,Zˉ=ξ2Xξ2\bar{X} = \xi_2X\xi_2^\dagger, \bar{Z} = \xi_2 X\xi_2^\dagger. In vector notation, X=(10)X=(1|0) and Z=(01)Z=(0|1) and these are mapped to vectors of length 2n22n_2. This mapping is already known and we have constructed it before.

Now, we have gl1g^1_l which is an operator over n1n_1 qubits, which means it is the product of n1n_1 different Pauli operators, i.e. gl1=P0P1Pn11g^1_l = P_0 \otimes P_1 \otimes \cdots \otimes P_{n_1-1}. It is represented by a vector of length 2n12n_1. So {ξ2n1gl1(ξ2n1)=ξ2P0ξ2ξ2P1ξ2ξ2Pn11ξ2.\{\xi_2^{\otimes n_1}g^1_l\left(\xi_2^{\otimes n_1}\right)^\dagger = \xi_2P_0\xi_2^\dagger \otimes \xi_2P_1\xi_2^\dagger \otimes \cdots \otimes \xi_2P_{n_1-1}\xi_2^\dagger. Our algorithm is now clear. We iterate over the operators in g=gl1g=g^1_l and encode each according to the mapping Xˉ=ξ2Xξ2,Zˉ=ξ2Xξ2\bar{X} = \xi_2X\xi_2^\dagger, \bar{Z} = \xi_2 X\xi_2^\dagger. We have to be careful about the shifting as before, because ξ2Piξ2\xi_2P_i\xi_2^\dagger acts on qubits n2in_2 i to n2(i+1)1n_2 (i+1) - 1.

# declare
# logical_x
# logical_z
for each g:
    encoded_g = zeros((1,2*n_1*n_2))
    for i in range(n1):
        if g[i] and g[n+i]: #P_i is the Y operator
            # multipling operators corresponds to adding their vectors mod 2
            encoded_g[n2*i: n2*(i+1)] += logical_x[:n2] + logical_z[:n2]
            encoded_g[n + n2*i: n + n2*(i+1)] += logical_x[n2:] + logical_z[n2:]
        elif g[i]: # P_i is the X operator
            encoded_g[n2*i: n2*(i+1)] += logical_x[:n2]
            encoded_g[n + n2*i: n + n2*(i+1)] += logical_x[n2:]
        elif g[n+i] # P_i is the Z operator
            encoded_g[n2*i: n2*(i+1)] += logical_z[:n2]
            encoded_g[n + n2*i: n + n2*(i+1)] += logical_z[n2:]    

That wasn't too difficult.

k2k_2 does not have to be 11, but k2k_2 divides n1n_1

Let us now relax the assumption that k2=1k_2=1, but let it be an interger that divides n1n_1. This will complicate the encoding in the second round. As before, the first round is ψk1C1ψˉn1.\ket{\psi}_{k_1} \stackrel{C_1}{\to} \ket{\bar\psi}_{n_1}. Because n1n_1 is divisible by k2k_2, these n1n_1 qubits can be divided into n1/k2n_1/k_2 blocks, each of size k2k_2. Let the blocks of qubits be called B(b)B(b) for b=0,,n1/k21b=0,\dots,n_1/k_2-1. Let γ=(γ0,,γn1/k11)\gamma = (\gamma_0,\dots,\gamma_{n_1/k_1-1}), and let BB be the basis of a 2k22^{k_2} dimensional Hilbert space. We can write the first-round encoded state as ψˉn1=γiBαγγ0k2γ1k2γn1/k21k2,\ket{\bar\psi}_{n_1} = \sum_{\ket{\gamma_i}\in B} \alpha_\gamma \ket{\gamma_0}_{k_2} \otimes \ket{\gamma_1}_{k_2} \otimes \cdots \otimes \ket{\gamma_{n_1/k_2 - 1}}_{k_2}, broken up into a sum over k2k_2-qubit basis states.

Now, we encode each block using C2C_2, to create a new encoded block E(b)E(b) of size n2n_2. This creates the final state ψˉn1C2ψˉˉ=γiBαγγˉ0n2γˉ1n2γˉn1/k21n2.\ket{\bar\psi}_{n_1} \stackrel{C_2}{\to}\ket{\bar{\bar\psi}} = \sum_{\ket{\gamma_i}\in B} \alpha_\gamma \ket{\bar\gamma_0}_{n_2} \otimes \ket{\bar\gamma_1}_{n_2} \otimes \cdots \otimes \ket{\bar\gamma_{n_1/k_2 - 1}}_{n_2}. This final state has n1/k2n_1/k_2 blocks each of size n2n_2 qubits, for a total of n=n1n2/k2n = n_1n_2/k_2 qubits. Hence, in this code k1k_1 qubits are encoded to n1n2/k2n_1n_2/k_2 qubits, which is fewer than before.

"k2 divides n1 concatenation"

The structure of the generators is similar to what we had above.

(1) If we apply the operator gl2g^2_l to the bb-th encoded block E(b)E(b), when the qubits are in state ψˉˉ\ket{\bar{\bar\psi}} we find that it stabilizes the state. Hence, it must be a stabilizer of the doubly encoded state. As before the n2n_2 sized operator gl2g^2_l when acting on the bb-th block is labelled gl2[n2b,n2(b+1)]g^2_l[n_2 * b, n_2 * (b+1)]. It's algorithmic implementation is as before, except the change in the number of blocks E(b)E(b).

(2) What about the gl1g^1_l associated generators? Things are a bit more convoluted because of the grouping of the qubits. Now, note that ξ2\xi_2 is an operator that takes k2k_2 qubits to n2n_2 qubits, and in the second encoding, we apply ξ2\xi_2 to each group B(b)B(b) of qubits. This means that ξ2n1/k2ψˉ=ψˉˉ.\xi_2^{\otimes n_1/k_2}\ket{\bar\psi} = \ket{\bar{\bar\psi}}. Hence, our stabilizers are given by ξ2n1/k2gl1(ξ2n1/k2)ψˉˉ=ψˉˉ.\xi_2^{\otimes n_1/k_2}g^1_l\left(\xi_2^{\otimes n_1/k_2}\right)^\dagger\ket{\bar{\bar\psi}} = \ket{\bar{\bar\psi}}.

How do we process ξ2n1/k2gl1(ξ2n1/k2)\xi_2^{\otimes n_1/k_2}g^1_l\left(\xi_2^{\otimes n_1/k_2}\right)^\dagger? If, as before, gl1=P0P1Pn1g^1_l = P_0 \otimes P_1\otimes \cdots \otimes P_{n_1}, then we break it up according to B(b)B(b) into chunks of k2k_2, to form gl1=(P0Pk21)(Pk2P2k21)(P(n1/k21)k2Pn11).g^1_l = (P_0 \otimes \dots \otimes P_{k_2-1}) \otimes (P_{k_2} \otimes \dots \otimes P_{2k_2-1}) \otimes \dots \otimes (P_{(n_1/k_2-1)k_2} \otimes \dots \otimes P_{n_1-1}). Then, ξ2n1/k2gl1(ξ2n1/k2)=ξ2(P0Pk21)ξ2ξ2(P(n1/k21)k2Pn11)ξ2.\xi_2^{\otimes n_1/k_2}g^1_l\left(\xi_2^{\otimes n_1/k_2}\right)^\dagger = \xi_2(P_0 \otimes \dots \otimes P_{k_2-1})\xi_2^\dagger \otimes \dots \otimes \xi_2(P_{(n_1/k_2-1)k_2} \otimes \dots \otimes P_{n_1-1})\xi_2^\dagger.

What do these arcane incantations mean? Just concentrate on one to-be-encoded block B(b), which has k2k_2 qubits. k2k_2 qubits have k2k_2 many XX operators, one for each qubit; k2k_2 many ZZ operators, etc. ξ2\xi_2 encodes these into encoded operators. So ξXjξ=Xˉji=0,,k21,\xi X_j \xi^\dagger = \bar{X}_j \quad i=0,\dots,k_2-1, ξZjξ=Zˉji=0,,k21,\xi Z_j \xi^\dagger = \bar{Z}_j \quad i=0,\dots,k_2-1, ξPjξ=Pˉji=0,,k21,Pi=Xi,Zi.\xi P_j \xi^\dagger = \bar{P}_j \quad i=0,\dots,k_2-1, \quad P_i = X_i, Z_i.

This means that in the operators ξ2(Pk2bPk2(b+1)1)ξ2\xi_2(P_{k_2b} \otimes \dots \otimes P_{k_2(b+1)-1} )\xi_2^\dagger acting on B(b)B(b), the jj-th operator PjP_j is encoded to Pˉj\bar{P}_j. This results in ξ2(Pˉk2bPˉk2(b+1)1)ξ2\xi_2(\bar{P}_{k_2b} \otimes \dots \otimes \bar{P}_{k_2(b+1)-1} )\xi_2^\dagger, which act on the E(b)E(b) block.

Recall that the B(b)B(b) block corresponds to qubits [k2b,k2(b+1)][k_2b, k_2(b+1)] and E(b)E(b) corresponds to qubits [n2b,n2(b+1)][n_2b, n_2(b+1)].

The algorithm acquires an additional loop over the blocks

# declare
# logical_xs
# logical_zs
encoded_g = zeros((1,2*n))
# iterate over each block
for b in range(n1/k2):
    # extract the B(b) block from the generator
    g_block_x = g[k2*b: k2*(b+1)]
    g_block_z = g[n1+k2*b:n1+k2*(b+1)]
    # now iterate over the qubits in the block
    for i in range(k2):
        if g_block_x[i] and g_block_z[i]: #P_i is the Y operator
            # place the $i$-th encoded logical gate into the E(b) block in the encoded_g
            encoded_g[n2*b: n2*(b+1)] += logical_xs[i][:n2] + logical_zs[i][:n2]
            encoded_g[n + n2*b: n + n2*(b+1)] += logical_xs[i][n2:] + logical_zs[i][n2:]
        elif g_block_x[i]: # P_i is the X operator
            encoded_g[n2*b: n2*(b+1)] += logical_xs[i][:n2]
            encoded_g[n + n2*b: n + n2*(b+1)] += logical_xs[i][n2:]
        elif g_block_z[i] # P_i is the Z operator
            encoded_g[n2*i: n2*(b+1)] += logical_zs[i][:n2]
            encoded_g[n + n2*b: n + n2*(b+1)] += logical_zs[i][n2:]    

Stac implements these algorithms, so you can concatenate arbitrary codes. Here is the example from the book reproduced. The code [[4,2,2]][[4,2,2]] is concatenated with itself. Note that k2=2k_2=2 and n1=4n_1=4 so k2k_2 divides n1n_1.

import stac
import numpy as np
# define the code
cd = stac.CommonCodes.generate_code('[[4,2,2]]')
# book uses a different set of logical operators
# than stac computes using the Gottesman method
cd.logical_xs = np.array(
[[1, 0, 1, 1, 0, 0, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 1]])
cd.logical_zs = np.array(
[[1, 0, 1, 0, 1, 1, 1, 0],
[0, 1, 0, 0, 0, 0, 1, 1]])

# this will create a new code object,
# and immediately compute the generator matrix
concat_code = stac.ConcatCode((cd, cd))
# display the generator matrix
# answer is correct







Let k2k_2 not divide n1n_1

Things are getting a bit more complicated. If we encode a block of k1k_1 qubits into a block of n1n_1 using C1C_1, then there is no way of dividing up the n1n_1 qubits into k2k_2-sized blocks that can be encoded using C2C_2.

"k2 does not divides n1 concatenation"

(1) The solution is to start with k2k_2 blocks of k1k_1 qubits each, which we will label as q(c), for c=1,,k2c=1,\dots,k_2. So our initial state will be Ψ=ψ0k1ψ1k1ψk21k1,\ket{\Psi} = \ket{\psi^0}_{k_1} \otimes \ket{\psi^1}_{k_1} \otimes \cdots \otimes \ket{\psi^{k_2-1}}_{k_1}, where there are k2k_2 terms in the product. We have a total of k2k1k_2k_1 qubits. Note that this steps means we have given up on the ability to encode an unknown quantum state, for which we only have one copy. However, for quantum computational algorithms, we rarely start with an unknown state, so this is a not a big impediment.

(2) Next, we encode each block q(c)q(c) using C1C_1 into a block Q(c)Q(c) of n2n_2 qubits. We obtain ΨC1Ψˉ=ψˉ0n1ψˉ1n1ψˉk21n1,\ket{\Psi} \stackrel{C_1}{\to} \ket{\bar\Psi} = \ket{\bar\psi^0}_{n_1} \otimes \ket{\bar\psi^1}_{n_1} \otimes \cdots \otimes \ket{\bar\psi^{k_2-1}}_{n_1}, which has a total of k2n1k_2n_1 qubits.

(3) For the next step, we will need to rearrange the qubits. We are going to pick the first qubit in each Q(c)Q(c) and make that one block, take the second qubit in each Q(c)Q(c) and make those a block, and so on. Each new block will be called B(b)B(b). Since, there are k2k_2 many Q(c)Q(c) blocks, each block B(b)B(b) will of size k2k_2 as well, And because the size of Q(c)Q(c) is n1n_1, there will be n1n_1 many B(b)B(b) blocks, with b=0,,n11b=0,\dots,n_1-1.

To make this explicit, we operate on the states we created above. First, we expand one term in the product above in some basis to obtain ψˉjn1=λi=0,1αλλ0jλ1jλn11jn1.\ket{\bar\psi^j}_{n_1} = \sum_{\lambda_i = 0,1}\alpha_\lambda\ket{\lambda_0^j\lambda_1^j\cdots\lambda^j_{n_1-1}}_{n_1}. Then, Ψˉ=λi0=0,1αλ0λ00λ10λn110n1λik21=0,1αλk21λ0k21λ1k21λn11k21n1.\ket{\bar\Psi} = \sum_{\lambda^0_i = 0,1}\alpha_\lambda^0\ket{\lambda^0_0\lambda^0_1\cdots\lambda^0_{n_1-1}}_{n_1} \otimes \cdots \otimes \sum_{\lambda^{k_2-1}_i = 0,1}\alpha_\lambda^{k_2-1}\ket{\lambda^{k_2-1}_0\lambda^{k_2-1}_1\cdots\lambda^{k_2-1}_{n_1-1}}_{n_1}. We can now rearrange these to obtain, Ψˉ=λi0,,λk21=0,1αλ0αλk21λ00λ01λ0k21k2λn210λn211λn21k21k2.\ket{\bar\Psi} = \sum_{\lambda^0_i,\dots,\lambda^{k_2-1}= 0,1}\alpha_\lambda^0\cdots\alpha_\lambda^{k_2-1} \ket{\lambda^0_0\lambda^1_0\cdots \lambda^{k_2-1}_0}_{k_2} \otimes \cdots \otimes \ket{\lambda^0_{n_2-1}\lambda^1_{n_2-1}\cdots \lambda^{k_2-1}_{n_2-1}}_{k_2}. To summarize, this state has n1n_1 blocks of size k2k_2 for a total of n1k2n_1k_2 qubits.

(4) We can now encode each block using C2C_2. Hence, ΨˉC2Ψˉˉ=λi0,,λk21=0,1αλ0αλk21λ00λ01λ0k21n2λn210λn211λn21k21n2.\ket{\bar\Psi} \stackrel{C_2}{\to} \ket{\bar{\bar\Psi}} = \sum_{\lambda^0_i,\dots,\lambda^{k_2-1}= 0,1}\alpha_\lambda^0\cdots\alpha_\lambda^{k_2-1} \ket{\overline{\lambda^0_0\lambda^1_0\cdots \lambda^{k_2-1}_0}}_{n_2} \otimes \cdots \otimes \ket{\overline{\lambda^0_{n_2-1}\lambda^1_{n_2-1}\cdots \lambda^{k_2-1}_{n_2-1}}}_{n_2}. This state now has n1n_1 blocks E(b)E(b) of size n2n_2, for a total of n1n2n_1n_2 qubits.

In summary, this concatenated code encodes k=k1k2k=k_1k_2 qubits into n=n1n2n=n_1n_2 qubits.

Obtaining the generators

We are now going to determine the generators of the final encoded state. Note, that we need a total of n1n2k1k2n_1n_2-k_1k_2 generators.

(1) As before, the generators of C2C_2 must by definition stabilize the state of each block E(b)E(b), gl2λ00λ01λ0k21n2=λ00λ01λ0k21n2.g^2_l\ket{\overline{\lambda^0_0\lambda^1_0\cdots \lambda^{k_2-1}_0}}_{n_2} = \ket{\overline{\lambda^0_0\lambda^1_0\cdots \lambda^{k_2-1}_0}}_{n_2}.

Hence, we assign a copy of all generators gl2g^2_l for each block E(b)E(b) to our collection. This means n1(n2k2)n_1(n_2-k_2) generators. The algorithm is the same, except for the number of E(b)E(b) blocks.

(2) The encoding of the C1C_1 generators is much more subtle. If gl1g^1_l is applied to a Q(c)Q(c) block, it stabilizes the state ψˉ\ket{\bar\psi}. But in the subsequent re-ordering, Q(c)Q(c) is broken up. To start with an example, consider gl1g^1_l acting on Q(0)Q(0), g1l=P0P1Pn11.g^l_1 = P_0 \otimes P_1 \otimes \cdots \otimes P_{n_1-1}. Where do the qubits that these PiP_i act on go after the re-ordering. Since, this is the 00-th block, PiP_i now acts on the 00-th position in the B(i)B(i) block. Subsequently, when we encode each B(i)B(i) using C2C_2, each of the PiP_i will map the the corresponding 00-th logical operator. Meaning if Pi=XP_i=X, then after encoding it should be Xˉ0\bar{X}_0. In the same way, if gl1g^1_l acts on Q(c)Q(c), then all its constitutive Pauli operators PiP_i go to the cc-th location in B(i)B(i) and hence should be mapped to Pˉc\bar{P}_c.

The algorithm for this is as follows:

# declare
# logical_xs
# logical_zs
# iterate over each block Q(c)
for c in range(k2):
    for each g:
        encoded_g = zeros((1,2*n))
        # now iterate over the qubits in g
        for i in range(n1):
            if g[i] and g[n+i]: #P_i is the Y operator
                # place the c-th encoded logical gate into the E(b) block in the encoded_g
                encoded_g[n2*i: n2*(i+1)] += logical_xs[c][:n2] + logical_zs[c][:n2]
                encoded_g[n + n2*i: n + n2*(i+1)] += logical_xs[c][n2:] + logical_zs[c][n2:]
            elif g[i]: # P_i is the X operator
                encoded_g[n2*i: n2*(i+1)] += logical_xs[c][:n2]
                encoded_g[n + n2*i: n + n2*(i+1)] += logical_xs[c][n2:]
            elif g[n+i] # P_i is the Z operator
                encoded_g[n2*i: n2*(i+1)] += logical_zs[i][:n2]
                encoded_g[n + n2*i: n + n2*(i+1)] += logical_zs[c][n2:] 

We can also reproduce the example from the book, in which C1=[[5,13]]C_1=[[5,13]] and C2=[[4,2,2]]C_2 = [[4,2,2]].

cd2 = stac.CommonCodes.generate_code('[[5,1,3]]')
concat_code = stac.ConcatCode((cd2, cd))



















Stac can just put the two algorithms together and concatenate an arbitrary number of codes.

concat_code = stac.ConcatCode((cd, cd2, cd2))
A [[100,2]] code

A final note about distance

The book shows that if C1C_1 has distance d1d_1 and C2C_2 has distance d2d_2, then the concatenated code CC has distance at least d1d2d_1d_2. We will look into this more next time.

[1] Gaitan, Frank, Quantum Error Correction and Fault Tolerant Quantum Computing (CRC Press, 2008).