Basic theory of quantum error correction

 

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

 

 

 

 

1) Encoding into higher dimensional space

In QEC, one needs to encode information into a higher dimensional Hilbert space, which can be a system of multiple qubits (like conventional repetition codes, Shor's code, Steane's code,...) or a $d$-level system, so-called qudit $\bracket{d>2}$. Here we discuss the later system, encoding a qubit into a qudit.
Suppose the error operators are generalized Pauli $X$ and $Z$ whose actions on qudit $\ket{j}$ could be defined by \begin{equation}
\begin{aligned}
    X \ket{j} &:= \ket{j+1   \pmod d }, \\
    Z \ket{j} &:= \omega^j \ket{j},
\end{aligned}
\label{generalize pauli}
\end{equation}
with $\omega = \exp \left( 2 \pi i /d\right)$ being the $d$-th root of unity. Note that $X$ and $Z$ satisfy
\begin{equation}
    Z X = \omega X Z,
\label{commutation}
\end{equation}
For $d=2$, Eq. (\ref{commutation}) returns to the familiar anti-commutation relation of 2D Pauli operators $\sigma_x$ and $\sigma_z$.
Demonstrate a code that can protect the qubit against the above errors.

Figure 1: QEC process for generalized $X$ error. Here $\mathcal{E}_X$ signifies the noise operation.

We first examine $X$ noise. As we have 2 possibilities of no error and error occurring, together with qubit state's dimension being 2, the required dimension of qudit is therefore $d =4$. 

Encoding: The physical qubit may be encoded as follows
\begin{equation}
\begin{aligned}
    &\ket{0} \rightarrow \ket{0}, \quad \ket{1} \rightarrow \ket{2}, \\
    &\ket{\psi}_X = a \ket{0} + b \ket{2}.
\end{aligned}
\end{equation}
Error detection: It is straightforward to verify that the codeword $\ket{\psi}_X$ is the $+1$ eigenstate of $Z^2$
\begin{equation}
    Z^2 \ket{\psi}_X =  \ket{\psi}_X, 
\end{equation}
and error operator $X$ anti-commutes with $Z^2$ so the erroneous state is the $-1$ one by 
\begin{equation}
    Z^2  X \ket{\psi}_X  = - X \ket{\psi}_X.
\end{equation}
Therefore, the error can be detected via measuring observable $Z^2$ by using an ancillary qubit as depicted in Fig. 1.
Recovery: If the error syndrome outcome is $-1$, we simply apply $X^\dagger$ to recover the noise-free state.

The generalized Pauli $Z$ error can be corrected in the same manner as we take Fourier-transform the logical qubit by 
\begin{equation}
\begin{aligned}
    &\ket{0} \rightarrow \frac{1}{2} \left(\ket{0}+ \ket{1} + \ket{2} + \ket{3} \right), \quad \ket{1} \rightarrow \frac{1}{2} \left(\ket{0} - \ket{1} + \ket{2} - \ket{3} \right) ,\\
    &\ket{\psi}_Z = \frac{a+b}{2} \left(\ket{0} + \ket{2} \right) + \frac{a-b}{2} \left(\ket{1} + \ket{3} \right).
\end{aligned}
\end{equation}
In this code, the roles of $Z$ and $X$ are interchanged: $X^2$ becomes the error-detection observable while $Z^\dagger$ is the recovery operator.

Figure 2: QEC process for generalized $Z$ error.

Figure 3: Concatenation of $X$ and $Z$ codes.

Similar to Shor code, we hierarchically add $Z$ code to $X$ code to fight against both noises: 2 levels of qubit state are first encoded to qudits $\ket{0}$ and $\ket{4}$ and then Fourier transformed by
\begin{equation}
\begin{aligned}
    &\ket{0} \rightarrow \ket{0} \xrightarrow{FT} \frac{1}{2} \left(\ket{0}+ \ket{2} + \ket{4} + \ket{6} \right), \quad \ket{1} \rightarrow \ket{4} \xrightarrow{FT} \frac{1}{2} \left(\ket{0} - \ket{2} + \ket{4} - \ket{6} \right) ,\\
    &\ket{\psi}_L = \frac{a+b}{2} \left(\ket{0} + \ket{4} \right) + \frac{a-b}{2} \left(\ket{2} + \ket{6} \right).
\end{aligned}
\end{equation}
It is easy to verify that $\ket{\psi}_L$ is the mutual $+1$ eigenstate of $X^4$ and $Z^4$. We also have the following anti-commuting identities  
\begin{equation}
\begin{aligned}
    Z X^4 &= \exp \left( \frac{2 \pi i}{8} \right) ^4 X^4 Z = - X^4 Z, \\
    Z^4 X &= \exp \left( \frac{2 \pi i}{8} \right) ^4 Z^4 X = - Z^4 X.
