An Introduction to Quantum Error Correction, Part 3: Classic Codes — Shor and Steane

Introduction

Recap of Part 2: From Theory to Analysis

In Part 2, we developed the essential mathematical machinery for analyzing stabilizer codes. We defined logical operators to manipulate encoded data, established the formal error correction condition, and introduced code distance (d) as the primary metric of a code’s power. With this complete theoretical toolkit, we can now move from abstract principles to concrete examples.

The Next Step: From Theory to Application

With this theory in hand, we can now explore how these principles are embodied in real-world codes that shaped the field of quantum error correction. In this post, we will dissect two foundational examples:

• The Shor Code: The very first quantum error-correcting code discovered. Its construction proved that protecting quantum states from noise was possible, a landmark achievement that ignited the field.
• The Steane Code: A more efficient and elegant code that revealed a deep connection between classical and quantum error correction principles.

We will apply our theoretical tools to analyze their stabilizer generators, identify their logical operators, and confirm how they both achieve the critical distance of $d=3$, enabling them to correct any arbitrary single-qubit error.

1. The Shor Code

The Shor code, developed by Peter Shor in 1995, was the first quantum error-correcting code ever discovered. Its creation was a pivotal moment, proving that active error correction was possible for quantum systems. It achieves this by cleverly nesting two simpler codes together.

1.1 The Structure: A Concatenated Code

The Shor code is a concatenated code, meaning it is constructed by composing two simpler codes, one nested inside the other, to protect against both bit-flip (X) and phase-flip (Z) errors.

The construction starts with a single logical qubit and applies two layers of encoding:

1. Outer Code (Phase-Flip Correction): First, the logical qubit is encoded using a 3-qubit phase-flip code. This code maps the logical basis states to the X-basis states $|+\rangle$ and $|-\rangle$:

   \[|0\rangle \mapsto |+++\rangle = \frac{1}{\sqrt{8}}(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)(|0\rangle+|1\rangle)\] \[|1\rangle \mapsto |- - - \rangle = \frac{1}{\sqrt{8}}(|0\rangle-|1\rangle)(|0\rangle-|1\rangle)(|0\rangle-|1\rangle)\]

2. Inner Code (Bit-Flip Correction): Next, each of the three qubits from the step above is itself encoded using the 3-qubit bit-flip code from Part 1. This encoding replaces each basis state as follows:

   \[|0\rangle \mapsto |000\rangle\] \[|1\rangle \mapsto |111\rangle\]

By substituting the inner code into the outer code, we get the final 9-qubit logical basis states. A logical $|0\rangle$ is encoded by first creating three $|+\rangle$ states and then encoding each one:

\[|+\rangle = \frac{1}{\sqrt{2}}(|0\rangle+|1\rangle) \quad \xrightarrow{\text{encode}} \quad \frac{1}{\sqrt{2}}(|000\rangle+|111\rangle)\] \[|0_L\rangle = \frac{1}{\sqrt{8}}(|000\rangle+|111\rangle) \otimes (|000\rangle+|111\rangle) \otimes (|000\rangle+|111\rangle)\]

Similarly, a logical \(|1\rangle\) is encoded by first creating three \(|-\rangle\) states:

\[|-\rangle = \frac{1}{\sqrt{2}}(|0\rangle-|1\rangle) \quad \xrightarrow{\text{encode}} \quad \frac{1}{\sqrt{2}}(|000\rangle-|111\rangle)\] \[|1_L\rangle = \frac{1}{\sqrt{8}}(|000\rangle-|111\rangle) \otimes (|000\rangle-|111\rangle) \otimes (|000\rangle-|111\rangle)\]

This concatenated structure ensures that bit-flip errors within a 3-qubit block are caught by the inner code, while phase-flip errors that affect an entire block are caught by the outer code.

1.2 The Stabilizer Generators: Combining Phase and Bit-Flip Correction

For a [[9, 1, 3]] code, we need $n-k=8$ independent stabilizer generators. These generators formalize the concatenated structure.

The first six generators handle bit-flip errors by checking the parity of qubits within each of the three blocks:

\[g_1=Z_1Z_2, \quad g_2=Z_2Z_3 \\ g_3=Z_4Z_5, \quad g_4=Z_5Z_6 \\ g_5=Z_7Z_8, \quad g_6=Z_8Z_9\]

The final two generators handle phase-flip errors by checking the phase parity across the blocks using X operators:

\[g_7=X_1X_2X_3X_4X_5X_6 \\ g_8=X_4X_5X_6X_7X_8X_9\]

One can verify that all eight of these operators commute with each other.

1.3 Logical Operators and Distance of 3

The logical operators are the smallest weight operators that commute with all eight stabilizers but are not themselves stabilizers. For the Shor code, a valid choice of logical Pauli operators is:

