Notes on quantum error correction · Part 2 · follows Roffe, section 4 · previous: Part 1 · next: Part 2.5

The stabilizer formalism

Part 1 built codes one stabilizer at a time. Section 4 turns the recipe into a framework: a code is a commuting set of Pauli operators, its logical qubits are what those operators leave free, and the syndrome is a list of commutation signs. This part sets out the framework and works through two examples: the \([[4,2,2]]\) code, which detects errors, and Shor's \([[9,1,3]]\) code, which corrects them. The figures are at the end, followed by problems.

Roffe §4

The [[n, k, d]] stabilizer code

A register of \(k\) data qubits is entangled with \(m = n - k\) redundancy qubits to form \(\ket\psi_\L\) (figure A, after the paper's figure 4), and each of \(m\) stabilizers \(P_i\) is measured with the ancilla circuit of part 1:

\[ E\ket\psi_\L\ket0_{A_i} \;\longmapsto\; \tfrac12(\I^{\otimes n} + P_i)\,E\ket\psi_\L\ket0_{A_i} + \tfrac12(\I^{\otimes n} - P_i)\,E\ket\psi_\L\ket1_{A_i} . \qquad\text{(eq. 29)} \]

Ancilla \(A_i\) reads 0 if \(P_i\) commutes with \(E\) and 1 if it anticommutes, and two Pauli strings anticommute exactly when they differ, both non-trivially, on an odd number of qubits. The \(m\) bits form the syndrome \(S\). Designing a code means choosing stabilizers that anticommute with the errors to be caught.

Roffe §4.1

The stabilizer group

The stabilizers must be Pauli operators that fix every code state and commute with one another, so that they can be measured in any order:

\[ \begin{aligned} \mathcal S &= \bigl\{ P_i \in \mathcal G_n \;\big|\; P_i\ket\psi_\L = (+1)\ket\psi_\L\ \forall \ket\psi_\L, \\ &\qquad [P_i, P_j] = 0\ \forall i, j \bigr\}, \\ \mathcal S &= \langle G_1, G_2, \ldots, G_m \rangle\nobreak . \qquad\text{(eq. 30, 31)} \end{aligned} \]

Products of stabilizers are stabilizers, so only a minimal generating set is measured: \(\langle Z_1Z_2, Z_2Z_3\rangle\) for the three-qubit code, not also \(Z_1Z_3 = (Z_1Z_2)(Z_2Z_3)\). Each independent generator halves the space, so \(m = n - k\) generators leave a \(2^k\)-dimensional codespace.

Roffe §4.2

Logical operators

An \([[n,k,d]]\) code has \(2k\) logical operators \(\bar X_i, \bar Z_i\) that act on the encoded qubits without decoding. Each commutes with every stabilizer, so it maps the codespace to itself, and each pair anticommutes, \(\{\bar X_i, \bar Z_i\} = 0\), as the single-qubit \(X\) and \(Z\) do. Multiplying a logical operator by a stabilizer gives another representative of the same logical operator, \(\bar L P_j\ket\psi_\L = \bar L\ket\psi_\L\). The distance \(d\) is the weight of the lightest representative of any non-trivial logical operator.

Beyond the guide

Reading \(n\), \(k\) and \(d\) off the stabilizers

The label \([[n,k,d]]\) looks like three design choices. It is not: once the generators \(G_1, \ldots, G_m\) are written down, all three numbers are fixed, and for a small code each can be computed by hand. (The double brackets mark a quantum code; a classical code, as in part 3, is written \([n,k,d]\).) This section gives the three computations in general and runs each on the three-qubit code of part 1, \(\mathcal S = \langle Z_1Z_2, Z_2Z_3\rangle\). The \([[4,2,2]]\) and Shor codes that follow are done the same way.

\(n\): count the physical qubits

\(n\) is the number of qubits every stabilizer acts on, the length of a generator once the identities are written in: \(Z_1Z_2 = Z \otimes Z \otimes \I\) on the three-qubit code, so \(n = 3\). It is the cost of the code, and the only one of the three numbers that is chosen directly.

\(k\): count the independent generators

Every Pauli string other than \(\pm\I^{\otimes n}\) squares to the identity and has zero trace, so its eigenvalues are \(+1\) and \(-1\), each on a subspace of dimension \(2^{n-1}\). Demanding \(G_1\ket\psi = +\ket\psi\) therefore keeps exactly half of the \(2^n\)-dimensional space. \(G_2\) commutes with \(G_1\), so it maps that half to itself, and it is traceless there as well, since \(\operatorname{tr}\bigl[\tfrac12(\I + G_1)\,G_2\bigr] = \tfrac12\operatorname{tr} G_2 + \tfrac12\operatorname{tr} G_1G_2 = 0\), \(G_1G_2\) being another non-identity Pauli string; so it halves the half. After \(m\) generators the joint \(+1\) eigenspace, which is the codespace, has dimension \(2^{n-m}\), room for \(k = n - m\) qubits, where \(m\) is the number of independent generators:

\[ k = n - m . \]

Two conditions hide in the word "independent". A generator that is a product of the others, such as \(Z_1Z_3 = (Z_1Z_2)(Z_2Z_3)\), is already \(+1\) on the space the others leave, halves nothing and does not count towards \(m\); listing it does no harm but changes no number. And no product of generators may equal \(-\I^{\otimes n}\), or the codespace is empty (problem 2). With that, \(k\) is a count, not a choice: the three-qubit code has \(m = 2\), so \(k = 3 - 2 = 1\), and its codespace \(\span\{\ket{000}, \ket{111}\}\) is indeed two-dimensional. The same \(m\) is the length of the syndrome, so \(2^{m} = 2^{n-k}\) is the number of error patterns the code can tell apart. To check independence mechanically, write each generator as a row of \(2n\) bits, its \(X\) part followed by its \(Z\) part; a product of generators is a sum of rows mod 2, so \(m\) is the rank of that matrix over \(\mathbb F_2\). The figures on every page compute \(k\) this way, and in part 3, where no row mixes \(X\) and \(Z\), it reads \(k = n - \operatorname{rank} H_X - \operatorname{rank} H_Z\).

\(d\): find the lightest error that slips through

Every Pauli operator \(E\) on the \(n\) qubits falls into one of three classes, decided by commutation alone:

  1. \(E\) anticommutes with at least one generator. Its syndrome is non-zero: detected.

  2. \(E\) commutes with every generator and is, up to a phase, an element of \(\mathcal S\). It leaves every code state unchanged: harmless.

  3. \(E\) commutes with every generator but is not in \(\mathcal S\). Its syndrome is zero, yet it changes the encoded state: an undetectable logical error.

Class 3 is exactly the set of logical operators of the previous section: the \(\bar X_i\) and \(\bar Z_i\), their products, and each of these multiplied by any stabilizer. The weight \(|E|\) of a Pauli operator is the number of qubits on which it is not the identity. Writing \([E, G_i] = 0\) for "commutes with every generator",

\[ d = \min\{ |E| : [E, G_i] = 0,\ E \notin \mathcal S \} . \]

In words, \(d\) is the smallest number of qubits an error can touch and still pass as a logical error. Roffe's phrasing, the lightest representative of any non-trivial logical operator, describes the same set from the other side. "Any representative" is the point: \(\bar L\) and \(\bar L P_j\) act identically on the codespace but may differ in weight, so \(d\) is not the weight of the first \(\bar X\) or \(\bar Z\) one happens to write down.

Three-qubit code. Weight 1: \(X_j\) and \(Y_j\) each anticommute with a \(Z\) check that touches qubit \(j\), class 1. \(Z_1\) commutes with both generators and is not in \(\mathcal S = \{\I, Z_1Z_2, Z_2Z_3, Z_1Z_3\}\), class 3. A logical error of weight 1 exists, \(Z_1 = \bar Z\), so \(d = 1\), which is part 1's conclusion. The lightest \(\bar X\) is \(X_1X_2X_3\), of weight 3, and no stabilizer lightens it, but the distance is the worst case over all logical errors, not the best.

Why this is the number that matters. An error of weight below \(d\) is in class 1 or 2, so a distance-\(d\) code detects every error on up to \(d - 1\) qubits. For correction, take two errors \(E\) and \(E'\) of weight at most \(t\) that share a syndrome. Their product \(E'E\) then commutes with every generator and has weight at most \(2t\). If \(2t \le d - 1\) it cannot be in class 3, so it is a stabilizer, and applying \(E'\) to undo \(E\) succeeds by eq. 37 even though the decoder could not tell the two apart. That is the rule \(d = 2t + 1\) of §4.5 below, and it is why degeneracy costs nothing.

By hand, \(d\) is found by listing Pauli strings in order of weight and stopping at the first one in class 3; figure B.2 does this for all 256 strings on four qubits. For a larger code one squeezes it from both sides: a class-3 operator of weight \(w\) gives \(d \le w\), and an argument that nothing lighter commutes with every generator gives \(d \ge w\) (problem 13 does this for the Shor code). Part 3 shows that for CSS codes the search splits into two classical ones.

three-qubit\([[4,2,2]]\)Shor
\(n\): physical qubits349
\(m\): independent generators228
\(k = n - m\)121
lightest class-3 operator\(Z_1\)\(X_1X_2\)\(X_1X_2X_3\)
\(d\): its weight123
The three parameters read off the generators of the codes in these notes. The \([[4,2,2]]\) and Shor columns are justified in the two sections that follow and in problems 8 and 13.

Roffe §4.3

The [[4,2,2]] detection code

The smallest code that notices both \(X\) and \(Z\) errors encodes two qubits in four, with codespace

\[ \begin{aligned} \ket{00}_\L &= \tfrac{1}{\sqrt2}(\ket{0000} + \ket{1111}), \\ \ket{01}_\L &= \tfrac{1}{\sqrt2}(\ket{0110} + \ket{1001}), \\ \ket{10}_\L &= \tfrac{1}{\sqrt2}(\ket{1010} + \ket{0101}), \\ \ket{11}_\L &= \tfrac{1}{\sqrt2}(\ket{1100} + \ket{0011}), \qquad\text{(eq. 32)} \end{aligned} \]

and stabilizers \(\mathcal S = \langle X_1X_2X_3X_4,\ Z_1Z_2Z_3Z_4 \rangle\). Every single-qubit \(X\) anticommutes with \(Z_1Z_2Z_3Z_4\), every single-qubit \(Z\) with \(X_1X_2X_3X_4\), and \(Y\) with both, so every single-qubit error is detected (table 3). The syndrome depends only on the kind of error, not the qubit, so nothing can be located. A choice of logical operators is

\[ \begin{aligned} \bar X_1 &= X_1X_3, &\quad \bar Z_1 &= Z_1Z_4, \\ \bar X_2 &= X_2X_3, &\quad \bar Z_2 &= Z_2Z_4 , \end{aligned} \qquad\text{(eq. 33)} \]

all of weight two, so \(d = 2\): a detection code. It catches every single-qubit error but not every error: the 18 two-qubit errors made of one Pauli type, such as \(X_1X_2\) or \(Z_2Z_4\), commute with both stabilizers, give syndrome 00 and act as logical operators. Figure B.2 sorts all 256 errors on four qubits by weight and syndrome. Two errors with the same syndrome differ by a logical operator, for example \(X_1X_2 = \bar X_1\bar X_2\) up to a stabilizer, which is exactly why undoing the wrong one would corrupt the data.

Roffe §4.4

Encoding by projection

A codeword can be prepared without a bespoke circuit by projecting onto the \(+1\) eigenspace of every generator,

\[ \begin{aligned} \ket0_\L &= \frac1N \prod_{P_i \in \langle\mathcal S\rangle} (\I^{\otimes n} + P_i)\,\ket{0^{\otimes n}}, \\ \ket{00}_\L &= \tfrac{1}{\sqrt2}(\I^{\otimes4} + X_1X_2X_3X_4)(\I^{\otimes4} + Z_1Z_2Z_3Z_4)\ket{0000} \\ &= \tfrac{1}{\sqrt2}(\ket{0000} + \ket{1111}), \qquad\text{(eq. 34, 35)} \end{aligned} \]

and the other codewords follow by applying logical \(\bar X\) operators. In hardware the projection is the syndrome-extraction circuit run on \(\ket{0^{\otimes n}}\); each ancilla then reads 0 or 1 with equal probability, as eq. 36 shows for \(X_1X_2X_3X_4\), and a 1 is fixed by an operator that anticommutes with that stabilizer only.

Eq. 34 fixes the codespace but not, in general, the logical value; for the \([[4,2,2]]\) code the two coincide. The Shor code below is one where they do not.

Roffe §4.5

Recovery

A code of distance \(d = 2t + 1\) corrects \(t\) errors, so codes with \(d \ge 3\) can correct and the \([[4,2,2]]\) code must repeat until it sees a clean syndrome. One cycle is: error \(E\), syndrome extraction, a decoder mapping the syndrome to a recovery \(R\) (paper's figure 6). It succeeds when

\[ RE\ket\psi_\L = (+1)\ket\psi_\L , \qquad\text{(eq. 37)} \]

which holds not only for \(R = E^\dagger\) but whenever \(RE\) is a stabilizer, and fails when

\[ RE\ket\psi_\L = \bar L\ket\psi_\L \qquad\text{(eq. 38)} \]

for a logical operator \(\bar L\): the state is back in the codespace with its information changed. Because success only needs \(RE \in \mathcal S\), several errors may share a syndrome harmlessly; such a code is degenerate.

Roffe §4.6

The Shor [[9,1,3]] code

Shor's code concatenates two three-qubit codes: the bit-flip code \(\mathcal C_{3b} = \span\{\ket{000}, \ket{111}\}\) with \(\mathcal S_{3b} = \langle Z_1Z_2, Z_2Z_3\rangle\), and the phase-flip code \(\mathcal C_{3p} = \span\{\ket{+++}, \ket{---}\}\) with \(\mathcal S_{3p} = \langle X_1X_2, X_2X_3\rangle\) (eq. 39, 40). Each qubit of the phase-flip code is itself a bit-flip code, \(\ket\pm \mapsto \ket\pm_{3b} = (\ket{000} \pm \ket{111})/\sqrt2\) (eq. 41, 42), giving

\[ \begin{aligned} \ket0_9 &= \tfrac{1}{\sqrt8}\,(\ket{000} + \ket{111})^{\otimes3}, \\ \ket1_9 &= \tfrac{1}{\sqrt8}\,(\ket{000} - \ket{111})^{\otimes3}, \qquad\text{(eq. 43)} \end{aligned} \] \[ \mathcal S_{[[9,1,3]]} \nobreak= \langle Z_1Z_2,\, Z_2Z_3,\, Z_4Z_5,\, Z_5Z_6,\, Z_7Z_8,\, Z_8Z_9,\goodbreak\, X_1X_2X_3X_4X_5X_6,\, X_4X_5X_6X_7X_8X_9 \rangle\nobreak . \qquad\text{(eq. 44)} \]

The six \(Z\)-type generators locate a bit flip within its block; the two \(X\)-type ones compare the signs of neighbouring blocks and so locate a phase flip to a block. Every single-qubit \(X\) error has its own syndrome, but \(Z_1, Z_2, Z_3\) share one (table 4). That costs nothing: if the decoder answers \(Z_1\) to an actual \(Z_2\), then \(RE = Z_1Z_2 \in \mathcal S\) and eq. 37 holds. The code corrects every single-qubit error and has \(d = 3\). The paper does not list logical operators; with eq. 43 they are \(\bar X = Z_1Z_4Z_7\), which flips the sign of every block, and \(\bar Z = X_1X_2X_3\), which reads the sign of one block.

From here the paper turns to the surface code. These notes take a detour first: CSS codes in part 3, of which Shor's code is one, since its generators are each made of only \(X\)s or only \(Z\)s.

Figures

Figure A is the general circuit of an \([[n, k, d]]\) stabilizer code. Figures B and C run that circuit for the two examples, one per tab: the \([[4,2,2]]\) code and the Shor code. Within each tab the parts share one error.

Figure AThe structure of an [[n, k, d]] stabilizer code (after the paper's figure 4)
Encoder Error Syndrome extraction |ψ⟩D k |0⟩R n−k |0⟩A1 s1 |0⟩A2 s2 |0⟩An−k sn−k ⋮ ⋮ ⋮ ⋮ Encoder |ψ⟩L E H H H H H H P1 P2 Pn−k ⋯ ⋯ ⋯ ⋯ ⋯
\(k\) data qubits \(\ket\psi_D\) and \(n-k\) redundancy qubits \(\ket0_R\) enter the encoder, which outputs the code state \(\ket\psi_\L\) on \(n\) qubits; a slash marks a bundle of qubits, with the bundle's size above it. The error \(E\) acts on that register. Each stabilizer \(P_i\) is then measured with its own ancilla \(A_i\): a Hadamard, \(P_i\) applied to the register when \(A_i\) is 1, a second Hadamard and a measurement, which is eq. 29. The \(n-k\) outcomes \(s_1 \ldots s_{n-k}\) form the syndrome.

Part B.1 is the circuit of the paper's figure 5: an encoder for two data qubits, the error, and the measurement of \(Z_1Z_2Z_3Z_4\) and \(X_1X_2X_3X_4\) with one ancilla each; step through it gate by gate. Click a qubit to cycle through \(X\), \(Z\) and \(Y\) errors, or click a table row; the parts share one error. The bars are drawn in the code's own basis: the codespace \(\C\) in its logical basis \(\ket{j}_\L\), and the error space the syndrome points to as \(R\cdot\C\), where \(R\) is the lightest error with that syndrome. So the bars show what the error did to the encoded information: identical to the input when undoing \(R\) would recover it, visibly changed when it would not. Try \(X_1\), then \(X_2\): same syndrome, different logical content. \(Y\) is applied as \(ZX = iY\); the global phase is invisible.

Part C.1 runs one full correction cycle of the paper's figure 6 on the Shor code: the encoder of eq. 41–43, the error, eight stabilizer measurements with one ancilla each, and the lookup-table recovery. It simulates all 17 qubits. Click a qubit to cycle through \(X\), \(Z\) and \(Y\) errors, or click a table row; the parts share one error. As in figure B, the bars are drawn in the code's logical basis, in \(\C\) and in the error space \(R\cdot\C\) the syndrome points to. For a degenerate pair such as \(Z_1\) and \(Z_2\) the bars are the same, which is why one recovery serves both. The figure opens with \(Z_2\) applied.

Problems

Each solution is hidden until you open it. Numbers can be checked against the figures above.

  1. When do Pauli strings commute? (a) Show that two \(n\)-qubit Pauli strings commute if and only if the number of positions where both are non-identity and different is even. (b) Does \(X_1Z_2X_3\) commute with \(Z_1Z_2Z_3Z_4\)? With \(X_1X_2X_3X_4\)?

    Solution

    (a) On one qubit, two Paulis commute when one is \(\I\) or they are equal, and anticommute otherwise. Moving \(Q\) past \(P\) position by position picks up a factor \(-1\) for each anticommuting position, so \(PQ = (-1)^{a} QP\) with \(a\) the number of such positions.

    (b) Against \(Z_1Z_2Z_3Z_4\), qubits 1 and 3 differ (\(X\) against \(Z\)) and qubit 2 agrees: two positions, so they commute. Against \(X_1X_2X_3X_4\), only qubit 2 differs: they anticommute, and that stabilizer would read \(-1\).

  2. The [[4,2,2]] stabilizer group. (a) List every element of \(\mathcal S = \langle X_1X_2X_3X_4, Z_1Z_2Z_3Z_4\rangle\), with signs. (b) The projector onto the codespace is \(P = \prod_i (\I + G_i)/2\). Use \(\operatorname{tr} P\) to show the codespace has dimension \(4 = 2^k\). (c) Why can \(-\I\) never belong to a stabilizer group?

    Solution

    (a) \(X_1X_2X_3X_4 \cdot Z_1Z_2Z_3Z_4 = \bigotimes_j X_jZ_j = (-i)^4\, Y_1Y_2Y_3Y_4 = Y_1Y_2Y_3Y_4\), so \(\mathcal S\) has four elements, all with sign \(+\): \(\I\), \(X_1X_2X_3X_4\), \(Z_1Z_2Z_3Z_4\) and \(Y_1Y_2Y_3Y_4\).

    (b) \(P = \tfrac14(\I + X^{\otimes4} + Z^{\otimes4} + Y^{\otimes4})\). Every non-identity Pauli string is traceless, so \(\operatorname{tr} P = 16/4 = 4\). In general \(\operatorname{tr} P = 2^n/2^m = 2^{n-m}\), which is why \(k = n - m\).

    (c) A code state would satisfy \(-\ket\psi = \ket\psi\), so the codespace would be empty.

  3. Sorting errors into the three classes. Use the three-qubit code \(\mathcal S = \langle Z_1Z_2, Z_2Z_3\rangle\) and the three classes of the section on reading \(n\), \(k\) and \(d\): detected, harmless, logical. (a) Place each of the nine weight-1 Paulis \(X_j\), \(Y_j\), \(Z_j\). (b) Place \(Z_1Z_3\), \(X_1X_2\), \(X_1Z_2\) and \(X_1X_2X_3\). (c) Read off \(d\). (d) Show that \(Z_1\), \(Z_2\) and \(Z_3\) are three representatives of the same logical operator.

    Solution

    (a) \(X_j\) and \(Y_j\) differ from \(Z\) on qubit \(j\), so each anticommutes with a generator that touches qubit \(j\): \(X_1, Y_1\) with \(Z_1Z_2\); \(X_2, Y_2\) with both; \(X_3, Y_3\) with \(Z_2Z_3\). All six are detected (class 1). \(Z_1, Z_2, Z_3\) commute with both generators, and none is in \(\mathcal S = \{\I, Z_1Z_2, Z_2Z_3, Z_1Z_3\}\): all three are logical errors (class 3).

    (b) \(Z_1Z_3 = (Z_1Z_2)(Z_2Z_3)\) is in \(\mathcal S\): harmless (class 2). \(X_1X_2\) differs from \(Z_1Z_2\) on two qubits (commutes) but from \(Z_2Z_3\) on one (anticommutes): detected. \(X_1Z_2\) differs from \(Z_1Z_2\) on qubit 1 only: detected. \(X_1X_2X_3\) differs from each generator on two qubits, so it commutes with both, and it is not in \(\mathcal S\): logical, in fact \(\bar X\).

    (c) The lightest class-3 operator found has weight 1, so \(d = 1\).

    (d) \(Z_2 = Z_1 \cdot Z_1Z_2\) and \(Z_3 = Z_1 \cdot Z_1Z_3\): each differs from \(Z_1\) by a stabilizer, so all three act identically on code states, as \(\bar Z\). On \(\alpha\ket{000} + \beta\ket{111}\) each gives \(\alpha\ket{000} - \beta\ket{111}\).

  4. The same code, written in bits. Write an \(n\)-qubit Pauli string as a row of \(2n\) bits \((x \mid z)\): \(x_j = 1\) if the string has \(X\) or \(Y\) on qubit \(j\), and \(z_j = 1\) if it has \(Z\) or \(Y\) there, so that on each qubit \(X \mapsto (1\mid0)\), \(Z \mapsto (0\mid1)\) and \(Y \mapsto (1\mid1)\). (a) Write \(Z_1Z_2\), \(Z_2Z_3\), \(Z_1Z_3\), \(Z_1\), \(X_1Z_2\) and \(X_1X_2X_3\) as rows. (b) Show that \((x\mid z)\) and \((x'\mid z')\) anticommute exactly when \(x \cdot z' + z \cdot x'\) is odd, and use it to redo the classes of \(Z_1\), \(X_1Z_2\) and \(X_1X_2X_3\) from the previous problem. (c) Multiplying Pauli strings adds their rows mod 2, up to a phase. Use this to show that the rows of \(Z_1Z_2\), \(Z_2Z_3\) and \(Z_1Z_3\) have rank 2, so that \(m = 2\) and \(k = 1\), and to decide whether \(Z_1\) and \(Z_1Z_3\) are in \(\mathcal S\).

    Solution

    (a) \(Z_1Z_2 = (000\mid110)\), \(Z_2Z_3 = (000\mid011)\), \(Z_1Z_3 = (000\mid101)\), \(Z_1 = (000\mid100)\), \(X_1Z_2 = (100\mid010)\), \(X_1X_2X_3 = (111\mid000)\).

    (b) On one qubit two Paulis anticommute when both are non-identity and different; checking the cases, that happens exactly when \(x_jz'_j + z_jx'_j = 1\) mod 2 (for instance \(X\) against \(Y\): \(1\cdot1 + 0\cdot1 = 1\); \(Y\) against \(Y\): \(1 + 1 = 0\)). Summing over qubits counts the anticommuting positions mod 2, which is problem 1(a). \(Z_1\) has \(x = 000\), and both generators have \(x' = 000\), so every product is 0: it commutes with both, as before. \(X_1Z_2\) against \(Z_1Z_2\): \(x\cdot z' = 100\cdot110 = 1\) and \(z\cdot x' = 0\), odd: anticommute. \(X_1X_2X_3\) against \(Z_1Z_2\): \(111\cdot110 = 2 = 0\); against \(Z_2Z_3\): \(111\cdot011 = 0\): it commutes with both.

    (c) \((000\mid110) + (000\mid011) = (000\mid101)\): the third row is the sum of the first two, so the rank is 2, \(m = 2\) and \(k = 3 - 2 = 1\). The sums of generator rows are \((000\mid000)\), \((000\mid110)\), \((000\mid011)\) and \((000\mid101)\), the four elements of \(\mathcal S\). The row of \(Z_1Z_3\) is among them (harmless); the row of \(Z_1\), \((000\mid100)\), is not (logical). This is the computation the figures run for every error.

  5. Is it a code? For each set of generators decide whether it defines a stabilizer code, and if so give \(n\), \(m\) and \(k\): (a) \(\langle X_1X_2, Z_1Z_2\rangle\); (b) \(\langle X_1X_2, Z_1\rangle\); (c) \(\langle X_1X_2, Z_1Z_2, Y_1Y_2\rangle\); (d) \(\langle Z_1Z_2, Z_2Z_3, Z_1Z_2Z_3\rangle\); (e) \(\langle Z_1Z_2, Z_2Z_3, Z_3Z_4\rangle\). For the valid ones with \(k = 0\), write down the single code state.

    Solution

    (a) The two differ on both qubits, so they commute, and neither is a product of the other: \(n = 2\), \(m = 2\), \(k = 0\). The codespace is one state, the one with even parity and \(X_1X_2 = +1\): \((\ket{00} + \ket{11})/\sqrt2\), a Bell pair. The group is \(\{\I, X_1X_2, Z_1Z_2, -Y_1Y_2\}\), since \(X_1X_2 \cdot Z_1Z_2 = (X_1Z_1)(X_2Z_2) = (-i)^2\,Y_1Y_2\).

    (b) \(X_1X_2\) and \(Z_1\) differ on qubit 1 only: they anticommute, so no state is a \(+1\) eigenstate of both, and this is not a code.

    (c) The three commute pairwise, but \(k = 2 - 3 = -1\) is impossible, which signals a dependence. In bits, \((11\mid00) + (00\mid11) = (11\mid11)\), the row of \(Y_1Y_2\), so the rank is 2; and by (a) the product of the first two is \(-Y_1Y_2\). Demanding \(Y_1Y_2 = +1\) and \(-Y_1Y_2 = +1\) at once puts \(-\I\) in the group and empties the codespace. Had the third generator been \(-Y_1Y_2\) it would have been redundant, and the code would be (a) again. Independence is a condition on rows and signs.

    (d) All \(Z\)-type, so they commute; the rows \(110\), \(011\), \(111\) have rank 3, since \(110 + 011 = 101 \ne 111\). \(n = 3\), \(m = 3\), \(k = 0\): the single state with every pair of bits equal and \(Z_1Z_2Z_3 = +1\), which is \(\ket{000}\). A valid code that stores nothing.

    (e) They commute and have rank 3: \(n = 4\), \(m = 3\), \(k = 1\), the four-qubit repetition code \(\span\{\ket{0000}, \ket{1111}\}\), still with \(d = 1\), since \(Z_1\) commutes with everything and is not a stabilizer. Adding a qubit and a check raised \(n\) and \(m\) together and left \(k\) and \(d\) alone.

  6. Adding a generator. Start from the \([[4,2,2]]\) code, \(\mathcal S = \langle X_1X_2X_3X_4, Z_1Z_2Z_3Z_4\rangle\), and add \(Z_1Z_2\) as a third generator. (a) Check that it commutes with both and is independent of them. What are \(n\), \(m\) and \(k\) now? (b) Show that every weight-1 Pauli is still detected, find a class-3 operator of weight 2, and give \(d\). Which two codewords of eq. 32 survive? (c) Now add \(X_1X_2\) as well. What are \(k\) and \(d\), and which state is the codespace? (d) Show from eq. 33 that \(Z_1Z_2 = \bar Z_1\bar Z_2\) and \(X_1X_2 = \bar X_1\bar X_2\), and say what each added generator did to the two logical qubits.

    Solution

    (a) \(Z_1Z_2\) differs from \(X_1X_2X_3X_4\) on two qubits and from \(Z_1Z_2Z_3Z_4\) on none, so it commutes with both, and it is none of \(\I\), \(X^{\otimes4}\), \(Z^{\otimes4}\), \(Y^{\otimes4}\), so it is independent. \(n = 4\), \(m = 3\), \(k = 1\).

    (b) Every \(X_j\) still anticommutes with \(Z^{\otimes4}\), every \(Z_j\) with \(X^{\otimes4}\) and every \(Y_j\) with both: all detected. \(X_1X_2\) differs from \(Z^{\otimes4}\) and from \(Z_1Z_2\) on two qubits each and from \(X^{\otimes4}\) on none, so it commutes with all three generators. The eight elements of the new group are \(\I\), \(X^{\otimes4}\), \(Z^{\otimes4}\), \(Y^{\otimes4}\), \(Z_1Z_2\), \(Z_3Z_4\), \(-Y_1Y_2X_3X_4\) and \(-X_1X_2Y_3Y_4\), and \(X_1X_2\) is not among them: class 3, weight 2, so \(d = 2\) and this is a \([[4,1,2]]\) code. \(Z_1Z_3\) is another class-3 operator of weight 2; it anticommutes with \(X_1X_2\), so the two can serve as \(\bar Z\) and \(\bar X\). The surviving codewords are those with \(Z_1Z_2 = +1\): \(\ket{00}_\L\) and \(\ket{11}_\L\). In \(\ket{01}_\L\) and \(\ket{10}_\L\) qubits 1 and 2 have odd parity, and they are thrown out.

    (c) \(X_1X_2\) commutes with all three generators, by (b), and is independent of them, so \(m = 4 = n\) and \(k = 0\). The codespace is the single state with \(X_1X_2 = +1\) inside \(\span\{\ket{00}_\L, \ket{11}_\L\}\); since \(X_1X_2\ket{00}_\L = \ket{11}_\L\), it is \((\ket{00}_\L + \ket{11}_\L)/\sqrt2 = \tfrac12(\ket{0000} + \ket{1111} + \ket{1100} + \ket{0011})\), which factorises as a Bell pair on qubits 1, 2 times a Bell pair on qubits 3, 4. With \(k = 0\) there are no logical operators, so no class 3, and \(d\) has no meaning: nothing is encoded to protect.

    (d) From eq. 33, \(\bar Z_1\bar Z_2 = Z_1Z_4 \cdot Z_2Z_4 = Z_1Z_2\) and \(\bar X_1\bar X_2 = X_1X_3 \cdot X_2X_3 = X_1X_2\). Adding \(Z_1Z_2\) as a generator demands \(\bar Z_1\bar Z_2 = +1\): it fixes the parity of the two logical bits and leaves one logical qubit free. Adding \(X_1X_2\) then demands \(\bar X_1\bar X_2 = +1\) and fixes the rest. Each independent generator is one promise about the state, and each promise costs one qubit of \(k\); when the promise is a logical operator, it fixes an encoded value rather than defining the code.

  7. The codespace as a state. (a) For \(\mathcal S = \langle Z_1Z_2, Z_2Z_3\rangle\) write the general code state, and check that \(Z_1\) acts on it as \(\bar Z\) and \(X_1X_2X_3\) as \(\bar X\). (b) Add \(X_1X_2X_3\) as a third generator. What are \(k\) and the codespace? (c) Add \(Z_1\) instead. (d) Which of the two states in (b) and (c) does eq. 34, projection onto the stabilizers alone, produce from \(\ket{000}\)? Relate the answer to the caveat on eq. 34 in the Shor section.

    Solution

    (a) \(Z_1Z_2 = Z_2Z_3 = +1\) forces all three bits equal: \(\alpha\ket{000} + \beta\ket{111}\). \(Z_1\) sends it to \(\alpha\ket{000} - \beta\ket{111}\), the logical \(Z\); \(X_1X_2X_3\) sends it to \(\alpha\ket{111} + \beta\ket{000}\), the logical \(X\).

    (b) \(m = 3 = n\), so \(k = 0\): one state, the \(+1\) eigenstate of \(X_1X_2X_3\) within (a), which is \(\alpha = \beta\): \((\ket{000} + \ket{111})/\sqrt2 = \ket+_\L\), the GHZ state.

    (c) \(Z_1 = +1\) forces \(\beta = 0\): \(\ket{000} = \ket0_\L\).

    (d) \(\ket{000}\) is already a \(+1\) eigenstate of both generators, so the projection returns \(\ket{000} = \ket0_\L\), the state of (c). Projecting fixes the codespace, which has room for one qubit; which codeword comes out depends on the input, and \(\ket{000}\) happens to satisfy \(\bar Z = +1\). For the Shor code, whose \(\bar Z\) is made of \(X\)s, the same projection of \(\ket{0^{\otimes 9}}\) gives \(\ket+_\L\), the analogue of (b). Promoting a logical operator to a generator, as in (b) and (c), is what pins the state down.

  8. Reading the logical operators. (a) Check that the operators of eq. 33 commute with both stabilizers, and that \(\bar X_1\) anticommutes with \(\bar Z_1\) but commutes with \(\bar Z_2\) (and likewise for qubit 2). (b) Write \(X_1X_2\), \(Z_1Z_2\) and \(Y_1Y_2\) as products of logical operators. Compare the weight-2 rows of figure B.2.

    Solution

    (a) Each of \(X_1X_3, X_2X_3\) meets \(Z_1Z_2Z_3Z_4\) on two qubits, and each of \(Z_1Z_4, Z_2Z_4\) meets \(X_1X_2X_3X_4\) on two, so all commute with \(\mathcal S\). \(\bar X_1 = X_1X_3\) and \(\bar Z_1 = Z_1Z_4\) share only qubit 1: they anticommute. \(\bar X_1\) and \(\bar Z_2 = Z_2Z_4\) share nothing: they commute. \(\bar X_2 = X_2X_3\) shares qubit 2 with \(\bar Z_2\) and nothing with \(\bar Z_1\).

    (b) \(\bar X_1\bar X_2 = X_1X_3X_2X_3 = X_1X_2\) and \(\bar Z_1\bar Z_2 = Z_1Z_4Z_2Z_4 = Z_1Z_2\). Then \(Y_1Y_2 \propto X_1X_2Z_1Z_2 = \bar X_1\bar X_2\bar Z_1\bar Z_2 \propto \bar Y_1\bar Y_2\). Each has weight two, gives syndrome 00 and changes both logical qubits, as figure B.2 reports.

  9. The quantum Singleton bound. Every \([[n,k,d]]\) code satisfies \(n - k \ge 2(d-1)\). (a) Check it for the \([[4,2,2]]\) and Shor \([[9,1,3]]\) codes. (b) Could a \([[4,2,3]]\) code exist? (c) What is the smallest \(n\) the bound allows for \(k = 1\), \(d = 3\)?

    Solution

    (a) \([[4,2,2]]\): \(2 \ge 2\), with equality. Shor: \(8 \ge 4\), with room to spare.

    (b) No: it would need \(2 \ge 4\).

    (c) \(n - 1 \ge 4\), so \(n \ge 5\). The five-qubit \([[5,1,3]]\) code exists and meets the bound; the Steane code of part 3 uses 7 qubits and the Shor code 9.

  10. Encoding from the wrong start. Prepare the \([[4,2,2]]\) code by measuring the stabilizers, starting from \(\ket{0001}\). (a) What does \(Z_1Z_2Z_3Z_4\) read? Find a single-qubit Pauli that fixes it without disturbing the \(X_1X_2X_3X_4\) measurement to come. (b) Then measure \(X_1X_2X_3X_4\). Which code state do you get for each outcome? Compare eq. 32.

    Solution

    (a) \(\ket{0001}\) has odd parity, so \(Z_1Z_2Z_3Z_4\) reads \(-1\) with certainty. The fix must anticommute with \(Z_1Z_2Z_3Z_4\) and commute with \(X_1X_2X_3X_4\): any single \(X_j\). Take \(X_1\), giving \(\ket{1001}\).

    (b) \(X_1X_2X_3X_4\ket{1001} = \ket{0110}\), so each outcome has probability \(\tfrac12\). Outcome \(+1\) leaves \((\ket{1001} + \ket{0110})/\sqrt2 = \ket{01}_\L\). Outcome \(-1\) leaves \((\ket{1001} - \ket{0110})/\sqrt2\); applying \(Z_1\), which anticommutes with \(X_1X_2X_3X_4\) only, turns it into \(-\ket{01}_\L\). Either way the result is \(\ket{01}_\L\), not \(\ket{00}_\L\): choosing \(X_4\) instead in (a) would have given \(\ket{0000}\) and then \(\ket{00}_\L\). The stabilizers fix the codespace; which codeword you land on depends on the fixes, the point of the caveat on eq. 34.

  11. Shor syndromes and degeneracy. Order the Shor generators as in eq. 44: \(Z_1Z_2\), \(Z_2Z_3\), \(Z_4Z_5\), \(Z_5Z_6\), \(Z_7Z_8\), \(Z_8Z_9\), \(X_1\cdots X_6\), \(X_4\cdots X_9\). (a) Give the syndromes of \(X_5\), \(Z_5\) and \(Y_5\). (b) Which other single-qubit errors share the syndrome of \(Z_5\), and why does the decoder’s choice among them not matter?

    Solution

    (a) \(X_5\) anticommutes with \(Z_4Z_5\) and \(Z_5Z_6\): 00110000. \(Z_5\) anticommutes with both \(X\) checks, since qubit 5 lies in both: 00000011. \(Y_5\) does both: 00110011.

    (b) \(Z_4\) and \(Z_6\) also lie in both \(X\) checks: 00000011. If the decoder answers \(Z_4\) to an actual \(Z_5\), then \(RE = Z_4Z_5\), a generator, so eq. 37 holds; \(Z_4Z_6 = Z_4Z_5 \cdot Z_5Z_6\) is a stabilizer too. The code is degenerate: these three errors need not be told apart.

  12. Two bit flips in the Shor code. The error \(X_1X_2\) hits the Shor code. (a) What is its syndrome? (b) The lookup decoder applies the single-qubit error with that syndrome. Which one, and what is the net operator? (c) Is the result harmless, detected, or a logical error? Contrast with \(Z_1Z_2\).

    Solution

    (a) \(X_1X_2\) meets \(Z_1Z_2\) on two qubits (commute) and \(Z_2Z_3\) on one (anticommute): 01000000.

    (b) That is the syndrome of \(X_3\), so \(R = X_3\) and \(RE = X_1X_2X_3\).

    (c) \(X_1X_2X_3\) commutes with every generator but is not in \(\mathcal S\), whose \(X\)-type elements are \(X_1\cdots X_6\), \(X_4\cdots X_9\) and their product \(X_1X_2X_3X_7X_8X_9\). It is \(\bar Z\): a logical error. Distance 3 corrects one error, not two. \(Z_1Z_2\), by contrast, is itself a stabilizer: syndrome 0 and no effect.

  13. Why the Shor code has distance 3. Show that no Pauli error of weight at most 2 acts as a nontrivial logical operator on the Shor code. Hint: split the error into its \(X\) part and its \(Z\) part (a \(Y\) contributes to both); the \(Z\) checks see only the \(X\) part, and the \(X\) checks only the \(Z\) part.

    Solution

    For the \(X\) part to pass the six \(Z\) checks, it must flip either none or all three qubits of each block, since each check compares two neighbours. With weight at most 2 no block can be complete, so the \(X\) part is \(\I\).

    For the \(Z\) part, let \(b_j\) be the parity of the number of \(Z\)s in block \(j\). The \(X\) checks read \(b_1 + b_2\) and \(b_2 + b_3\), so the \(Z\) part passes when \(b_1 = b_2 = b_3\). All three odd needs at least three \(Z\)s, so all are even: two \(Z\)s in one block, such as \(Z_1Z_3 = Z_1Z_2 \cdot Z_2Z_3\), a stabilizer.

    So every undetected error of weight at most 2 is harmless, while \(X_1X_2X_3\) and \(Z_1Z_4Z_7\) are logical operators of weight 3: \(d = 3\).