Quantum error correction

Arbitrary-precision quantum control of qubit systems is a lofty goal due to the sensitivity of quantum states to environmental influences and technological roadblocks in quantum state manipulation that manifest themselves as errors in a quantum algorithm. Quantum error correcting codes and, in general, fault-tolerant schemes have been invented to guarantee that reliable quantum computation is possible in the presence of noise. The philosophy of quantum error correction is to encode a qubit of information as an entangled state of a many-qubit system in a manner that the encoded information is robust to local errors.

The set of encoded messages as manybody entangled states are called quantum error correcting codes. This page describes how to specify a quantum error correcting code in chflow and perform some basic operations on them.

Defining a quantum error correcting code

The types of quantum error correcting codes that can be handled by chflow include any stabilizer code. A stabilizer code is a (+1) eigenspace of a commuting set of Pauli operators, that form an abelian subgroup of the Pauli group called the stabilizer group. Hence, in order to specify the code, it suffices to specify a generating set for the associated stabilizer group, viz a viz the stabilizer generators. Besides, one can provide a name for the code, by which it can be recalled in future in the chflow interface. A stabilizer code described by n-k mutually commuting n-qubit stabilizer generators, describes a k-dimensional subspace of the Hilbert space, thereby encoding k-logical qubits. The values of n and k must also be specified while describing the code. In addition to these parameters, one can choose (or not) to specify the distance of the stabilizer code, see here for details.

Representations for stabilizer generators

A list of stabilizer generators can be specified in two ways. One, as a string of Pauli operator symbols with I, X, Y, Z denoting the respective Pauli matrices. By a string of Pauli symbols, we mean the tensor product of the corresponding Pauli matrices. Below is a set of 4 stabilizer generators that whose eigenspace encodes one logical qubit.

X Z I Z X
X X Z I Z
Z X X Z I
I Z X X Z

The resulting stabilizer code is commonly known as the 5 qubit code.

Another popular representation of stabilizer generators comes from the mapping from Pauli matrices to binary sequences of two bits, known as the symplectic representation. In chflow a stabilizer generator can be specified in terms of its symplectic representation with the following encoding.

I -> 00
X -> 10
Y -> 11
Z -> 01

A n-qubit Pauli operator P (or tensor product of n Pauli matrices) is represented by a binary sequence uv where u and v are sequences of n bits. This is done in two steps. First, P is expressed in the form A.B where A and B are n-qubit Pauli operators such that A is a tensor product of Pauli operators in {I,X} and B is a tensor product of Pauli operators in {I,Z}. Then, u is derived from A by setting the i-th bit of u to 1 whenever the i-th qubit of A is acted by a Z and 0 otherwise. Likewise, the i-th bit of v is set to 1 if and only if the i-th qubit of A is acted by the Pauli operator X.

As an example, the stabilizer generators of the 5-qubit code are transformed to the rows of the following binary matrix.

1 0 0 0 1 0 1 0 1 0
1 1 0 0 0 0 0 1 0 1
0 1 1 0 0 1 0 0 1 0
0 0 1 1 0 0 1 0 0 1

In chflow the stabilizer generators of a n,k stabilizer code can be provided either as a a set of n-k strings of Pauli operators, each consisting of n characters in {I, X, Y, Z} or as a (n-k) x 2n binary matrix whose rows are the symplectic representations of the stabilizer generators (as in the above example). More examples of such binary matrices to define stabilizer codes can be found here.

Canonical basis for a stabilizer code

The stabilizer group can be used to define subgroups of the Pauli group whose relevance is more apparent in the context of quantum error correction. In addition to specifying the code space, the stabilizer generators are useful in determining whether any given n-qubit state is in the code space or not. This condition is true if and only if the measurement of every stabilizer generator on the corresponding state results in +1. Hence, errors can be detected by measuring the stabilizer generators. The list of all measurement outcomes from the n-k stabilizer generators can be mapped to an binary sequence s whose i-th bit is 1 if and only if the corresponding measurement outcome is -1 and 0 otherwise. s is known as the syndrome. Note that if an error E affects the encoded state, the corresponding syndrome, s(E) has a its i-th bit set to 1 if and only if the i-th stabilizer generator anti commutes with E, i.e, {S_i, E} = 0. Hence, the syndrome gives us non-trivial information on the error.

