Chapter 10

This is really just observing that the circuit acts like this on the relevant basis states

The rest follows by linearity.

Note that \(X=P_+-P_-\) and \(I=P_++P_-\). Hence

\[ X\rho X = P_+\rho P_+ + P_-\rho P_- - (P_+\rho P_- + P_-\rho P_+) = 2(P_+\rho P_+ + P_-\rho P_-) - I\rho I . \]

Hence

\[ \calE(\rho) = (1 - 2p)\rho + 2p (P_+\rho P_+ + P_-\rho P_-) . \]

QED.

Let us define the following projectors

That is, the \(x\) has a special meaning and just stands for the place where the identity acts. Define \(P_{ixx}\) etc analogously. Note that e.g. \(P_{ixx}P_{xjx}=P_{ijx}\). Since \(Z_1=P_{0xx}-P_{1xx}\), \(Z_2=P_{x0x}-P_{x1x}\), \(Z_3=P_{xx0}-P_{xx1}\) we have the following spectral decomposition of the observables we are interested in:

Let \(P_j\) for \(j=0..3\) be the projectors from (10.5) to (10.8). If we measure for example \(+1\) for \(Z_1Z_2\) and \(+1\) for \(Z_2Z_3\) this corresponds to the projection (note: the order of the projections is not important due to commutativity)

\[ (+1, +1):\; (P_{00x} + P_{11x})(P_{x00} + P_{x11}) = P_{000} + P_{111} = P_0 . \]

In the same way the other three measurements can be mapped to the \(P_j\) too:

Hence the projectors are the same, just re-labeled. QED.

The projectors are just \(P_j=\proj{j}\) for \(j=0..7\) (note that the binary representations for the numbers from \(0\) to \(7\) are \(000\), \(001\), \(010\), \(011\), \(100\), \(101\), \(110\), \(111\)). A corresponding observable distinguishing each projector would be \(A=\sum_jj\proj{j}\).

Recall that the encoded state is \(\ket{\psi}=a\ket{000}+b\ket{111}\). Let \(k=0\), \(k=1\), \(k=2\), \(k=3\) denote no error, error in qubit 1, 2, 3, respectively. Let \(M_k\) be the set of possible measurements for the given value of \(k\). We have

Moreover, measuring \(0,1,2,4\) happens with probability \(\abs{a}^2\) and measuring \(7,6,5,3\) happens with probability \(\abs{b}^2\) (conditioned on a fixed value for \(j\)). Since the four sets are disjoint we can infer the error (the value of \(k\)) from the measurement (e.g. measuring \(1\) or \(6\) implies that the error was \(k=1\) (with certainty if only one of the three errors "is allowed" to happen)).

If we measure \(j\) and infer the error \(k\) according to the sets \(M_k\) we would correct it by applying \(X_k\) to the state. In other words, the following quantum operation \(\calR\) performs the syndrome measurement followed by the recovery:

Note that \(\calR\) is indeed trace-preserving (\(\sum_jE_j^\dagger\?E_j)=I\)). Recall \(\ket{\psi}=a\ket{000}+b\ket{111}\). Then (the no error case)

\[ \calR(\ket{\psi}) = \abs{a}^2 \proj{000} + \abs{b}^2 \proj{111} . \]

The same formula holds for \(\ket{\psi}\) replaced by \(X_k\ket{\psi}\) (\(k=1..3\)). Hence, for the following noise channel

\[ \calE(\rho) = (1-p)\rho + \sum_{k=1}^3 p_k X_k \rho X_k \]

where \(\sum_kp_k=p\) (this implies trace-preservation, but we could more generally assume \(\ldots\leq\?p\), meaning that with certain probability "something else" happens), which stands for having at most one bit-flip (with probability \(p_k\) at position \(k\)), we have

\[ \calR\circ\calE(\ket{\psi}) = \abs{a}^2 \proj{000} + \abs{b}^2 \proj{111} . \]

(If \(\calE\) was not trace-preserving the RHS would have a factor \(1-p+\sum_jp_j\).) Hence the bit-flip error gets indeed corrected, but unwanted side effects happen too. The final state after recovery is either \(\ket{000}\) (probability \(\abs{a}^2\)) or \(\ket{111}\) (probability \(\abs{b}^2\)). That is the state collapses to a basis state. This is only correct if \(\ket{\psi}\) was already in a basis state (\(a=0\) or \(b=0\)) - which is the claim of part 2.

Let us consider two cases:

1. We do not get to know the results of the syndrome measurement.
2. We get to know the results of the syndrome measurement.

In case 1 the whole error correction procedure is given by \(\calR\) from the solution of part 2. Let \(\rho=\calR\circ\calE(\ket{\psi})\). Then

\[ F(\ket{\psi},\rho) = \sqrt{\bra{\psi}\rho\ket{\psi}} = \sqrt{\abs{a}^4 + \abs{b}^4} . \]

Since \(\abs{a}^2+\abs{b}^2=1\) the minimum occurs at \(\abs{a}^2=\abs{b}^2=1/2\). Hence \(F\geq1/\sqrt{2}\) in that case.

In case 2 the post-correction state \(\rho\) is either \(\ket{000}\) (probability \(\abs{a}^2\)) or \(\ket{111}\) (probability \(\abs{b}^2\)). Hence

\[ F(\ket{\psi},\rho) \in \left\{\sqrt{\braket{\psi}{i_L}\braket{i_L}{\psi}} \; \middle| \; i\in\{0,1\}\right\} = \{\abs{a}, \abs{b}\} , \]

where the first alternative occurs with probability \(\abs{a}^2\) and the second one with \(\abs{b}^2\).

In both cases the minimial fidelity does not depend on the specifics of the noise model and in particular is always bad if \(\abs{a}\) and \(\abs{b}\) are bounded away from \(0\) (or equivalently, from \(1\)).

Remark

The minimum fidelity of case 1 is the weighted root square mean of the two possible fidelities of case 2. The weights are \(\abs{a}^2\) and \(\abs{b}^2\). See e.g. generalized mean on wikipedia for more infos. To make this more apparent consider \(\sigma=p\proj{0}+(1-p)\proj{1}\) (and \(\ket{\psi}=a\ket{0}+b\ket{1}\)):

\[ F(\ket{\psi},\sigma) = \sqrt{\bra{\psi}\sigma\ket{\psi}} = \sqrt{p\abs{a}^2+(1-p)\abs{b}^2} . \]

Here \(p\) and \(1-p\) are the weights.

Let us denote

With this notation the Shor code is given by

Hence we have the following encoding:

\[ \ket{\psi} = \ket{\psi_0} = a\ket{0_L} + b\ket{1_L} = a\ket{\pi\pi\pi} + b\ket{\mu\mu\mu} . \]

In this notation a phase flip error is represented naturally. For example a phase flip in one of the three qubits in the first block of \(\ket{\psi}\) is given by

\[ \ket{\psi_1} = a\ket{\mu\pi\pi} + b\ket{\pi\mu\mu} . \]

It doesn't matter in which of the three qubits, it always leads to the same state. The other two errors (phase flip in the second or third block) are given by

Now observe that

Hence e.g. measuring a state \(\ket{ijk}\) (\(i,j,k\in\{\pi,\mu\}\)) with respect to \(A\) detects if \(i=j\) (measurement result: \(+1\)) or \(i\neq\?j\) (measurement result: \(+1\)). Because of their special structure this translates to \(\ket{\psi_k}\). For the four errors (first one is no error) we get the following measurement results (each with certainty):

Hence we can infer the syndrome \(k\) (which error occured) from the measurement - as desired. QED.

Let us reuse the notation from the solution of exercise 10.5. Clearly

\[ Z_1Z_2Z_3 \ket{\pi} = \ket{\mu} \text{ and } Z_1Z_2Z_3 \ket{\mu} = \ket{\pi} . \]

An error in the first three qubits means that the corresponding state is \(\ket{\psi_1}\). By the above we have:

\[ Z_1Z_2Z_3 \ket{\psi_1} = \ket{\psi} . \]

QED.

Clearly \(PX_iX_jP=\delta_{ij}P\). Hence

Hence the conditions are satisfied and there exists an error correction procedure \(\calR\) for this noise.

By the previous calculation and Theorem 10.1 there exists a trace-preserving quantum operation \(\calR\) such that

\[ \calR \circ \calE (P\rho P) = [(1-p)^3 + 3p(1-p)^2] \, P \rho P . \]

The concrete form of the proportionality factor follows from (10.25) as it equals \(\sum_kd_{kk}\). Since this is a trace this formula would even be true if \((d_{ij})\) wasn't already diagonal.

To compute the Kraus matrices \(R_k\) of \(\calR\) we need the \(E_k\) such that the \((d_{ij})\) are diagonal. This is already the case

\[ d = \diag((1-p)^3, p(1-p)^2, p(1-p)^2, p(1-p)^2) . \]

From the proof of Theorem 10.1 we know that

\[ R_k = U_k^\dagger P_k \]

where \(P_k=U_kPU_k^\dagger\) and \(E_kP=\sqrt{d_{kk}}U_kP\) is a polar decomposition. The \(P_k\) are the projectors onto \(E_kC\) (\(C\) being the code space onto which \(P\) projects). The diagonality of \((d_{ij})\) implies that \(P_iP_j=\delta_{ij}P_i\) (meaning that the error subspaces are orthogonal to each other).

Clearly we can set \(U_0=I\) (it is only uniquely defined on the image of \(P\)). For \(k=1\) we have

\[ E_1 P = \sqrt{p(1-p)^2} X_1 P . \]

This is already a polar decomposition (the Pauli operators are unitary). Hence we can just set \(U_1=X_1\) and analogously \(U_k=X_k\) for \(k=1..3\). Hence

Note that this corresponds to the already in (10.5-10.8) introduced syndrome measurement operators. The Kraus matrices of \(\calR\) are

\[ R_k = U_k^\dagger P_k = \begin{cases} IP = P & \text{for } k = 0 , \\ X_k X_kPX_k = PX_k & \text{for } k \in \{1,2,3\} . \end{cases} \]

Let us reduce this to the bit flip code. To convert to the bit flip code we only have to conjugate the projector of the code and the Kraus operators of the errors by \(H^{\otimes3}\) (Hadamard).

\[ \proj{000} + \proj{111} = H^{\otimes3} \proj{+++} + \proj{---} H^{\otimes3} \]

and

\[ X_k = H^{\otimes3} Z_k H^{\otimes3} . \]

Let \(P\) be the projector of the phase flip code and let \(E_i\) be the mentioned errors it corrects. Let \(Q\) and \(F_j\) be the same thing for the bit flip.

\[ P E_i^\dagger E_j P = H^{\otimes3} Q F_i^\dagger F_j Q H^{\otimes3} = H^{\otimes3} \delta_{ij} Q H^{\otimes3} = \delta_{ij} P . \]

In the second equality we used what we already know about the bit flip code.

We can also verify this explicitly. Let \(P=P_{+++}+P_{---}\) be the projector onto the code, where we use the notation \(P_{ijk}=\proj{ijk}\). Clearly \(PE_i^\dagger\?E_iP=PIP=P\). Moreover

\[ PZ_1P = (P_{+++} + P_{---})(P_{-++} + P_{+--}) = 0 \]

and

\[ PZ_1Z_2P = (P_{+++} + P_{---})(P_{--+} + P_{++-}) = 0 . \]

Similarly \(PIZ_jP=PZ_iZ_jP=0\) for \(i\neq\?j\). Hence \(PE_i^\dagger\?E_iP=\delta_{ij}\).

Recall that the phase flip code corrects the errors \(I\), \(Z_1\), \(Z_2\), and \(Z_3\). By theorem 10.2 linear combinations of these errors are corrected too. Note that we have

Hence those errors are corrected too.

Let us denote

The Shor code is given by he projector

\[ P = \proj{\pi\pi\pi} + \proj{\mu\mu\mu} . \]

It is not hard to see that the errors transform the code space into a set of mutually orthogonal subspaces - with one exception. The effect of \(Z_j\) is the same if \(j\) stays within one "block" (there are three block \(\{1,2,3\}\), \(\{4,5,6\}\), and \(\{7,8,9\}\)). Hence:

\[ PE_i^\dagger E_j P = \begin{cases} P & \text{if } i=j \text{ or } E_i,E_j \text{ both Z on same block} , \\ 0 & \text{else} . \end{cases} \]

We already know that the quantum operation

\[ \calE(\rho) = \frac{1}{2} I \]

is the depolarizing channel with \(p=1\). By (8.102) this is equal to