\end{aligned}
\end{equation}
We argue in the same way with problem (a), where $-1$ outcomes of measuring observables $X^4$ and $Z^4$ are signs of $Z$ and $X$ errors.

2) Discretization of errors

The key feature of quantum error correction is the ability to correct a continuum of errors. This feature can be proven via the quantum error-correction condition. 
QEC condition: Let $\mathcal{E} = \left\{ E_i \; \vert \; i = 1,\ldots m \right\}$ and $\mathcal{R} = \left\{ \mathcal{R}_j \; \vert \; j = 1,\ldots n \right\}$ respectively be an error operation and a recovery operator. Prove that the necessary and sufficient condition for $\mathcal{E}$ being correctable by $\mathcal{R}$ is 
\begin{equation}
    R_j E_i = A_{ji} \mathbf{I},
\end{equation}
where $A_{ij}$ is a complex $n \times m $ matrix. 
Discretization of error: Prove that error operation $\mathcal{F}$ whose element operations are linear combinations of $E_i$'s by 
\begin{equation}
    F_k = \sum_i^m B_{ik} E_{i}  
\end{equation}
can also be corrected by $\mathcal{R}$. Which underlying property does allow $\mathcal{R}$ to have such ability?
Solution
Necessity: Given that the error $\mathcal{E}$ is corrected by a trace-preserving recovery operator $\mathcal{R}$, we have
\begin{equation}
    \rho = \mathcal{R} \left( \frac{\mathcal{E \left( \rho \right)}}{\tr \left(\mathcal{E} \left( \rho \right) \right)} \right), 
    \label{definitionofrecovery}
\end{equation}
where $\rho = \ket{\psi} \bra{\psi}$  is the density operator of the encoded state. We expand then take traces of both sides of Eq. (\ref{definitionofrecovery}) 
\begin{equation}
\begin{aligned}
    1 &= \frac{1}{\tr \left(\mathcal{E} \left( \rho \right) \right)} \sum_{i j} \bra{\psi} R_j E_i \rho E_i^\dagger R_j^\dagger \ket{\psi}\\
    &= \frac{1}{\tr \left(\mathcal{E} \left( \rho \right) \right)} \sum_{i j} \bra{\psi} R_j E_i \ket{\psi} \bra{\psi} E_i^\dagger R_j^\dagger \ket{\psi}\\
    \Leftrightarrow \tr \left(\mathcal{E} \left( \rho \right) \right)  &=   \sum_{i j} \vert \bra{\psi} R_j E_i \ket{\psi} \vert^2.
\end{aligned}
\label{trace}
\end{equation}
In the next step, we will prove that the codeword $\ket{\psi}$ is eigenstate of operator $R_jE_i$ corresponding to eigenvalue of $ \bra{\psi} R_j E_i \ket{\psi} $. We first examine 
\begin{equation}
\begin{aligned}
\vert \left( R_jE_i -  \bra{\psi} R_j E_i \ket{\psi}  \right) \ket{\psi} \vert^2 &= \bra{\psi} E_i^\dagger R_j^\dagger R_j E_i \ket{\psi}  - \vert \bra{\psi} R_j E_i \ket{\psi} \vert^2,
\end{aligned}
\label{4}
\end{equation}
then take the summation all over indices $i$ and $j$ , the right-handed side equation equals to
\begin{equation}
\begin{aligned}
&\sum_i \bra{\psi} E_i^\dagger \underbrace{\sum_j R_j^\dagger R_j}_{I} E_i \ket{\psi}  - \underbrace{\sum_{ij} \vert \bra{\psi} R_j E_i \ket{\psi} \vert^2}_{\tr \left(\mathcal{E} \left( \rho \right) \right)}\\
= &\sum_i \bra{\psi} E_i^\dagger  E_i \ket{\psi}  - \tr \left(\mathcal{E} \left( \rho \right) \right) = 0.
\end{aligned}
\end{equation}
The left-handed side of Eq. (\ref{4}) therefore vanishes, which implies 
\begin{equation}
    R_j E_i \ket{\psi} = \bra{\psi} R_j E_i \ket{\psi} \ket{\psi}.