The best one can deduce from the syndrome s(E) about E is that it must be of the form E = T.N where N commutes with every stabilizer generator and T anti commutes with only those that are indicated in s(E). We can formulate a systematic procedure of constructing T using operators in {T_1, T_2, ..., T_(n-k)} which satisfy the following commutation relations.

[T_i, T_j] = 0 for all 1 <= i, j <= n-k.
[T_i, S_j] = 0 for all 1 <= i, j <= n-k such that i != j.
{T_i, S_j} = 0 for all 1 <= i <= n-k.

The generators {T_1, T_2, ..., T_(n-k)} are often referred to as Pure Errors and they generate an abelian subgroup of the Pauli group. Now, T can be expressed as T = F_1 . F_2 . F_3 ... F_(n-k) where F_i = T_i whenever the i-th bit of s(E) is 1 and I otherwise.

With that said, it is easy to see that the syndrome cannot uniquely specify an error. Consider an operator that commutes with all the stabilizer generators (and hence the entire stabilizer group) but is not a stabilizer. Mathematically, such operators belong to the set N(S)\S where N(S) is the normalizer of the stabilizer subgroup in the Pauli group. Errors in this set cannot be detected, however, they affect the encoded states in a non-trivial manner. The smallest weight of an element in this set is the distance of the stabilizer code.

In order to compute the generators of N(S) given the generators of S, one must make use of two facts. First, every element in N(S) commutes with every element of S. Second, when two Pauli operators A and B commute, their corresponding symplectic vectors u and v are orthogonal with respect to the symplectic inner product (defined in the section above). Consequently, the element of N(S) can be derived by computing the null space of the (n-k) x 2n binary matrix containing the symplectic representation of the stabilizer generators, over the symplectic inner product. The function NullSpace(mat) in src/define/qcode.py achieves this purpose.

Let us investigate the structure of N(S). Clearly, it contains S. Furthermore elements N_1 and N_2 of N(S)\S that are related by a stabilizer, i.e, N_1 = N_2 . S act identically on all the encoded states. Hence, the quotient group N(S)/S describes the set of distinct non-trivial transformations on the encoded states. Representatives of the cosets in N(S)/S are called logical operators. Their name comes from the fact that they can be used to perform logical operations within the encoded subspace of the stabilizer code, such as logical gates. The cosets together must describe any Pauli operation on the encoded space, i.e, they must be isomorphic to the set of k-qubit Pauli operators. Consequently, their generators are denoted by {\bar{X}_{i}, \bar{Z}_{i}}^{k}_{i = 1} with the following commutation relations.

{\bar{X}_{i}, \bar{Z}_{i}} = 0 for all 1 <= i <= k
[\bar{X}_{i}, S_{j}] = 0 for all 1 <= i <= k, 1 <= j <= n - k.
[\bar{Z}_{i}, S_{j}] = 0 for all 1 <= i <= k, 1 <= j <= n - k.
[\bar{X}_{i}, T_{j}] = 0 for all 1 <= i <= k, 1 <= j <= n - k.
[\bar{Z}_{i}, T_{j}] = 0 for all 1 <= i <= k, 1 <= j <= n - k.

Note: the last two commutation relations are not mandatory, however, it simplifies a lot of calculations.

In order to derive the logical generators from those of the normalizer N(S), we can use the symplectic gram schmidt orthogonalization procedure mentioned in this work. The function ComputeLogicals(...) in src/define/qcode.py achieves this purpose. It only remains to determine the pure error generators which can be realized from the observation that the i-th pure error commutes with all but the i-th stabilizer generator. Hence is lies in the normalizer of the set of logical operators and stabilizer generators except for the i-th one. We can reuse the algorithms for computing N(S) to arrive at the pure error generators. For more details, see the function ComputePureErrors(...) in src/define/qcode.py.

Complete description of a stabilizer code

Hence, the complete definition of a stabilizer code should be provided in the form of a text file that is placed in codes/. Any lines in the file that begin with # are ignored when read by chflow. Any information about the code is provided in a new line that follows a keyword in the same or the previous line. The keywords should be one of {name, nkd, stabilizer, logical, pureerror}. The string in the new line following "name" must contain information about n, k, and d for the quantum code. If the real value of d is not known, it can be set to 1. The format of this line is: nkd <value of n>,<value of k>,<value of d>. The stabilizer generators must be provided in the n-k lines following a line with the keyword stabilizer. These lines can either contain the stabilizer generators as Pauli strings or symplectic vectors. Optionally, if one wishes to specify the generators for the logical operators and/or the pure errors (and hence the complete canonical basis for the stabilizer code), these must be formatted in the same manner as the stabilizer generators and follow the lines containing the keywords logical and pureerror respectively. The following is an example to define the 5-qubit code.