• Logical X: $\bar{X} = X_1X_2X_3$ (or any product of three X’s within a single block).
• Logical Z: $\bar{Z} = Z_1Z_4Z_7$ (or any product of three Z’s, one from each block).

These operators anti-commute with each other as required, \(\{\bar{X}, \bar{Z}\}=0\) , and both commute with all eight stabilizer generators. The minimum weight of any such non-trivial logical operator is three.

Therefore, the Shor code’s distance is d=3. According to the rule $t = \lfloor (d-1)/2 \rfloor$, this confirms the code can correct any arbitrary single-qubit error ($t=1$), making it a fully-fledged quantum error-correcting code.

1.4 Syndrome Analysis of the Shor Code

We will now analyze the code’s response to errors of increasing weight by calculating their syndromes and assessing the outcome of the correction process. The syndrome $s$ is an 8-bit vector where each bit $s_i$ is defined by the relation $g_i E = (-1)^{s_i} E g_i$.

Case 1: Weight-1 Error ($E=Z_1$)

• Syndrome Calculation: We compute the commutation relation for $E=Z_1$ with the eight stabilizer generators \(\{g_i\}\).

  • For the Z-type stabilizers ( \(i \in \{1, \dots, 6\}\) ),

    \[[g_i, Z_1] = 0 \implies s_i=0\]

  • For the X-type stabilizers, $Z_1$ anti-commutes with $g_7$ and commutes with $g_8$:

    \[\{g_7, Z_1\} = 0 \implies s_7=1\] \[[g_8, Z_1] = 0 \implies s_8=0\]

  The resulting syndrome is $s_{Z_1} = (00000010)$.

• Correction: This syndrome is degenerate, as the errors $Z_2$ and $Z_3$ produce the same signature. A decoder may choose the correction $C=Z_1$. If the true error was, for example, $E=Z_2$, the residual operator on the state is $C^\dagger E = Z_1 Z_2 = g_1$. Since $g_1 \in S$, it acts as the logical identity $\bar{I}$, and the logical state is correctly restored.

Case 2: Weight-2 Errors

• Subcase A: Trivial Error ($E = Z_1Z_2$)

  The error $E = Z_1Z_2$ is an element of the stabilizer group ($E=g_1 \in S$). It commutes with all stabilizers by definition, producing the trivial syndrome $(00000000)$. As an element of $S$, it is equivalent to the logical identity and requires no correction.

• Subcase B: Detectable Error ($E_A = Z_1Z_4$)

  The weight-2 error $E_A = Z_1Z_4$ is detected, but its syndrome is degenerate with a lower-weight error, leading to a correction failure.

  • Syndrome Calculation: Computing the commutation relations,

    \[[g_i, Z_1Z_4] = 0 \quad \text{for } i \in \{1, \dots, 6, 7\}\] \[\{g_8, Z_1Z_4\} = 0\]

    This yields the syndrome $s_A = (00000001)$.

  • Syndrome Degeneracy: Now consider the weight-1 error $E_B = Z_7$. Its commutation relations are:

    \[[g_i, Z_7] = 0 \quad \text{for } i \in \{1, \dots, 6, 7\}\] \[\{g_8, Z_7\} = 0\]

    This yields the syndrome $s_B = (00000001)$.

  • Correction Failure: Since $s_A = s_B$, the syndromes are degenerate. A minimum-weight decoder, upon measuring this syndrome, assumes the most probable cause is the lowest-weight error, $E_B = Z_7$. The decoder applies the correction $C=E_B=Z_7$. If the true error was $E_A$, the residual operator left on the state is:

    \[C^\dagger E_A = Z_7^\dagger (Z_1Z_4) = Z_1Z_4Z_7\]

    This residual operator is the logical operator $\bar{Z}$, which is not an element of the stabilizer group ($Z_1Z_4Z_7 \notin S$). Therefore, a logical error has been applied to the state, and the correction has failed, demonstrating the code is designed to correct only for errors of weight $t=1$.

Case 3: Weight-3 Error (Logical Error)

Consider the error $E = Z_1Z_4Z_7$, which is a logical operator $\bar{Z} \in Z(S) \setminus S$.

• Syndrome Calculation: By definition of a logical operator, it commutes with all stabilizer generators.

  \[[g_i, Z_1Z_4Z_7] = 0 \quad \text{for all } i \in \{1, \dots, 8\}\]

  The syndrome is trivial, $s=(00000000)$.

• Correction Failure: The error is undetectable, and no correction is applied. The operator silently corrupts the encoded state, causing a logical phase-flip. As this is a lowest-weight non-trivial logical operator, its weight confirms the code’s distance is d=3.

2. The Steane Code

The Steane code, discovered by Andrew Steane in 1996, is a cornerstone of quantum error correction. It is highly celebrated for its elegant, symmetric structure and its deep connection to classical coding theory, offering a more efficient construction than the Shor code while achieving the same level of protection.