\[ \calE(\rho) = \frac{1}{4} (I\rho I + X\rho X + Y\rho Y + Z\rho Z) . \]

Hence the relevant operation elements are

\[ \left\{\frac{1}{2}I, \frac{1}{2}X, \frac{1}{2}Y, \frac{1}{2}Z \right\} . \]

Let us follow the hint of the book.

\[ F(\ket{0}, \calE(\proj{0})) = \sqrt{(1-p) + \frac{p}{3}(\bra{0}X\ket{0}^2 + \bra{0}Y\ket{0}^2 + \bra{0}Z\ket{0}^2)} = \sqrt{(1-p) + \frac{p}{3}} = \sqrt{1-\frac{2p}{3}} . \]

Let \(\ket{\psi}\) be an arbitrary state and \(U\) be a unitary operator such that \(\ket{\psi}=U\ket{0}\). Then

\[ F(\ket{\psi}, \calE(\proj{\psi})) = F(U\ket{0}, U\calE(\proj{0})U^\dagger) = F(\ket{0}, \calE(\proj{0})) = \sqrt{1-\frac{2p}{3}} . \]

In the second equality we used that the fidelity is invariant under unitary transformations.

We could also prove the claim by using an alternative formula for the depolarizing channel:

\[ \calE(\rho) = \frac{2p}{3} I + \left(1 - \frac{4p}{3}\right) \rho . \]

(compare equations (8.100) and (8.102).) Hence

\[ F(\ket{\psi}, \calE(\proj{\psi})) = \sqrt{\frac{2p}{3} + \left(1 - \frac{4p}{3}\right)} = \sqrt{1-\frac{2p}{3}} . \]

Yet another approach first calculates

\[ F(\ket{\psi}, \calE(\proj{\psi})) = \sqrt{(1-p) + \frac{p}{3}(\bra{\psi}X\ket{\psi}^2 + \bra{\psi}Y\ket{\psi}^2 + \bra{\psi}Z\ket{\psi}^2)} . \]

Recall the representation \(\proj{\psi}=2\inv(I+\vec{r}\cdot\vec{\sigma})\) of a qubit in the bloch sphere (\(\abs{\vec{r}}=1\)). One can show that

\[ \bra{\psi}Z\ket{\psi} = r_z \]

and analogous formulas for \(r_x\) and \(r_y\). Hence

\[ F(\ket{\psi}, \calE(\proj{\psi})) = \sqrt{(1-p) + \frac{p}{3}\abs{\vec{r}}^2} = \sqrt{1-\frac{2p}{3}} . \]

Remark

To see e.g.

\[ \bra{\psi}Z\ket{\psi} = r_z \]

observe that

\[ \bra{\psi}Z\ket{\psi} = \trace{\proj{\psi}Z} = r_z . \]

In the last equality we used that the Pauli matrices (including \(I\)) are an orthogonal set with respect to the Hilbert-Schmidt scalar product (with norm \(\sqrt{2}\) for each base vector). The other two formulas for \(r_x\) and \(r_y\) follow along the same lines.

If you want to see the last equality directly, observe that (using \(S=\sqrt{Z}\))

\[ \trace{\proj{\psi}Z} = \trace{S\proj{\psi}S} \]

and use \(SIS=Z\), \(SXS=\ii\?X\), \(SYS=\ii\?Y\), \(SZS=I\) (only the last term has a non-zero trace).

Let us use sage to get an algebraic expression for \(F\). First define amplitude damping

E0 = matrix.diagonal([1, sqrt(1-g)])
E1 = matrix([[0, sqrt(g)], [0, 0]])
AD = make_operation([E0, E1])

Now we can use this to compute \(F\):

psi = a*ket('0') + b*ket('1')
psi_mat = matrix(psi).T
rho = AD(psi_mat*psi_mat.H).simplify_full()
(psi.conjugate() * rho * psi).simplify_full()

2*a*b*sqrt(-g + 1)*conjugate(a)*conjugate(b) + a^2*conjugate(a)^2 + b^2*conjugate(b)^2 + (a*b*conjugate(a)*conjugate(b) - b^2*conjugate(b)^2)*g

This looks a bit ugly so let us rewrite this:

\[ F = \abs{a}^4 + \abs{b}^4 + \gamma(\abs{a}^2 \abs{b}^2 - \abs{b}^4) + 2\sqrt{1-\gamma}\, \abs{a}^2\abs{b}^2 . \]

Substituting \(x=\abs{a}^2\) and \(y=\abs{b}^2\) this can be written as:

\[ F = \sqrt{f(x,y)} = \sqrt{x^2 + y^2 + \gamma (xy - y^2) + 2\sqrt{1-\gamma} \, xy} , \]

under the constraint \(x+y=1\) and \(x,y\geq0\). Thus we have to solve a constrained minimization problem. There are two possibilities. The first one is that the minimum occurs at the boundaries of the feasible region. Therefore let us calculate

The second possibility is that the minimum occurs in the inside of the feasible region. In that case we might try to find it by the method of Lagrange multipliers:

This looks a bit complicated so let us change the strategy a bit by defining a parameterization of the feasible region

\[ g(s) = f(s,1-s) . \]

Abbreviating \(\alpha=\gamma+2\sqrt{1-\gamma}\) we see that

Observe that \(\alpha+\gamma\geq2\). Hence \(c_0,c_1\geq0\) which implies that there is a \(s_0\geq0\) such that \(g\) is increasing for \(s\leq\?s_0\) and decreasing afterwards (note also that \(s_0\) could be larger than \(1\)). Hence a local extremum can only be a local maximum and the minimum is indeed obtained at the boundary:

\[ f(0, 1) = g(0) = 1 - \gamma . \]

Hence \(F_{\min}=\sqrt{1-\gamma}\) . QED.

Let \(\mathbb{1}_r\in\?\BB^r\) be the vector containing just ones. A generator for this code is given by the tensor product

\[ G = I_k \otimes \mathbb{1}_r . \]

This naturally reproduces the special cases \(r=3\), \(k\in\{1,2\}\) from the book.

Let \((e_j)\) be the standard basis vectors in \(\BB^k\). The code generated by \(G\) is just the image \(C=G\BB^k\) of \(G\) which in turn is given by all linear combinations of \((Ge_j)\). Let \(G'\) be the generator found by adding column \(k\) to column \(l\neq\?k\).

We have to show that \(C=G'\BB^k\). For this in turn it suffices to show that \((G'e_j)\) spans \(C\). First of all observe that

