# Theory of Quantum Error Correction for General Noise

## Proof.

Recall the necessary and sufficient conditions for a code $`𝒞`$ to permit correction of the errors in $`𝒥_e`$ : $`𝒞`$ detects the operators in $`𝒥_e^{}𝒥_e`$. This condition is also correct for c-codes with a transmission basis. Since $`𝒥_e^{}𝒥_e𝒥_{2e}`$, the result follows.  

Error Bounds. To make the analysis based on minimum distance and $`e`$-error correction useful, it is necessary to show that $`e`$-error-correcting codes protect information well. We give a quantitative relationship for the worst-case error as a function of time $`t`$.

###### Theorem 2

The error amplitude of information protected in an $`e`$-error-correcting (c-)code is at most $`(\lambda t)^{e+1}/(e+1)!`$.

We defer the proof until after error-correcting codes have been characterized as subsystems. Note that independence from the internal Hamiltonian of the environment implies that even if the latter is subject to arbitrary, adversarial manipulation, the error-correcting code still effectively protects information on a time scale of $`O(1/\lambda )`$.

Existence of Large Codes. A goal of constructing good error-correcting codes is to maximize the dimension of minimum (c-)distance $`d`$ codes. The greedy algorithm for constructing good minimum-distance classical codes works well in the general case. Let $`\{E_1=I,E_2,\mathrm{},E_D\}`$ be a basis of $`𝒥_{d1}`$, with dimension $`D`$, and let $`x`$ denote the least integer $`x`$.

###### Theorem 3

There exist codes of $`S`$ with minimum c-distance $`d`$ of dimension at least $`\frac{N}{D}`$.

## Proof.

Minimum c-distance is equivalent to the existence of an orthonormal basis $`|c_1,\mathrm{},|c_k`$ of the c-code such that, for each operator $`E_l`$ to be detected,

$`c_i|E_l|c_j`$ $`=`$ $`\alpha _{i,l}\delta _{i,j}.`$ (4)   
The proof greedily constructs such a basis. Let $`|c_1`$ be any state of $`S`$. Suppose that $`|c_1,\mathrm{},|c_k`$ have been found, fulfilling (4). Choose $`|c_{k+1}`$ orthogonal to the vectors $`E_i|c_j`$, $`i=1,\mathrm{},D`$, $`j=1,\mathrm{},k`$. Such a state exists provided that $`kD<N`$. The new set of $`|c_i`$ satisfies (4). Upon continuing until the set cannot be extended, a c-code of dimension at least $`\frac{N}{D}`$ is found.  

Our best general construction of good codes for quantum information is based on finding a subcode of a c-code.

###### Theorem 4

There exist minimum distance $`d`$ codes of $`S`$ of dimension at least $`\frac{N}{D}\frac{1}{D+1}`$.

## Proof.

Let $`𝒞`$ be a c-code of $`S`$ of dimension at least $`\frac{N}{D}`$ with basis $`|c_i`$ satisfying (4). Let $`Y`$ be the set of indices of the basis vectors. To construct a large quantum code, we partition $`Y`$ into subsets $`Y_i`$ and seek non-negative coefficients $`\beta _{i,j}`$, satisfying $`_{jY_i}\beta _{i,j}=1`$. Let $`|q_i=_{jY_i}\sqrt{\beta _{i,j}}|c_j`$. Then the orthonormal vectors $`|q_i`$ span the desired code provided

$`q_i|E_l|q_j`$ $`=`$ $`\gamma _l\delta _{ij},i,j,l.`$ (5)   
Compute $`\gamma _{l,i}=_{jY_i}\beta _{i,j}\alpha _{j,l}`$, the $`\alpha _{j,l}`$’s being given in (4). We need the $`\gamma _{l,i}`$ to be independent of $`i`$. This problem can be cast in terms of a convex sets problem. We need to find as many disjoint subsets of the set of vectors $`\stackrel{}{\alpha }_j=\{\alpha _{j,l}\}_l`$ with the property that their convex closures have a common intersection. Since $`𝒥_{d1}`$ is -closed, the $`\stackrel{}{\alpha }_j`$ live in a subspace of real dimension $`D`$. By invoking a generalization of Radon’s Theorem , a necessary condition for the existence of at least $`r`$ such sets is $`r(D+1)DN/D`$. The result follows.  

While the result of Thm. 4 is fully general, the proof does not yield a straightforward constructive method. Also, the lower bound on the existence of good codes is sub-optimal for various systems of interest, including qubits with linear interactions, where the achieved rate is well below the best lower bounds known . According to Thms. 3 and 4, the above bounds for minimum distance $`d`$ codes are found to be less favorable for independent than for collective interactions, both for classical and for quantum information. This reflects the lower level of complexity of the error process generated by collective interactions.