\end{equation}
The above equality holds for all codewords $\ket{\psi}$ and $R_j E_i$s are linear operations over Hilbert space, therefore the eigenvalue $\bra{\psi} R_j E_i \ket{\psi}$ must be a complex constant, say $A_{ji}$. Hence, in the codeword space, $R_j E_i$ is proportional to identity operator by  
\begin{equation}
    R_j E_i = A_{ji} \mathbf{I}.
\label{condition}
\end{equation}
Sufficiency: Given that Eq. (\ref{condition}) is satisfied, substituting to Eq. (\ref{trace}) we obtain 
\begin{equation}
    \tr \left( \mathcal{E} \rho \right) = \sum_{ji} A_{ji} A^*_{ij} = \sum_{ji} \vert A_{ji} \vert^2.
\end{equation}
We then verify whether the effect of $\mathcal{R} \circ \mathcal{E}$ would recover the noise-free codeword 
\begin{equation}
\begin{aligned}
\mathcal{R} \left( \frac{\mathcal{E} \left( \rho \right)}{\tr \left( \mathcal{E} \rho \right) } \right) &=  \sum_{ji} \frac{R_j E_i \rho E_i^\dagger R_j^\dagger}{\tr \left( \mathcal{E} \left( \rho\right) \right)} \\
&= \sum_{ji} \frac{ \vert A_{ji} \vert^2 \rho }{\tr \left( \mathcal{E} \left( \rho \right) \right)} \\
&= \rho \quad \Box
\end{aligned}
\end{equation}
We have completely proven the condition of QEC.
It is straightforward to compute the composition $\mathcal{R} \circ \mathcal{F}$
\begin{equation}
\begin{aligned}
    R_j F_k &=  \sum_i B_{ik} R_j E_{i} =  \sum_i B_{ik} A_{ji} \mathbf{I} \\
    &=\left( A B \right)_{jk} \mathbf{I}.
\end{aligned}
\end{equation}
Multiplication of $A$ and $B$ is also a complex matrix, therefore error operation $\mathcal{F}$ is correctable with $\mathcal{R}$.
The underlying property for such ability of $\mathcal{R}$ is quantum parallelism. As noise operator $F_k$ can be expanded in terms of $E_i$'s, the recovery process is written as
\begin{equation}
    \sum_j R_j F_k \rho F_k^\dagger R_j^\dagger = \sum_{ji} \vert B_{ik} \vert^2 R_j \left( E_j \rho E_j^\dagger \right) R_j^\dagger.
\end{equation}
Quantum parallelism allows $\mathcal{R}$ to correct all components $\left( E_j \rho E_j^\dagger \right)$'s simultaneously and hence $\mathcal{F}$.

3) An example of discretization

Take the code described in problem (a) as an example to illustrate how QEC discretizes errors. Suppose that the qudit is subjected to an arbitrary noise channel by 
\begin{equation}
    E =  a_0 I + a_1 X + a_2 XZ + a_3 Z ,
\end{equation}
where complex parameters satisfy $\sum_{i=0}^{3} \vert a_i \vert^2=1$. Prove that by measuring error syndromes, the superposition will be collapsed into one of four error possibilities with corresponding probability of $\vert a_i \vert^2$, and thus the error is perfectly corrected.
Solution
One should notice that measuring error syndromes $X^4$ and $Z^4$ are identical to phase estimating them, where outcomes of ancillary qubits being $0$ and $1$ respectively correspond to phase $0$ and $\pi$. 
We consider to measure $X^4$ first. The erroneous state is a superposition of $X^4$ operator's $\pm 1$ eigenvectors 
\begin{equation}
    E \ket{\psi}_L = \underbrace{\bracket{a_0 I + a_1 X} \ket{\psi}_L}_{+1 \text{ eigenvector}} + \underbrace{\bracket{a_2 XZ + a_3 Z} \ket{\psi}_L}_{-1 \text{ eigenvector}}.
\end{equation}
As explained in the phase estimation note, this state will collapse to either $\bracket{a_0 I + a_1 X} \ket{\psi}_L$ or $\bracket{a_2 XZ + a_3 Z} \ket{\psi}_L$, while the estimated phases correspondingly reveal 'no $Z$ error' or '$Z$ error'.
After error $Z$ being corrected, the resultant state is a superposition of 'no $X$ error' and '$X$ error'
\begin{equation}
    \bracket{a_i I + a_j X} \ket{\psi}_L \quad \bracket{i = 0,3 \; \vert \; j = 1,2},
\end{equation}
and measuring (or phase estimating) $Z^4$ will detect the error and collapse the state with corresponding probability $\vert a_i \vert^2$. 
The reversed order of measuring error syndromes ($Z^4$ then $X^4$) doesn't change the obtained result.

 

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