\[ Ge_j = G'e_j \text{ for } j \neq l . \]

Hence it suffices to show that \(\{Ge_k,Ge_l\}\) spans the same space as \(\{G'e_k,G'e_l\}\). Observe that

This shows the claim. QED.

Recall that a code \(C\), in terms of a parity check matrix \(H\), is defined as

\[ y \in C \Leftrightarrow \forall i: \sum_j H_{ij} y_j = 0 . \]

Let \(H'\) be a matrix obtained from \(H\) by adding row \(k\) to row \(l\). Let \(C'\) be the code defined by \(H'\). We have to show \(C'=C\). Let \(y\in\?C\). Then we have

\[ \forall i\neq l: \sum_j H'_{ij} y_j = 0 . \]

because for those \(i\) we have \(H'_{ij}=H_{ij}\). Moreover

\[ \sum_j H'_{lj} y_j = \sum_j H_{kj} y_j + \sum_j H_{lj} y_j = 0 , \]

by definition of \(H'\). Hence \(y\in\?C'\). Since \(y\in\?C\) was arbitrary this shows \(C\subseteq\?C'\). By symmetry we also have \(C'\subseteq\?C\). In fact, \(H\) can be obtained from \(H'\) by adding row \(k\) to line \(l\) so the same reasoning applies to the reverse inclusion. QED.

Let \(G_1\) and \(H_1\) be the generator and parity check matrix for \(k=1\) bits (see equations (10.53) and (10.58)). We have

\[ G_2 = I_2 \otimes G_1 . \]

(C.f. the solution of exercise 10.14.) This suggests to define

\[ H_2 = I_2 \otimes H_1 = \begin{bmatrix} 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 \?\end{bmatrix} . \]

This clearly does the job. It makes sense to compare this to exercise 10.18.

Recall that a code \(C\) is just the image of the generator \(C=G\BB^k\). On the other hand it can be defined as the kernel of the parity check matrix: \(C=\{y|Hy=0\}\). Since every code word has the form \(y=Gx\) we see that \(HGx=0\) for every \(x\). Hence the claim follows. QED.

Clearly \(G\) has rank \(k\). Hence its images has the same dimension as the kernel of \(H\) (which is \(k\)). We only have to verify that \(HG=0\) (c.f. exercise 10.18). But this is easy:

\[ HG = A I_k - I_{n-k} A = A - A = 0 . \]

Let us divide the proof into two parts. In part one we assume that \(H\) has \(d\) linearly dependent columns. In part two we assume that every \(d-1\) columns are linearly independent.

Part 1

Assume that \(H\) has \(d\) linearly dependent columns \(c_1,\ldots,c_d\). We want to show that there exists a \(y\in\?C\) (i.e. \(y\in\BB^n\) such that \(Hy=0\)) with \(\wt{y}\leq\?d\).

Linear dependence means that there exist coefficients \(\alpha_i\in\BB\) such that

\[ 0 = \sum_i \alpha_i c_i . \]

Without loss of generality we may assume that all \(\alpha_i\) are equal to \(1\). Otherwise there would exist a subset of \(d'\?<\?d\) columns such that this is fulfilled.

Let \(J=\{i_1,\ldots,i_d\}\) be the indices of these columns in \(H\). Let \(y\in\BB^n\) be such that \(y_i=1\) if \(i\in\?J\) and \(y_i=0\) otherwise. By construction we have \(\wt{y}=d\) and \(Hy=0\). This shows the claim of part 1.

Part 2

Assume that every \(d-1\) columns are linearly independent. We have to show that \(Hy=0\) implies \(\wt{y}\geq\?d\).

The assumption implies that every for every \(y\) with \(\wt{y}\leq\?d-1\) we have \(Hy\neq0\). But this is equivalent to the claim.

Taking parts 1 and 2 together we see that \(d(C)=d\) is equivalent to: Any \(d-1\) columns of \(H\) are linearly independent but there exist \(d\) columns which are linearly dependent. QED.

This follows directly from exercise 10.20. In fact, the parity check matrix \(H\in\BB^{(n-k)\times\?n}\) of the code must have full rank \(n-k\) in order for the code space to be \(k\)​-dimensional (otherwise it would be bigger and there could be no bijection between the code words and the elements of \(\BB^k\)).

On the other hand, from \(d(C)=d\), using exercise 10.20, we see that the rank of \(H\) must be at least \(d-1\). Hence \(n-k\geq\?d-1\). QED.

The parity check matrix of the Hamming code is made of matrices with columns \(h_j\) being the binary representation of \(j\) for \(j\in\{1,\ldots,2^r-1\}\). Hence

\[ h_1 + h_2 = h_3 , \]

implying that the first three columns are linearly dependent. On the other hand any two columns are linearly independent since

\[ h_i + h_j = 0 \]

implies \(i=j\). Now the claim follows from exercise 10.20. QED.

In this proof we use the so called probabilistic method which seems to be the standard way to prove this bound (see e.g. wikipedia for the general case of linear codes over finite fields).

Let \(n\geq\?k\) to be fixed later. The main idea is to consider a uniform probability distribution over \(\BB^{n\times\?k}\) and draw random generators \(G\) from it (let us denote the generated code by \(C\)). The idea is to show that there is a non-zero probability that the drawn generator generates a code with the desired properties.

Note one subtle thing here: the generator must be injective in order to generate a \(k\)​-dimensional code. Therefore consider the following lemma.

Lemma

For all \(n\geq\?k\) let \(P(n,k)\) be the probability that a uniformly at random drawn matrix \(G\in\BB^{n\times\?k}\) has rank \(k\). There exists a constant \(P_\infty\?>\?0\) (which does not depend on \(n\) or \(k\)) such that \(P(n,k)\geq\?P_\infty\).

Proof

Clearly \(P(n,k)\geq\?P(k,k)\). So we only have to consider the case \(n=k\). For \(l\leq\?k\) let \(P_l\) be the probability that a random matrix from \(\BB^{l\times\?k}\) has rank \(l\). Clearly

\[ P_1 = (2^k - 1) / 2^k = 1 - 2^{-k} \]

because there is only one vector (the zero vector) which leads to a single rowed rank-zero matrix. Observe that

\[ P_{l+1} = P_l \cdot (2^k - 2^l) /2^k . \]

This is because in order to have \(l+1\) independent rows you first need \(l\) independent rows and the last row has to be outside the \(l\)​-dimensional subspace (with \(2^l\) elements) of the first \(l\) rows. Hence

\[ P(k,k) = P_k = \prod_{j=1}^{k} (1 - 2^{-j}) \geq \prod_{j=1}^{\infty} (1 - 2^{-j}) =: P_\infty > 0 . \]

QED.

Our goal is to prove that for sufficiently large \(n\) (considering also non-injective \(G\))

\[ \prob{d(C)\geq d} > P_\infty \]

because then

\[ \prob{d(C)\geq d \text{ and } \rank{G}=k} \geq \prob{d(C)\geq d} - P_\infty > 0 . \]

which proves the claim. Let us estimate the probability that the distance of the code is not at least \(d\). In order to show the above bound it suffices to show that the following can be made arbitrary small (for large \(n\)):

\[ \prob{d(C)\leq d-1} \leq \sum_{x\in\BB^k\backslash\{0\}} \prob{\wt{Gx} \leq d-1} = \frac{V_d}{2^{n-k}} . \]

The first inequality follows from the fact that the event \(d(C)\leq\?d-1\) is equivalent to the event that at least one of the code words has distance at most \(d-1\) (also use the sub-additivity of probabilities). For the equality on the right let us first note that for each \(x\) the code word \(Gx\) is uniformly distributed (each column of \(G\) is uniformly distrubuted and so is each sum of columns). Hence \(\prob{\wt{Gx}\leq\?d-1}=V_d/2^n\) where

\[ V_d = \sum_{i=0}^{d-1} \binom{n}{i} \]

is the number of potential code words with weight at most \(d-1\).

Lemma

\(V_d\leq2^{H(\delta)n}\) if \(\delta\leq1/2\), where \(\delta=(d-1)/n\).

Remark

A reverse inequality is is also true: \(V_d\geq2^{H(\delta)n+o(n)}\). This can be seen from Stirlings formula. Actually I knew this reverse inequality already since I solved exercise 6.14, see e.g. here to get an idea for the proof. This is the reason I found it natural to connect \(V_d\) to the entropy. I was a bit surprised to find out that the \(V_d\leq\ldots\) inequality has such a clean form (no Landau notation).

Proof

The claim follows from this:

\[ \sum_{i=0}^{d-1} \binom{n}{i} 2^{-H(\delta)n} = \sum_{i=0}^{d-1} \binom{n}{i} \delta^{d-1} (1-\delta)^{n-d+1} \leq \sum_{i=0}^{d-1} \binom{n}{i} \delta^j (1-\delta)^{j-d} = (\delta + (1 - \delta))^n = 1 . \]

For the inequality in the middle it is important to have \(\delta\leq1/2\). The last equality is just the binomial formula. QED.

Using the lemma in the estimate for the probability that \(d(C)\leq\?d-1\) we get

\[ P := \prob{d(C)\leq d-1} \leq \left[\frac{2^{H(\delta)+O(n\inv)}}{2^{1-R}}\right]^n = \left[\frac{2^{R+o(1)}}{2^{1-H(\delta)}}\right]^n . \]

Here we choose \(d\) minimal so that \(\delta\leq(d-1)/n\) holds. Hence \(\delta=(d-1+O(1))/n\) which explains the \(O(n\inv)\) in the inequalities above.

Let us suppose we can choose \(R\) such that

Then we would have \(P\leq2^{-\varepsilon\?n/2}\) which is arbitrary small if \(n\) is large enough - which proves the desired bound. But since \(R=k/n\) this is indeed possible if we choose \(n\) large enough and \(k\) appropriately. QED.

Weakly self dual means \(C\subseteq\?C^{\bot}\). Hence

\[ H^{\bot} G = 0 , \]

where \(G\) is the generator of \(C\) and \(H^\bot\) the parity check matrix of \(C^\bot\). But a parity check matrix of \(C^\bot\) is \(H^\bot=G^T\). QED.

By definition of dual codes we have \(x\cdot\?y=0\) if \(x\in\?C^\bot\) and \(y\in\?C\). Hence, in that case

\[ \sum_{y\in\?C}(-1)^{x\cdot y} = \sum_{y\in\?C} 1 = \abs{C} \]

Assume now that \(x\in\?C^\bot\). Hence there exists a \(\tilde{y}\in\?C\) such that \(x\cdot\?\tilde{y}=1\). Let us decompose \(C=C'\oplus\?\tilde{y}\BB\). Hence

\[ \sum_{y\in C}(-1)^{x\cdot y} = \sum_{y'\in C'} \sum_{\alpha=0}^1 (-1)^{y'\cdot x + \alpha\tilde{y}\cdot x} = \sum_{y'\in C'} 0 = 0 . \]

QED.

Let us explain it on the specific example of the \([3,1]\) repetition code:

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

A corresponding circuit would be

a_0: ──■─────────────────
       │
a_1: ──┼────■────■───────
       │    │    │
a_2: ──┼────┼────┼────■──
     ┌─┴─┐┌─┴─┐  │    │
b_0: ┤ X ├┤ X ├──┼────┼──
     └───┘└───┘┌─┴─┐┌─┴─┐
b_1: ──────────┤ X ├┤ X ├
               └───┘└───┘

The idea is that for each \((i,j)\) with \(H_{ij}=1\) we have a CNOT with control at target \(b_i\) and control \(a_j\).

By using \(X\), \(Z\), and Hadamard gates one can unitarily transform the code into the following form

\[ \ket{x+C_2} = \frac{1}{\sqrt{\abs{C_2}}} \sum_{y\in\?C_2} (-1)^{u\cdot x} \ket{x+y} = (-1)^{u\cdot x} \frac{1}{\sqrt{\abs{C_2}}} \sum_{y\in\?C_2} \ket{x+y} . \]

Basically we introduce errors \(e_1=v\) and \(e_2=u\) on purpose to accomplish that. Now it is not hard to verify that the factor \((-1)^{u\cdot\?x}\) does not interfere with the analysis from the book.

The claim follows essentially from the following calculation:

# Standard parity check matrix for the [7,3] Hamming code:
H = matrix(GF(2), [
    [0, 0, 0, 1, 1, 1, 1],
    [0, 1, 1, 0, 0, 1, 1],
    [1, 0, 1, 0, 1, 0, 1],
])

# We want to check that this is indeed a generator:
G = matrix(GF(2), [
    [1, 0, 0, 0, 0, 1, 1],
    [0, 1, 0, 0, 1, 0, 1],
    [0, 0, 1, 0, 1, 1, 0],
    [0, 0, 0, 1, 1, 1, 1],
]).T

assert H*G == matrix.zero(3, 4)
"PASSED"

'PASSED'

One important thing to note is that \(G\) has full rank (obviously). Hence \(HG=0\) is sufficient to prove \(G\) to be a generator of the \([7,4]\) Hamming code.

We have

Since the kernel of a linear operator is a linear subspace and since the intersection of linear subscpaces is again linear the claim follows.

Recall the elementary logical rule that \(\neg\?a\Rightarrow\neg\?b\) is equivalent to \(a\Leftarrow\?b\). Hence, we have to prove that \(\pm\ii\?I\in\?S\) implies \(-I\in\?S\). But this is obvious! QED.

One direction of the implication is obvious. Therefore let us just prove the other direction.

Assume that all \(g_i\) and \(g_j\) commute. One can show that every \(g\in\?S\) can be represented (not necessarily uniquely) as

\[ g = \prod_{j=1}^l g_j^{x_j} \]

where \(x_j\in\ZZ\), and that inversion and products are represented as follows

where \(h=\prod_{j=1}^lg_j^{y_j}\). More precisely: if we already know that \(g\) and \(h\) have such a representation then from commutativity the representations for \(g\inv\) and \(gh\) easily follow. Now observe that the set \(S'\) of \(g\) which can be represented like this must be contained in \(S\) (because the \((g_j)\) generate \(S\)). But we have just seen that making products and inverses doesn't take us outside of \(S'\). Hence \(S'=S\) as claimed.

But now it is obvious that \(S\) is abelian because the standard representations of \(gh\) and \(hg\) are the same. QED.

Remark

Above we used the fact that if \(g_i\) and \(g_j\) commute then also \(g_i^x\) and \(g_j^y\) commute for any \(x,y\in\ZZ\). This is clear for non-negative \(x\), \(y\). The general case follows from the fact that \(g_j\) and \(g_i\inv\) commute. In fact, let \(a=g_j\inv\?g_i\) and \(b=g_ig_j\inv\). Since \(g_i\) and \(g_j\) commute we have \(g_ja=g_jb\). But this implies \(a=b\).

Note that there is a subtle error in the paragraph right before the exercise. Moreover I think it makes sense to prove a more general theorem given in the intro section of this site. So let us do this.

An element of the CSS code looks like this

\[ \ket{x+C_2} = \frac{1}{\sqrt{\abs{C_2}}} \sum_{y\in C_2} \ket{x + y} , \]

where \(x\in\?C_1\). Recall that \(C_2\subseteq\?C_1\). Hence all the \(x+y\) above also belong to \(C_1\). Hence \(A(x+y)=0\). Hence for all \(i=1..(n-k_1)\) we have

(I write \(A_i\) for the \(i\)​-th row of \(A\).) Hence the \(g_{k_2+1}\) stabilize the code. To prove the same statement for \(g_i\) with \(i=1..k_2\) we switch to the X-basis by applying the Hadamard transform to the state. Note that this transform changes the \(X\) in the definition of the \(g_i\) to \(Z\). As in section 10.4.2 we see that

\[ H^{\otimes n} \ket{x+C_2} = \sqrt{\frac{\abs{C_2}}{2^n}} \sum_{z\in C_2^\top} (-1)^{x\cdot z} \ket{z} . \]

Hence we see in a similar way as in the first part that

By dividing away the Hadamard transform we see that the \(g_i\) for \(i=1..k_2\) stabilize the CSS code too. This already shows the claim of the exercise.

In order to finish the proof of the theorem we need to show that the given generators do not stabilize an even larger space than the desired CSS code. But this is basically a dimensionality argument. By design the CSS code has dimension \(2^{k}\) where \(k=k_1-k_2\). On the other hand under certain conditions a stabilizer code with \(n-k\) generators has the same dimension. Said conditions are that \(-I\notin\?S\) and that the generators commute (Proposition 10.5). The latter is clear from the form of the generators. The former follows from the fact that the parity check matrices have full rank. QED.

Let \(\beta=r(g)\Lambda\?r(g')^T\) (which is an element of \(\BB\)). We will show that

\[ gg' = (-1)^\beta g'g , \]

which implies the claim of the exercise. Let us write

where \(N_j,N'_j\in\{I,X,Y,Z\}\), and \(\alpha,\alpha'\in\{1,-1,\ii,-\ii\}\). Without loss of generality we may assume \(\alpha=\alpha'=1\). Moreover let us split \(r=r_x\oplus\?r_z\) where \(r_x\) is responsible for the first \(n\) bits and \(r_z\) for the last \(n\) bits. We have

\[ \beta = r_x(g) \cdot r_z(g') + r_z(g) \cdot r_x(g') = \sum_{j=1}^n \underbrace{r_x(N_j) \cdot r_z(N'_j) + r_z(N_j) \cdot r_x(N'_j)}_{=:\beta_j} . \]

It is not hard to verify that \(N_jN'_j=(-1)^{\beta_j}N'_jN_j\). Hence \(gg'=(-1)^{\sum_j\beta_j}g'g\). QED.

The claim of the exercise is wrong. To see this consider the following counterexample. Let

\[ g_1 = X, \; g_2 = Z . \]

Clearly \(g_j^2=I\) for all \(j\), and \(g_j\neq-I\) for all \(j\). On the other hand \(XZXZ=-ZZ=-I\) and hence \(-I\in\?S\). One might wonder if the claim becomes true if one assumes that the \(g_j\) commute (and are independent). But this is also not true as the following counterexample shows:

\[ g_1 = Z, \; g_2 = -Z . \]

Recall that any \(g\in\?G_n\) has the form

where \(N_j\in\{I,X,Y,Z\}\), and \(\alpha\in\{1,-1,\ii,-\ii\}\). Hence \(g^2=\alpha^2I=\pm\?I\). By \(-I\notin\?S\) we must have \(g^2=I\) as desired. QED.

This is a simple and slightly tedious exercise. Hence let us do some fun version of this exercise: let qiskit solve it! Therefore let us define the following auxiliary function:

def print_ex1036(pauli_strings: list[str]):
    """Given a list of Pauli strings (e.g. ["XI", "IX"]) print how CX acts on them."""
    qc = QuantumCircuit(2)
    qc.cx(1, 0)  # swapping control and target compensates for different qubit order
    U = Clifford(qc)

    print("Applying CX acts as")
    for pstring in pauli_strings:
        p0 = Pauli(pstring)
        p1 = p0.evolve(U, frame="s")
        print(f"{p0} -> {p1}")

It prints the solution to this exercise. We also included YI and IY for later reference.

print_ex1036(["XI", "IX", "ZI", "IZ", "YI", "IY"])

Applying CX acts as
XI -> XX
IX -> IX
ZI -> ZI
IZ -> ZZ
YI -> YX
IY -> ZY

In case you wonder whether p0.evolve swallows the phase: it does not, as can be seen from here:

qc = QuantumCircuit(1)
qc.x(0)
U = Clifford(qc)
Pauli("Y").evolve(U)

-Y

As you can see it shows the minus sign and we can correctly infer \(XYX=-Y\).

Knowing the transformation for \(Z_1\) and \(X_1\) suffices to calculate this (also note that \(U^\dagger=U\)):

\[ UY_1U = -\ii UZ_1X_1U = -\ii UZ_1UUX_1U = -\ii Z_1X_1X_2 = Y_1X_2 . \]

Note also that this coincides with the output in the solution of exercise 10.36.

Let us generalize the exercise by considering \(n\) qubits and assuming that \(U\) and \(V\) act in the same way on \(Z_j\) and \(X_j\) for all \(j=1..n\). Since these Paulis already generate the whole Pauli group \(G_n\) we have

\[ \forall g\in G_n: \; UgU^\dagger = VgV^\dagger . \]

Let us note that we can easily deduce that this even holds for all \(g\in\CC^{2^n\times\?2^n}\). The reason is that the \(4^n\) possible Pauli operators (without phase) form a basis for this matrix space (they are orthogonal with respect to the Hilbert-Schmidt inner product). But we do not need this. Instead consider \(J=V^\dagger\?U\) and observe that

\[ \forall g\in G_n: \; JgJ^\dagger = g = IgI . \]

We have to show that \(J=e^{\ii\varphi}I\) for some \(\varphi\). Note that a stabilizer for the one dimensional space \(\CC\ket{k}\) generated by a standard basis element \(\ket{k}\) is given by \(\langle(-1)^{k_j}Z_j\;|\;j=1..n\rangle\) (where \(k_1\ldots\?k_n\) is the binary expansion of \(k\)). Hence \(J\) has to map \(\CC\ket{k}\) to itself (as \(I\) does). In other words

\[ J = \sum_{k=1}^n e^{\ii\varphi_k} \proj{k} . \]

For a binary vector \(v\in\BB^n\) let \(X^v=\bigotimes_{j=1}^nX^{v_j}\). Observe that (here \(v+k\) is performed in \(\BB^n\))

Comparing this with \(IX^vI\) we see that \(\varphi_k-\varphi_{v+k}=0\) for all \(k\) and \(v\). In other words, all the \(\varphi_k\) are the same. QED.

The equality \(SZS^\dagger=Z\) follows from the fact that \(S=\sqrt{Z}\) is a function of \(Z\) (in the sense of the functional calculus for hermitian operators) and hence commutes with \(Z\).

The equality \(SXS^\dagger=Y\) most easily follows from the bloch sphere interpretation. In fact, \(S=\ii\?R_z(\pi/2)\) is a rotation by 90° around the z-axis. This rotation maps the x-axis to the y-axis.

QED.

A single qubit normalizer gate is a gate \(U\) which satisfies

\[ UZU^\dagger , UXU^\dagger \in \{\pm X, \pm Y, \pm Z\} . \]

We can restrict our attention to the action of \(U\) on \(Z\) and \(X\) because the action on the other Pauli gates are either trivial (for \(I\)) or can be inferred like in this example: \(UYU^\dagger=-\ii\?UZU^\dagger\?UXU^\dagger\) (because \(Y=-\ii\?ZX\) or more generally \(\langle\?Z,X\rangle=G_1\)). In case you wonder why I do not allow e.g. \(UZU^\dagger=\pm\?I\) or \(UZU^\dagger=\pm\ii\?Z\): This is not possible because conjugation preserves eigenvalues.

A convenient way to go on is to switch into the Bloch sphere picture. In that sense \(U\) can be identified (neglecting global phase) with a rotation (in three dimensional real space) which maps \(\hat{z}\) and \(\hat{x}\) to two (orthogonal) axes (including their negatives). In other words \(\hat{z}\) and \(\hat{x}\) are mapped to \(\{\pm\hat{x},\pm\hat{y},\pm\hat{z}\}\) where every combination is possible if orthogonality is satisfied (e.g. mapping both \(\hat{z}\) and \(\hat{x}\) to \(\hat{z}\) is not possible). In the following we identify the Pauli matrices \(X,Y,Z\) with their corresponding axes \(\hat{x},\hat{y},\hat{z}\).

Note that the Bloch sphere interpretation shows that \(U\) is already uniquely defined by its action on \(Z\) and \(X\) (for a rotation the action on the third axis is fixed by orthogonality and orientation-preservation). Compare this to the solution of exercise 10.38 which also shows this.

Let us show that rotations by (multiples of) 90° around any coordinate axis can be used to compose \(U\). Let \(\calR\) denote the group of all such rotations. Clearly there is a \(V\in\calR\) which satisfies

\[ V Z V^\dagger = U Z U^\dagger . \]

In case we already have \(VXV^\dagger=UXU^\dagger\) we are done (\(V=U\), hence \(U\in\calR\)). Otherwise we know that \(UXU^\dagger\) and \(VXV^\dagger\) are both orthogonal (in the bloch sphere) to \(VZV^\dagger\). Hence there is a \(W\in\calR\) with rotation axis \(VZV^\dagger\) such that \(WVXV^\dagger\?W^\dagger=UXU^\dagger\). Since \(W\) leaves \(VZV^\dagger\) invariant we have \(W=U\) and thus \(U\in\calR\).

It remains to show that \(\calR=\langle\?H,S\rangle\). Note that \(S=\sqrt{Z}=\ii\?R_z(\pi/2)\) is a rotation by 90° around \(Z\). Hence \(S\in\calR\). Moreover \(H=(X+Z)/\sqrt{2}\) is a rotation by 180° around the axis \((X+Z)/\sqrt{2}\). We know that \(HZH=X\) and \(HXH=Z\). Hence \(H\) is a normalizer and thus \(H\in\calR\). But let us give an explicit formula in terms of elements of \(\calR\) (you can use the procedure used to show \(U\in\calR\) to find it)

\[ H = R_x(\pi) R_y(\pi/2) \in \calR . \]

Hence \(\langle\?H,S\rangle\subseteq\calR\). For the other directions note that the 90° rotations around the three axes \(Z\), \(X\), and \(Y\) are:

\[ \sqrt{Z} = S, \quad \sqrt{X} = HSH, \quad \sqrt{Y} = S\sqrt{X}S^\dagger = SHSHS^3 . \]

To see all this also note that \(Y=SXS^\dagger\) and \(S^\dagger=S^3\). Hence \(\calR\subseteq\langle\?H,S\rangle\).

Let us first calculate a matrix representation of the circuit given in the exercise:

Hence the circuit implements the following unitary operator

\[ \tilde{U} = \frac{1}{\sqrt{2}} \begin{bmatrix} U' & g'U' \\ gU' & -gg'U' \end{bmatrix} . \]

We have to show that \(U=\tilde{U}\). Let us note that \(g\) and \(g'\) commute because \(Z_1\) and \(X_1\) already anti-commute.

Now let us investigate \(U\). Let us write it in block form where each block \(U_{ij}\) represents \(n\) qubits:

\[ U = \begin{bmatrix} U_{00} & U_{01} \\ U_{10} & U_{11} \end{bmatrix} . \]

Note that this already implies \(U_{00}=U'/\sqrt{2}\) (by definition of \(U'\)). Unitarity of \(U\) (\(UU^\dagger=I\)) implies for \(k\in\{0,1\}\):

\[ \sum_{k=0}^1 U_{ik}U_{jk}^\dagger = \delta_{ij} I_n . \]

Consider

\[ X_1\otimes\?g = UZ_1U^\dagger = \sum_{ij}\sum_k (-1)^k \ket{i}\bra{j} \otimes U_{ik} U_{jk}^\dagger . \]

It is not hard to see that this and the unitarity relation imply

\[ \sqrt{2}U_{ij} \text{ is unitary}, \]

and

\[ U_{0k}U_{1k}^\dagger = \frac{1}{2} (-1)^k g = U_{1k}U_{0k}^\dagger . \]

In particular \(U'=\sqrt{2}U_{00}\) is unitary. Moreover, those findings further imply

Next consider

\[ Z_1\otimes g' = UX_1U^\dagger = \sum_{ij}\sum_k \ket{i}\bra{j} \otimes U_{ik}U_{j\overline{k}}^\dagger , \]

where \(\overline{k}=k+1\) (in \(\BB\)). From this we deduce

The first of these two relations can be used with the formulas for \(U_{10}\) and \(U_{11}\) to deduce \(U_{00}U_{11}^\dagger=gU_{11}U_{00}^\dagger\?g\). This can be used in the second relation and again with said formulas (to replace \(U_{10}\)) to obtain

\[ U_{11} = -gg' U_{00} = \frac{-1}{\sqrt{2}} gg' U' . \]

From this we also deduce \(U_{01}=-gU_{11}=g'U'/\sqrt{2}\). Hence we proved \(U=\tilde{U}\). It remains to count the number of gates to implement the circuit given for \(\tilde{U}=U\). By the induction hypothesis we need \(O(n^2)\) gates (CNOT, \(S\), \(H\)) to implement \(U'\) (it is clearly a normalizer because \(U\) is one and we will show that the rest in the circuit is also a normalizer). The controlled Pauli gates \(C(g)\) and \(C(g')\) can be implemented by at most \(n\) gates of the form \(C(N)\) where \(N\in\{\pm\,X,\pm\,Y,\pm\,Z\}\) (each of which are normalizer gates and can be implemented by at most five of our base gates).

To summarize: If \(s_n=O(n^2)\) is the maximal number of gates (\(S\), \(H\), CNOT) needed to implement an \(n\)​-qubit normalizer gate, then the circuit \(U\) can be implemented in at most

\[ s_n + 10n + 1 = O(n^2) \]

many gates.

Let \(U\) be any \(n+1\)​-qubit normalizer gate. Then we have

where we assume that \(M,N\in\{\pm\,I,\pm\,X,\pm\,Y,\pm\,Z\}\) and \(g\) and \(g'\) are a product of such operators (even without sign to make them unique). There are two cases:

Case 1

\(M,N\in\{\pm\,X,\pm\,Y,\pm\,Z\}\) are both "proper" Pauli operators (none of them is plus/minus the identity).

Case 2

\(M=\pm\,I\) or \(N=\pm\,I\).

Consider case 1. By the proof of part (1) we can apply \(O(1)\) many single qubit operations to implement a circuit \(V\) which does \(VMV^\dagger=X\) and \(VNV^\dagger=Z\). Hence \(VU\) satisfies the assumptions of part (2) and this case can be reduced to part (2).

Consider case 2. Recall that swap gates can be implemented by three CNOT gates. Try to find a qubit \(j\) so that both \(M\otimes\?g\) and \(N\otimes\?g'\) have a proper Pauli at position \(j\). If this is possible we can just swap qubits \(1\) and \(j\) to reduce to case 1. Otherwise we can at least assume that e.g. \(M\neq\pm\?I\) by a swap argument. Hence we have the following situation

where again by a swap argument \(K\neq\pm\?I\) can be assumed. Without loss of generality we can even assume that \(M=X\) and \(K=Z\):

In fact, this follows from part (1) by applying single qubit operations to the first and second qubit. Note that applying a single CNOT gate (with control at \(1\) and target at \(2\)) the RHS can be replaced by

which leaves us in the situation of case 1. QED.

The equations

\[ TZT^\dagger = Z; \quad TXT^\dagger = \frac{X+Y}{\sqrt{2}} \]

can be seen in exact the same way as the corresponding equations in exercise 10.39. The first one follows most easily from commutativity, using \(T=\sqrt[4]{Z}\). The second one from the fact that \(T\) is a 45° rotation around the z-axis which maps the x-axis to \((\hat{x}+\hat{y})/\sqrt{2}\).

The relations \(UNU^\dagger=N\) for \(N=Z_1,Z_2,X_3\) follow from commutativity (the Toffoli gate is a sum of tensor products of the eigen-projectors of \(Z_1\), \(Z_2\) with \(X_3\) because a controlled gate like \(C(V)\) is just \(\proj{0}\otimes\?I+\proj{1}\otimes\?V\)).

For the remaining three formulas let us use sage to verify them:

U = CCX
assert U == U.H, "CCX is symmetric!"

assert U * XII * U == kron(X, II + ZI + IX - kron(Z,X)) / 2
assert U * IXI * U == (IXI + IXI*ZII + IXI*IIX - kron(Z,X,X)) / 2
assert U * IIZ * U == kron(II + ZI + IZ - kron(Z,Z), Z) / 2
"PASSED"

'PASSED'

To find these formulas one could use that the Pauli matrices (without phase) form an orthogonal basis of \(\CC^{2^n\times2^n}\) with respect to the Hilbert-Schmidt scalar product. Also note that the norm of each Pauli operator is \(2^{n/2}\). Hence to compute e.g. the coefficients of \(UX_1U^\dagger\) one could do the following:

A = U * XII * U
assert A == A.H, "Nice to have, to avoid typing A.H all the time."
# For example: coefficients of XII and IXI of A are:
assert trace(A * XII) / 8 == 1/2
assert trace(A * IXI) / 8 == 0
# ... and so on.
"PASSED"

'PASSED'

The circuit can be divided into three major steps:

• Unitary evolution up until the measurements,
• Measuring the first two qubits in the Z-basis,
• Performing conditioned operations on the third qubit.

I split up the solution according to the three stages. Additionally I add a section on a specific example to get some feeling for how things work out.

Recall that the normalizer of a subgroup \(S\) of a group \(G\) is

\[ N(S) = \left\{ g\in G\; | \; \forall s\in S: gsg\inv \in g \right\} . \]

By the group property, if \(g\in\?S\) then also \(gsg\inv\in\?S\). Hence \(S\subseteq\?N(S)\). QED.

Obviously we have \(Z(S)\subseteq\?N(S)\) (for any subgroup \(S\) of any group). Hence we only have to show the other inclusion and this is where we need the fact that we are in the Pauli group and \(-I\notin\?S\).

Let \(g\in\?N(S)\).

Recall that for \(g,h\in\?G_n\) we have \(gh=\pm\?hg\), that is, two elements of the Pauli group either commute or anti-commute. In particular

\[ \forall s \in S: gsg^\dagger = \pm s . \]

We have to show that always the \(+\) sign holds. Assume to the contrary that there is a \(s\in\?S\) such that \(gsg^\dagger=-s\). Using \(g\in\?N(S)\) we deduce \(-s\in\?S\). Note that \(s^2=I\) by exercise 10.35. Hence \(S\owns\?s\cdot(-s)=-I\) - contradiction! QED.

Let us first consider the case that we know that the errors only happen in the first \(d-1\) qubits. The set of all such errors is the linear span of the following set of base errors:

\[ \calE = \left\{\bigotimes_{j=1}^{d-1} N_j \otimes I^{\otimes(n-d+1)} \; \middle| \; N_j \in \{I,X,Y,Z\} \right\} . \]

To see this recall that the Pauli operators are an orthogonal basis with respect to the Hilbert-Schmidt inner product. By theorem 10.2 a recovery procedure \(\calR\) which corrects all errors in \(\calE\) also corrects all errors in the linear span and hence all errors affecting the first \(d-1\) qubits.

Clearly the weight of \(E^\dagger\?F\) is at most \(d-1\) for every \(E,F\in\calE\). Since \(C(S)\) has distance \(d\) this means that \(E^\dagger\?F\notin\?N(S)\backslash\?S\). By theorem 10.8 there exists a recovery procedure \(\calR\) which corrects all errors in \(\calE\).

More generally consider errors at arbitrary positions. Let \(\varepsilon\in\BB^n\) encode at which positions an error occured (\(\varepsilon_j=1\) means that an error might have happened at position \(j\) and \(\varepsilon=0\) means that definitively no error occured at position \(j\)). We consider only the \(\binom{n}{d-1}\) many \(\varepsilon\in\BB^n\) which have weight \(d-1\) (they could have smaller weight but this doesn't change anything in the arguments). The argument above obviously generalizes to: For every error for which we know the corresponding error locations \(\varepsilon\) (with weight \(d-1\)) there is a recovery procedure \(\calR_{\epsilon}\) (only depending on \(\varepsilon\)) which corrects this error.

To summarize, the general error correction procedure is:

• Determine the location of the errors \(\varepsilon\in\BB^n\).
• Apply \(\calR_{\varepsilon}\) to correct a possible error.

QED.

We already know that \(Z_1Z_2\) and \(Z_2Z_3\) are generators of the stabilizer of the bit flip code. Since "everything" about the phase flip code is just the Hadamard transform of the bit flip code, the claim follows.

Alternatively you could first check that the code words

\[ a\ket{+++} + b\ket{---} \]

of the phase flip code are stabilized by \(X_1X_2\) and \(X_2X_3\) (which is easy to see). From the beginning of chapter 10.5.1 (p. 455) we know that this implies that \(S=\langle\?X_1X_2,X_2X_3\rangle\) commutes (which is clear) and does not contain \(-I\). Hence using that \(X_1X_2\) and \(X_2X_3\) are independent proposition 10.5 implies that the generated code \(V_S\) is two dimensional. We have already seen that \(V_S\) contains the phase flip code, so it must be identical with it. QED.

The Shor code encodes the two logical qubits as

\[ \ket{k_L} = \bigotimes_{j=1}^3 \frac{1}{\sqrt{2}} (\ket{000} + (-1)^k \ket{111}), \quad (k\in\BB) . \]

It is sufficient to check that the generators \(g_i\) stabilize the two base code words. In fact, by the argument from the beginning of chapter 10.5.1 (p. 455) all \(g_i\) commute (which is easy to see directly) and \(-I\notin\?S\). Since the \(g_i\) are clearly independent a dimensionality argument based on proposition 10.5 then shows that \(S\) only stabilizes the Shor code and not a larger code space.

Now let us check that the generators indeed stabilize the base code words. Observe that the qubits of \(\ket{k_L}\) can be split into three identical blocks with three qubits each. The generators \(g_i\) for \(i=1..6\) leave each single block invariant, hence they stabilize \(\ket{k_L}\). Moreover \(g_7\) inverts the sign (the \((-1)^k\) term) of the first two blocks, which in total has no effect either. Hence \(g_7\) stabilizes \(\ket{k_L}\). A similar argument applies to \(g_8\). QED.

That \(\bar{Z}\) and \(\bar{X}\) commute with the \(g_i\) should be clear from inspection. That they anti-commute with each other is also clear.

Let \(\ket{k_L}\) for \(k\in\BB\) be the two base code words of the Shor code for the two standard base states of the logical qubit.

In my opinion the easiest way to see that \(\bar{Z}\) is independent from the generators is to observe that it stabilizes \(\ket{0_L}\) but not \(\ket{1_L}\) (eigenvalue \(-1\)). (If \(\bar{Z}\) were dependent it would be an element of the generated subgroup \(S\) and hence had to stabilize both code words.) The justification to call it "Z" comes from \(\bar{Z}\ket{k_L}=(-1)^k\ket{k_L}\). A similar argument applies to \(\bar{X}\) which swaps \(\ket{0_L}\) with \(\ket{1_L}\) (which justifies to call it "X"). QED.

Remark

Another possible definition of the Z and X operator would be \(\bar{Z}=X_1X_2X_3\) and \(\bar{X}=Z_1Z_4Z_7\). Those two operators behave the same way on the code space as the original operators.

A basis for the set \(\calE\) of single qubit errors is given by all Pauli operators on five qubits with weight (at most) one (e.g. XIIII, IIZII, etc.).

In principle we have to check that \(E^\dagger\?F\notin\?N(S)\backslash\?S\) for every combination of of \(E,F\in\calE\). These are a lot of checks to perform. We can simplify the task by using the following lemma:

Lemma

For \(E,F\in\calE\) we have

1. \(E^\dagger\?F\in\?S\) is equivalent to \(E\cong\?F\), that is, they are identical if restricted to the stabilized subspace \(V_S\).
2. \(E^\dagger\?F\in\?N(S)\) is equivalent to \(E\) and \(F\) having the same syndromes.

Proof of (1)

By assumption we have \(s:=E^\dagger\?F\in\?S\). In other words \(F=Es\). This implies \(F\ket{\psi}=E\ket{\psi}\) for each \(\ket{\psi}\in\?V_S\). QED.

Proof of (2)

By exercise 10.44 (\(Z(S)=N(S)\) in our situation) we have

\[ \forall g\in S: \; E^\dagger F g = g E^\dagger F . \]

Note that this is the same as

\[ \forall g\in S: \; F g F^\dagger = E g E^\dagger . \]

Let \(\beta(g,E)\) be the syndrome of \(E\) when the observable \(g\in\?S\) is measured. Recall that this means \(EgE^\dagger=(-1)^{\beta(g,E)}g\). Using what we mentioned at the beginning of the proof this yields the claim. QED.

We will show that the fifteen "proper" errors \(\calE\backslash\?I^{\otimes5}\) all have different non-zero syndromes. Using the lemma we see that this is sufficient to prove that the code corrects all single qubit errors. It would be OK if some errors have the same syndrome as long as they act identically on the code space (\(E^\dagger\?F\in\?S\)), but this does not happen for the five qubit code.

In order to show this, let us use qiskit:

def compute_syndromes(generators: list[Pauli]):
    """Given the generators of a [n,k=1] code this computes the syndromes for
    each possible single qubit (Pauli) error."""
    n = generators[0].num_qubits
    paulis = ["X", "Y", "Z"]

    errors = [Pauli("I"*i + p + "I"*(n-i-1))
              for (i, p) in product(range(n), paulis)]

    syndromes = dict()

    for err in errors:
        syndrome = ""
        for i, gi in enumerate(generators, 1):
            if gi.anticommutes(err):
                syndrome += "1"
            else:
                syndrome += "0"

        syndromes[err.to_label()] = syndrome

    return syndromes

This function can now be used to compute the syndromes of the five qubit code:

g1 = Pauli("XZZXI")
g2 = Pauli("IXZZX")
g3 = Pauli("XIXZZ")
g4 = Pauli("ZXIXZ")
generators = [g1, g2, g3, g4]

syndromes = compute_syndromes(generators)
assert len(syndromes) == 15, "For each of 5 positions and 3 Paulis one syndrome."
assert len(set(syndromes.values())) == 15, "No duplicate syndromes!"


for error, syndrome in sorted(syndromes.items(), key=(lambda x: x[1])):
    print(f"{syndrome}: {error}")

0001: XIIII
0010: IIZII
0011: IIIIX
0100: IIIIZ
0101: IZIII
0110: IIIXI
0111: IIIIY
1000: IXIII
1001: IIIZI
1010: ZIIII
1011: YIIII
1100: IIXII
1101: IYIII
1110: IIYII
1111: IIIYI

The quantum hamming bound is

\[ \sum_{j=0}^t \binom{n}{j} 3^j \leq 2^{n-k} . \]

For the five qubit code we have \(n=5\), \(k=1\), and \(t=1\). Plugging this in yields:

\[ 1 + \binom{5}{1} 3^1 \leq 2^{5-1} , \]

which is clearly satisfied with equality.

Recall that the quantum hamming bound only applies to non-degenerate codes. The five qubit is acutally non-degenerate (we have seen in the solution of exercise 10.49 that the syndromes of all base errors are different). For \(k=t=1\) the hamming bound says:

\[ 3n + 1 \leq 2^{n-1} , \]

which has \(n=5\) as the smallest solution. Hence this exercise shows that the hamming bound is actually tight for \(k=t=1\) in the sense that there really is a non-degenerate code with just \(n=5\) qubits.

In the course of solving exercise 10.32 we have already seen that the check matrix looks like described. It remains to show that if \(C_1\) and \(C_2^\top\) correct \(t\) (classical) errors then the CSS code corrects \(t\) quantum errors.

Let \(H_1\) be the parity check matrix of \(C_1\) and let \(H_2\) be the parity check matrix of \(C_2^\top\).

Let \(E,F\) be two phase-less Pauli errors (products of Pauli matrices, without additional factor \(\pm1,\pm\ii\)) with weight less or equal to \(d\) such that \(d\leq\?t\). According to theorem 10.8 we have to show that \(E^\dagger\?F\notin\?N(S)\backslash\?S\). Without loss of generality we may assume that \(E\neq\?F\). We will even show that \(E^\dagger\?F\notin\?N(S)\), in other words, the syndromes of \(E\) and \(F\) are different (implying that a CSS code is non-degenerate, see the lemma in my solution of exercise 10.49).

Let us abbreviate \(N=\bigotimes_{j=1}^nN_j=E^\dagger\?F\) and define \((x,z)\in\BB^{2n}\) to be its encoding such that \((x_j,z_j)\) tells whether \(N_j\) is \(I\), \(X\), \(Y\), or \(Z\), in the same way as the check matrix \(G\) encodes this information. Recall that \(Z(S)=N(S)\) (exercise 10.44). Hence \(N\notin\?N(S)\) is the same as \(Ng_j=-g_jN\) for at least one \(j\). On the other hand the latter is equivalent to \(G_j\Lambda(x,z)^T=1\) (for some \(j\)), where \(G_j\) is just the \(j\)​th row of \(G\) which encodes \(g_j\). This in turn is equivalent to: \(H_1x\neq0\) or \(H_2z\neq0\).

On the other hand, since \(N\) has weight at most \(2d\) the weights of \(x\) and \(z\) are at most \(2d\) too. Moreover at least one of \(x\) and \(z\) has to be non-zero (because we assumed \(E\neq\?F\), or more precisely \(E^\dagger\?F\) not being a scalar multiple of the identity). By assumption \(C_1\) and \(C_2^\top\) both correct \(t\) errors and \(2d\?<\?2t+1\), hence \(H_1x\neq0\) or \(H_2z\neq0\) as desired. QED.

A characteristic of the code word \(\ket{0_L}\) is that each of its base-kets contains an even number of \(1\). This implies \(\bar{Z}\ket{0_L}=\ket{0_L}\). Similarly \(\ket{1_L}\) has only base kets with an odd number of ones, hence \(\bar{Z}\ket{1_L}=-\ket{1_L}\).

Moreover \(\ket{1_L}\) can be constructed from \(\ket{0_L}\) by just replacing each \(1\) by a \(0\) and vice versa. But this is just what \(\bar{X}\) does. Hence \(\bar{X}\ket{0_L}=\ket{1_L}\) and \(\bar{X}\ket{1_L}=\ket{0_L}\).

As suggested by the remark let us prove that

\[ M=\{g_1,\ldots,g_{n-k},\bar{Z}_1,\ldots,\bar{Z}_k\} \]

is independent. By assumptions (made in the main text) the elements of \(M\) commute and \(-I\) is not part of the generated group \(S_Z=\langle\?M\rangle\). Hence, the homomorphism (of groups) \(r:S_Z\to\BB^{2n}\) is injective. This implies that independence is an invariant property, that is:

\[ M \text{ independent} \quad \Longleftrightarrow \quad r(M) := \{r(g) \;|\; g\in M\} \text{ independent.} \]

Moreover independence in \(\BB^{2n}\) as a group is the same as independence in \(\BB^{2n}\) as a vector space over \(\BB\). Hence, in order prove independence we can use linear algebra methods. Let \(G\) be the check matrix (where the \(j\)​th row is \(r(g_j)\)) in standard form and let

\[ G_z = \begin{bmatrix} 0 & 0 & 0 & A_2^T & 0 & I \end{bmatrix} , \]

be the "check matrix" for the Z operators as given by the book (which actually defines the Z operators by the isomorphism \(r\)). Note that the \(I\in\BB^{k\times\?k}\) in the sixth block is responsible for \(G_z\) having (full) rank \(k\). In the same way the \(I\in\BB^{r\times\?r}\) (first block-column) and \(I\in\BB^{(n-k-r)\times\?(n-k-r)}\) (fifth block-column) are responsible for \(G\) having (full) rank \(n-k\). Hence

\[ \?\begin{bmatrix} G \\ G_z \end{bmatrix} \]

as full rank \(n-k=(n-k-r)+r\) because the three mentioned identities all live in different block-columns. This shows the independece of \(r(M)\) and hence of \(M\). QED.

Recall that within the linear algebra framework we have

\[ \bar{X} = \left[ \begin{array}{ccc|ccc} 0 & E^T & I & C^T & 0 & 0 \end{array} \right] , \]

where each line corresponds to a \(\bar{X}_j\) according to the homomorphism \(r\). From

\[ G \Lambda \bar{X}^T = \begin{bmatrix} IC + CI \\ IE + EI \end{bmatrix} = 0 \in \BB^{(n-k)\otimes k} . \]

we deduce that all \(g_i\) commute with all \(\bar{X}_j\). That all \(\bar{X}_j\) commute with each other is obvious from the structure of its matrix representation.

Independence of the set of generators and X operators (as a single set) follows from linear independence of their linear algebra representation. That the latter is true follows from looking where the identity matrices are because those are responsible for making \(G\) and \(\bar{X}\) into full-row-rank matrices. For the former we have identities in columns 1 and 5, for the latter we have it at column 3.

Finally we have

\[ \bar{Z} \Lambda \bar{X}^T = I\cdot I = I \in \BB^{k\times k} , \]

which precisely means that \(\bar{Z}_i\) and \(\bar{X}_j\) commute iff \(i\neq\?j\). QED.

This is just plugging stuff in. In the linear algebra framework we have:

\[ \bar{X} = \left[ \begin{array}{ccccccc|ccccccc} 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right] \in \BB^{1\times14} . \]

This corresponds to a single logical X operator which equals \(X_4X_5X_7\). As a bonus: in the same way we get \(Z_1Z_2Z_7\) as the logical Z operator.

Let \(N\) be one of the logical X or Z operators. Let \(g\in\?S\) and \(\ket{\psi}\in\?C\) an element of the code. The generators let the code invariant, hence \(g\ket{\psi}=\ket{\psi}\). On the other hand \(g\) commutes with \(N\) by construction of the logical Pauli operators. Hence

\[ gN \ket{\psi} = Ng \ket{\psi} = N \ket{\psi} , \]

which is precisely the claim. QED.

Let us use the code prepared in one of the introductory sections to this site. First consider the 5 qubit code.

cm = generators_to_check_matrix(generators_5qubit_code_repr())
transform_check_matrix(cm, [
    # n = 5, k = 1
    ["add row", 0, 2],
    ["add row", 1, 3],
    ["add row", 3, 2],
    ["add row", 3, 0],
    # Now we know r = 4, Hence the middle part is trivial!
])

[1 0 0 0 1 1 1 0 1 1]
[0 1 0 0 1 0 0 1 1 0]
[0 0 1 0 1 1 1 0 0 0]
[0 0 0 1 1 1 0 1 1 1]

Hence the 5 qubit code is an example where the the place for the matrix \(A_1\) completely vanishes (\(n-k-r=0\)). Next consider Shor's nine qubit code:

cm = generators_to_check_matrix(generators_shor_code_repr())
transform_check_matrix(cm, [
    # n = 9, k = 1, already see that r = 2
    ["swap rows", 0, 6],
    ["swap rows", 1, 7],
    ["swap qubits", 1, 3],
    ["add row", 1, 0],
    # X part is in standard form now. But by accident the Z part too!
])

[1 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0]
[0 1 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0]
[0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1]
[0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0]
[0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0]

The action of of the circuit in Figure 10.13 is

where \(Q_{\pm}=(I\pm\?M)/2\) are the projectors onto the eigenspaces of \(M\). This shows that the circuits works as described (measures \(M\)).

The LHS in Figure 10.14 and 10.15 is just a special case (\(M=X\) or \(M=Z\)) of Figure 10.13. The RHS in each of Figure 10.14 and 10.15 follow from two simple properties:

\[ \cz = H_2 \cx H_2 \]

on the one hand, and that for \(\cz\) the source and target play the same role (can be swapped without changing the action of the gate).

I do not know what to say more except that it is very easy to see. You just have to do it. One thing to remark is maybe that the transformation behaves like a transposition of matrices.

Using the utility code we can easily construct the circuits using qiskit.

generators = generators_5qubit_code()
qc = make_syndrome_circuit(generators, with_barrier=False)
qc.draw()

       ┌───┐                       ┌───┐
|0>_0: ┤ H ├────────■──────────────┤ H ├─────────────────────────────────────────────
       ├───┤        │              └───┘            ┌───┐
|0>_1: ┤ H ├────────┼────────────────■──────────────┤ H ├────────────────────────────
       ├───┤        │                │              └───┘            ┌───┐
|0>_2: ┤ H ├────────┼────────────────┼────────────────■──────────────┤ H ├───────────
       ├───┤        │                │                │              └───┘      ┌───┐
|0>_3: ┤ H ├────────┼────────────────┼────────────────┼────────────────■────────┤ H ├
       └───┘┌───────┴───────┐┌───────┴───────┐┌───────┴───────┐┌───────┴───────┐└───┘
  q_0: ─────┤0              ├┤0              ├┤0              ├┤0              ├─────
            │               ││               ││               ││               │
  q_1: ─────┤1              ├┤1              ├┤1              ├┤1              ├─────
            │               ││               ││               ││               │
  q_2: ─────┤2 Pauli(XZZXI) ├┤2 Pauli(IXZZX) ├┤2 Pauli(XIXZZ) ├┤2 Pauli(ZXIXZ) ├─────
            │               ││               ││               ││               │
  q_3: ─────┤3              ├┤3              ├┤3              ├┤3              ├─────
            │               ││               ││               ││               │
  q_4: ─────┤4              ├┤4              ├┤4              ├┤4              ├─────
            └───────────────┘└───────────────┘└───────────────┘└───────────────┘

Alternatively one can decompose the controlled pauli matrices. Unfortunately this also decomposes \(Z=HXH\):

generators = generators_5qubit_code()
qc = make_syndrome_circuit(generators, with_barrier=True)
qc.decompose(["cpauli"]).draw()

       ┌───┐ ░                                ░                                ░                               »
|0>_0: ┤ H ├─░───■────■─────────■────■────────░────────────────────────────────░───────────────────────────────»
       ├───┤ ░   │    │         │    │        ░                                ░                               »
|0>_1: ┤ H ├─░───┼────┼─────────┼────┼────────░───■────■─────────■────■────────░───────────────────────────────»
       ├───┤ ░   │    │         │    │        ░   │    │         │    │        ░                               »
|0>_2: ┤ H ├─░───┼────┼─────────┼────┼────────░───┼────┼─────────┼────┼────────░────────■─────────■────■───────»
       ├───┤ ░   │    │         │    │        ░   │    │         │    │        ░        │         │    │       »
|0>_3: ┤ H ├─░───┼────┼─────────┼────┼────────░───┼────┼─────────┼────┼────────░────────┼─────────┼────┼───────»
       └───┘ ░   │    │         │    │        ░ ┌─┴─┐  │         │    │        ░ ┌───┐┌─┴─┐┌───┐  │    │       »
  q_0: ──────░───┼────┼─────────┼────┼────────░─┤ X ├──┼─────────┼────┼────────░─┤ H ├┤ X ├┤ H ├──┼────┼───────»
             ░ ┌─┴─┐  │         │    │        ░ ├───┤┌─┴─┐┌───┐  │    │        ░ ├───┤└───┘└───┘┌─┴─┐  │  ┌───┐»
  q_1: ──────░─┤ X ├──┼─────────┼────┼────────░─┤ H ├┤ X ├┤ H ├──┼────┼────────░─┤ H ├──────────┤ X ├──┼──┤ H ├»
             ░ ├───┤┌─┴─┐┌───┐  │    │        ░ ├───┤└───┘└───┘┌─┴─┐  │  ┌───┐ ░ └───┘          └───┘┌─┴─┐└───┘»
  q_2: ──────░─┤ H ├┤ X ├┤ H ├──┼────┼────────░─┤ H ├──────────┤ X ├──┼──┤ H ├─░─────────────────────┤ X ├─────»
             ░ ├───┤└───┘└───┘┌─┴─┐  │  ┌───┐ ░ └───┘          └───┘┌─┴─┐└───┘ ░                     └───┘     »
  q_3: ──────░─┤ H ├──────────┤ X ├──┼──┤ H ├─░─────────────────────┤ X ├──────░───────────────────────────────»
             ░ └───┘          └───┘┌─┴─┐└───┘ ░                     └───┘      ░                               »
  q_4: ──────░─────────────────────┤ X ├──────░────────────────────────────────░───────────────────────────────»
             ░                     └───┘      ░                                ░                               »
«             ░                                     ░ ┌───┐
«|0>_0: ──────░─────────────────────────────────────░─┤ H ├
«             ░                                     ░ ├───┤
«|0>_1: ──────░─────────────────────────────────────░─┤ H ├
«             ░                                     ░ ├───┤
«|0>_2: ──■───░─────────────────────────────────────░─┤ H ├
«         │   ░                                     ░ ├───┤
«|0>_3: ──┼───░────────■────■─────────■────■────────░─┤ H ├
«         │   ░ ┌───┐┌─┴─┐  │  ┌───┐  │    │        ░ └───┘
«  q_0: ──┼───░─┤ H ├┤ X ├──┼──┤ H ├──┼────┼────────░──────
«         │   ░ └───┘└───┘┌─┴─┐└───┘  │    │        ░
«  q_1: ──┼───░───────────┤ X ├───────┼────┼────────░──────
«         │   ░           └───┘       │    │        ░
«  q_2: ──┼───░───────────────────────┼────┼────────░──────
«         │   ░                     ┌─┴─┐  │        ░
«  q_3: ──┼───░─────────────────────┤ X ├──┼────────░──────
«       ┌─┴─┐ ░ ┌───┐               └───┘┌─┴─┐┌───┐ ░
«  q_4: ┤ X ├─░─┤ H ├────────────────────┤ X ├┤ H ├─░──────
«       └───┘ ░ └───┘                    └───┘└───┘ ░

For the shor code I only print the compact representations:

generators = generators_shor_code()
qc = make_syndrome_circuit(generators, with_barrier=False)
qc.draw()

       ┌───┐                             ┌───┐                                                  »
|0>_0: ┤ H ├──────────■──────────────────┤ H ├──────────────────────────────────────────────────»
       ├───┤          │                  └───┘                ┌───┐                             »
|0>_1: ┤ H ├──────────┼────────────────────■──────────────────┤ H ├─────────────────────────────»
       ├───┤          │                    │                  └───┘                ┌───┐        »
|0>_2: ┤ H ├──────────┼────────────────────┼────────────────────■──────────────────┤ H ├────────»
       ├───┤          │                    │                    │                  └───┘        »
|0>_3: ┤ H ├──────────┼────────────────────┼────────────────────┼────────────────────■──────────»
       ├───┤          │                    │                    │                    │          »
|0>_4: ┤ H ├──────────┼────────────────────┼────────────────────┼────────────────────┼──────────»
       ├───┤          │                    │                    │                    │          »
|0>_5: ┤ H ├──────────┼────────────────────┼────────────────────┼────────────────────┼──────────»
       ├───┤          │                    │                    │                    │          »
|0>_6: ┤ H ├──────────┼────────────────────┼────────────────────┼────────────────────┼──────────»
       ├───┤          │                    │                    │                    │          »
|0>_7: ┤ H ├──────────┼────────────────────┼────────────────────┼────────────────────┼──────────»
       └───┘┌─────────┴─────────┐┌─────────┴─────────┐┌─────────┴─────────┐┌─────────┴─────────┐»
  q_0: ─────┤0                  ├┤0                  ├┤0                  ├┤0                  ├»
            │                   ││                   ││                   ││                   │»
  q_1: ─────┤1                  ├┤1                  ├┤1                  ├┤1                  ├»
            │                   ││                   ││                   ││                   │»
  q_2: ─────┤2                  ├┤2                  ├┤2                  ├┤2                  ├»
            │                   ││                   ││                   ││                   │»
  q_3: ─────┤3                  ├┤3                  ├┤3                  ├┤3                  ├»
            │                   ││                   ││                   ││                   │»
  q_4: ─────┤4 Pauli(ZZIIIIIII) ├┤4 Pauli(IZZIIIIII) ├┤4 Pauli(IIIZZIIII) ├┤4 Pauli(IIIIZZIII) ├»
            │                   ││                   ││                   ││                   │»
  q_5: ─────┤5                  ├┤5                  ├┤5                  ├┤5                  ├»
            │                   ││                   ││                   ││                   │»
  q_6: ─────┤6                  ├┤6                  ├┤6                  ├┤6                  ├»
            │                   ││                   ││                   ││                   │»
  q_7: ─────┤7                  ├┤7                  ├┤7                  ├┤7                  ├»
            │                   ││                   ││                   ││                   │»
  q_8: ─────┤8                  ├┤8                  ├┤8                  ├┤8                  ├»
            └───────────────────┘└───────────────────┘└───────────────────┘└───────────────────┘»
«
«|0>_0: ─────────────────────────────────────────────────────────────────────────────────────────
«
«|0>_1: ─────────────────────────────────────────────────────────────────────────────────────────
«
«|0>_2: ─────────────────────────────────────────────────────────────────────────────────────────
«               ┌───┐
«|0>_3: ────────┤ H ├────────────────────────────────────────────────────────────────────────────
«               └───┘                ┌───┐
«|0>_4: ──────────■──────────────────┤ H ├───────────────────────────────────────────────────────
«                 │                  └───┘                ┌───┐
«|0>_5: ──────────┼────────────────────■──────────────────┤ H ├──────────────────────────────────
«                 │                    │                  └───┘                ┌───┐
«|0>_6: ──────────┼────────────────────┼────────────────────■──────────────────┤ H ├─────────────
«                 │                    │                    │                  └───┘        ┌───┐
«|0>_7: ──────────┼────────────────────┼────────────────────┼────────────────────■──────────┤ H ├
«       ┌─────────┴─────────┐┌─────────┴─────────┐┌─────────┴─────────┐┌─────────┴─────────┐└───┘
«  q_0: ┤0                  ├┤0                  ├┤0                  ├┤0                  ├─────
«       │                   ││                   ││                   ││                   │
«  q_1: ┤1                  ├┤1                  ├┤1                  ├┤1                  ├─────
«       │                   ││                   ││                   ││                   │
«  q_2: ┤2                  ├┤2                  ├┤2                  ├┤2                  ├─────
«       │                   ││                   ││                   ││                   │
«  q_3: ┤3                  ├┤3                  ├┤3                  ├┤3                  ├─────
«       │                   ││                   ││                   ││                   │
«  q_4: ┤4 Pauli(IIIIIIZZI) ├┤4 Pauli(IIIIIIIZZ) ├┤4 Pauli(XXXXXXIII) ├┤4 Pauli(IIIXXXXXX) ├─────
«       │                   ││                   ││                   ││                   │
«  q_5: ┤5                  ├┤5                  ├┤5                  ├┤5                  ├─────
«       │                   ││                   ││                   ││                   │
«  q_6: ┤6                  ├┤6                  ├┤6                  ├┤6                  ├─────
«       │                   ││                   ││                   ││                   │
«  q_7: ┤7                  ├┤7                  ├┤7                  ├┤7                  ├─────
«       │                   ││                   ││                   ││                   │
«  q_8: ┤8                  ├┤8                  ├┤8                  ├┤8                  ├─────
«       └───────────────────┘└───────────────────┘└───────────────────┘└───────────────────┘

This can easily be done using the code we have produced for previous exercises.

generators = generators_steane_code_standard()
steane_syndromes = compute_syndromes(generators)

assert len(steane_syndromes) == 3*7, "Steane code is non-degenerate (1)"
assert len(set(steane_syndromes.values())) == 3*7, "Steane code is non-degenerate (2)"

def shorten(pauli_str: str):
    ret = None

    if (i := pauli_str.find('Z')) != -1:
        ret = f"Z_{i+1}"
    elif (i := pauli_str.find('X')) != -1:
        ret = f"X_{i+1}"
    elif (i := pauli_str.find('Y')) != -1:
        ret = f"Y_{i+1}"

    assert ret != None, "Invalid input"
    s = pauli_str[:i] + "I" + pauli_str[i+1:]
    assert s == "I" * len(pauli_str), "Invalid input"

    return ret

# This prints the syndromes and their error E (note: E=E.H)
for error, syndrome in sorted(steane_syndromes.items(), key=(lambda x: x[1])):
    print(f"{syndrome}: {error}, {shorten(error)}")

000001: IIIIIXI, X_6
000010: IIIIXII, X_5
000011: IXIIIII, X_2
000100: IIIXIII, X_4
000101: XIIIIII, X_1
000110: IIIIIIX, X_7
000111: IIXIIII, X_3
001000: IIZIIII, Z_3
001111: IIYIIII, Y_3
010000: IZIIIII, Z_2
010011: IYIIIII, Y_2
011000: IIIZIII, Z_4
011100: IIIYIII, Y_4
100000: ZIIIIII, Z_1
100101: YIIIIII, Y_1
101000: IIIIZII, Z_5
101010: IIIIYII, Y_5
110000: IIIIIIZ, Z_7
110110: IIIIIIY, Y_7
111000: IIIIIZI, Z_6
111001: IIIIIYI, Y_6

Let us assume that we first encode everything with \(C_1\) and then, on top of this, we encode every of the resulting \(n_1\) qubits with \(C_2\). Clearly this leads to a space with \(n_1n_2\) dimensions which we use to encode a single logical qubit.

What are the generators of the concatenated code \(C_2\circ\?C_1\)? Therefore let \((g^{(1)}_i)_{i\in1..n_1}\) and \((g^{(2)}_i)_{i\in1..n_2}\) be the generators of \(C_1\) and \(C_2\) (individually). The stabilizer of \(C_2\circ\?C_1\) has two responsibilities

1. Stabilize each of the \(n_2\) copies of \(C_1\) (one for each qubit of \(C_2\)).
2. On top of that, stabilize \(C_2\) relative to \(C_1\).

For the first responsibility we use the following \(n_2(n_1-1)\) generators:

\[ \tilde{g}_{l,k} = I \ldots \otimes g_k^{(1)} \otimes \ldots I , \]

for \(k=1..n_1\) and \(l=1..n_2\) and the factor \(g_k^{(1)}\) sits at position \(l\) in the tensor product. For the second set of stabilizer generators let us first write

\[ g_k^{(2)} = \bigotimes_{j=1}^{n_2} N_{k,j} , \]

where \(N_{k,j}\in\{I,X,Y,Z\}\). Moreover let \(\bar{N}_{kj}\) be the "lifting" of \(N_{kj}\) to \(C_1\). Then the second set of stabilizer generators (containing \(n_2-1\) elements) are

\[ \bar{g}_k = \bigotimes_{j=1}^{n_2} \bar{N}_{k,j} , \]

where \(k=1..n_2\). Note that by construction of the lifted operators the \(\bar{N}_{kj}\) commute with all generators from the first set. Overall we found the \(n_1n_2-1\) generators of \(C_2\circ\?C_1\)!

Let \(\ket{\pm_L}=(\ket{0_L}\pm\ket{1_L})/\sqrt(2)\) be the eigenstates of \(\bar{X}\). From \(\bar{X}\ket{+_L}=\ket{+_L}\) and \(\bar{X}=U\bar{Z}U^\dagger\) we obtain

\[ U^\dagger \ket{+_L} = \bar{Z} U^\dagger \ket{+_L} . \]

Hence \(U^\dagger\ket{+_L}\) is a \(+1\) eigenstate of \(\bar{Z}\). Hence

\[ U^\dagger\ket{+_L} = e^{\ii\varphi_{0}} \ket{0_L} . \]

In the same way (using \(\bar{X}\ket{-_L}=-\ket{-_L}\) and again \(\bar{X}=U\bar{Z}U^\dagger\)) we obtain

\[ U^\dagger\ket{-_L} = e^{\ii\varphi_{1}} \ket{1_L} . \]

It remains to show that \(\varphi_0=\varphi_1=:\varphi\). Note that it is not possible to show that \(\varphi=0\) (simply because it is wrong in general).

From \(\bar{Z}\ket{-_L}=\ket{+_L}\) and \(U\ket{X}U^\dagger=\bar{Z}\) we deduce

\[ \ket{-_L} = U\bar{X}U^\dagger \ket{+_L} = U\bar{X} e^{\ii\varphi_0} \ket{0_L} = U e^{\ii\varphi_0} \ket{1_L} = e^{\ii(\varphi_0-\varphi_1)} \ket{-_L} . \]

Hence \(\varphi_0=\varphi_1\) as desired. QED.

As mentioned we already know the following propagation rule \(\cx_{12}X_1=X_1X_2\cx_{12}\). Moreover, from exercise 4.20 we know that

\[ \cx_{21} = H_1H_2 \cx_{12} H_1H_2 . \]

Hence

Hence a \(Z\) error at the control of \(\cx\) progagates as two \(Z\), one at control and one at the target.

Let \(\ket{\psi}=a\ket{0}+\ket{1}\). Let us track the action of the first circuit:

Hence measuring \(0\) or \(1\) occurs with probability 50% (which is not important but nice to know) and after measuring \(0\) the state in the first wire is already \(\ket{\psi}\). If \(1\) is measured only a \(Z\) is needed to transform the state into \(\ket{\psi}\).

For the second circuit we proceed analogously:

After measuring \(0\) the state in the first wire is already \(\ket{\psi}\). If \(1\) is measured only a \(X\) is needed to transform the state into \(\ket{\psi}\).

That \(T\) commutes with \(U\) follows from the fact that \(T\equiv\?R_z(\pi/4)\) is a function of the \(Z\) operator whose eigenstates form the decision states of the CNOT gate (\(U\)). Here with \(\equiv\) I mean equality up to global phase. That \(TX=\exp(−\ii\pi/4)SXT\) follows essentially from the bloch sphere interpretation:

\[ XTX \equiv X R_z(\pi/4) X = R_z(-\pi/4) \equiv S^\dagger T \equiv XSXT . \]

The correct phase is not really important here but could also be recovered because there are transparent rules to translate between \(T,S,Z\) on the one hand and \(R_z(\theta)\) including phase on the other hand. For example:

\[ T = \sqrt[4]{Z} = e^{i\pi/8} R_z(\pi/4) . \]

Having this commutation relation at hand it is easy to commute \(T\) from the end to the desired place near the beginning of the circuit.

There are several simple ways to see these identities. The most straightforward way is to check that the circuits act the same on the eight basis states \(\ket{ijk}\) (\(i,j,k\in\{0,1\}\)). This is essentially what we do in the following, but we take some simple shortcuts which save us from tabulating eight possibilities for each identity (instead we only have to consider two carefully chosen cases).

Consider identity (1). Clearly both circuits act the same way on the first two circuits. For the first circuit we see that it only acts non-trivially (with an \(X\)) on the third qubit if \(i=0\), \(j=1\). It is not hard to see that the second circuit does the same.

Consider identity (2). It is not hard to see that both circuits map \(\ket{11k}\) to \((-1)^k\ket{11\bar{k}}\), where \(k=k+1\mod2\). On the other hand, if at least one of \(i\), \(j\) is not \(1\), then both circuits act as \(\ket{ijk}\mapsto(-1)^{k}\ket{ijk}\).

Part (1) is really just two times the second circuit and one time the third circuit from exercise 10.65.

For part (2) there isn't much to say. The exercise statement already explained that this follows from the identities from exercise 10.67.

For part (3) observe that the non-ancilla part of the circuit only contains Clifford gates (some of which are classically controlled). In the main text we have already seen how to implement those in the Steane code. So assuming the ancilla can also be prepared so that it is already Steane-encoded the whole circuit can be implemented in a fault tolerant way.

The following argumentation is designed to work with the 7-qubit Steane code. However, it is generic as it applies to any \([n,1]\) stabilizer code showing that the arguments also apply to e.g. the 5-qubit code. Note however that strictly speaking several assumptions go into the construction of the schematic circuit from Firgure 10.28. For example we assume that the controlled-​\(M\) operation can be implemented in a transversal way. For this exercise we are only concerned about the Prepare-Verify part of the circuit allowing us to be more general. But you can always set \(n=7\) to restrict everything to the Steane code and keep things simple.

Let us distinguish two cases:

1. A single error in the preparation stage (and no error in verification stage).
2. A single error in the verification stage (and no error in preparation stage).

Consider case 1 (error in preparation stage). Let us briefly show that multiple \(X\) errors are possible directly after the preparation stage even if only one of its components fails. To see this assume that the first CNOT between the first and second ancilla produces a single \(X\) error at its control qubit (ancilla 1). By the propagation rules for CNOT this error gets distributed (by the following CNOT gates) to almost all ancilla qubits, leading to the following total error after preparation:

\[X\otimes I \otimes X^{\otimes n-2}\]

For that reason we assume that the error after the preparation stage is in the most general form according to the error model from the main text

\[ E = \bigotimes_{j=1}^n N_j, \text{ where } N_j \in \{I,X,Y,Z\} . \]

Recall that this error model says that a component fails with a certain probability \(p\) and produces only Pauli errors at its outputs. If no errors would have occured the output of the preparation stage is a cat state:

\[ \cat = \frac{1}{\sqrt{2}} (\ket{0^n} + \ket{1^n}) . \]

With error the output is \(E\cat\). Now we show that the verification stage detects if any \(X\) or \(Y\) errors are present (but it does not see \(Z\) errors). In fact, the verification stage can be implemented as a series of \(n-1\) pairs of CNOT gates

\[ G_j = \cx_{j,x} \cx_{j+1,x}, \quad (j=1..n-1), \]

(\(x\) being an additional ancilla outside the "main" ancillas initialized to \(\ket{0}\) for each \(G_j\)) which are followed by a measurement (each). It is not hard to see that the verification step implements the measurement of all \(g_j=Z_jZ_{j+1}\) for \(j=1..n-1\). These operators can be seen as the stabilizer of the two dimensional subspace spanned by

\[ \ket{0^n}, \ket{1^n} , \]

which contains \(\cat\). Thus applying verification to \(E\cat\) the verification either detects an error (which saves us) or it says "OK" and the final state is one of two possibilities

\[ \catp{\pm} = \frac{1}{\sqrt{2}} (\ket{0^n} \pm \ket{1^n}) , \]

Note that \(\catp{+}=\cat\) is the cat state and contains effectively no errors but could be the result of an even number of \(Z\) errors (which do not affect the cat state). In case of an odd number of \(Z\) errors we get \(\catp{-}\). This would be a "proper" error. It does not propagate into the data qubits (because \(Z\) commutes with the control of any controlled gate) but it would be decoded into \(\ket{10^{n-1}}\) which would be measured as \(1\) at the first ancilla. Hence this error would basically swap the measurement result for the overall procedure (whose goal is to measure an operator \(M\) whose eigenvalues are \(\pm1\)). This concludes case 1, as we have seen that actually no \(X\) or \(Y\) errors can hide from the verification procedure.

Consider case 2 (verification fails). In that case, by assumption, the preparation stage correctly produces \(\cat\). Any error (\(X,Y,Z\)) originating from a control of the \(G_j\) (see above) can only propagate into the additional ancillas and hence not into the rest of the \(n\) "main" ancillas. Moreover, although a \(Z\) error in the additional ancillas can propagate into the main ancillas, but \(X\) cannot. Similarly a \(Y=\ii\?ZX\) error in the additional ancillas can only propagate a \(Z\) error into the main ancillas.

Hence, in this case, a \(X\) or \(Y\) error can only be produced if it originates from a part of a component (a control of the CNOT gates) which is attached to the main ancillas and furthermore it cannot further propagate into the other main ancillas. QED.

In this solution we do not need to restrict to the Steane code. Instead we consider a general stabilizer code on \(n\) qubits (Steane has \(n=7\)) for which the transversal construction for the controlled \(M\) operator works as outlined and such that \(n\) is odd. See also the first paragraph of the solution of exercise 10.69.

Let us briefly recall that \(Z\) errors commute with the control of any controlled gate \(C(U)\). In fact, we have

\[ C(U) = P_0\otimes I + P_1\otimes U . \]

Note that the projections \(P_j=\proj{j}\) onto the standard basis actually commute with \(Z\) because the standard basis is the eigenbasis of \(Z\) (by definition). For that reason we have

\[ C(U) \cdot Z\otimes I = (P_0 Z) \otimes I + (P_1 Z) \otimes U = (Z P_0) \otimes I + (Z P_1) \otimes U = Z\otimes I \cdot C(U) . \]

This implies that \(Z\) errors in the ancillas cannot propagate into the data qubits because ancillas and data are only connected via CNOT gates (with controls in the ancillas). This shows the first part of the claim.

Now let us check how \(Z\) errors affect the measurement. For that purpose let us define

\[ \catp{\pm} = \frac{1}{\sqrt{2}} ( \ket{0^n} \pm \ket{1^n} ) \]

and first consider the working of the operator measurement in case no error happens. Let \(\ket{\psi}\) be the encoded data and decompose it into

\[ \ket{\psi} = a\ket{\psi_+} + b\ket{\psi_-} , \]

where \(\ket{\psi_{\pm}}\) are the encoded eigenstates of \(M\) (with eigenvalues \(\pm1\)). Right before applying the controlled \(M\) the state is \(\cat\ket{\psi}\). After applying the (encoded) controlled \(M\) operator we get (after reordering terms)

Here at this point we need that the transversal construction of the encoded controlled \(M\) gate looks like in Figure 10.28 (see also Figure 10.24) and the coded uses an odd number \(n\) of qubits (so that \((-1)^n=-1\)). Decoding transforms it into

Hence, measuring \(0\) (in the first ancilla) yields \(\ket{\psi_+}\) in the data qubits, and measuring \(1\) yields \(\ket{\psi_-}\) in the data qubit. This is as desired.

What happens if we get \(r\geq1\) many \(Z\) errors after the prepare-verify stages? If \(r\) is even this does not affect the cat state and the procedure works as expected. If \(r\) is odd the cat state \(\cat=\catp{\?+}\) is replaced by \(\catp{-}\). In essence, in the above derivation \(\catp{+}\) and \(\catp{-}\) swap their roles. Hence, right before measurement we get the state

This implies that we infer the wrong eigenvalue in this case (with 100% probability). QED.

Let us consider this exercise for the 7-qubit Steane code. Let us denote the ancilla qubits by the labels \(a_i\) and the qubits for the data by \(d_i\) (\(i=1..7\)). We show that the encoded controlled \(M\) operator is given by a product of controlled \(V=ZSX\) gates with controls and targets as in Figure 10.24 (where the first block are the ancillas and the second block the data):

\[ \prod_{i=1}^{7} C(ZSX)_{a_i,d_i} \]

First of all observe that

This is the behaviour we want to have on the encoded qubits (logical qubits). On the other hand we have (on the physical qubits)

This is exactly what we want for the Steane code! In fact, the logical Pauli operators are \(\bar{Z}=Z^{\otimes7}\), \(\bar{X}=X^{\otimes7}\), and \(\bar{Y}=-Y^{\otimes7}\). The formula for \(\bar{Y}\) follows from \(Y=\ii\?XZ\). So the minus sign in front of \(Y\) is exactly what we want. QED.

By construction we have

\[ \ket{\Theta} = \mathrm{CCX} H_1 H_2 \ket{000} . \]

So in order to find generators of the stabilizer of \(\ket{\Theta}\) we start with the generators

\[ \langle Z_1, Z_2, Z_3 \rangle \]

of \(\ket{000}\) and apply the stabilizer formalism. Applying the two Hadamard gates according to the stabilizer formalism (every generator gets conjugated by the gates: \(g\mapsto\?UgU^\dagger\)) yields

\[ \langle X_1, X_2, Z_3 \rangle . \]

The interesting thing happens when we apply the Toffoli gate (a non-clifford gate). In that case we leave the Pauli group and get:

\[ \langle X_1\cx_{23}, X_2\cx_{13}, Z_3\cz_{12} \rangle . \]

To see this use exercise 10.67. All three generators are three qubit gates, but they still have eigenvalues \(\pm1\) (as they are produced by conjugation).

Now I would like to use the construction from 10.28. However there are several problems I cannot solve at the moment. For example the construction requires to put yet another layer of control to the generators. Since the generators already contain controlled gates this requires doubly controlled gates (a priori at least). This does not look like a promising approach to me. So I leave this solution open ended …

The construction which is described above is just a variation of the schematic given in Figure 10.28. Each of the six measurements (one for each generator) has its own block of seven ancilla qubits (but the same data block). Measuring them in a row implies that we get a state \(\ket{\psi}\) (in the data block) which is a simultaneous eigenstate of the six generators. Repeating this procedure three times and taking majority votes ensures a success probability for a correct measurement of \(O(p^2)\) (NOTE: this is not explicitly mentioned in the book but each repetition reuses the data-block output from the previous iteration. This works because errors do not propagate in the data block and hence at most one qubit is corrupted in case a single component fails).

As already mentioned, after all this the state \(\ket{\psi}\) is a simultaneous eigenstate of the six generators. Let us denote the measurement result by a bit vector \(b\in\BB^6\). The state \(\ket{\psi}\) is \(\ket{0_L}\) iff \(b=0^6\). Otherwise we can correct the state by treating \(b\) as a syndrome and apply operators according to the table produced in the solution of exercise 10.61.

Conceptually one does exactly the same as for the Steane code. Just have a look into exercise 10.73. I see no benefit in repeating it here.