Building CSS Codes from Classical Codes

Hello! Welcome to your tenth lesson in our module on Quantum Error Correction Fundamentals.

In our last session, we took a focused look at the classical world, establishing the algebraic machinery of linear codes. You learned how to define a code C using either a generator matrix G or a parity-check matrix H, and, most importantly, you explored the powerful concept of the dual code C^⊥.

Today, we'll see the direct payoff of that work. We will use the tools of classical coding theory to construct the Calderbank-Shor-Steane (CSS) codes, a large and fundamentally important family of quantum stabilizer codes. This construction elegantly demonstrates how properties of classical codes translate into the ability to protect quantum information.

Your learning outcome for this lesson is to: Construct a Calderbank-Shor-Steane (CSS) code from a pair of classical linear codes and derive its distance and logical operators.

We'll see that the key to building a valid CSS code lies in a specific orthogonality relationship between two classical codes—a relationship defined precisely by the dual code concept you've just mastered.

1. The CSS Construction: A "Divide and Conquer" Strategy

The core idea behind CSS codes is to handle bit-flip (X) errors and phase-flip (Z) errors independently, using the machinery of classical codes that are designed to correct bit-flips.

Recall that a classical code C is defined by its parity-check matrix H, where a bit string c is a codeword if Hc^T = 0. An error e is detected if He^T ≠ 0.

The CSS construction uses two classical linear codes to build one quantum code:

1. An [n, k_Z, d_Z] classical code, let's call it C_Z. We use its (n-k_Z) × n parity-check matrix, H_Z, to define Z-type stabilizers. For each row h in H_Z, we create a stabilizer S = Z^h. These stabilizers are designed to detect X errors. An X error X^e will anticommute with Z^h if e \cdot h \neq 0. The full set of Z stabilizers can detect any X error X^e as long as e is not a codeword in C_Z.