# This file defines the Steane [[5,1,3]] code, in http://www.codetables.de/QECC.php?q=4&n=5&k=1.
name
FiveQubit 5,1,3
stabilizer
Z X I X Z
Z Z X I X
X Z Z X I
I X Z Z X

The above file is available in code/5qc.txt. Finally, this code can be loaded in chflow using the qcode command as below. Other useful commands concerning the loaded quantum code are

1. qcbasis that prints the canonical basis for stabilizer, logical and pure error generators along with the commutation relations.
2. qcminw that prepares a syndrome look up table for a minimum weight decoder.
3. qcprint that prints all properties of a quantum code.

poulingroup@Andrew-Ferriss-iMac:chflow$./chflow.sh 
>> qcode 5qc
>> qcbasis

N = 5, K = 1
Stabilizer generators Z Z X I X           
                     Y I Y X X           
                     Y X X Y I           
                     Z X I X Z           
Logical generators   X X X X X           
                     Z I X X I           
Pure error generators I X I I I           
                     I I X I I           
                     I I I X I           
                     I I I I X           
Commutation relations
              S_0     S_1     S_2     S_3     L_0     L_1     T_0     T_1     T_2     T_3 
S_0           0       0       0       0       0       0       1       0       0       0 
S_1           0       0       0       0       0       0       0       1       0       0 
S_2           0       0       0       0       0       0       0       0       1       0 
S_3           0       0       0       0       0       0       0       0       0       1 
L_0           0       0       0       0       0       1       0       0       0       0 
L_1           0       0       0       0       1       0       0       0       0       0 
T_0           1       0       0       0       0       0       0       0       0       0 
T_1           0       1       0       0       0       0       0       0       0       0 
T_2           0       0       1       0       0       0       0       0       0       0 
T_3           0       0       0       1       0       0       0       0       0       0 

>> qcminw
Preparing syndrome lookup table.
>> qcprint

Name                           FiveQubit                     
[[N, K, D]]                    [[5, 1, 3]]                   
Stabilizer generators          Z Z X I X                     
                               Y I Y X X                     
                               Y X X Y I                     
                               Z X I X Z                     
Logical generators             X X X X X                     
                               Z I X X I                     
Pure error generators          I X I I I                     
                               I I X I I                     
                               I I I X I                     
                               I I I I X                     


Look up table                  s     L                       
                               0     I                       
                               1     I                       
                               2     I                       
                               3     Z                       
                               4     I                       
                               5     Y                       
                               6     Z                       
                               7     Y                       
                               8     I                       
                               9     Y                       
                               10    Y                       
                               11    Z                       
                               12    Z                       
                               13    Z                       
                               14    Y                       
                               15    X                       
xxxxx
>> 

Decoding stabilizer codes

Hence any Pauli error (operator) E can be expressed as E = T.L.S where T is a pure error, L is a logical operator and S is a stabilizer. Furthermore, T is completely fixed by s(E). Decoding is the process of determining a logical operator L* such that E.L* is a stabilizer. The optimal method of computing L* is known as maximum likelihood decoding (sometimes, soft decoding) and a suboptimal (and often efficient) method is referred to as minimum weight decoding or hard decoding. See this article for more details.

The essence of maximum likelihood decoding is to identify L* with the most likely coset of errors. That is, to compute a logical operator L* whose probability P(L*), given by the sum of probabilities of all errors P(L*) = \sum_{S}P(T.L*.S) over all stabilizers, is the maximum amongst other logical operators. The assignment of probability to an error is provided by the description of the underlying physical noise model.

On the other hand, minimum weight decoding attempts to compute the element N* of N(S) such that E = T.N* has the largest probability. There is indeed a conceptual difference between the two strategies that is discussed at length in this article. Often, the most probable error also happens to be the one with the least weight, hence the name minimum weight decoding. Notice that for this decoder, the list of N* for every syndrome can be precomputed. This list is often called a look up table. In chflow this lookup table can be computed using the qcminw command.

In a simulation of quantum error correction, the type of decoder to be used can be selected by setting the decoder flag appropriately in the submission input file. The value 0 to decoder applies a soft decoder and 1 applies a hard decoder.