Subsystems. If a system consists of a number of qubits, the obvious subsystems are the qubits. If the system consists of a number of photon modes, each mode is a subsystem. However, in order to use these modes as qubits, one could choose the two polarization states for a single photon in a mode as the computational basis. The relevant system is then the subspace where each mode is occupied by exactly one photon, and it is in this subspace that we can identify the qubit subsystems. In both examples, subsystems appear as factors (in the tensor product sense) of subspaces of a larger state space. To avoid working with explicit bases and states, it is convenient to resort to a general algebraic definition. We shall characterize a subsystem of $`S`$ in terms of a subalgebra of operators acting on $`𝒮`$ together with an irrep of the subalgebra. This is motivated by the following fundamental result from the representation theory of -closed operator algebras .

###### Theorem 5

Let $`𝒜`$ be a -closed algebra of operators on $`𝒮`$, including the identity. Then $`𝒮`$ is isomorphic to a direct sum,

$`𝒮`$ $``$ $`{\displaystyle \underset{i}{}}𝒞_i𝒵_i,`$ (6)   
in such a way that in the representation on the righthandside, $`𝒜=_i\text{Mat}(𝒞_i)I^{(Z_i)}`$ and the commutant of $`𝒜`$ is given by $`Z(𝒜)=_iI^{(C_i)}\text{Mat}(𝒵_i)`$.

Here, $`\text{Mat}()`$ denotes the set of all linear operators from $``$ to itself, while the commutant $`Z(𝒜)`$ is the space of all operators commuting with $`𝒜`$. Formally, each factor $`Z_i`$ $`(C_i)`$ in Thm. 5 defines a subsystem of $`S`$ with associated state space $`𝒵_i`$ $`(𝒞_i)`$. As a result of the theorem, subsystems are naturally definable in terms of either algebras or their commutants.

Noiseless Subsystems. Consider the interaction algebra $`𝒥`$ associated with (1). Since $`𝒥`$ is -closed, the representation of Thm. 5 applies. For each subsystem $`Z_i`$, states in $`𝒵_i`$ are completely immune to the interaction, as the interaction operators only act on the co-factor $`𝒞_i`$. Thus, $`Z_i`$ is a noiseless subsystem i.e., a subsystem where information is intrinsically stabilized against the effects of the noise. As remarked above, a trivial example occurs if we are given two qubits, where only the second one is susceptible to noise. In this case, information in the first qubit is canonically maintained with no need for corrective action. Noiseless (or decoherence-free) subspaces  can be recognized as special cases of the general decomposition (6) for appropriate interaction algebras $`𝒥`$. However, relevant situations can be devised, where noiseless subsystems exist in the absence of noiseless subspaces.

Example. Let us consider three qubits $`A,B,C`$ with collective linear interactions. The interactions are the generators for spatial rotations. As pointed out in , no state of three qubits is invariant under spatial rotations, the minimal implementation of a noiseless subspace requiring $`n=4`$ qubits. However, the state space decomposes into one spin-$`\frac{3}{2}`$ and two spin-$`\frac{1}{2}`$ irreducible subspaces. The two spin-$`\frac{1}{2}`$ components together are representable as the product of two two-state spaces as in Thm. 5, with $`𝒥`$ acting only on the first. Thus the second one is a noiseless subsystem. Another method of finding this subsystem is to observe that the commutant $`Z(𝒥)`$ is non-trivial. In particular, it includes the scalars under spatial rotations,

$`s_1`$ $`=`$ $`\sigma _x^{(A)}\sigma _x^{(B)}+\sigma _y^{(A)}\sigma _y^{(B)}+\sigma _z^{(A)}\sigma _z^{(B)},`$ (7)   
$`s_2`$ $`=`$ $`\sigma _x^{(A)}\sigma _x^{(C)}+\sigma _y^{(A)}\sigma _y^{(C)}+\sigma _z^{(A)}\sigma _z^{(C)},`$ (8)   
which are generating observables for the noiseless subsystem. Equivalently, the latter is seen to support one of the irreps of the algebra generated by the scalars.