2.1 A Quantum Code from a Classical Blueprint

The design of the Steane code is a direct “quantization” of the classical [7, 4, 3] Hamming code, one of the most famous classical error-correcting codes. The classical code uses a parity-check matrix $H$ to define its codewords:

\[H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{pmatrix}\]

A 7-bit string $c$ is a valid codeword if $Hc^T = 0 \pmod 2$. The Steane code ingeniously uses this same matrix to define both its bit-flip and phase-flip checks. The three rows of $H$ define which qubits participate in each stabilizer check: a ‘1’ in column $j$ means qubit $j$ is included in the check.

• To check for bit-flip (X) errors, we create Z-type stabilizers.
• To check for phase-flip (Z) errors, we create X-type stabilizers.

This dual construction provides balanced protection against both fundamental error types.

2.2 The Stabilizer Generators

The Steane code is a [[7, 1, 3]] code, requiring $n-k=6$ independent stabilizer generators. Following the blueprint from the Hamming matrix, we define three X-type and three Z-type generators. Each generator corresponds to a row in the parity-check matrix.

The stabilizer group $S = \langle g_1, \dots, g_6 \rangle$ is generated by:

• X-type Stabilizers (detect Z errors):

  \[g_1 = X_4X_5X_6X_7\] \[g_2 = X_2X_3X_6X_7\] \[g_3 = X_1X_3X_5X_7\]

• Z-type Stabilizers (detect X errors):

  \[g_4 = Z_4Z_5Z_6Z_7\] \[g_5 = Z_2Z_3Z_6Z_7\] \[g_6 = Z_1Z_3Z_5Z_7\]

One can verify that all X-type generators commute with all Z-type generators because they always share an even number of qubits (either two or four), ensuring the group is Abelian.

2.3 Logical Operators and Code Distance

The logical operators for the Steane code are highly symmetric. A common and intuitive choice is to apply the same Pauli operator to all seven qubits:

• Logical X: $\bar{X} = X_1X_2X_3X_4X_5X_6X_7 = X^{\otimes 7}$
• Logical Z: $\bar{Z} = Z_1Z_2Z_3Z_4Z_5Z_6Z_7 = Z^{\otimes 7}$

These operators commute with all six stabilizer generators because they have an even overlap with each one (four qubits). However, these operators have a weight of 7. The code’s distance is defined by the minimum weight operator in $Z(S)\setminus S$. For the Steane code, there are logical operators of weight 3, such as:

\[\bar{L}_X = X_1X_2X_3 \quad \text{and} \quad \bar{L}_Z = Z_1Z_2Z_3\]

These operators are not stabilizers, but they commute with the entire stabilizer group. Since the minimum weight of a non-trivial logical operator is three, the distance of the Steane code is d=3. This confirms it can correct any arbitrary single-qubit error ($t=1$).

2.4 A Key Feature for Fault Tolerance: Transversal Gates

The Steane code possesses an extremely desirable property for fault-tolerant quantum computation: it supports a transversal Hadamard gate.

A gate is transversal if the logical operation on the encoded qubit can be implemented by applying the corresponding physical gate to each physical qubit individually, without any interaction between them. For the Hadamard gate:

\[H_L = H \otimes H \otimes H \otimes H \otimes H \otimes H \otimes H = H^{\otimes 7}\]

This is a powerful feature because it prevents errors from spreading. An error on one qubit during the gate application remains on that qubit and does not propagate to others, making it easier to correct. We can verify that this gate preserves the codespace by showing that it correctly maps the stabilizer group onto itself:

\[H_L S_X H_L^\dagger = (H^{\otimes 7}) (X_i \dots) (H^{\otimes 7}) = (HXH)_i \dots = Z_i \dots = S_Z\] \[H_L S_Z H_L^\dagger = (H^{\otimes 7}) (Z_i \dots) (H^{\otimes 7}) = (HZH)_i \dots = X_i \dots = S_X\]

Since the Hadamard gate simply swaps the X and Z stabilizers, the codespace is preserved, and the gate is a valid logical operation. This property makes the Steane code an important blueprint for fault-tolerant architectures.

---

What’s Next: The Leap to Scalable Architectures

While the Shor and Steane codes are foundational, their complex connectivity requirements make them challenging to implement on the 2D layouts of modern quantum hardware. This practical constraint motivates the need for a new class of codes designed with physical implementation in mind.

In Part 4, we will explore the surface code, a modern topological approach that has become the leading candidate for building large-scale, fault-tolerant quantum computers. We will see how arranging qubits on a simple 2D grid and using only local stabilizer checks provides a practical and powerful path forward.

---

Further Reading

For another excellent and detailed perspective on QEC, from the Shor code to the surface code, Arthur Pesah’s blog is a highly recommended resource.

• Arthur Pesah’s Blog: https://arthurpesah.me/blog/