Quantum error correction: Steane 7-qubit code

\( \def\ket#1{{ \left| #1 \right> }} \) \( \def\bracket#1{{ \left( #1 \right) }} \) \( \def\bra#1{{ \left< #1 \right| }} \)

$\left[7,1 \right]$ Steane code is an ubiquitous example of Calderbank-Shor-Steane (CSS) class of quantum error correction codes. Steane code was constructed from classical $\left[7,4,3 \right]$ Hamming code whose parity-check matrix takes the following form
\begin{equation}
H  = 
\begin{pmatrix}
0 & 0 & 0 & 1 & 1 & 1& 1\\
0 & 1 & 1 & 0 & 0 & 1& 1\\
1 & 0 & 1 & 0 & 1 & 0& 1
\end{pmatrix}.
\label{parity}
\end{equation}

Question (a): Let $C$ be a $\left[n,k \right]$ linear code and $C^\perp$ be the dual code of $C$, if $x \in C^\perp$ then $\sum_{y\in C} \left(-1 \right)^{x \cdot y} = \vert C \vert $, while if $x \notin C^\perp$ then show that $\sum_{y\in C} \left(-1 \right)^{x \cdot y} = 0 $.

As for $x \in C^\perp$, it is straightforward from the definition of dual code that $x$ is orthogonal to all codewords of $C$
\begin{equation}
\begin{aligned}
    x \cdot y &=0 \quad \forall y \in C\\
    \Rightarrow \sum_{y\in C} \left(-1 \right)^{x \cdot y} &= \dim C = 2^k = \vert C \vert.
\end{aligned}
\end{equation}
As for $x \notin C^\perp$, as codewords $y$ are linear combinations of columns of $n \times k$ generator matrix $G$, there exist at least one column of $G$ that is not orthogonal to $x$. We call $m$ as the number of columns not orthogonal to $x$ which satisfies $1 \le m < k$. Suppose that an even number columns from $k$ are picked and assigned by coefficients 1, the linear combinations of them with $k-m$ orthogonal-to-$x$ columns would form a space orthogonal $S^\perp$ to $x$. The dimension of $S^\perp$ is
\begin{equation}
   \dim S^\perp =\sum_{j=0,2,4,\ldots}^{m}  
    \begin{pmatrix}
    k\\m
    \end{pmatrix}  2^{k-m}.
\label{dim1}
\end{equation}
We use the fact that 
\begin{equation}
    \left( 1+x \right)^m = \sum_{j=0}^{m} \begin{pmatrix}
    m\\j
    \end{pmatrix} x^j.
    \label{binomial}
\end{equation}
We differentiate both sides of Eq. (\ref{binomial}) at $x=-1$ and obtain
\begin{equation}
    \sum_{j=0,2,4,\ldots}^{m} \begin{pmatrix}
    m\\j
    \end{pmatrix} =
    \sum_{j=1,3,5,\ldots}^{m} \begin{pmatrix}
    m\\j
    \end{pmatrix} = 
    \frac{1}{2}\sum_{j=0}^{m} \begin{pmatrix}
    m\\j
    \end{pmatrix} = 2^{m-1}.
\label{dim2}
\end{equation}
From Eqs. (\ref{dim1}) and (\ref{dim2}) we obtain
\begin{equation}
     \dim S^\perp = 2^{m-1} 2^{k-m}= 2^{k-1}.
\end{equation}
Let $S$ be the space non-orthogonal to $x$, it is obvious that $S^\perp \oplus S = C$ so
\begin{equation}
     \dim S^\perp = \dim S =2^{k-1}.
\end{equation}
We therefore have
\begin{equation}
\begin{aligned}
    \sum_{y\in C} \left(-1 \right)^{x \cdot y} &= \sum_{y\in S} \left(-1 \right)^{x \cdot y} + \sum_{y\in S^\perp} \left(-1 \right)^{x \cdot y} \\
    &= \left(-1 \right)^{1} \dim S + \left(-1 \right)^{0} \dim S^\perp = 0 \quad \Box
\end{aligned}
\end{equation}

 

Question (b): Based on the definition of CSS code and result from problem (a), prove that the stabilizers of Steane code have positions of $Z$ and $X$ operators identical to positions of $1$s in the parity matrix $H$ in Eq. (\ref{parity}).
\begin{equation}
\begin{aligned}
g_1 = X_1 X_2 X_3 X_4, \quad \quad g_4 = Z_1 Z_2 Z_3 Z_4, \\
g_2 = X_1 X_3 X_5 X_7, \quad \quad g_5 = Z_1 Z_3 Z_5 Z_7, \\
g_3 = X_2 X_3 X_6 X_7, \quad \quad g_6 = Z_2 Z_3 Z_6 Z_7. \\
\end{aligned}
\end{equation}

We recall the definition of CSS code: given $C_1$ and $C_2$ are $\left[ n, k_1 \right]$ and $\left[ n, k_2 \right]$ linear codes such that $C_2 \subset C_1$ and $C_1$ and $C_2^\perp$ both correct $t$ errors, the CSS code of $C_1$ over $C_2$, denoted as CSS$\left(C_1, C_2 \right)$, is the quantum state $\ket{x + C_2}$ written as
\begin{equation}
    \ket{x+ C_2} \equiv \frac{1}{\sqrt{\vert C_2 \vert}} \sum_{y \in C_2} \ket{x+y},
    \label{CSScodeword}
\end{equation}
where $+$ signifies the bitwise exclusive-OR operator (or bitwise addition modulo $2$). Steane code is CSS code of $\left[7,4,3 \right]$ Hamming code over its dual, which is mathematically written as CSS$\left(C, C^\perp \right)$. 

From the definition, we deduct that both codewords $x$ and $y$ are in $C$ so we straightforwardly have
\begin{equation}
    H \cdot \left( x + y \right) = 0,
\end{equation}
here the dot $\cdot$ is bitwise AND operator. Since the effects of Pauli Z operators on computational basis vectors are governed by parity (an even number of products of $Z \ket{1}$ yields $1$ while an odd number yields $-1$) just like the bitwise AND operator, we could obtain the following similarities
\begin{equation}
\begin{aligned}
\begin{pmatrix}
0 & 0 & 0 & 1 & 1 & 1& 1\\
0 & 1 & 1 & 0 & 0 & 1& 1\\
1 & 0 & 1 & 0 & 1 & 0& 1
\end{pmatrix} &\leftrightarrow 
\begin{pmatrix}
I_1 & I_2 & I_3 & Z_4 & Z_5 & Z_6 & Z_7\\
I_1 & Z_2 & Z_3 & I_4 & I_5 & Z_6 & Z_7\\
Z_1 & I_2 & Z_3 & I_4 & Z_5 & I_6 & Z_7
\end{pmatrix} = \begin{pmatrix}
g_4 \\
g_5 \\
g_6 
\end{pmatrix}\\[10pt]
    H \cdot \left(x+y\right) = 0 &\leftrightarrow g_i \ket{x+y} = +1 \ket{x+y} \quad  \forall i =4,5,6.
\end{aligned}
\end{equation}
Quantum parallelism allows quantum operators to act simultaneously on a superposition so we have
\begin{equation}
    g_i \ket{x + C_2} =  \ket{x + C_2} \quad  \forall i =4,5,6. 
\end{equation}
We have proven that $g_4$ through $g_6$ were stabilizers of Steane code. As for $g_1$ through $g_3$, it is more convenient to transform the codeword to Hadamard basis
\begin{equation}
   \ket{x+ C_2}_H = H_1H_2\ldots H_7 \ket{x+C_2} = \frac{1}{\sqrt{\vert C_2 \vert 2^n}} \sum_{z} \sum_{y \in C_2} \left( -1 \right)^{\left( x+y \right) \cdot z} \ket{z}.
    \label{hadamardbasis}
\end{equation}
The result in problem (a) helps to simplify Eq. (\ref{hadamardbasis}) as
\begin{equation}
\begin{aligned}
    \ket{x+C_2}_H &= \frac{1}{\sqrt{\vert C_2 \vert 2^n}} \sum_{z} \sum_{y \in C_2} \left( -1 \right)^{\left( x+y \right) \cdot z} \ket{z}\\
    &= \frac{1}{\sqrt{\vert C_2 \vert 2^n}} \sum_{z \in C_2^\perp}  \left( -1 \right)^{ x \cdot z} \ket{z}.
\end{aligned}
\label{z}
\end{equation}
Notice that in Steane code, $C_2^\perp = C_1 = C$ so the code word $z$ in Eq. (\ref{z}) belongs to the kernel of parity matrix $H$, which means $\ket{x+C_2}_H$ is stabilized by $g_4$ through $g_6$ as proven above
\begin{equation}
    g_i \ket{x + C_2}_H =  \ket{x + C_2}_H \quad  \forall i =4,5,6.
    \label{haha}
\end{equation}
Transforming back to the computational basis, Eq. (\ref{haha}) reads
\begin{equation}
    g_i \ket{x + C_2} =  \ket{x + C_2} \quad  \forall i =1,2,3.
\end{equation}
We have successfully pointed out all 6 generators of Steane code.

 

 

Question (c): Using stabilizer formalism, explicitly demonstrate the way Steane code corrects single-qubit Pauli errors (bit-flip, phase-flip and combined bit-phase flip) and an arbitrary single-qubit error.

Circuit to encode Steane 7-qubit code. Here $\ket{\psi}$ is the qubit we want to protect.

Recall that Steane codeword is the vector space stabilized by 6 following generators
\begin{equation}
\begin{aligned}
g_1 = X_1 X_2 X_3 X_4, \quad \quad g_4 = Z_1 Z_2 Z_3 Z_4, \\
g_2 = X_1 X_3 X_5 X_7,\quad \quad g_5 = Z_1 Z_3 Z_5 Z_7, \\
g_3 = X_2 X_3 X_6 X_7, \quad \quad g_6 = Z_2 Z_3 Z_6 Z_7. \\
\end{aligned}
\end{equation}
We first point out how Steane code corrects discrete Pauli errors. For simplicity, we assume that the error occurs at the $7^{th}$-qubit $\ket{\psi}$. As for bit-flip error, represented by $X_7$, the system is now stabilized by
\begin{equation}
\left< X_7 g_i X_7^{\dagger}  \right>= \left< g_1,g_2,g_3,g_4,-g_5,-g_6 \right>,
\end{equation}
which indicates that when we measure all observables $g_1$ to $g_6$, we deterministically get the following outcome string
\begin{equation}
\left\{ 1,1,1,1,-1,-1 \right\}.
\label{outcome}
\end{equation}
Eq. (\ref{outcome}) says that both measurements of $g_5$ and $g_6$ yield $-1$, which uniquely detects bit-flip occurring at $7^{th}$ qubit. We simply correct the error by applying $X_7$ to the system one more time. We do the same for phase-flip error $Z_7$ and straightforwardly obtain the outcome of 
\begin{equation}
\left\{ 1,-1,-1,1,1,1 \right\},
\end{equation}
where $-1$ outcomes of $g_2$ and $g_3$ uniquely detect phase-flip at $7^{th}$ qubit. Table. 1 lists all possibility of error types to verify the unique error detection of Steane code. As for the combined bit-phase flip, its syndrome is simply addition of bit and phase flips. For instance, if the combined bit-phase flip occurs at the qubit 7, the outcome string will be 
\begin{equation}
    \left\{1,-1,-1,1,-1,-1 \right\}.
\end{equation}

Table 1: Error correction with Steane code.

Now we tackle the question of a continuous error. Without loss of generality we assume the error, denoted as $E_7$, occurs at the $7^{th}$ qubit. Since noise operator $E_7$ is unitary, it can be decomposed to Pauli operators as
\begin{equation}
E_7 = a_0 I + a_1 X_7 + a_2 X_7 Z_7 + a_3 Z_7,
\label{error}
\end{equation}
where complex parameters satisfy $\sum_{i=0}^{3} \vert a_i \vert^2 =1$. Surprisingly, measurements of observables help to collapse the noise into one of four correctable errors $I$ (no error), $X_7$ (bit-flip), $Z_7$ (phase-flip) and $X_7Z_7$ (combined bit and phase flip) as explained above. Let's take an example where all observables are measured, the process is described as follows

Measure $g_1 = X_1 X_2 X_3 X_4$

Outcome is trivial $+1$ since $\left[ E_7, g_1 \right] =0$. 

Measure $g_2 = X_1 X_3 X_5 X_7$

$X_7Z_7$ and $Z_7$ do not commute with $g_2$ so there are two possibilities: either $+1$ outcome where noise $E_7$ collapses to $a_0 I + a_1 X_7$ with probability of $\vert a_0\vert^2+\vert a_1 \vert^2$ or $-1$ outcome where noise $E_7$ collapses to $a_2 X_7 Z_7 + a_3 Z_7$ with probability of $\vert a_2\vert^2+\vert a_3 \vert^2$.
Proof
We denote the output of Steane encoding state in Fig. \ref{fig} as $\ket{\varphi_S}$. The probability of getting $\pm 1$ outcome reads
\begin{equation}
    p \left(\pm 1 \right) = \bra{\varphi{}_{S}} E_7^\dagger \; \frac{I \pm X_1 X_2 X_3 X_4}{2} \; E_7 \ket{\varphi_S}.
\end{equation}
To simplify the above equation, we should notice that average value of single-qubit Pauli operator for state $\ket{\varphi_S}$ is zero. For example, as mentioned above $X_7 \ket{\varphi_S}$ will be transformed to $\ket{\phi}$ stabilized by $-g_5$
\begin{equation}
     -g_5 \ket{\phi} = \ket{\phi}.
\end{equation}
$\ket{\varphi_S}$ is stabilized by $g_5$ so we have
\begin{equation}
    \begin{aligned}
    - \bra{\varphi }g_5^2 \ket{\phi} &= \left< \varphi \vert \phi \right> \\
    \Rightarrow - \left< \varphi \vert \phi \right> & = \left< \varphi \vert \phi \right> =0. \quad \Box
    \end{aligned}
\end{equation}
With that trick in mind we obtain
\begin{equation}
\begin{aligned}
     p \left(+1 \right) &= \vert a_0 \vert^2 + \vert a_1 \vert^2 \\
     p \left(-1 \right) &= \vert a_2 \vert^2 + \vert a_3 \vert^2 .
\end{aligned}
\end{equation}
As for $-1$ outcome, phase-flip error is revealed. Once we apply the recovery operator $Z_7$, the final state of this step is a superposition of no error $I$ and bit-flip error $X_7$
\begin{equation}
    \left( a_0 I + a_1 X_7 \right) \ket{\varphi_S}.
\end{equation}

Measure $g_3 = X_2 X_3 X_6 X_7$ and $g_4 = Z_1 Z_2 Z_3 Z_4$ 

Outcomes are $+1$ because they all commute with $X_7$.

Measure $g_5 = Z_1 Z_3 Z_5 Z_7$

We argue in the same way with measuring $g_2$: $+1$ outcome where the noise is collapsed to no error $I$ with probability $\vert a_0 \vert^2$ or $-1$ outcome with probability $\vert a_1 \vert^2$ where we detect $X_7$ and recover by applying one more $X_7$.

Therefore, the continuous error is totally detected and corrected by Steane code.

Useful reference: Chapter 10,  Quantum computation and quantum information (Nielsen MA, Chuang I.)