2. An [n, k_X, d_X] classical code, C_X. We use its (n-k_X) × n parity-check matrix, H_X, to define X-type stabilizers. For each row h' in H_X, we create a stabilizer S' = X^{h'}. These stabilizers detect Z errors. Any Z error Z^e is detected as long as e is not a codeword in C_X.

The Crucial Commutativity Condition

For this set of X-type and Z-type operators to form a valid stabilizer group S, they must all commute with each other.

• Two X-type stabilizers always commute with each other.
• Two Z-type stabilizers always commute with each other.
• An X-type stabilizer X^{h_x} (where h_x is a row of H_X) commutes with a Z-type stabilizer Z^{h_z} (where h_z is a row of H_Z) if and only if their supports have an even number of overlapping qubits. This is equivalent to the condition h_x \cdot h_z = 0 (mod 2).

For all stabilizers to commute, every row of H_X must be orthogonal to every row of H_Z. This implies the matrix product H_X H_Z^T = 0.

Now, let's connect this to what we know about dual codes. The rows of H_X form a basis for the dual code C_X^\perp. The condition H_X H_Z^T = 0 means that every basis vector of C_X^\perp is in the null space of H_Z. The null space of H_Z is, by definition, the code C_Z. This leads to the fundamental design rule for CSS codes:

CSS Condition: C_X^\perp \subseteq C_Z

Because of the symmetric nature of duality ((C^\perp)^\perp = C), this also implies the reverse condition: C_Z^\perp \subseteq C_X. The parity checks of one code must be codewords in the other.

To see a formal walkthrough of this construction, please read the following resource.

When this condition is met, we successfully form a quantum stabilizer code CSS(C_X, C_Z).

• Physical Qubits (n): Same as the block length of the classical codes.
• Stabilizer Generators: There are (n - k_X) independent X-type generators and (n - k_Z) independent Z-type generators. The total number of independent generators is (n - k_X) + (n - k_Z).
• Logical Qubits (k): The number of logical qubits is n minus the number of independent stabilizers.
  $k=n-(n-k_X)-(n-k_Z)=k_X+k_Z-n$
  This gives us a [[n, k_X + k_Z - n]] quantum code.

2. Example: The Steane Code

The Steane [[7, 1, 3]] code is a canonical example of the CSS construction. It is built from just one classical code: the famous Hamming [7, 4, 3] code, which we'll call C_H.

From the previous lesson, we know that C_H is an [n, k] = [7, 4] code. Its dual, C_H^\perp, is an [n, n-k] = [7, 3] code. A special property of the Hamming code is that it is weakly self-dual, meaning C_H^\perp \subseteq C_H. (This is not true for general codes).

This property makes it perfect for the CSS construction. We can choose both classical codes to be the Hamming code:

• C_X = C_H
• C_Z = C_H

The CSS condition C_X^\perp \subseteq C_Z becomes C_H^\perp \subseteq C_H, which we know is true.

Let's calculate the parameters of the resulting quantum code:

• n = 7
• k_X = 4, k_Z = 4
• k = k_X + k_Z - n = 4 + 4 - 7 = 1

So we get a [[7, 1]] code. We have successfully encoded one logical qubit into seven physical qubits. The stabilizers are generated from the parity-check matrix of the Hamming code, H_H.

• Z-stabilizers: The 3 rows of H_H define 3 Z-type stabilizers (e.g., ZIZIZIZ, IZZIIZZ, IZIZIZZ).
• X-stabilizers: The same 3 rows of H_H define 3 X-type stabilizers (e.g., XIXIXIX, IXXIIXX, IXIXIXX).

3. Logical Operators and Distance

The power of a code is determined by its distance, which is the weight of the smallest non-trivial logical operator. For a CSS code, the logical operators have a particularly clear interpretation.

An operator is a logical operator if it commutes with all stabilizers but is not itself a product of stabilizers. Let's analyze a purely X-type logical operator, X_L = X^c.

• Commuting with Stabilizers: X^c must commute with all Z-type stabilizers (Z^{h_z} for h_z a row of H_Z). This requires c \cdot h_z = 0 for all such h_z, which is precisely the condition for c to be a codeword in C_Z.
• Not a Stabilizer: X^c must not be in the stabilizer group S. The X-type stabilizers are of the form X^a where a \in C_X^\perp.

Combining these, a non-trivial logical X operator is of the form X^c where c \in C_Z \setminus C_X^\perp. Symmetrically, a non-trivial logical Z operator is Z^c where `c \in C_X \setminus C_Z^\perp$.

The distance of the quantum code is the minimum weight of such an operator. We define two separate distances for X and Z errors:

• The logical X distance, d_X, is the minimum weight of a non-trivial logical X operator: d_X = \min\{ \text{wt}(c) \mid c \in C_Z \setminus C_X^\perp \}.
• The logical Z distance, d_Z, is the minimum weight of a non-trivial logical Z operator: d_Z = \min\{ \text{wt}(c) \mid c \in C_X \setminus C_Z^\perp \}.

The overall distance d of the CSS code is the minimum of these two: d = \min(d_X, d_Z).

The following reading provides a detailed derivation of this result.

4. Distance of the Steane Code Revisited

Let's apply this formula to our Steane code example, where C_X = C_Z = C_H (the [7,4,3] Hamming code) and C_X^\perp = C_Z^\perp = C_H^\perp (the [7,3,4] dual code).

• d_X = \min\{ \text{wt}(c) \mid c \in C_H \setminus C_H^\perp \}
  The minimum weight of any non-zero codeword in C_H is d(C_H) = 3. Since C_H^\perp has minimum weight 4, none of the weight-3 codewords of C_H are in C_H^\perp. Therefore, the minimum weight of an element in C_H \setminus C_H^\perp is simply 3. So, d_X = 3.

• d_Z = \min\{ \text{wt}(c) \mid c \in C_H \setminus C_H^\perp \}
  The calculation is identical: d_Z = 3.

• d = \min(d_X, d_Z) = 3.

This confirms that the Steane code is a [[7, 1, 3]] code. Its distance of 3 means it can correct any single-qubit error, since floor((3-1)/2) = 1.

• Logical Operators:
  • The logical \bar{X} operators are X^c where c is any codeword in C_H that is not in C_H^\perp. The lowest-weight choices are the weight-3 codewords of the Hamming code.
  • Similarly, the logical \bar{Z} operators are Z^c where c is any weight-3 codeword of the Hamming code.

Test your understanding!

Consider a CSS code constructed from two classical codes:

• C_1: a [15, 11, 3] Hamming code.
• C_2 = C_1^\perp: the dual of the Hamming code, which is a [15, 4, 7] code.

Let's build a CSS code with C_X = C_1 and C_Z = C_2.

1. First, verify that this is a valid choice. Does C_X^\perp \subseteq C_Z hold?
2. What are the parameters [[n, k, d]] of the resulting quantum code CSS(C_1, C_2)?

Show answer

1. Validity Check:
   We need to check if C_X^\perp \subseteq C_Z.
   We are given C_X = C_1. Therefore, C_X^\perp = (C_1)^\perp = C_2.
   We are also given C_Z = C_2.
   The condition C_X^\perp \subseteq C_Z becomes C_2 \subseteq C_2, which is trivially true. So, this is a valid construction.

2. Code Parameters:

   • n: The block length is n = 15.
   • k: The number of logical qubits is k = k_X + k_Z - n.
     • C_X = C_1 is a [15, 11] code, so k_X = 11.
     • C_Z = C_2 is a [15, 4] code, so k_Z = 4.
     • k = 11 + 4 - 15 = 0. This code has zero logical qubits! It is a [[15, 0]] code, defining a single quantum state. While a valid code, it cannot store information. This happens because C_Z = C_X^\perp, which is the boundary case of the containment condition C_X^\perp \subseteq C_Z.
   • d: We need to calculate d_X and d_Z.
     • d_X = \min\{ \text{wt}(c) \mid c \in C_Z \setminus C_X^\perp \}. Here, this is \min\{ \text{wt}(c) \mid c \in C_2 \setminus C_2 \}. The set C_2 \setminus C_2 is empty. By convention, the minimum over an empty set is infinity. So d_X = \infty.
     • d_Z = \min\{ \text{wt}(c) \mid c \in C_X \setminus C_Z^\perp \}. Here, C_X = C_1 and C_Z^\perp = (C_2)^\perp = ((C_1)^\perp)^\perp = C_1. So we need \min\{ \text{wt}(c) \mid c \in C_1 \setminus C_1 \}, which is also \infty.
   • Something seems off. Let's re-read the definition of logical operators. They are in N(S) \ S. In our case, the stabilizer group S is the normalizer N(S). S = {X^a Z^b | a \in C_X^\perp, b \in C_Z^\perp} and N(S) = {X^a Z^b | a \in C_Z, b \in C_X}. Since C_Z=C_X^\perp and C_X=C_Z^\perp, these sets are identical. There are no non-trivial logical operators, which is consistent with k=0. The distance of a k=0 code is usually considered infinite. The code [[15, 0, d]] with d=\min(d(C_1), d(C_2)) = \min(3,7)=3 is a better way to think of this.

This example shows that not every valid CSS construction yields a useful code for storing quantum information. To get k > 0, we need k_X + k_Z > n, which requires that C_X^\perp is a proper subset of C_Z.

Conclusion

In this lesson, we bridged the gap between classical and quantum error correction by exploring the elegant CSS construction. You've seen how the properties of two classical codes, linked by the concept of duality, directly determine the parameters and power of a new quantum code.

Key Takeaways:

• CSS codes are built from two classical linear codes, C_X and C_Z, which handle Z and X errors respectively.
• A valid CSS code can be constructed if and only if C_X^\perp \subseteq C_Z.
• The resulting quantum code CSS(C_X, C_Z) has parameters [[n, k_X + k_Z - n, d]].
• The logical X operators are associated with codewords in C_Z \setminus C_X^\perp.
• The logical Z operators are associated with codewords in C_X \setminus C_Z^\perp.
• The distance d is the minimum weight of these non-trivial logical operators.

Preview of the next lesson:
We have now studied the Shor code and the general CSS construction. This concludes our module on the fundamentals of quantum error correction. We are now prepared to move into Module 6: "Fault-Tolerant Quantum Computing". In the next lesson, we will begin by distinguishing between Clifford and non-Clifford gates and analyzing the Gottesman-Knill theorem, which sets fundamental limits on the classical simulation of quantum circuits and motivates the need for fault-tolerant designs.