Error-correcting Codes as Subsystems. The traditional view of error-correcting codes involves encoding the information and correcting errors after the information carriers are transmitted through a noisy channel. The concept of noiseless subsystem shows that, for the purposes of information maintenance, it is not necessary to correct errors, insofar as they affect components independent of the system where information is stored. In general, we wish to protect the information against all errors in $`𝒥_e`$ for some reasonably large $`e`$. Since a subsystem unaffected by the operators in $`𝒥_e`$ is automatically noiseless, but in most cases of interest noiseless subsystems do not exist, it is necessary to take an active role in maintaining information. Rather than using error correction to restore the overall state of the system after errors happened, we propose to use a quantum operation before the latter occur, in such a way that the net effect of the quantum operation followed by errors in $`𝒥_e`$ assures preservation of the information in a subsystem. A quantum operation is described by a family $`𝒜=\{A_i\}_i`$ of linear operators acting on $`𝒮`$, evolving the system density operator as $`\rho `$ $``$ $`_iA_i\rho A_i^{}`$. The combined action of the quantum operation, followed by errors in $`𝒥_e`$, is represented by the product of an operator $`E𝒥_e`$ and one of the operators $`A_i𝒜`$. Consequently, a state of a noiseless subsystem of the -closed algebra generated by $`𝒥_e𝒜`$ is preserved in this process.

###### Theorem 6

Every $`e`$-error-correcting code arises as a noiseless subsystem of $`𝒥_e𝒜`$ for some $`𝒜`$ with the property that $`I\text{span}(𝒜^{}𝒜)`$. Conversely, every noiseless subsystem of $`𝒥_e𝒜`$ with $`𝒜`$ satisfying the above condition corresponds to an $`e`$-error-correcting code.

## Proof.

The fact that error-correcting codes yield such noiseless subsystems follows from Thm. III.5 of  by letting $`𝒜`$ consist of operators that return the state of the error system to the state $`|(0)`$ (in the notation of ). Conversely, the condition $`I\text{span}(𝒜^{}𝒜)`$ ensures the existence of a quantum operation whose operators are in $`𝒜`$. Thus, the process suggested earlier protects the information against errors in $`𝒥_e`$. Because of the necessity of the conditions for error-correcting codes , there exists an associated $`e`$-error-correcting code in the usual sense.  

As a consequence, noiseless subsystems are infinite-distance quantum error-correcting codes.

Error Analysis. We are now ready to give a proof of Thm. 2 based on viewing error-correcting codes as subsystems protected by an initial quantum operation $`𝒜`$.

## Proof of Thm. 2.

By purifying the environment , we can assume that the environment’s initial state is $`|\psi __B`$. The initial state of the system has the intended state in the subsystem associated with the error-correcting code. Again, by purifying and by adding the reference system to $`S`$, we can assume that the state is given by $`|\varphi _0__S`$. The quantum operation $`𝒜`$ can be assumed to arise from a unitary evolution $`U`$ applied to $`|\varphi _0__S|0__A`$, where $`A`$ is an ancillary system. Let $`|\varphi =U|\varphi _0__S|0__A`$ and consider the subsequent interaction with the environment over time $`t`$. By slicing the interaction time into intervals of duration $`t/n`$, the overall evolution up to time $`t`$ can be written as ($`\mathrm{}=1`$)

$`\underset{n\mathrm{}}{lim}{\displaystyle \underset{k=1}{\overset{n}{}}}\delta U_k^{(S)}\delta U_k^{(B)}|\varphi |\psi __B,`$ (9)   
where $`\delta U_k^{(S)}`$, $`\delta U_k^{(B)}`$ denote the unitary evolutions during the $`k`$’th interval due to $`J`$ and to the environment’s internal Hamiltonian respectively. It suffices to consider a first-order expansion $`\delta U_k^{(S)}=IiJ(t/n)+O((t/n)^2)`$. The elements contributing noise all involve at least $`e+1`$ factors of $`J`$. By distributing some of the sums $`IiJt/n`$ starting at the first time interval, the expression inside the limit can be thought of as a sum over the branches of a binary tree of products of operators associated with the edges and nodes of the tree . The root node is labeled $`\delta U_1^{(B)},`$ and its two edges by $`I`$ and $`iJt/n`$ respectively. The two children are labeled by $`\delta U_2^{(B)}`$, their descendant edges by $`I`$ and $`iJt/n`$ and so on. We choose to terminate a branch at a point where there are $`e+1`$ factors of $`iJt/n`$ on its path and label the leaf with the remaining product of unitary operators. The total error is estimated by summing the error amplitudes associated with the products along each of these terminated branches. A counting argument shows that there are $`\left(\genfrac{}{}{0pt}{}{n}{e+1}\right)`$ such branches. Using $`|CD||C||D|`$ and the fact that unitary operators preserve the amplitude, the error of each such branch is bounded by $`(\lambda t/n)^{e+1}`$. Thus, the error amplitude is at most $`\left(\genfrac{}{}{0pt}{}{n}{e+1}\right)(\lambda t/n)^{e+1}(\lambda t)^{e+1}/(e+1)!`$.  

