Received October 14th, 2021.
Classical error-correction is the process by which data is protected from being corrupted by noise. In its simplest form we wish to protect a sequence of zeros and ones which are either being stored or transmitted. A repetition code gives a simple protection against a bit flip error in which a 0 flips to a 1 and vice-versa. To employ this code, instead of sending a 0 we send three zeros, 000, and instead of a 1 we send three ones, 111. Thus, to send the message 00110 we would send 000000111111000. On receipt, we make a majority decision on each block of three bits. In other words, if a block of three bits is 000, 001, 010 or 100 then, since the majority of the bits are zero, we suppose that 000 was sent and decode as 0. In this way, the sequence 001000110111001 is decoded as 00110. Even though three bit flips occurred we still managed to recover the initial data. Thus, we have seen a simple way to recover our data as long as no more than one in every sequence of three bits is flipped. Unfortunately we have to send three bits for every one bit of information. If we have a particularly noisy channel then we must send even more bits per bit of information. One can do better by using more sophisticated codes. The Hamming code encodes four bits onto seven bits and is able to correct one bit flip in every sequence of seven bits. Note that the rate of the repetition code above was 1/3 whereas the
Hamming code is 4/7 which is a vast improvement. Finding codes with high rate which are robust enough to allow us to detect and correct errors is a central problem of classical error-correction.
Quantum error-correction is the process by which a quantum state is protected from being corrupted by noise. Noise is a significant problem in quantum computation since, by their very nature, quantum states are unstable and liable to interference from the surrounding environment. A quantum state is usually denoted by |ψ〉, a column vector of the complex vector space 
. The parameter n is the number of quantum particles in the system we are considering. If we have an 80 qubit quantum computer then n = 80. The reason we have 
is that we are assuming the individual quantum particles will be in one of two states, usually denoted by |0〉 and |1〉, upon measurement. This measurement may be simply observation. The |0〉 and |1〉 are column vectors of and form an orthonormal basis of this vector space. A particle exhibiting quantum properties can be in a superposition of these states. Thus, a single qubit can be in a
state
|ψ〉 = a|0〉 + b|1〉 ∈
For example, a photon, after passing through a beam splitter, maybe in the state 1/√2(|0〉 + |1〉), where |0〉 corresponds to the horizontal direction and |1〉 to the vertical direction. Upon observation, the particle will be in |0〉 or |1〉. One interpretation of the state |ψ〉 is that it will be in |0〉 with a probability aā and |1〉 with a probability b¯b. Here, z¯ is the complex conjugate of the complex number z. Since probabilities must sum to 1, we have that aā + b¯b = 1. Thus, the quantum state of a single particle is described by a unit vector in and more generally the quantum state of a system of n particles is described by a unit vector in . We generally use the orthonormal basis
for the vector space .
A more surprising property than superposition is that quantum particles can become entangled. Consider the state of a system of two quantum particles
If the first particle is observed to be in state |0〉 then second particle will necessarily be in state |0〉, since the coefficient of |01〉 is zero and thus there is no chance that the second particle will be found in state |1〉. That is, the particles are entangled. Entanglement is a very useful property; quantum error-correction relies on entanglement.
As in classical error-correction, where we encode k bits of data with n bits, one encodes k qubits of information onto n qubits. The image of this map is a k-dimensional subspace Q of which is our quantum error-correcting code. Changes to the state |ψ〉 of the quantum system are given by unitary linear transformations. Consider, for the moment, just one particle. The linear transformations of are given by 2 × 2 matrices, which as a vector space is 4-dimensional. Thus, an error in one particle is a unitary linear transformation which is a linear combination of 4 linearly independent matrices. A convenient basis for this space of matrices is the set of Pauli matrices,
One major theorem of quantum error-correction states that if one can correct a set ε of errors then one can correct all errors in the span of matrices of ε, [1, Theorem 10.2].
For any |ψ〉, we denote by 〈ψ| the corresponding row vector whose coordinates have been conjugated. Thus, 〈φ|ψ〉 is the standard inner product on the complex space. The other major theorem of quantum error-correction tells us precisely the property that Q should have so that there exists a recovery map that
allows us to recover |ψ〉 ∈ Q, after the noisy error operator has been applied to |ψ〉. To be able to correct all errors in a set ε, and therefore all linear combinations of errors in ε, it suffices that
(1)
for any errors Ei , Ej ∈ ε and for all |ψ〉, |φ〉 ∈ Q.
The essential observation here is that orthogonal states of Q remain orthogonal after the errors are applied to them.
What kind of errors are we trying to correct? In classical errorcorrection we try to correct small weight errors, i.e. errors which have a small number of bit flips. The same is true of quantum errors. The Pauli operators are of the form
where σ〉 ∈ {1, X, Y, Z}. We typically expect ε to contain all tensor products where most of the σi are the 2×2 identity matrix 1 and just a few are one of the other Pauli matrices.
How do we find a quantum error-correcting code Q? Most known constructions are stabiliser codes, so named because Q is stabilised by a large set S of Pauli operators. The set S is chosen to be an abelian subgroup of the multiplicative group of Pauli operators. Observe that since Y = iXZ and the Pauli matrices
either commute or anti-commute, the set of Pauli operators becomes a multiplicative group if we allow ourselves to scale by ±1 and ±i. The code
Now we can check that we can correct all errors E that are not in the centraliser of S. Since E is not in the centraliser of S, there is an M ∈ S such that EM = cME, c ≠ 1. Then, for all |ψ〉, |φ〉 ∈ Q,
from which it follows that 〈ψ|E|φ〉 = 0, Thus, the condition (1) is satisfied for all E†i Ej . Therefore, we only need find abelian subgroups S for which the centraliser of S has no small weight Pauli operators.
Let us summarise the quantum error-correction process. We store quantum information on k qubits on a state |ψ〉 which is a vector in a k-dimensional error-correcting code Q. We have a recovery map which will map E|ψ〉 to |ψ〉 for any linear combination of small weight Pauli operators E. We will wish to process the information, that is apply some unitary transformation to the state |ψ〉. This must be done fault-tolerantly. That is, we must apply logic gates designed according to Q, so that the probability that a large weight error occurs is arbitrarily small. The design of fault tolerant logic gates is another interesting aspect of quantum error-correction. Finally, after the computation is complete, we measure the quantum state to learn the result of the computation. Details of the known quantum algorithms can be found in Chapters 5 and 6 of [1]. The design of quantum algorithms is yet another interesting branch of quantum computation. For more details on this and all of the above see [1].
References
[1] Michael Nielsen and Isaac Chuang, Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press, 2011.