Markovian Noise. As mentioned above, in many cases involving infinite dimensional environments the estimate of Thm. 2 cannot be used without redefining $`\lambda `$. For instance, when the noise is to a good approximation Markovian, the evolution of the system density operator can be written as $`\rho `$ $``$ $`\rho _t=lim_n\mathrm{}_{t/n}^n(\rho )`$, where the superoperator $`_{t/n}`$ takes the form $`_{t/n}(\rho )=\rho +(t/n)(_iL_i\rho L_i^{}+V\rho +\rho V^{})`$ for a suitable choice of operators $`L_i`$ and $`V`$ . Our techniques apply with $`𝒥_1`$ given by the linear span of $`I`$, these operators and their Hermitian transposes. The bound of Thm. 2 holds provided we replace error amplitude with error probability and redefine $`\lambda `$ as

$`\lambda `$ $`=`$ $`2|V|+|L_1|^2+|L_2|^2+\mathrm{}.`$ (10)   
The need to consider error probability rather than amplitude is due to the statistical nature of Markovian noise.

###### Theorem 7

The error probability of information protected in an $`e`$-error-correcting (c-)code subjected to Markovian noise is bounded by $`(\lambda t)^{e+1}/(e+1)!`$.

## Proof.

Let $`\rho `$ be the state of the system after the protecting quantum operation has been applied, and $`\rho _t=lim_n\mathrm{}_{t/n}^n(\rho )`$. If we write $`\rho _t=\rho _c+\rho _e`$, where $`\rho _c`$ has no error in the subsystem of interest, then the error probability is bounded by $`\text{tr}(\sqrt{\rho _e^{}\rho _e})`$. The product of $`n`$ infinitesimal evolutions can be expanded as in the proof of Thm. 2, but replacing unitary operators with trace-preserving superoperators and omitting the environmental contribution. The non-identity terms in the branches are superoperators of the form $`\rho ^{\prime \prime }`$ $``$ $`(t/n)(_iL_i\rho ^{\prime \prime }L_i^{}+V\rho ^{\prime \prime }+\rho ^{\prime \prime }V^{})`$, whose effect can be bounded by the parameter $`\lambda `$ given in (10). (Use the fact that if we define $`l_1(\rho )=\text{tr}(\sqrt{\rho ^{}\rho })`$, then $`l_1(\rho U)l_1(\rho )|U|`$).  

In the past, error probability has been used in almost all treatments of noise. Therefore, Thm. 7 further connects our formulation of error correction to the usual one.

Discrete Quantum Operations. A picture of the situation involving qubits coupled to independent environments, which is what has been typically addressed by quantum error-correction theory, is that a known, somewhat noisy quantum operation is applied to each qubit. In this case, time does not play an explicit role. Instead, we are given quantum operations $`_i`$, each expressible in the form $`_i(\rho )`$ $`=`$ $`(I+V_i)\rho (I+V_i^{})+L_{i1}\rho L_{i1}^{}+L_{i2}\rho L_{i2}^{}+\mathrm{}`$. The noise operation involves applying each quantum operation to the system in some order. To apply our theory and bounds to this situation, define $`𝒥_1`$ as the span of $`I`$, the operators $`V_i`$, $`L_{ij}`$ and their Hermitian transposes. The noise-strength parameter can be redefined as $`\lambda =\mathrm{max}_i(2|V_i|+|V_i|^2+_j|L_{ij}|^2)`$, so that Thm. 7 applies for $`t=1`$. This gives estimates not far from the standard ones in the case of qubits subject to depolarizing noise .

Time-Dependent Noise. Time-dependent noise can arise from the use of a rotating frame to compensate for internal evolution of the system, or to compensate for time-dependent control actions, such as the ones exploited in decoupling schemes for open quantum systems . To adapt our theory to this situation, it suffices to maximize the expression of $`\lambda `$ over time and choose $`𝒥_1`$ as the span of all first-order operators occurring at various times.

Summary. By suitably incorporating the description of the error generation process within a general algebraic setting, we showed how to reformulate quantum error correction without restricting the statistical properties of the environmental noise. The existence of large codes was established for both classical and quantum information, opening the way to accurate quantum computations in the presence of arbitrary errors. In addition to substantially strengthening the power of quantum error-correction theory, our analysis points to the notion of a noiseless subsystem as an emerging unifying framework for quantum information protection. Full exploitation of the above concept should prove fruitful in the general context of quantum information processing.

Acknowledgments. We thank Asher Peres for the three qubit example of a noiseless subsystem. E. K. and R. L. received support from the Department of Energy, under contract W-7405-ENG-36, and from the NSA. L. V. was supported in part by DARPA/ARO under the QUIC initiative.