text:
# Permutationally Invariant Codes for Quantum Error Correction

## 1 Introduction

Quantum error correction is now well-developed in the case of those stabilizer codes , which arise as subspaces stabilized by Abelian subgroups of the Pauli group. These codes, also known as “additive codes,” can be regarded as an extension of classical binary codes over $`Z_2`$ to codes over $`GF(4)`$ which satisfy an additional orthogonality condition. They generalize the classical notion of distance and thus seem best suited to situations in which all one-bit errors are equally likely and the noise is uncorrelated.

There are other approaches to fault tolerant computation which use structures which are resistant to decoherence, e.g., topological quantum computation and decoherence free (DF) subspaces or subsystems. (See  and  respectively for further discussion and references.) Some physical implementations may also be designed to protect against certain types of errors. Much of the current analysis is based on simple models using independent errors. In more realistic models some types of correlated errors may be more probable than arbitrary two-bit errors (and possibly even than certain one-bit errors). Hybrid approaches to fault tolerance which combine resiliency (either through encoding or hardware design) with error correction may require codes with properties different from those stabilized by Abelian subgroups of the Pauli group.

It is now known  that other types of quantum codes, often called “non-additive,” exist. Although some attempts  have been made to develop classes of non-additive codes, much of this work, e.g., , has been for non-binary codes. In this paper we consider a natural generalization of stabilizer codes to binary codes associated with the action of non-Abelian groups. We concentrate our attention on the symmetric group as a case study, and call a code on which the symmetric group acts trivially permutationally invariant. We will be particularly interested in the use of higher dimensional representations for the correction of two-bit errors, and the ways in which the degeneracy associated with permutational invariance of code words allows the correction of more two-bit errors than would be expected by simple dimensional arguments.

We find a number of new codes. In particular, we give two new 7-bit codes which are impervious to exchange and can correct all one-bit errors together with some rather special two-bit errors. We show that the classical 5-bit repetition code can correct more two-bit quantum errors than those associated with a single type of one-bit error. We show that there is a large family of permutationally invariant 9-bit codes in addition to the simple one found in . Unfortunately, none of these 9-bit codes is as powerful for two-bit error correction as one might expect.

Although the discovery of new codes is always of interest, we emphasize that our primary goal is to study permutationally invariant codes as examples of codes obtained from the action of a non-Abelian group. These non-Abelian groups will, typically, be more general than subgroups of the Pauli group.

It is worth pointing out some significant differences between our approach and the “Clifford codes” associated with “nice error bases” as proposed by Knill  and developed by Klappenecker and Rötteler . Their approach, which considers generalizations of the Pauli group for $`d>2`$, yields non-stabilizer codes only for $`d4`$; we obtain new non-stabilizer codes for $`d=2`$. (Although our approach could, in principle, be applied for any $`d`$, we study only $`d=2`$.) In the KKR approach, the code is associated with a normal subgroup $`N`$ of an error group, but need not come from bases for the trivial representation of $`N`$. We retain the requirement that a code subspace is spanned by bases for the trivial representation of a group, but the non-Abelian group defining our code need not be associated with an error group in the sense of Knill . From a formal point of view, our group and error sets reside in an operator algebra associated with the usual Pauli group, but we do not use this structure.

It was recognized earlier , in the context of DF subspaces, that quantum error correcting codes can be obtained as stabilizers for non-Abelian groups. However, the use of higher dimensional irreducible representations for error correction was not explored. Moreover, the original philosophy underlying the DF approach to fault tolerant quantum computation, namely, to avoid anything which might perturb the system out of the stable subspace, is antithetical to active error correction. In  the use of encoding to facilitate universal computation, rather than error correction, was introduced. Another important development was the generalization of DF subspaces to DF subsystems , in which the code itself can transform as a higher dimensional representation. The notion of stabilizer was then modified in  to encompass DF subsystems as well. There is now an extensive literature on various aspects of both DF subspaces and systems, including proposals for hybridization of DF methods with active error correction, and scenarios in which DF encoding can replace active error correction. We refer the reader to  for references and further discussion.

Although motivated by the expected utility of codes capable of correcting specific set of correlated errors, we do not present a physical model leading to such sets. We deal only with construction of codes, leaving their application within a full-fledged scheme for fault tolerance for further investigation.

The rest of this paper is organized as follows. In the next section, we outline the basic set-up and notation we will use. We describe different classes of conditions associated with one-bit errors in Section 3 and analyze them in Section 4. In Section 5, we consider two-bit error correction. In Section 6 we first consider some explicit examples of codes for $`n=5,7`$ or $`9`$; we then show that none of the 9-bit codes can correct all double errors of one type.

## 2 Preliminaries

### 2.1 Stabilizers and error sets

In the general situation, we have a set of errors $`=\{e_1,e_2\mathrm{}e_M\}`$ which we want to correct. We will also have a unitary group $`𝒢`$ which acts on the vector space $`𝐂^{2^n}`$. The elements of both $``$ and $`𝒢`$ will be linear operators which act on $`𝐂^{2^n}`$. Typically, these will be non-trivial linear combinations of elements of the Pauli group, rather than simply tensor products of Pauli matrices. In particular, we can consider $`S_n`$ as the group generated by the exchange operators $`E_{rs}`$ which can be written as

$`E_{rs}={\displaystyle \frac{1}{2}}\left[II+X_rX_s+Y_rY_s+Z_rZ_s\right]`$ (1)
where $`X_k,Y_k,Z_k`$ denote the action of the $`\sigma _x,\sigma _y`$ and $`\sigma _z`$ operators on bit $`k`$. Note that the set $`\{E_{1s}:s=2\mathrm{}n\}`$ suffices to generate the group $`S_n`$.

Since $`𝐂^{2^n}`$ is invariant under the action of $`𝒢`$, it can be decomposed into invariant subspaces corresponding to irreducible representations of $`𝒢`$. As is well-known , those subspaces corresponding to inequivalent representations are orthogonal, and those for equivalent representations can be chosen orthogonal. We want to exploit the freedom in the latter to construct codes with particular properties, and use the additional orthogonality from inequivalent representations for error correction.

Now suppose there is a subspace $`T`$ which is stabilized by $`𝒢`$, in the sense $`g|w=|w`$ for all $`g𝒢`$ and all $`|wT`$. Consider a subset of errors $`^{}`$ which is invariant under $`𝒢`$ in the sense $`ge_pg^1^{}`$ for $`e_p^{}`$. Then the space $`^{}(T)`$ spanned by $`\{e_p|w:e_p^{},|wT\}`$ is also invariant under $`𝒢`$ since

$`ge_p|w=(ge_pg^1)g|w=e_q|w.`$ (2)
Hence the space $`^{}(T)`$ can be decomposed into an orthogonal sum corresponding to irreducible representations of $`𝒢`$. Since the span of $`^{}`$ itself is invariant under $`𝒢`$, it too can be decomposed into a sum of irreducible subspaces. In fact, one can regard the two spaces $`^{}(T)`$ and span$`\{^{}\}`$ as being decomposed in parallel into orthogonal sums corresponding to irreducible representations of $`𝒢`$.

For example, the set of single bit flips $`_X^{}=\{X_1,X_2,\mathrm{}X_n\}`$ is invariant under $`S_n`$. In fact, its span is isomorphic to the standard $`n`$-dimensional representation of $`S_n`$, which decomposes into the sum of the trivial representation, spanned by $`_rX_r`$, and the $`(n1)`$-dimensional irreducible representation, spanned by $`X_1X_2,\mathrm{},X_1X_n`$. Similar considerations hold for the errors $`\{Y_1,\mathrm{}Y_n\}`$, and $`\{Z_1,\mathrm{}Z_n\}`$

The resulting linear combinations of errors $`X_pX_q`$ may not be invertible. However, this poses no problems for error correction because we will only need to “invert” when a measurement shows we are in $`(X_pX_q)T`$ which is orthogonal to the null space of $`(X_pX_q)`$.

In view of their role as bases for the trivial representation, it is useful to define the average errors $`\overline{X},\overline{Y},\overline{Z}`$ as

$`\overline{X}={\displaystyle \frac{1}{n}}{\displaystyle \underset{k=1}{\overset{n}{}}}X_k\overline{Y}={\displaystyle \frac{1}{n}}{\displaystyle \underset{k=1}{\overset{n}{}}}Y_k\overline{Z}={\displaystyle \frac{1}{n}}{\displaystyle \underset{k=1}{\overset{n}{}}}Z_k`$ (3)
Note that $`X_rX_s=(X_1X_s)(X_1X_r)`$, and recall that a code that can correct errors in a set $``$ can also correct any complex linear combination of these errors. Thus, the error sets

$``$ $`=`$ $`\{I,X_k,Y_k,Z_k,k=1\mathrm{}n\},\text{and}`$
$``$ $`=`$ $`\{I,\overline{X},\overline{Y},\overline{Z},X_1X_k,Y_1Y_k,Z_1Z_k,k=2\mathrm{}n\}`$ (4)
are equivalent.

### 2.2 Notation

The $`2^n`$dimensional complex vector space $`𝐂^{2^n}`$ has an orthonormal basis $`\{|v=|v_1,v_2\mathrm{}v_n|\}`$ indexed by binary $`n`$-tuples $`v=(v_1,v_2\mathrm{}v_n)(𝐙_2)^n`$. If an orthonormal basis $`|0,|1`$ for $`𝐂^2`$ is fixed, this is simply the basis of tensor products of the form $`|v_1|v_2\mathrm{}|v_n`$ with each $`v_i𝐙_2`$. The symmetric group $`S_n`$ acts on $`𝐂^{2^n}`$ via a natural action on these basis vectors; if $`𝒫`$ takes $`(1\mathrm{}n)(i_1\mathrm{}i_n)`$, then $`𝒫|v_1,v_2\mathrm{}v_n=|v_{i_1},v_{i_2}\mathrm{}v_{i_n}`$. Define

$`𝒲_k=\text{span}\{|v:\mathrm{wt}(v)=k\}`$ (5)
where $`\mathrm{wt}(v)`$ is the number of $`k`$ for which $`v_k=1`$. (This is the classical Hamming weight of $`v`$.) Then $`𝐂^{2^n}=_{k=0}^n𝒲_k`$ is the orthogonal direct sum of the $`𝒲_k`$. Moreover, each $`𝒲_k`$ is invariant under $`S_n`$ and can be further decomposed into an orthogonal sum of spaces affording inequivalent irreducible representations of $`S_n`$. This yields an orthogonal decomposition of $`𝐂^{2^n}`$ into irreducible subspaces. However, unlike the regular representation, some irreducible representations occur more than once in $`𝐂^{2^n}`$, and others not at all. Appendix B describes the decomposition of $`𝒲_k`$ into irreducible subspaces for $`n=5,7,9`$.

Each $`𝒲_k`$ contains the trivial representation, for which we introduce the basis vector

$`W_k={\displaystyle \underset{\mathrm{wt}(v)=k}{}}|v={\displaystyle \underset{𝒫}{}}𝒫|\underset{\kappa }{\underset{}{1\mathrm{}1}}\underset{n\kappa }{\underset{}{0\mathrm{}0}}`$ (6)
where the second sum ranges over those permutations $`𝒫`$ which yield distinct vectors $`|v`$. Thus $`W_k,W_k=\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$. Occasionally we will use the normalized vectors $`\widehat{W}_k=\left(\genfrac{}{}{0pt}{}{n}{k}\right)^{1/2}W_k`$. Although normalized vectors are useful for many purpose, those denoted $`W_k`$ are more convenient in combinatoric computations.

Finally, we will make repeated use of the combinatoric identity

$`\left({\displaystyle \genfrac{}{}{0pt}{}{N}{K}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{N}{KJ}}\right)={\displaystyle \frac{N2K+J}{N+J}}\left({\displaystyle \genfrac{}{}{0pt}{}{N+J}{K}}\right)`$ (7)
which holds for J = 1,2 and is easy to verify. We will occasionally use the convention that $`\left(\genfrac{}{}{0pt}{}{N}{K}\right)=0`$ when $`N<K`$.

### 2.3 Codes

Given a (possibly non-Abelian) group $`𝒢`$, we define a code $`𝒞`$ as a subspace of $`𝐂^{2^n}`$ which is stabilized by $`𝒢`$ in the sense

$`g|v=|v\text{ for all }g𝒢\text{and all}|v𝒞.`$ (8)
If $`𝒞`$ has dimension $`2^m`$, then one can effectively encode $`m`$ logical binary units in $`n`$ physical qubits. We will restrict ourselves here to the simple case of $`1`$ to $`n`$ encoding, for which $`m=1`$ and $`𝒞`$ is two-dimensional. A code is often specified by an orthonormal basis for $`𝒞`$, in which case each basis vector, or “code word” can be regarded as a basis for the trivial representation of $`𝒢`$. In the case of two-dimensional codes, we can interpret these basis vectors as a logical $`0`$ and $`1`$, and will label them $`|c_0`$ and $`|c_1`$ accordingly.

We now consider two-dimensional codes for the group $`𝒢=S_n`$. If $`|v=|v_1,v_2\mathrm{}v_n`$ is a basis vector of $`𝐂^{2^n}`$ of weight $`k`$, (or, equivalently, a binary n-tuple of weight $`k`$) then $`\{g|v:gS_n\}`$ is the set of all basis vectors of weight $`k`$. Therefore, any vector satisfying $`g|v=|v\text{ for all }gS_n`$ must have the form $`_ka_kW_k`$, so that we can write a permutationally invariant code as a pair of basis vectors of the form

$`|c_0={\displaystyle \underset{k}{}}a_kW_k\text{ and }|c_1={\displaystyle \underset{k}{}}b_kW_k`$ (9)
for some complex numbers $`a_k`$ and $`b_k`$ with $`_k\overline{a}_kb_k=0`$. A vector $`_kd_kW_k`$ is called even (resp. odd) if $`d_k`$ is nonzero only when $`k`$ is even (resp. odd).

Note that we have defined a code so that the individual basis vectors are permutationally invariant. This is a stronger requirement than that the subspace defined by the code is invariant under $`S_n`$. However, the distinction is unlikely to matter in practice. In the case of two-dimensional codes, the two types of invariance are equivalent whenever $`n>3`$. In general one can have an invariant subspace of dimension $`2^m`$ only if it can be written as a direct sum of irreducible subspaces whose dimensions sum to $`2^m`$; this will usually consist of $`2^m`$ copies of the trivial representation, in which case the code words are also invariant.

We will be primarily interested in codes of the form (9) which also satisfy the following two conditions (which together imply that $`n`$ is odd).

* $`b_k=a_{nk}`$ or, equivalently, $`|c_1=(_jX_j)|c_0`$.
* $`c_0`$ is even and $`c_1`$ is odd or, equivalently, $`(_jZ_j)|c_{\mathrm{}}=(1)^{\mathrm{}}|c_{\mathrm{}}`$.

When (I) and (II) both hold, we can write

$`|c_0={\displaystyle \underset{j=0}{\overset{(n1)/2}{}}}a_{2j}W_{2j},|c_1={\displaystyle \underset{j=0}{\overset{(n1)/2}{}}}a_{n2j1}W_{2j+1}.`$ (10)
In addition to simplifying the analysis and ensuring that certain inner products are zero, these assumptions serve another purpose. They ensure that the logical $`X`$ and $`Z`$ operations can be implemented on the code words by $`_jX_j`$ and $`_jZ_j`$ respectively. Since the actual use of codes in fault tolerant computation requires a mechanism for implementing gates on the code words , this is an important consideration. Moreover, there is little loss of generality in this assumption. The operators $`_jX_j`$ and $`_jZ_j`$ lie in the commutant of $`S_n`$. Therefore, they necessarily map invariant subspaces of $`S_n`$ to invariant subspaces of $`S_n`$. In the case of the code space, we require the stronger condition that

$`[_jX_j]𝒞=𝒞\text{and}[_jZ_j]𝒞=𝒞.`$ (11)
When (11) holds, there is no loss of generality in assuming (I) and (II). These simply restrict the choice of basis in way that is convenient and can always be satisfied.

Our goal is to construct a permutationally invariant 2-dimensional code that can correct all single qubit errors, and to examine the types of two-bit errors that can be corrected.

As noted at the end of Section 1, non-Abelian stabilizers were considered previously in the context of DF subspace codes. Conversely, one can consider a permutationally invariant code as a DF subspace which arises from the highly idealized situation in which a quantum computer is completely insulated from its environment, but the qubits are the spin components of identical particles which interact.111For a complete analogy to DF subspaces, only those particles within each logical encoded unit would be permitted to interact with each other. Interactions between particles in different units, would lead to exchange errors between units. However, since these would appear as single bit errors in each logical unit, they would also be correctable. Then, as discussed in , even in the absence of spin-spin interactions, the Pauli principle induces an effective interaction between qubits whose DF subspace group is precisely that generated by exchanges. In essence, the Pauli principle requires correlations between the spatial and spin components so that spatial interactions (such as the Coulomb interaction) affect the spin components. The result of tracing over the spatial component yields a completely positive map on the spin components, as in the standard noise model. Only a fully symmetric spin function allows the full wave function to be a product (with an anti-symmetric spatial function) consistent with the Pauli principle for fermions. Thus, a DF subspace is precisely one which transforms as the trivial (or fully symmetric) representation of $`S_n`$. Although this is not a very realistic DF scenario, it is useful to see how codes constructed for different purposes can be interpreted within the DF subspace , as well as the stabilizer, formalism.

## 3 Error correction conditions

The now well-known necessary and sufficient condition  for the code $`𝒞`$ to correct errors in a set $`=\{e_1\mathrm{}e_M\}`$ can be stated as

$`e_pc_i,e_qc_j=\delta _{ij}d_{pq}e_p,e_q.`$ (12)
where the matrix $`d_{pq}`$ does not depend on $`i,j`$. One often chooses codes for which $`d_{pq}=\delta _{pq}\mu _p`$, but that is not necessary. Indeed, the requirement

$`d_{pq}e_pc_0,e_qc_0=e_pc_1,e_qc_1,`$ (13)
which is implicit in (12), implies that one can always transform the error set into a modified one $`\stackrel{~}{}`$ for which the stronger condition $`\stackrel{~}{d}_{pq}=\delta _{pq}\mu _p`$ holds.

Strictly speaking one can only determine whether or not a particular set of errors is correctable; not whether a particular error or type of error is “correctable”. However, it is often natural to look for codes for which the set of correctable errors includes all errors of a particular type, e.g., the one-bit errors. One can then ask what additional errors could be added to this subset to yield a set $``$ satisfying (12). In our discussion of such situations, the subset involved may be implied by the context.

We will find it useful to think of (12) as defining a pair of matrices $`D^{ii}`$ with elements $`d_{pq}^i=e_pc_i,e_qc_i`$ for $`i=0,1`$ and a matrix $`B=D^{01}`$ with elements $`b_{pq}d_{pq}^{01}=e_pc_0,e_qc_1`$. Then (12) is equivalent to the requirements $`B=0`$ and $`D^{00}=D^{11}`$. (Because $`d_{pq}^{10}`$ and $`d_{qp}^{01}`$ are complex conjugates, $`D^{01}=0D^{10}=0`$. Hence we need not consider $`D^{10}`$ explicitly and will use only $`BD^{01}`$.) For simplicity, we omit the superscript in $`d_{pq}^i`$.

For example, the 9-bit permutationally invariant code in  corrects single qubit errors as well as the Pauli exchange errors (transpositions) $`E_{rs}`$, for the 36 unordered pairs $`r,s`$. We can consider the above matrices with respect to the errors $`=\{I,E_{rs},X_1,\mathrm{},X_9,Y_1,\mathrm{},Y_9,Z_1,\mathrm{},Z_9\}`$. It was shown that $`D^{00}=D^{11}`$ and has the block diagonal form

$`\left(\begin{array}{cccc}D_0& 0& 0& 0\\ 0& D_{XX}& 0& 0\\ 0& 0& D_{YY}& 0\\ 0& 0& 0& D_{ZZ}\end{array}\right)`$ (14)
where $`D_0`$ is a $`37\times 37`$ rank one matrix and the $`9\times 9`$ matrices $`D_{XX},D_{YY},D_{ZZ}`$ correspond to the one-bit errors indicated by the subscripts. These all have the cyclic form

$`\left(\begin{array}{cccc}a& b& \mathrm{}& b\\ b& a& \mathrm{}& b\\ \mathrm{}& & & \mathrm{}\\ b& b& \mathrm{}& a\end{array}\right).`$ (15)
For any permutationally invariant code the blocks $`D_{XX},D_{YY},D_{ZZ}`$ necessarily have the form (15). Such matrices can always be diagonalized by a change of basis to $`(1,1\mathrm{}1)`$ and its orthogonal complement. This corresponds to replacing the errors $`\{f_1,f_2\mathrm{}f_n\}`$ by the corresponding average $`\{\overline{f}\}`$ and a suitable orthogonalization of $`\{f_1f_k,k=2\mathrm{}n\}`$ where $`f`$ denotes any of $`X,Y,Z`$.

Now the orthogonality of subspaces associated with different irreducible representations ensures that

$`\overline{f}W_j,(g_rg_s)W_k=0`$ (16)
for all $`j,k`$ and any choice of $`\overline{f}=I,\overline{X},\overline{Y},\overline{Z}`$ and $`g=X,Y,Z`$. Alternatively, we can show this directly by observing that the exchange operator $`E_{rs}`$ is unitary so that

$`\overline{f}W_j,(g_rg_s)W_k`$ $`=`$ $`E_{rs}\overline{f}E_{rs}(E_{rs}W_j),E_{rs}(g_rg_s)E_{rs}(E_{rs}W_k)`$
$`=`$ $`\overline{f}W_j,(g_sg_r)W_k`$
$`=`$ $`\overline{f}W_j,(g_rg_s)W_k`$
which implies (16). For such codes, each of the matrices $`D^{ii},(i=0,1)`$ and $`B`$ have the form below (which we write only for $`D`$) with respect to the order in (4).

$`\left(\begin{array}{cc}\begin{array}{cccc}d_{II}& d_{IX}& d_{IY}& d_{IZ}\\ d_{XI}& d_{XX}& d_{XY}& d_{XZ}\\ d_{YI}& d_{YX}& d_{YY}& d_{YZ}\\ d_{ZI}& d_{ZX}& d_{ZY}& d_{ZZ}\end{array}& \mathrm{𝟎}\\ \mathrm{𝟎}& \begin{array}{ccc}D_{XX}& D_{XY}& D_{XZ}\\ D_{YX}& D_{YY}& D_{YZ}\\ D_{ZX}& D_{ZY}& D_{ZZ}\end{array}\end{array}\right)`$ (17)
Conditions (I) and (II) immediately give many additional zero entries. One nice way to see which entries are zero is to observe that $`_kZ_k`$ commutes with $`Z_r`$ and anti-commutes with $`X_r`$ and $`Y_r`$ for all $`r`$. Thus, for every one-bit error $`e_p`$, $`e_p(_kZ_k)=ϵ_p^Z(_kZ_k)e_p`$, where

$`ϵ_p^Z=\{\begin{array}{ccc}+1\hfill & \text{ for }\hfill & e_p\{I,\overline{Z},(Z_rZ_s)\}\hfill \\ 1\hfill & \text{ for }\hfill & e_p\{\overline{X},\overline{Y},(X_rX_s),(Y_rY_s)\}\hfill \end{array}`$ (20)
Also, $`_kZ_k`$ is unitary so that

$`e_pc_i,e_qc_j`$ $`=`$ $`(_kZ_k)e_pc_i,(_kZ_k)e_qc_j`$
$`=`$ $`ϵ_p^Zϵ_q^Ze_p(_kZ_k)c_i,e_q(_kZ_k)c_j`$
$`=`$ $`ϵ_p^Zϵ_q^Z(1)^{i+j}e_pc_i,e_qc_j.`$
From this we can conclude the following.

* When $`i=j`$, $`e_pc_i,e_qc_i=0`$ whenever $`ϵ_p^Zϵ_q^Z`$ Thus, $`d_{IX}=d_{IY}=d_{XZ}=d_{YZ}=0`$ and $`D_{XZ}=D_{YZ}=0`$.
* When $`ij`$, $`e_pc_i,e_pc_j=0`$ whenever $`ϵ_p^Z=ϵ_q^Z`$, from which we can conclude $`b_{IZ}=b_{ZI}=b_{XY}=b_{YX}=0`$ and $`B_{XX}=B_{YY}=B_{ZZ}=B_{XY}=B_{YX}=0`$.

Combining this with $`d_{fg}=0d_{gf}=0`$ and $`D_{fg}=0D_{gf}=0`$, we find that the $`D^{ii}`$ have the form

$`\left(\begin{array}{cc}\begin{array}{cccc}d_{II}& 0& 0& d_{IZ}\\ 0& d_{XX}& d_{XY}& 0\\ 0& d_{YX}& d_{YY}& 0\\ d_{ZI}& 0& 0& d_{ZZ}\end{array}& 0\\ 0& \begin{array}{ccc}D_{XX}& D_{XY}& 0\\ D_{YX}& D_{YY}& 0\\ 0& 0& D_{ZZ}\end{array}\end{array}\right)`$ (21)
and $`B`$ has the form

$`\left(\begin{array}{cc}\begin{array}{cccc}0& b_{IX}& b_{IY}& 0\\ b_{XI}& 0& 0& b_{XZ}\\ b_{YI}& 0& 0& b_{YZ}\\ 0& b_{ZX}& b_{ZY}& 0\end{array}& \mathrm{𝟎}\\ \mathrm{𝟎}& \begin{array}{ccc}0& 0& B_{XZ}\\ 0& 0& B_{YZ}\\ B_{ZX}& B_{ZY}& 0\end{array}\end{array}\right)`$ (22)
Now, observe that $`_kX_k`$ commutes with $`X_r`$ and anti-commutes with $`Y_r`$ and $`Z_r`$. Proceeding as above, we find

$`ϵ_p^X=\{\begin{array}{ccc}+1\hfill & \text{ for }\hfill & e_p\{I,\overline{X},(X_rX_s)\}\hfill \\ 1\hfill & \text{ for }\hfill & e_p\{\overline{Y},\overline{Z},(Y_rY_s),(Z_rZ_s)\}\hfill \end{array}`$ (25)
and

$`e_pc_i,e_qc_j`$ $`=`$ $`(_kX_k)e_pc_i,(_kX_k)e_qc_j`$
$`=`$ $`ϵ_p^Xϵ_q^Xe_p(_kX_k)c_i,e_q(_kX_k)c_j`$
$`=`$ $`ϵ_p^Xϵ_q^Xe_pc_{i+1},e_qc_{j+1},`$
where we interpret $`i+1`$ and $`j+1`$ mod 2. Thus we can conclude

* When $`i=j`$, condition (12) holds whenever $`ϵ_p^X=ϵ_q^X`$. (This means, in particular, that the diagonal entries and blocks of $`D^{00}`$ and $`D^{11}`$ agree.)
* When $`i=j`$ and $`ϵ_p^Xϵ_q^X`$, condition (12) can only be satisfied if $`e_pc_i,e_qc_i=0`$ for $`i=0,1`$. Thus we must have $`d_{IZ}=d_{XY}=0`$ and $`D_{XY}=0`$.
* When $`ij`$, $`e_pc_0,e_qc_1=\pm e_pc_1,e_qc_0=\pm \overline{e_qc_0,e_pc_1}`$. Thus, we can conclude, e.g., that matrix entries $`b_{XZ}=0b_{ZX}=0`$ and blocks $`B_{XZ}=0B_{ZX}=0`$, so it suffices to check entries of $`B`$ above the main diagonal.

Thus, when conditions (I) and (II) are satisfied, we find that sufficient (and necessary) conditions for (12) to hold are that

* All off-diagonal entries and blocks in (21) are zero,
* All remaining entries in (22) are zero.

Moreover, it suffices to check matrix elements above the main diagonal in (21) and (22).

We can break these conditions into several groups, which will turn out to be related or equivalent.

* Conditions $`b_{IX}=b_{IY}=b_{ZX}=b_{ZY}=0`$, which are equivalent to $`c_0,(\overline{X}\pm i\overline{Y})c_1=\overline{Z}c_0,(\overline{X}\pm \overline{Y})c_1=0`$. These will yield just two conditions when the $`a_k`$ are real.
* Conditions $`d_{IZ}=d_{XY}=0`$, i.e., $`c_0,\overline{Z}c_0=\overline{X}c_0,\overline{Y}c_0=0`$. These will reduce to one condition when the $`a_k`$ are real.
* The block conditions $`B_{XZ}=B_{YZ}=0`$, which are equivalent to
$`[(X_1X_r)\pm i(Y_1Y_r)]c_0,(Z_1Z_s)c_1=0`$ for $`2r,sn`$.
* The block condition $`D_{XY}=0`$, which is equivalent to
$`(X_1X_r)c_0,(Y_1Y_s)c_0=0`$ for $`2r,sn`$.

We will see that for codes which satisfy conditions (I) and (II) and have all coefficients real, conditions (c) on blocks will be satisfied whenever (a) holds; and conditions (d) on blocks will be satisfied whenever (b) holds. Thus, we will only need to satisfy three non-linear equations for such codes. We can summarize this as follows.

###### Theorem 1

Assume that the coefficients $`a_k`$ associated with a permutationally invariant code which has the form (10) and length $`n`$ are all real. Such a code can correct all one-bit errors if and only if the following equations hold.

$`0`$ $`=`$ $`{\displaystyle \frac{n+1}{2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n+1}{2}}}\right)a_{\frac{n+1}{2}}^2+2{\displaystyle \underset{m=1}{\overset{(n1)/4}{}}}a_{2m}a_{n2m+1}\mathrm{\hspace{0.17em}2}m\left({\displaystyle \genfrac{}{}{0pt}{}{n}{2m}}\right)`$ (26)
$`0`$ $`=`$ $`{\displaystyle \frac{n+1}{2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n1}{2}}}\right)a_{\frac{n1}{2}}^2+2{\displaystyle \underset{m=0}{\overset{(n3)/4}{}}}a_{2m}a_{n2m1}(n2m)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{2m}}\right)`$ (27)
$`0`$ $`=`$ $`{\displaystyle \underset{m=0}{\overset{(n1)/2}{}}}a_{2m}^2(n4m)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{2m}}\right)`$ (28)
The theorem will follow from the analysis in the next section. The result can be extended to complex $`a_k`$ as discussed in Appendix C. As noted before, it is implicit in (10) that $`n`$ is odd.

## 4 Error condition analysis

### 4.1 Conditions of type (a) — $`c_0,c_1`$ orthogonality

First we give expressions for the action of the average errors $`\overline{X}`$, $`\overline{Y}`$ and $`\overline{Z}`$. It is easy to check that for $`0kn`$

$`n\overline{Z}W_k`$ $`=`$ $`(n2k)W_k`$ (29)
$`n\overline{X}W_k`$ $`=`$ $`(k+1)W_{k+1}+(nk+1)W_{k1}`$ (30)
$`in\overline{Y}W_k`$ $`=`$ $`(k+1)W_{k+1}(nk+1)W_{k1},`$ (31)
where it is understood that if $`m<0`$ or $`m>n`$, $`W_m`$ should be replaced by zero; for example, $`n\overline{X}W_0=W_1`$.

To analyze the requirement $`b_{IX}=b_{IY}=b_{ZX}=b_{ZY}=0`$, it is equivalent (and somewhat easier) to use the conditions

$`0`$ $`=`$ $`c_0,(\overline{X}\pm i\overline{Y})c_1,\text{and}`$ (32)
$`0`$ $`=`$ $`\overline{Z}c_0,(\overline{X}\pm i\overline{Y})c_1`$ (33)
When condition (I) holds, these conditions become

$`nc_0,(\overline{X}+i\overline{Y})c_1`$ $`=`$ $`2{\displaystyle \underset{k=1}{\overset{n}{}}}k\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)\overline{a}_ka_{nk+1}=0`$ (34)
$`n^2\overline{Z}c_0,(\overline{X}+i\overline{Y})c_1`$ $`=`$ $`2{\displaystyle \underset{k=1}{\overset{n}{}}}(n2k)k\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)\overline{a}_ka_{nk+1}=0`$ (35)
$`nc_0,(\overline{X}i\overline{Y})c_1`$ $`=`$ $`2{\displaystyle \underset{k=0}{\overset{n1}{}}}(nk)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)\overline{a}_ka_{nk1}=0`$ (36)
$`n^2\overline{Z}c_0,(\overline{X}i\overline{Y})c_1`$ $`=`$ $`2{\displaystyle \underset{k=0}{\overset{n1}{}}}(n2k)(nk)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)\overline{a}_ka_{nk1}=0`$ (37)
Thus far, condition (I) has played a minor role and one can easily obtain more general conditions by replacing $`a_{nk}`$ by $`b_k`$ above. Now, however, we make explicit use of the fact that all products have the form $`\overline{a}_ka_{nk+1}`$ to conclude that the real parts of the expressions in (34) and (35) and in (36) and (37) agree up to sign, which leads to the following lemma.

###### Lemma 2

When the coefficients $`a_k`$ are all real, the equations (34) to (37) are equivalent in pairs, (34 ) $``$ (35 ) and (36) $``$ (37 ). When $`n`$ is odd these reduce to

$`0`$ $`=`$ $`{\displaystyle \underset{k=1}{\overset{(n1)/2}{}}}a_ka_{nk+1}2k\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)+a_{\frac{n+1}{2}}^2\frac{n+1}{2}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n+1}{2}}}\right)`$ (38)
$`0`$ $`=`$ $`{\displaystyle \underset{k=0}{\overset{(n3)/2}{}}}a_ka_{nk1}2(nk)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)+a_{\frac{n1}{2}}^2\frac{n+1}{2}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n1}{2}}}\right).`$ (39)
When $`n`$ is even, similar expressions hold with upper limits of $`n/2`$ and $`n/21`$ respectively but without any extra square terms analogous to $`a_{\frac{n\pm 1}{2}}^2`$.

When condition (II) holds, equations (38) and (39) reduce to (26) and (27), which proves the first part of Theorem 1.

Proof: First, observe that for $`m\frac{n+1}{2}`$, the term $`a_ma_{nm+1}`$ occurs twice in (34), once for $`m=k`$ and once for $`m=nk+1`$. Thus, the coefficient of $`a_ma_{nm+1}`$ is

$`m\left({\displaystyle \genfrac{}{}{0pt}{}{n}{m}}\right)+(nm+1)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{nm+1}}\right)=2m\left({\displaystyle \genfrac{}{}{0pt}{}{n}{m}}\right)`$
The coefficient of the same term in (35) is

$$(n2m)m\left(\genfrac{}{}{0pt}{}{n}{m}\right)+[n2(nm+1)](nm+1)\left(\genfrac{}{}{0pt}{}{n}{nm+1}\right)=2m\left(\genfrac{}{}{0pt}{}{n}{m}\right).$$

To obtain a general proof and reduction to (26), it suffices to make the change of variable $`knk+1`$ when $`k\frac{n+3}{2}`$ in (34 ) and (35) and, as above, use the elementary identity

$`m\left({\displaystyle \genfrac{}{}{0pt}{}{n}{m}}\right)=(nm+1)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{nm+1}}\right).`$ (40)
Similarly, the change of variable $`knk1`$ for $`k\frac{n+1}{2}`$ in (36 ) and (37) yields (27). QED

### 4.2 Conditions of type (b)— off-diagonal conditions

Using (29) to (31) one finds that

$`n\overline{X}W_k,in\overline{Y}W_k`$ $`=`$ $`W_k,n\overline{Z}W_k=(n2k)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)`$
$`n\overline{X}W_k,in\overline{Y}W_{k+2}`$ $`=`$ $`n\overline{X}W_{k+2},in\overline{Y}W_k`$
$`n\overline{X}W_j,in\overline{Y}W_{\mathrm{}}`$ $`=`$ $`0\text{ if }j\mathrm{}\pm 2,0.`$
From these relations, it follows that when all $`a_k`$ and $`b_k`$ are real

$`n^2\overline{X}c_j,i\overline{Y}c_j=nc_j,\overline{Z}c_j={\displaystyle \underset{k}{}}\alpha _k^2(n2k)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)`$ (41)
where $`\alpha _k`$ equals $`a_k`$ or $`b_k`$ according as $`j`$ equals 0 or 1. Thus, we can conclude that when $`a_k,b_k`$ are real, the off-diagonal conditions $`d_{IZ}=d_{XY}=0`$ hold if and only if

$`{\displaystyle \underset{k}{}}a_k^2(n2k)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)={\displaystyle \underset{k}{}}b_k^2(n2k)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)=0.`$ (42)
This reduces to to (28) when conditions I and (II) are satisfied. If some $`a_k,b_k`$ are not real, then (41) holds with $`\alpha _k^2`$ replaced by $`|a_k|^2`$ or $`|b_k|^2`$, but the additional condition (116) is needed to ensure that the imaginary part of $`\overline{X}c_i,i\overline{Y}c_i`$ is zero, as discussed in Appendix C.

### 4.3 Conditions of type (c) — block $`c_0,c_1`$ orthogonality.

It will again be useful to replace the separate $`X,Y`$ equations by their sums and differences. The requirement that the blocks $`B_{XZ}=B_{YZ}=0`$ is equivalent to

$`\left[(X_1X_r)\pm i(Y_1Y_r)\right]c_0,(Z_1Z_s)c_1=0.`$ (43)
for $`2r,sn`$. We now need results from Appendix A. When conditions (I) and (II) hold, equations (86a), (86b) and (86c) imply that (43) is equivalent to the following pair of equations

$`{\displaystyle \underset{m=0}{\overset{(n3)/2}{}}}\overline{a}_{2m}a_{n2m1}\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{2m}}\right)`$ $`=`$ $`0,\text{and}`$ (44)
$`{\displaystyle \underset{m=1}{\overset{(n1)/2}{}}}\overline{a}_{2m}a_{n2m+1}\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{2m2}}\right)`$ $`=`$ $`0.`$ (45)
To see that these are equivalent to (26) and (27), again make a change of variable of the form $`knk1`$ in the second half of each sum and use the identities

$`\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{k}}\right)+(1\delta _{k0})\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{nk1}}\right)`$ $`=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{k}}\right)={\displaystyle \frac{nk}{n}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)`$
$`(1\delta _{k1})\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{k2}}\right)+\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{nk1}}\right)`$ $`=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{n1}{k1}}\right)={\displaystyle \frac{k}{n}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right).`$
### 4.4 Conditions of type (d)— block off-diagonal conditions

We now consider the condition $`d_{XY}=0`$ which means that

$`(X_1X_r)c_0,i(Y_1Y_s)c_0=0`$ (46)
for all choices of $`2r,sn`$. The crucial fact is that the inner products of this type with $`r=s`$ and $`rs`$ differ only by a factor of $`2`$ as shown by (84) in Appendix A.

###### Theorem 3

When conditions (I) and (II) are satisfied and the $`a_k`$ are real, (46) holds if and only if (28) does.

Proof: It follows from (85b) and (85c) that when $`1,r,s`$ are distinct

$`(X_1X_r)c_0,i(Y_1Y_r)c_0`$ $`=`$ $`2(X_1X_r)c_0,i(Y_1Y_s)c_0`$ (47)
$`=`$ $`2A_0+2{\displaystyle \underset{m=1}{\overset{(n3)/2}{}}}\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{2m}}\right)A_m`$
where $`A_m=|a_{2m}|^2|a_{2m+2}|^2+a_{2m}\overline{a}_{2m+2}\overline{a}_{2m}a_{2m+2}`$. Thus when the $`a_k`$ are real, (46) will be satisfied for all choices of $`r,s`$ if

$`a_0^2+{\displaystyle \underset{m=1}{\overset{(n3)/2}{}}}a_{2m}^2\left[\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{2m}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{2(m1)}}\right)\right](n2)a_{n1}^2=0.`$ (48)
One can then conclude that (48) is equivalent to (28) if $`n\left[\left(\genfrac{}{}{0pt}{}{n2}{2m}\right)\left(\genfrac{}{}{0pt}{}{n2}{2(m1)}\right)\right]=(n4m)\left(\genfrac{}{}{0pt}{}{n}{2m}\right)`$ which follows from (7) with $`N=n2,K=2m,J=2`$.

## 5 Two-bit errors

### 5.1 Some special types of two-bit errors

The standard 7-bit CSS code  can correct two-bit errors of the form $`X_rZ_s`$ but not those of the form $`X_rX_s`$ or $`Z_rZ_s`$. The last two are far more likely to occur, especially for nearest neighbors. We now consider the effect of two-bit errors of the same type, which we call “double” errors, on permutationally invariant codes.

Recall that exchange errors have the form (1). Permutationally invariant codes are designed so that exchange errors are degenerate with the identity, i.e., $`E_{rs}|c_j=|c_j`$ for $`j=0,1`$. Now consider the following three errors

$`F_{rs}`$ $`=`$ $`\frac{1}{2}\left[IIX_rX_sY_rY_s+Z_rZ_s\right]`$ (49a)
$`G_{rs}`$ $`=`$ $`\frac{1}{2}\left[II+X_rX_sY_rY_sZ_rZ_s\right]`$ (49b)
$`H_{rs}`$ $`=`$ $`\frac{1}{2}\left[IIX_rX_s+Y_rY_sZ_rZ_s\right]`$ (49c)
and observe that

* $`F_{rs}`$ exchanges two bits and multiplies by $`1`$ if and only if the values of the bits are different.
* $`G_{rs}`$ flips the two bits $`r`$ and $`s`$ if and only if they are the same.
* $`H_{rs}`$ flips the two bits $`r`$ and $`s`$ and then multiplies by $`1`$ if and only if they are the same.

In a product basis of the form $`|00,|01,|10,|11`$ these operators are represented by the matrices

$`E_{rs}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right)`$ $`F_{rs}=\left(\begin{array}{cccc}1& 0& 0& 0\\ 0& 0& 1& 0\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}\right)`$
$`G_{rs}=\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 0\end{array}\right)`$ $`H_{rs}=\left(\begin{array}{cccc}0& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 0\end{array}\right).`$
Any code which can correct all errors of the type $`E_{rs},F_{rs},G_{rs},H_{rs}`$ can also correct any error of the form $`Z_rZ_s,X_rX_s,Y_rY_s`$, since an error of one type can be written as a linear combination of those of the other. For permutationally invariant codes, these two types of errors are actually equivalent.

###### Theorem 4

If $`|\psi `$ is permutationally invariant (i.e., $`E_{rs}|\psi =|\psi `$ for all $`r,s`$), then the operators $`F_{rs},G_{rs}`$ and $`H_{rs}`$ have the same effect on $`|\psi `$ as $`Z_rZ_s,X_rX_s`$, and $`Y_rY_s`$ respectively, i.e., $`F_{rs}|\psi =Z_rZ_s|\psi `$, $`G_{rs}|\psi =X_rX_s|\psi `$ and $`H_{rs}|\psi =Y_rY_s|\psi `$.

Proof: First note that $`E_{rs}+F_{rs}=I+Z_rZ_s`$. Then

$`F_{rs}|\psi =\left(I+Z_rZ_sE_{rs}\right)|\psi =|\psi +Z_rZ_s|\psi |\psi =Z_rZ_s|\psi `$
The other two cases are done similarly using $`E_{rs}+G_{rs}`$ and $`E_{rs}+H_{rs}`$ respectively.

### 5.2 Two-bit error correction conditions

We begin with some simple, but fundamental, results. The first follows from the fact that all double errors preserve parity.

###### Theorem 5

Whenever condition (II) is satisfied,

$`e_pc_0,e_qc_1=0`$ (50)
for any pair of errors in the set $`\{I,Z_rZ_s,X_rX_s,Y_rY_s\}`$ or, equivalently, in the set $`\{I,E_{rs},F_{rs},G_{rs},H_{rs}\}`$.

The next theorem says that all inner products of the form $`Z_rZ_sc_j,Z_qZ_tc_j`$, $`Z_rZ_sc_j,X_qX_tc_j`$ etc. are independent of $`j=0,1`$. It follows easily from the equivalence of condition (I) to $`(_kX_k)|c_0=|c_1`$, and the fact that $`_kX_k`$ is a unitary operator which commutes with any error of the form $`X_rX_s`$, $`Y_rY_s`$ or $`Z_rZ_s`$.

###### Theorem 6

Whenever condition (I) is satisfied,

$`f_rf_sc_0,g_qg_tc_0=f_rf_sc_1,g_qg_t,c_1`$ (51)
where $`f,g`$ denote any of $`\{X,Y,Z\}`$ (the same as well as different) and $`r,s,q,t`$ are arbitrary.

One is often interested in knowing which two-bit errors can be corrected in addition to one-bit errors. Conditions involving the average error $`\overline{ZZ}`$ can be readily calculated by noting that

$`{\displaystyle \underset{rs}{}}Z_rZ_s={\displaystyle \underset{r,s}{}}Z_rZ_s{\displaystyle \underset{r}{}}Z_r^2=\left({\displaystyle \underset{r}{}}Z_r\right)^2nI=(n\overline{Z})^2nI.`$ (52)
Combining this with (29), one finds

$`n(n1)\overline{ZZ}W_k=\left({\displaystyle \underset{rs}{}}Z_rZ_s\right)W_k=[(n2k)^2n]W_k.`$ (53)
The additional conditions needed to correct all errors of the form $`Z_rZ_s`$ include $`\overline{Z}c_0,\overline{ZZ}c_0=0`$ and $`\overline{ZZ}c_0,(\overline{X}\pm i\overline{Y})c_1=0`$. The latter gives the following pair of conditions

$`0`$ $`=`$ $`2{\displaystyle \underset{k=1}{\overset{n}{}}}[(n2k)^2n]k\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)\overline{a}_ka_{nk+1}`$ (54)
$`0`$ $`=`$ $`2{\displaystyle \underset{k=0}{\overset{n1}{}}}[(n2k)^2n](nk)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)\overline{a}_ka_{nk1}`$ (55)
Using (29) and (53), one finds that $`\overline{Z}c_0,\overline{ZZ}c_0=d_{Z,ZZ}=0`$ is equivalent to

$`0`$ $`=`$ $`{\displaystyle \underset{k}{}}|a_k|^2(n2k)[(n2k)^2n]\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right).`$ (56)
Although one can write down a similar set of conditions for the correction of errors of the form $`X_rX_s`$, it is probably easier to use the following observation.

###### Theorem 7

A permutationally invariant code $`|c_0,|c_1`$ which satisfies conditions (I) and (II) \[and corrects a specified set of one-bit errors\]  can correct all errors of the form $`Z_rZ_s`$ if and only if the code

$`|C_j=H^n|c_0+(1)^jH^n|c_1`$ (57)
can correct all errors of the form $`X_rX_s`$.

The map $`|c_j|C_j`$ in (57) consists of a Hadamard gate acting on all qubits, followed by an effective Hadamard operation on the resulting code words themselves. This is extremely useful and is its own inverse. We will refer to it as the “Hadamard code map”.

### 5.3 Degeneracy enhancement of classical codes

It follows from Theorems 5 and 6 that every permutationally invariant code for which both conditions (I) and (II) are satisfied can correct all double errors of the form $`Z_rZ_s,X_rX_s,Y_rY_s`$ provided that we do not also require single bit errors to be correctable. For example, the 3-bit repetition code $`|c_0=|000,|c_1=|111`$ is generally regarded as able to correct all single bit flips, but no other errors. However, one could instead use it to correct all double bit flips, at the expense of the ability to correct any single bit errors. The theorem above says that it can do even more — it can correct all two-bit errors of the same type. Although this might seem surprising at first, it is easy to understand why it is true. For this code $`Z_rZ_s|c_j=|c_j`$ so that $`Z_rZ_s`$ is degenerate with the identity. Similarly, $`Y_rY_s`$ is degenerate with $`X_rX_s`$. Note that this degeneracy extends to any n-bit repetition code

$`|c_0=|00\mathrm{}0=W_0,|c_1=|11\mathrm{}1=W_n.`$ (58)
When $`n5`$, the simple repetition code (58) can correct all single and all double bit flips. Indeed, for $`n=5`$, this is just a classical code for two-bit error correction. Applying the Hadamard code map (57) to (58) yields a code which can correct all single and double phase errors. In fact, omitting the normalizing coefficients, this code is

$`|C_0=`$ $`H^n|c_0+H^n|c_1`$ $`={\displaystyle \underset{m}{}}W_{2m}`$ (59a)
$`|C_1=`$ $`H^n|c_0H^n|c_1`$ $`={\displaystyle \underset{m}{}}W_{2m+1}`$ (59b)
Because the phase errors preserve parity, the necessary and sufficient conditions for a code satisfying conditions (I) and (II) to correct both single and double phase errors are

$`0`$ $`=`$ $`c_0,\overline{Z}c_0`$ (60a)
$`0`$ $`=`$ $`\overline{Z}c_0,\overline{ZZ}c_0`$ (60b)
$`0`$ $`=`$ $`(Z_1Z_t)c_0,Z_1Z_sc_0=0(ts).`$ (60c)
Note that since $`(Z_1Z_t)c_0,\overline{ZZ}c_0=0`$, the single and double-Z errors which transform as the $`(n1)`$-dimensional representation are orthogonal if and only if (60c) holds. In fact, as shown after (110) in Appendix A, (60c) is redundant, i.e., it is satisfied whenever (60a) and (60b) hold. Thus, one finds that the necessary and sufficient conditions for a code satisfying conditions (I) and (II) to correct single and double phase errors are (42) \[which becomes (113) when $`a_k`$ is complex\] and (56), which we rewrite below.

$`0`$ $`=`$ $`{\displaystyle \underset{k}{}}|a_k|^2(n2k)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)=0`$ (61a)
$`0`$ $`=`$ $`{\displaystyle \underset{k}{}}|a_k|^2(n2k)[(n2k)^2n]\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)=0.`$ (61b)
When $`n=5`$, the pair of equations in (61) has exactly one solution (up to normalization), namely $`|a_0|^2=|a_2|^2=|a_4|^2`$. Choosing identical phases yields the code in (59). In addition to correcting all one and two-bit phase errors, it can also correct all errors of the form $`X_rX_s`$ and $`Y_rY_s`$. Choosing other phases yields other codes and taking the Hadamard code map yields classical codes for two-bit error correction that are distinct from (58). These also satisfy conditions (I) and (II) and, hence, can correct all double $`Z_rZ_s`$ and $`Y_rY_s`$ errors as well as single and double bit flips when used as quantum codes.

When $`n7`$ and odd, the pair of equations (61) has infinitely many solutions in addition to $`|a_0|^2=|a_2|^2\mathrm{}=|a_{n1}|^2`$. Taking the Hadamard transform then yields infinitely many classical codes for two bit error correction.

### 5.4 Higher dimensional representations

In this section we take some preliminary steps toward exploiting higher dimensional irreducible representations for correction of errors in addition to one-bit errors. First, we review the mutually orthogonal subspaces required for the correction of single errors. The operators $`I,\overline{X},\overline{Y},\overline{Z}`$ acting on the code words $`|c_0,|c_1`$ require four pairs of one-dimensional subspaces which transform as the trivial representation. The three sets of differences $`X_1X_r`$, $`Y_1Y_r`$, and $`Z_1Z_r`$ acting on the code words require three pairs of subspaces of dimension $`n1`$ which transform as the even $`(n1)`$-dimensional representation. But (as described in Appendix B) the decomposition of $`𝐂^{2^n}`$ into an orthogonal sum of irreducible subspaces includes other irreducible representations of $`S_n`$.

The next irreducible representation has dimension $`\frac{n(n3)}{2}`$ and arises in the decomposition of double errors of one type, e.g., $`f_{rs}=X_rX_s`$. Consider the subspace generated by $`f_{rs}W_k`$ for $`k=2`$ (or $`k=n2`$) as $`r,s`$ run through all $`\frac{n(n1)}{2}`$ combinations of $`r<s`$. This subspace splits into an orthogonal direct sum consisting of

* a 1-dimensional subspace spanned by $`\overline{ff}W_k`$ where $`\overline{ff}=\left(\genfrac{}{}{0pt}{}{n}{2}\right)^1_{rs}f_{rs}`$ is the average error of this type,
* an $`(n1)`$-dimensional subspace spanned by the vectors $`f_rW_k`$ for $`r=2,3\mathrm{}n`$ where $`\overline{f}_r=_{s=2}^nf_{1s}_{sr}f_{rs}r=2,3\mathrm{}n`$ , and
* an $`\frac{n(n3)}{2}`$-dimensional subspace which is obtained by taking the orthogonal complement of the vectors $`\overline{ff}W_k`$ and $`f_rW_k`$ in span$`\{f_{rs}W_k\}`$ .

As described in Section 2.1, the error set $`\{f_{rs}\}`$ can be correspondingly decomposed into bases for representations of $`S_n`$ with dimensions $`1`$, $`n1`$, and $`\frac{n(n3)}{2}`$.

For an explicit example of the last type of error, consider $`n=4`$. Then $`𝒲_2`$ splits into three subspaces, corresponding to irreducible representations of dimensions 1, 3 and 2. The last is spanned by the vectors:

$`2f_{12}f_{13}f_{14}f_{23}f_{24}+2f_{34}`$
$`f_{12}+f_{13}2f_{14}2f_{23}+f_{24}+f_{34}`$
There is a sense in which these errors are rather delocalized, since they act on all six pairs of qubits. Although one could eliminate some pairs by a different choice of basis vectors, one can not, e.g., eliminate all terms of the form $`f_{j4}`$ involving the 4th qubit. This delocalization is, unfortunately, the antithesis of what one might want in certain situations, such as errors between nearest neighbors.

We now focus on $`n=7`$ as an example and note that $`𝐂^{2^7}`$ can be decomposed into an orthogonal sum of irreducible subspaces spanned by

* 8 orthogonal bases for the trivial 1-dimensional representation,
* 6 orthogonal bases for the even 6-dimensional representation,
* 4 orthogonal bases for a 14-dimensional representation,
* 2 orthogonal bases for a second, inequivalent, 14-dimensional representation.

Thus, correcting the one-bit errors requires all of the available $`1`$ and $`6`$ dimensional representations. However, the two types of $`14`$-dimensional representations are available to correct two-bit errors. One of these $`14`$-dimensional representations has spin $`\frac{3}{2}`$ and is associated with the partition $`[5,2]`$. This is the $`\frac{n(n3)}{2}`$-dimensional representation which arises in the decomposition of $`f_{rs}`$ errors described above, and can be used to correct the corresponding subclass of double errors, There are three kinds of double errors, those from $`Z_rZ_s`$, from $`X_rX_s`$, and from $`Y_rY_s`$. This would seem to require six orthogonal subspaces which transform as this 14-dimensional representation; however, we have only four — one each from $`𝒲_2,𝒲_3,𝒲_4,𝒲_5`$. Nevertheless, Theorems 5 and 6 imply that all three types of double errors can be corrected.

This is indeed the case and is the result of degeneracy. For permutationally invariant codes,

$`(X_rX_s+Z_rZ_s+Y_rY_s)|\psi =|\psi .`$ (62)
Thus, it suffices to correct any two of $`X_rX_s`$, $`Z_rZ_s`$, $`Y_rY_s`$ to ensure that all three types of errors can be corrected, and this requires only four 14-dimensional subspaces, exactly what one has available when $`n=7`$. Thus, a 7-bit permutationally invariant code which can correct all one-bit errors can also correct all errors in the 14-dimensional irreducible components of the decompositions of $`X_rX_s`$, $`Z_rZ_s`$, and $`Y_rY_s`$. This implies that arbitrary double errors would be corrected about $`2/3`$ of the time. Similarly, a 9-bit code could correct them about $`3/4`$ of the time. Unfortunately, the other $`1/3`$ (or 1/4) of the time, the procedure does not simply fail to detect the error — it incorrectly interprets a two-bit error as a one-bit error and the attempted correction actually introduces additional errors.

We next consider the case $`n=9`$. Correcting the one-bit errors uses 8 of the 10 available $`1`$-dimensional representations and 6 of the 8 available $`8`$-dimensional representations. In addition to the six $`27`$-dimensional representations, two $`1`$-dimensional representations and two $`8`$-dimensional representations are also potentially available to correct some two-bit errors. Correcting one type of $`f_{rs}`$ double errors would require a pair of $`1`$-dimensional, $`8`$-dimensional and $`27`$-dimensional subspaces. Based on dimensional considerations, one might expect to correct one type of double error completely using a 9-bit permutationally invariant code. Unfortunately, as will be shown in Section 6.5, this is not possible.

One can still ask what additional errors can be corrected with permutationally invariant 9-bit codes. The operators $`I,\overline{X},\overline{Y},\overline{Z}`$ acting on the code words $`|c_0,|c_1`$ generate an 8-dimensional space. Taking the orthogonal complement in the 10-dimensional subspace spanned by $`\{W_0,W_1\mathrm{}W_9\}`$ yields a two-dimensional subspace. There is a family of linear operators which map $`|c_0,|c_1`$ to a pair of orthogonal vectors in this two-dimensional subspace. Any member of this family can be chosen as an additional correctable error. Similarly, there will be a set of correctable errors which transform as the 8-dimensional representation and whose action on the code words spans the orthogonal complement of the one-bit errors in span$`\left(_{k=1}^8𝒰_k^8\right)`$. Although a procedure for obtaining these operators can be written down, we have been unable to characterize them in a useful way.

## 6 Special cases

### 6.1 n = 5

When $`n=5`$, conditions (I) and (II) hold, and all $`a_k`$ are real, the three necessary and sufficient conditions in Theorem 1 become

$`a_2a_4=0`$
$`a_0a_4+3a_2^2=0`$
$`a_0^2+2a_2^23a_4^2=0.`$
It is easy to verify that these have no non-trivial solution. This is not surprising. It is well-known that the 5-bit code for correcting all one-bit quantum errors is essentially unique and is not permutationally symmetric.

Nevertheless, there is still something to be learned by looking at 5-bit codes. As discussed in section 5.3, the simple repetition code

$`|c_0=|00000,|c_1=|11111`$ (63)
corrects both all single and all double bit flips, and

$`|C_0=`$ $`H^5|c_0+H^5|c_1`$ $`=W_0+W_2+W_4`$ (64a)
$`|C_1=`$ $`H^5|c_0H^5|c_1`$ $`=W_5+W_3+W_1`$ (64b)
corrects all single and double phase errors. In fact, when $`n=5`$, equations (61a) and (61b) imply that the only codes satisfying conditions (I) and (II) are those with $`|a_0|^2=|a_2|^2=|a_4|^2`$.

Moreover, both codes can correct all double errors of the form $`X_jX_k`$, $`Y_jY_k`$, $`Z_jZ_k`$. To see this, note that $`Z_rZ_s|\psi =|\psi `$ on the span of (63) so that (62) implies $`X_rX_s|\psi =Y_rY_s|\psi `$, i.e., the pair $`\{Z_rZ_s,I\}`$ is degenerate and this induces a degeneracy on the pair $`\{X_rX_s,Y_rY_s\}`$.

Thus, the 5-bit codes (63) and (64) can each correct more types of quantum errors than one might expect from their classical distance properties. They are optimal for the correction of all one-bit and two-bit errors of a particular type (phase or bit flip) and can not correct additional one-bit errors. Nevertheless they can correct additional types of two-bit errors.

### 6.2 n = 7

When $`n=7`$, conditions (I) and (II) hold, and all $`a_k`$ are real, the three conditions in Theorem 1 become

$`3a_2a_6+5a_4^2=0`$ (65a)
$`a_0a_6+15a_2a_4=0`$ (65b)
$`a_0^2+9a_2^25a_4^25a_6^2=0.`$ (65c)
It is not hard to see that $`a_6=0`$ implies all $`a_k=0`$. Therefore we can divide through by $`a_6`$ or, equivalently, assume without loss of generality that $`a_6=1`$. Then (65a) and (65b) imply $`a_2=\frac{5}{3}a_4^2`$ and $`a_0=25a_4^3`$. Letting $`x=a_4^2`$ and substituting in (65c) yields

$$125x^3+5x^2x1=0,$$

to which $`x=\frac{1}{5}`$ is the only real solution, giving

$$a_0=\pm \sqrt{5}a_2=\frac{1}{3}a_4=\pm \frac{1}{\sqrt{5}}a_6=1.$$

It is then straightforward to verify that both signs in the normalized vector

$`|c_0`$ $`=`$ $`\frac{1}{8}\left[\pm \sqrt{15}\widehat{W}_0\sqrt{7}\widehat{W}_2\pm \sqrt{21}\widehat{W}_4+\sqrt{21}\widehat{W}_6\right]`$ (66)
yield acceptable codes. This gives two distinct new codes when $`n=7`$.

It is interesting — and a good check — to write the vectors $`\overline{X}|c_1,\overline{Y}|c_1,\overline{Z}|c_0`$ and see that together with $`|c_0`$ they form an orthogonal set. Up to normalizing scalars, we have

$`\overline{Z}|c_0`$ $`=`$ $`\sqrt{\frac{1}{7}}\left[\pm \sqrt{35}\widehat{W}_0\sqrt{3}\widehat{W}_2\widehat{W}_45\widehat{W}_6\right]`$
$`\overline{X}|c_1`$ $`=`$ $`\sqrt{\frac{1}{7}}\left[\sqrt{7}\widehat{W}_0+\sqrt{3}(2\pm \sqrt{5})\widehat{W}_2+(\pm 4\sqrt{5})\widehat{W}_4+(\pm \sqrt{5}2)\widehat{W}_6\right]`$
$`\overline{Y}|c_1`$ $`=`$ $`\sqrt{\frac{1}{7}}\left[\sqrt{7}\widehat{W}_0+\sqrt{3}(2\sqrt{5})\widehat{W}_2+(\pm 4+\sqrt{5})\widehat{W}_4+(\sqrt{5}2)\widehat{W}_6\right]`$
Remark: One might ask if one can obtain additional permutationally invariant 7-bit codes by allowing complex coefficients. In that case the following equations are necessary and sufficient.

$`0`$ $`=`$ $`10|a_4|^2+3(\overline{a}_2a_6+a_2\overline{a}_6)`$ (67a)
$`0`$ $`=`$ $`\overline{a}_2a_6a_2\overline{a}_6`$ (67b)
$`0`$ $`=`$ $`(\overline{a}_0a_6+a_0\overline{a}_6)+15(\overline{a}_2a_4+a_2\overline{a}_4)`$ (67c)
$`0`$ $`=`$ $`(a_0\overline{a}_6\overline{a}_0a_6)+5(a_2\overline{a}_4\overline{a}_2a_4)`$ (67d)
$`0`$ $`=`$ $`|a_0|^2+9|a_2|^25|a_4|^25|a_6|^2`$ (67e)
$`0`$ $`=`$ $`(\overline{a}_0a_2a_0\overline{a}_2)+10(\overline{a}_2a_4a_2\overline{a}_4)+5(\overline{a}_4a_6a_4\overline{a}_6).`$ (67f)
As in the real case, $`a_6=0`$ forces all coefficients to be zero, so we can assume $`a_6=1`$. Then (67b) implies that $`a_2`$ is real and (67b) that $`a_2=(5/3)|a_4|^2`$. However, (67d) and (67f) yield a pair of linear equations for $`\mathrm{Im}a_0`$ and $`\mathrm{Im}a_4`$ which have a non-zero solution if and only if $`a_2=+1`$ which is not consistent with $`a_2=(5/3)|a_4|^2`$. Thus, there are no permutationally invariant 7-bit codes other than those in (66).

### 6.3 n = 9

When $`n=9`$, conditions (I) and (II) hold, and all $`a_k`$ are real, the three conditions in Theorem 1 become

$`a_2a_8+7a_4a_6=0`$ (68a)
$`35a_4^2+a_0a_8+28a_2a_6=0`$ (68b)
$`a_0^2+20a_2^2+14a_4^228a_6^27a_8^2=0.`$ (68c)
We now show that these have have infinitely many solutions. First, suppose $`a_8=0`$, so that the first equation becomes $`a_4a_6=0`$. If $`a_6=0`$, then all the coefficients are zero. If $`a_4=0`$ then we find the only possibility is $`a_2=0`$ and $`a_0^2=28a_6^2`$, giving the two solutions found in . To find the remaining solutions we may assume $`a_8=1`$.

If $`a_6=0`$, then also $`a_2=0`$ and $`a_0=35a_4^2`$ where $`a_4^2=x`$ is the positive root of the quadratic equation $`175x^2+2x1=0`$. This gives two more solutions. If $`a_0=0`$, then we find all of the remaining coefficients depend on $`a_6^2=t`$, where $`t`$ is a positive root of the cubic $`f(t)=(28^3/5)t^3+(228^2/5)t^24t1`$:

$$a_4=(28/5)t,a_6=\pm \sqrt{t},a_2=(728)t.$$

Since $`f(0)<0`$ and $`f(1)>0`$, $`f`$ does have a positive root (approximately $`t=0.478`$), and this gives two more solutions.

There are no further solutions with any of the $`a_k`$ equal to zero, so now assume they are all nonzero. Writing $`x=a_6^2`$ and $`t=a_4`$, it follows that

$$a_2=\pm 7\sqrt{x}ta_0=7(28tx5t^2)$$

where $`x`$ and $`t`$ satisfy the equation

$$x^2(5488t^2)+4x(490t^3+35t^21)+(175t^4+2t^21)=0.$$

Using Maple, one can verify that there are infinitely many values of $`t`$ (e.g., all for which $`0.25<t<0.4`$) for which this quadratic in $`x`$ has at least one positive solution. Thus there are infinitely many solutions in which all the coefficients $`a_{2m}`$ are non-zero real numbers.

### 6.4 Conditions for double error correction with 9-bit codes

As discussed in Section 5.2, a 9-bit permutationally invariant codes which can correct all errors of type $`Z_rZ_s`$ as well as all one-bit errors, must satisfy at least 9 conditions. In the notation of Section 3, there are six of the form $`b_{IX}=b_{IY}=b_{ZX}=b_{ZY}=b_{ZZ,X}=b_{ZZ,Y}=0`$ and three of the form $`d_{XY}=d_{IZ}=d_{Z,ZZ}=0`$.

First, consider the conditions (34), (35) and (54) which correspond to the requirements $`\overline{f}c_0,(\overline{X}+i\overline{Y})c_1=0`$ with $`f=I,Z`$ or $`ZZ`$. For $`n=9`$ these are equivalent to

$`\overline{a}_2a_8+7\overline{a}_4a_6`$ $`+7\overline{a}_6a_4`$ $`+\overline{a}_8a_2=0`$ (69a)
$`5\overline{a}_2a_8+7\overline{a}_4a_6`$ $`21\overline{a}_6a_4`$ $`7\overline{a}_8a_2=0`$ (69b)
$`2\overline{a}_2a_87\overline{a}_4a_6`$ $`+5\overline{a}_8a_2=0.`$ (69c)
These can be treated as a set of 3 linear equations in the 4 unknowns, $`\overline{a}_2a_8`$, $`\overline{a}_4a_6,\overline{a}_6a_4,\overline{a}_8a_2`$ from which one finds that the group (69) is equivalent to

$`\overline{a}_2a_8=\overline{a}_8a_2=i\nu `$ (70a)
$`\overline{a}_4a_6=\overline{a}_6a_4=i{\displaystyle \frac{3}{7}}\nu `$ (70b)
for some real parameter $`\nu `$. Note also that $`\mathrm{Re}\overline{a}_4a_6=\mathrm{Re}\overline{a}_2a_8=0`$ implies that any real solutions must have $`a_4a_6=a_2a_8=0`$. However, all such solutions have been found above and none satisfy the additional requirements below. Hence, correcting all double-$`Z`$ errors does require complex coefficients.

Next we consider the conditions (36), (37) and (55) which correspond to the requirements $`\overline{f}c_0,(\overline{X}i\overline{Y})c_1=0`$ with $`f=I,Z`$ or $`ZZ`$. These become

$`\overline{a}_0a_8+28\overline{a}_2a_6+70|a_4|^2`$ $`+28\overline{a}_6a_2`$ $`+\overline{a}_8a_0=0`$ (71a)
$`9\overline{a}_0a_8+140\overline{a}_2a_6+70|a_4|^2`$ $`84\overline{a}_6a_2`$ $`7\overline{a}_8a_0=0`$ (71b)
$`9\overline{a}_0a_8+56\overline{a}_2a_670|a_4|^2`$ $`+5\overline{a}_8a_0=0`$ (71c)
which can be rewritten as

$`\mathrm{Re}\overline{a}_0a_8+28\mathrm{Re}\overline{a}_2a_6+`$ $`35|a_4|^2`$ $`=0`$ (72a)
$`7\mathrm{Re}\overline{a}_0a_8+28\mathrm{Re}\overline{a}_2a_6`$ $`35|a_4|^2`$ $`=0`$ (72b)
$`\mathrm{Im}\overline{a}_0a_8+14\mathrm{Im}\overline{a}_2a_6`$ $`=0`$ (72c)
since (71a) and (71b) have the same real part while (71b) and (71c) have the same imaginary part. Equations (72a) and (72b) are equivalent to

$`\mathrm{Re}\overline{a}_0a_8`$ $`=`$ $`{\displaystyle \frac{35}{3}}|a_4|^2`$ (73a)
$`\mathrm{Re}\overline{a}_2a_6`$ $`=`$ $`{\displaystyle \frac{5}{3}}|a_4|^2.`$ (73b)
To these conditions we need to add the requirements $`\overline{X}c_j,i\overline{Y}c_j=c_j,\overline{Z}c_j=\overline{Z}c_j,\overline{ZZ}c_j=0`$ which become.

$`|a_0|^2+20|a_2|^2+14|a_4|^228|a_6|^27|a_8|^2`$ $`=`$ $`0`$ (74a)
$`9|a_0|^2+40|a_2|^214|a_4|^235|a_8|^2`$ $`=`$ $`0`$ (74b)
$`\mathrm{Im}\overline{a}_0a_2+21\mathrm{Im}\overline{a}_2a_4+35\mathrm{Im}\overline{a}_4a_6+7\mathrm{Im}\overline{a}_6a_8`$ $`=`$ $`0.`$ (74c)
The last equation (74c) is precisely the condition $`\mathrm{Im}\overline{X}c_j,i\overline{Y}c_j=0`$ and is obtained as the reduction of (116) when $`n=9`$ and conditions I and II hold.

To recap, we have three groups of equations; namely, (69) from the conditions $`b_{fX}+ib_{fY}=0`$, (71) from the conditions $`b_{fX}ib_{fY}=0`$, and (74) from the conditions $`d_{XY}=d_{IZ}=d_{Z,ZZ}=0`$. In what follows, we will use the equivalent conditions (70) in place of (69), and (73) or (72c) in place of (71).

### 6.5 Limits on correction of $`\overline{ZZ}`$ and one-bit errors

To analyze the conditions obtained above, write $`a_k=x_k+iy_k`$. We can assume without loss of generality that $`a_8=1`$; then (70a) implies that $`a_2=i\nu `$ and (73) implies $`y_6=\frac{5}{3\nu }|a_4|^2`$. We also have that (70b) implies $`a_6=\frac{3\nu }{7}\frac{1}{|a_4|^2}a_4i`$ from which we can conclude $`y_6=\frac{3\nu }{7}\frac{x_4}{|a_4|^2}`$. Equating the two expressions above for $`y_6`$ yields

$`\nu ^2`$ $`=`$ $`{\displaystyle \frac{35}{9}}{\displaystyle \frac{|a_4|^4}{x_4}}`$ (75)
which implies that $`x_4<0`$. Under the assumption $`a_8=1`$, (74c) becomes

$`0`$ $`=`$ $`\nu \left(x_021x_4+15{\displaystyle \frac{7}{\nu }}y_6\right)`$ (76)
$`=`$ $`\nu \left({\displaystyle \frac{35}{3}}|a_4|^2+21|x_4|+15+{\displaystyle \frac{35}{3\nu ^2}}|a_4|^2\right)`$
The last equation implies that either $`\nu =0`$ or $`a_4=0`$, either of which generates only a trivial solution. Thus there is no non-trivial solution to the seven equations (69), (71) and (74c).

By Theorem 7, this implies that there is no 9-bit permutationally invariant code which can correct all one-bit errors as well as one type of double error.

One might wonder if there is a 9-bit code which satisfies all the conditions above, except (74c). Such a code would still be of some interest. It would be able to correct all single and double $`Z`$ errors, and detect all single $`X`$ and $`Y`$ errors. However, it would not be able to correct $`X_k`$ and $`Y_k`$ errors because it could not reliably distinguish between them. Unfortunately, even this is not possible.

We return to the equations (69) and (71) and observe that there are infinitely many solutions that can be expressed using one complex variable $`a_4`$, or two real variables $`x_4,y_4`$, in either case with the constraint $`\mathrm{Im}a_4=x_4<0`$. Let $`x=x_4>0`$ and $`y=y_4`$. Then we have

$`a_0`$ $`={\displaystyle \frac{35}{3}}\left(12i{\displaystyle \frac{y_4}{x_4}}\right)|a_4|^2`$ $`|a_0|^2`$ $`={\displaystyle \frac{35^2}{9}}{\displaystyle \frac{x^2+4y^2}{x^2}}(x^2+y^2)^2`$
$`a_2`$ $`=i\nu =\pm i{\displaystyle \frac{\sqrt{35}}{3}}{\displaystyle \frac{|a_4|^2}{\sqrt{|x_4|}}}`$ $`|a_2|^2`$ $`={\displaystyle \frac{35}{9}}{\displaystyle \frac{(x^2+y^2)^2}{x}}`$
$`a_4`$ $`=x_4+iy_4`$ $`|a_4|^2`$ $`=x^2+y^2`$
$`a_6`$ $`=\pm i{\displaystyle \frac{\sqrt{35}}{7}}{\displaystyle \frac{a_4}{\sqrt{|x_4|}}}`$ $`|a_6|^2`$ $`={\displaystyle \frac{5}{7}}{\displaystyle \frac{x^2+y^2}{x}}`$
$`a_8`$ $`=1`$ $`|a_8|^2`$ $`=1.`$
Substituting into (74a) and (74b) yields two equations in two unknowns which have no solution. Thus, there is no 9-bit code which satisfies all the desired equations except (74c).

We also considered the possibility of dropping all $`Y_k`$ conditions to find a code which could correct all errors of the form single $`X_k`$, single $`Z_k`$ and double $`Z_jZ_k`$. However, this is as restrictive as dropping only (74c).

## 7 Concluding Remarks

Permutationally invariant codes which can correct all one-bit errors require a minimum of seven qubits. We have shown that there are two distinct 7-bit codes of this type. Although one might expect that 9-bit codes could also correct one class of double errors, a detailed analysis shows that this is not possible. Even a 9-bit code which could correct all one-bit errors of the form $`X_k`$ and $`Z_k`$ and all two bit errors of the form $`Z_jZ_k`$ does not exist. If one modifies this to the requirement that the code be able to correct all one bit errors of the form $`X_k`$ and double errors of the form $`X_jX_k`$ and $`Z_jZ_k`$, this can be done. However, it does not require 9-bits; it can be achieved using the simple 5-bit repetition code (63) which can correct all double errors of the form $`X_jX_k`$ and $`Y_jY_k`$ as well.

Permutationally invariant codes are highly degenerate, since all $`\left(\genfrac{}{}{0pt}{}{n}{2}\right)`$ exchange errors are equivalent to the identity. As discussed in Section 5.3, and illustrated by the 5-bit repetition code, this degeneracy can sometimes lead to enhanced ability to correct two-bit errors. However, there are also limitations on their ability to correct all two-bit errors of a given type as well as all one-bit errors, as shown by our analysis of of 9-bit codes. Although the reasons for this remain unclear, it may be that the “degeneracy enhancement” also gives hidden constraints, i.e., that one is implicitly trying to correct more two-bit errors than those from which the conditions were obtained.

We have concentrated here on the construction of permutationally invariant codes. Actual implementation would require a number of additional considerations. For example, one would need a mechanism for initializing the computer in states corresponding to $`|c_0|c_0\mathrm{}|c_0`$. One could then obtain any state of the form $`|c_{k_1}|c_{k_2}\mathrm{}|c_{k_m}`$ with $`k_i\{0,1\}`$ by application of $`_{j=1}^nX_{\kappa n+j}`$ for suitable choices of $`\kappa `$. One also needs a mechanism for decoding, including a set of measurements which can distinguish between the different error subspaces, as well as a circuit for implementing the error correction process.

Finally, one needs a set of gates for universal computation. As noted in Section 2.3, the logical $`X`$ and $`Z`$ operations are easily implemented as products of their single-bit counterparts. The logical $`Y`$ is given by the product $`i[_jX_j][_jZ_j]=(1)^{(n1)/2}[_jY_j]`$ when $`n`$ is odd. Moreover, the $`X,Y,Z`$ gates all lie in the commutant of $`S_n`$. This implies that all gates needed for universal computation (including a non-trivial two-bit gate) also lie in the commutant since they can be written as linear combinations of these operations, the identity, and their products. (Alternatively, one could observe that all logical actions on code words must be permutationally symmetric and, hence, lie in the commutant of $`S_n`$.) However, this does not necessarily mean that all the desired gates can be implemented as products of a small set of one and two-bit gates. We leave the question of a practical implementation of a universal set of gates on code words for further investigation.

We have only begun to explore the potential of non-Abelian stabilizer codes for quantum error correction; other examples should be studied. In addition to the issues identified above, there may be others which arise if one wants to combine non-Abelian stabilizers with other approaches to fault tolerant computation.

Acknowledgment: Parts of this work were done while MBR was an exchange professor at the University of Massachusetts Amherst and while HP was at the University of Sussex and Queen Mary College of the University of London during her sabbatical. The authors are grateful to these institutions for their hospitality.

## Appendix A Differences of one-bit errors

In this section we will need some additional notation. Let $`\epsilon _r`$ denote the binary n-tuple with components $`\epsilon _j=\delta _{jr}`$ so that $`v+\epsilon _r`$ has components $`v_j+\delta _{jr}`$ with addition mod 2. Let $`\overline{1}`$ be the binary n-tuple with all elements equal to $`1`$. We will use $`\mathrm{s}(v)=\{j:v_j0\}`$ to denote the support of of $`v=(v_1,\mathrm{},v_n)`$.

It will be convenient to also introduce the vector

$`V_k(r,s)={\displaystyle \underset{\begin{array}{c}\mathrm{wt}(v)=k\\ r,s\mathrm{s}(v)\end{array}}{}}(|v+\epsilon _r|v+\epsilon _s)`$ (79)
which is well-defined for $`k=0,1,\mathrm{}(n2)`$, and has the following properties when $`rs`$.

$`V_k(r,s),W_{\mathrm{}}`$ $`=`$ $`0\text{for all}r,s,k,\mathrm{}`$ (80)
$`V_k(r,s),V_{\mathrm{}}(q,t)`$ $`=`$ $`0\text{for}m\mathrm{}r,s,q,t`$ (81)
$`V_k(r,s),V_k(r,s)`$ $`=`$ $`2\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{k}}\right)`$ (82)
$`V_k(r,s),V_k(r,t)`$ $`=`$ $`\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{k}}\right)\text{for}r,s,t\text{all distinct}.`$ (83)
These are all straightforward, except (83) which follows from

$`V_k(r,s),V_k(r,t)=\left({\displaystyle \genfrac{}{}{0pt}{}{n3}{k}}\right)+\left({\displaystyle \genfrac{}{}{0pt}{}{n3}{k1}}\right)`$
and the easily verified combinatoric identity $`\left(\genfrac{}{}{0pt}{}{n2}{k}\right)=\left(\genfrac{}{}{0pt}{}{n3}{k}\right)+\left(\genfrac{}{}{0pt}{}{n3}{k1}\right)`$.

An important consequence of (82) and (83) is that they imply that, for $`st`$,

$`V_k(r,s),V_k(r,s)=2V_k(r,s),V_k(r,t).`$ (84)
This result plays an essential role in section 4.4.

Our main results are that, for any code of the general form (9),

$`(Z_rZ_s)|c_0`$ $`=`$ $`2{\displaystyle \underset{k=1}{\overset{n1}{}}}a_kV_{k1}(r,s)`$ (85a)
$`(X_rX_s)|c_0`$ $`=`$ $`{\displaystyle \underset{k=0}{\overset{n2}{}}}(a_ka_{k+2})V_k(r,s)`$ (85b)
$`i(Y_rY_s)|c_0`$ $`=`$ $`{\displaystyle \underset{k=0}{\overset{n2}{}}}(a_k+a_{k+2})V_k(r,s)`$ (85c)
with similar equations for $`|c_1`$ and $`b_k`$. Under the assumption that conditions (I) and (II) hold, we find the following variants useful

$`(Z_rZ_s)|c_1`$ $`=`$ $`2{\displaystyle \underset{m=0}{\overset{(n1)/2}{}}}a_{n2m1}V_{2m}(r,s)`$ (86a)
$`\left[(X_rX_s)+i(Y_rY_s)\right]|c_0`$ $`=`$ $`2{\displaystyle \underset{m=0}{\overset{(n3)/2}{}}}a_{2m}V_{2m}(r,s)`$ (86b)
$`\left[(X_rX_s)i(Y_rY_s)\right]|c_0`$ $`=`$ $`2{\displaystyle \underset{m=1}{\overset{(n1)/2}{}}}a_{2m}V_{2m2}(r,s).`$ (86c)
To prove (85a) and (86) in the case of $`Z_r`$, it suffices to observe that

$`(Z_rZ_s)W_k=\{\begin{array}{ccc}0\hfill & \text{for}& k=0,n\hfill \\ 2V_{k1}(r,s)\hfill & \text{for}& 1kn1\hfill \end{array}`$ (89)
which is easily verified.

Equations (85b) and (85c) can be verified by some rather straightforward, but tedious, computations and combinatorics. One approach is to write out the effect of the errors $`X_r`$ and $`Y_r`$. Since these results are identical except for the signs of some terms, we introduce

$`\omega _{XY}\{\begin{array}{ccc}+1& \text{for}& X\\ 1& \text{for}& iY\end{array}`$ (92)
and write the equations only for $`X_r`$ with the understanding that these results hold for $`Y_r`$ with the sign changes indicated by $`\omega _{XY}`$

$`X_rW_0`$ $`=`$ $`|\epsilon _r`$
$`X_rW_k`$ $`=`$ $`{\displaystyle \underset{\begin{array}{c}\mathrm{wt}(v)=k\\ r\mathrm{s}(v)\end{array}}{}}|v+\epsilon _r+\omega _{XY}{\displaystyle \underset{\begin{array}{c}\mathrm{wt}(u)=k1\\ rs(u)\end{array}}{}}|u\text{for }\mathrm{\hspace{0.33em}1}kn1`$ (97)
$`X_rW_n`$ $`=`$ $`\omega _{XY}|\overline{1}+\epsilon _r.`$
For distinct $`r`$, $`s`$, we want to determine the effect of the differences $`X_rX_s`$, $`Y_rY_s`$ on the $`W_k`$, and for this purpose, the following expression, which we write only for $`2kn2`$, is useful.

$`X_rW_k`$ $`=`$ $`{\displaystyle \underset{\begin{array}{c}\mathrm{wt}(v)=k\\ r,s\mathrm{s}(v)\end{array}}{}}|v+\epsilon _r+{\displaystyle \underset{\begin{array}{c}\mathrm{wt}(v)=k1\\ r,s\mathrm{s}(v)\end{array}}{}}|v+\epsilon _s+\epsilon _r`$ (102)
$`+\omega _{XY}{\displaystyle \underset{\begin{array}{c}\mathrm{wt}(u)=k1\\ r,ss(u)\end{array}}{}}|u+\omega _{XY}{\displaystyle \underset{\begin{array}{c}\mathrm{wt}(u)=k2\\ r,ss(u)\end{array}}{}}|u+\epsilon _s`$ (107)
Then (107) implies

$`(X_rX_s)W_0`$ $`=`$ $`|\epsilon _r|\epsilon _s=V_0(r,s)`$
$`(X_rX_s)W_1`$ $`=`$ $`{\displaystyle \underset{jr,s}{}}(|\epsilon _j+\epsilon _r|\epsilon _j+\epsilon _s)=V_1(r,s)`$
$`(X_rX_s)W_k`$ $`=`$ $`V_k(r,s)\omega _{XY}V_{k2}(r,s)`$
$`(X_rX_s)W_{n1}`$ $`=`$ $`\omega _{XY}{\displaystyle \underset{jr,s}{}}(|\overline{1}+\epsilon _j+\epsilon _r|\overline{1}+\epsilon _j+\epsilon _s)=\omega _{XY}V_{n3}(r,s)`$
$`(X_rX_s)W_n`$ $`=`$ $`\omega _{XY}(|\overline{1}+\epsilon _r|\overline{1}+\epsilon _s)=\omega _{XY}V_{n2}(r,s).`$
To analyze double phase errors, first observe that when $`\overline{f}c_i,\overline{ZZ}c_j=0`$ (with $`f=X,Y,Z`$), the analogous inner products involving $`(n1)`$-dimensional representations will be zero if and only if $`(f_1f_t)c_i,Z_rZ_sc_j=0`$. By considering the action of the transposition $`(1t)`$, one can show that this holds whenever $`\{1,t\}=\{r,s\}`$ or $`\{1,t\}\{r,s\}=\mathrm{}`$. Hence, it suffices to consider $`r=1`$ and $`ts`$, in which case one can use (85a) and $`Z_1Z_s=IZ_1(Z_1Z_s)`$ to conclude that

$`Z_1Z_s|c_0=|c_0+2{\displaystyle \underset{k=1}{\overset{n1}{}}}a_kZ_1V_{k1}(1,s).`$ (108)
We will also need the formula

$`Z_1V_k(1,s),V_k(1,t)=\left({\displaystyle \genfrac{}{}{0pt}{}{n3}{k1}}\right)\left({\displaystyle \genfrac{}{}{0pt}{}{n3}{k}}\right)={\displaystyle \frac{2k+2n}{n2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{k}}\right)`$ (109)
which follows from (7) with $`N=n3`$.

We now let $`f=Z`$. Using (85a) again and (109) with $`k=2m1`$, one finds $`(Z_1Z_t)c_0,Z_1Z_sc_0=0`$ if and only if

$`{\displaystyle \underset{m=1}{\overset{(n1)/2}{}}}|a_{2m}|^2{\displaystyle \frac{4mn}{n2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{2m}}\right)=0.`$ (110)
Then it follows from $`\frac{2kn}{n2}\left(\genfrac{}{}{0pt}{}{n2}{k1}\right)=\frac{(2kn)k(nk)}{n(n1)(n2)}\left(\genfrac{}{}{0pt}{}{n}{k}\right)`$ that (110) is equivalent to (60b) minus $`n^2n`$ times equation (60a). Thus, the “block” conditions for double phase errors do not add additional constraints when conditions (I) and (II) hold.

The cases $`f=X\pm iY`$, and $`i=0,j=1`$, can be dealt with similarly, but are not needed here. We note only that, unlike the case $`f=Z`$, they do generate additional constraints.

## Appendix B Decomposition into irreducibles

In view of the repeated use of decompositions into irreducible subspaces, we explicitly write out some of them. Recall that $`𝐂^{2^n}=_{k=0}^n𝒲_k`$; each $`𝒲_k`$ is the eigenspace of the operator $`S_z\frac{1}{2}_kZ_k=\frac{n}{2}\overline{Z}`$ with eigenvalue $`\frac{1}{2}(n2k)`$. Each $`𝒲_k`$ can be further decomposed into a direct sum of subspaces which transform as irreducible representations of $`S_n`$. In fact, the action of $`S_n`$ on $`𝒲_k`$ or $`𝒲_{nk}`$ is its action on sets of size $`k`$ in $`\{1,\mathrm{},n\}`$. For $`0k\frac{n}{2}`$, $`𝒲_k`$ is known to decompose into a sum of irreducible subspaces indexed by the partitions $`[nj,j]`$ for $`j=0,\mathrm{},k`$, each appearing once. Physicists may recognize that this is equivalent to a decomposition into simultaneous eigenspaces of $`S_z`$ and the total spin222In this one paragraph, we use the familiar $`S_x,S_y,S_z`$, rather than the equivalent $`\frac{n}{2}\overline{X},\frac{n}{2}\overline{Y},\frac{n}{2}\overline{Z}`$, to denote the components of spin, and trust that context suffices to distinguish them from the symmetric group denoted $`S_n`$, which is a very different entity.  operator $`𝐒^2=S_x^2+S_y^2+S_z^2`$ with eigenvalue $`s(s+1)`$ for $`s=\frac{n}{2},\frac{n}{2}1,\mathrm{}\frac{1}{2}|n2k|`$.

To facilitate use in counting arguments, as in Section 5.4, we adopt the convention of labeling an irreducible subspace (in part) by its dimension. Thus, $`𝒰_k^d`$ denotes an irreducible subspace of $`𝒲_k`$ with dimension $`d`$.

For $`n=5`$

$`𝒲_0`$ $`=`$ $`𝒰_0^1`$
$`𝒲_1`$ $`=`$ $`𝒰_1^1𝒰_1^4`$
$`𝒲_2`$ $`=`$ $`𝒰_2^1𝒰_2^4𝒰_2^5`$
$`𝒲_3`$ $`=`$ $`𝒰_3^1𝒰_3^4𝒰_3^5`$
$`𝒲_4`$ $`=`$ $`𝒰_4^1𝒰_4^4`$
$`𝒲_5`$ $`=`$ $`𝒰_5^1`$
For $`n=7`$

$`𝒲_0`$ $`=`$ $`𝒰_0^1`$
$`𝒲_1`$ $`=`$ $`𝒰_1^1𝒰_1^6`$
$`𝒲_2`$ $`=`$ $`𝒰_2^1𝒰_2^6𝒰_2^{14}`$
$`𝒲_3`$ $`=`$ $`𝒰_3^1𝒰_3^6𝒰_3^{14}𝒰_4^{\stackrel{~}{14}}`$
$`𝒲_4`$ $`=`$ $`𝒰_4^1𝒰_4^6𝒰_4^{14}𝒰_4^{\stackrel{~}{14}}`$
$`𝒲_5`$ $`=`$ $`𝒰_5^1𝒰_5^6𝒰_5^{14}`$
$`𝒲_6`$ $`=`$ $`𝒰_6^1𝒰_6^6`$
$`𝒲_7`$ $`=`$ $`𝒰_7^1`$
where $`𝒰_2^{14}`$ denotes the irreducible representation associated with the partition $`[5,2]`$ and $`𝒰_4^{\stackrel{~}{14}}`$ a second, distinct, 14-dimensional irreducible representation associated with $`[4,3]`$. In terms of spin, $`𝒰_2^{14}`$ has $`s=\frac{3}{2}`$ and $`𝒰_4^{\stackrel{~}{14}}`$ has $`s=\frac{1}{2}`$.

For $`n=9`$

$`𝒲_0`$ $`=`$ $`𝒰_0^1`$
$`𝒲_1`$ $`=`$ $`𝒰_1^1𝒰_1^8`$
$`𝒲_2`$ $`=`$ $`𝒰_2^1𝒰_2^8𝒰_2^{27}`$
$`𝒲_3`$ $`=`$ $`𝒰_3^1𝒰_3^8𝒰_3^{27}𝒰_4^{48}`$
$`𝒲_4`$ $`=`$ $`𝒰_4^1𝒰_4^8𝒰_4^{27}𝒰_4^{48}𝒰_4^{42}`$
$`𝒲_5`$ $`=`$ $`𝒰_5^1𝒰_5^8𝒰_5^{27}𝒰_5^{48}𝒰_4^{42}`$
$`𝒲_6`$ $`=`$ $`𝒰_6^1𝒰_6^8𝒰_6^{27}𝒰_4^{48}`$
$`𝒲_7`$ $`=`$ $`𝒰_7^1𝒰_7^8𝒰_7^{27}`$
$`𝒲_8`$ $`=`$ $`𝒰_8^1𝒰_8^8`$
$`𝒲_9`$ $`=`$ $`𝒰_9^1`$
## Appendix C Complex coefficients

If the $`a_k`$ are not real, then one must modify the analysis in Section 4 accordingly, and require both real and imaginary parts of the resulting equations to be zero. We again use the classification of error conditions described at the end of Section 3. We omit the details and summarize the results.

* Setting the real parts of (34)-(37) to zero yields the pair of equations

$`0`$ $`=`$ $`{\displaystyle \frac{n+1}{2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n+1}{2}}}\right)a_{\frac{n+1}{2}}^2+2{\displaystyle \underset{k=1}{\overset{(n1)/2}{}}}k\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)\mathrm{Re}(\overline{a}_ka_{nk+1})`$ (111)
$`0`$ $`=`$ $`{\displaystyle \frac{n+1}{2}}\left({\displaystyle \genfrac{}{}{0pt}{}{n}{\frac{n1}{2}}}\right)a_{\frac{n1}{2}}^2+2{\displaystyle \underset{k=0}{\overset{(n3)/2}{}}}(nk)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)\mathrm{Re}(\overline{a}_ka_{nk1}).`$ (112)
The imaginary parts of both (34) and (36) are always zero and do not place any additional restrictions on $`a_k`$. Setting the imaginary parts of (35) and (37) to zero yields the conditions

$`0`$ $`=`$ $`{\displaystyle \underset{k=1}{\overset{(n1)/2}{}}}\mathrm{Im}[\overline{a}_ka_{nk+1}]k(n2k+1)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right)`$ (113)
$`0`$ $`=`$ $`{\displaystyle \underset{k=0}{\overset{(n1)/2}{}}}\mathrm{Im}[\overline{a}_ka_{nk1}](nk)(n2k1)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right).`$ (114)
* The condition (42) from the off diagonal terms in $`D`$ becomes

$`0={\displaystyle \underset{k=0}{\overset{n}{}}}|a_k|^2(n2k)\left({\displaystyle \genfrac{}{}{0pt}{}{n}{k}}\right).`$ (115)
(This is sufficient to ensure that $`d_{IZ}=0`$ and $`D_{IZ}=0`$, as well as that the real part of (47) is zero.) To ensure that the imaginary part of $`\overline{X}c_i,i\overline{Y}c_i`$ is zero we must also require

$`0`$ $`=`$ $`{\displaystyle \underset{k=1}{\overset{n1}{}}}\mathrm{Im}[\overline{a}_{k+1}a_{k1}].\left({\displaystyle \genfrac{}{}{0pt}{}{n2}{k1}}\right).`$ (116)
(This also ensures that the imaginary part of (47) is zero so that $`d_{XY}=0`$ and $`D_{XY}=0`$.)

As before, we analyze the “block” conditions only under the assumption that conditions (I) and (II) hold. As for real coefficients, these conditions do not yield new requirements.

* Setting the imaginary parts of (44) and (45) to zero yields conditions equivalent to (113) and (114).
* The expression in (47) gives two conditions. The first is equivalent to (115) and the second to (116) with $`k=2m+1`$.


format: text

text:
# Size-dependent decoherence of excitonic states in semiconductor microcrystallites

## Abstract

The size-dependent decoherence of the exciton states resulting from the spontaneous emission is investigated in a semiconductor spherical microcrystallite under condition $`a_BR_0\lambda `$. In general, the larger size of the microcrystallite corresponds to the shorter coherence time. If the initial state is a superposition of two different excitonic coherent states, the coherence time depends on both the overlap of two excitonic coherent states and the size of the microcrystallite. When the system with fixed size is initially in the even or odd coherent states, the larger average number of the excitons corresponds to the faster decoherence. When the average number of the excitons is given, the bigger size of the microcrystallite corresponds to the faster decoherence. The decoherence of the exciton states for the materials GaAs and CdS is numerically studied by our theoretical analysis.

The field of quantum computation and information processing is being extensively investigated due to possibility of finding solutions to some intractable problems on classical computers using the paradigm of quantum mechanics. Superposition principle of quantum mechanics forms the strong basis for the realization of the quantum computation and information processing schemes. The carrier of the quantum information is called as qubit which can take not only logical zero or one values as in its classical counterpart, but also their superposition. Any two-level system is suitable for the realization of qubits.

As low-dimensional semiconductor structures, quantum dots are very promising candidates for carrying quantum information because of their atom-like properties. The experimentalists have made great progress in the coherent observation and manipulation of states in systems of quantum dots st ; jp ; hirayama , including demonstration of the quantum entanglement of excitons in a single dot 5  and a quantum dot molecule 6 , or Rabi oscillations of excitons in single quantum dot kam . The quantum gate realization based on the localized electron spins of quantum dots as qubits has been proposed dot1 . A scheme of the controllable interactions between two distant quantum dot spins by combining the cavity quantum electrodynamics (QED) with electronic spin degrees of freedom in quantum dots was proposed imamoglu , and the degree of quantum entanglement was further analyzed Adam . The reference 7  theoretically investigates the entanglement of excitonic states in the system of the optically driven coupled quantum dots and proposes a method to prepare maximally entangled Bell and Greenberger-Horne-Zeilinger states. An all optical implementation of quantum information processing with semiconductor macro atoms based on excitons was also proposed bb .

It is well known that pure quantum superposition states can hardly survive for a long time. Because the interaction of any system with the surrounding environment is unavoidable in a physical realization, the energy of the superposed state of the system is dissipated into environment or the relative phase of the superposed components is disturbed by the environment. The environment effect on the qubit defined by the exciton state has been investigated liu ; fj ; zanardi  in quantum dot with fixed size. However, in general, one can expect that increasing the size of a quantum dot results in stronger decoherence rates due to the increased overlap between the system and the environment.

In this report, the size-dependent decoherence is discussed in detail for a system of the semiconductor spherical microcrystallite (SSM) whose radius $`R_0`$ is smaller than the wavelength $`\lambda `$ of the relevant radiation field, but much larger than the Bohr radius $`a_B`$ of exciton in bulk semiconductor, i.e. $`a_BR_0\lambda `$. We assume that the excitation density is so low that the average number of excitons in the Bohr radius volume is no more than one. Thus the interactions between the excitons can be neglected. For the optically allowed lowest-energy excitons, the size-dependent Hamiltonian can be given under the rotating wave approximation as han .

$`H`$ $`=`$ $`\mathrm{}\mathrm{\Omega }b^{}b+\mathrm{}{\displaystyle \underset{k}{}}\omega _ka_k^{}a_k`$ (1)
$`+`$ $`\mathrm{}\chi {\displaystyle \underset{k}{}}{\displaystyle \frac{\widehat{e}_k\stackrel{}{\mu }_{cv}}{\sqrt{\mathrm{}ck}}}(b^{}a_k+ba_k^{})`$
with $`\chi =\frac{4\mathrm{\Omega }R_0^{3/2}}{\sqrt{V\pi a_B^3}}`$. Here $`\widehat{e}_k`$ is a unit polarization vector of radiation field, $`\stackrel{}{\mu }_{cv}`$ is interband transition dipole moment, $`V`$ is volume of the microcrystallite, $`k`$ is wave vector of the radiation field, $`a_k(a_k^{})`$ are the annihilation (creation) operators of radiation field with frequency $`\omega _k`$, and $`b(b^{})`$ is the annihilation (creation) operator of the exciton with the transition energy $`\mathrm{}\mathrm{\Omega }=E_gE_{exc}^b+\frac{\mathrm{}^2\pi ^2}{2MR_0^2}`$ where $`E_g`$ is the energy gap between the conduction and valence bands, $`E_{exc}^b`$ is binding energy of the excitons and $`M`$ is the mass for the center-of-mass motion which is a sum of the effective masses $`m_e`$ and $`m_h`$ for the electron and hole, respectively, in the conduction and valence bands, i.e. $`M=m_e+m_h`$. The operators for both radiation field and excitons are bosons. The Hamiltonian (1) shows that both the exciton energy $`\mathrm{\Omega }`$ and the coupling constants $`(\chi \widehat{e}_k\stackrel{}{\mu }_{cv})/\sqrt{\mathrm{}ck}`$ between the exciton and radiation fields depend on the size $`R_0`$ of the microcrystallite, which means that the different sizes of the microcrystallites result in the different decay rates of the excitonic states.

In order to show how the different sizes of microcrystallites affect the coherence of the exciton states, we give the Heisenberg equations of motion for operators of the radiation field and excitons corresponding to Hamiltonian (1) as scully ; Yu-xi

$`{\displaystyle \frac{B(t)}{t}}=`$ $`i\chi {\displaystyle \underset{k}{}}{\displaystyle \frac{\widehat{e}_k\stackrel{}{\mu }_{cv}}{\sqrt{\mathrm{}ck}}}A_k(t)e^{i\omega _kt+i\mathrm{\Omega }t},`$ (2a)
$`{\displaystyle \frac{A_k(t)}{t}}=`$ $`i\chi {\displaystyle \frac{\widehat{e}_k\stackrel{}{\mu }_{cv}}{\sqrt{\mathrm{}ck}}}B(t)e^{i\mathrm{\Omega }t+i\omega _kt},`$ (2b)
where we have applied rotating frame transformation to the exciton and radiation field variables with $`b(t)=B(t)e^{i\mathrm{\Omega }t}`$ and $`a_k(t)=A_k(t)e^{i\omega _kt}`$. Then we can obtain the formal solution of $`A_k(t)`$ as

$$A_k(t)=A_k(0)i\chi \frac{\widehat{e}_k\stackrel{}{\mu }_{cv}}{\sqrt{\mathrm{}ck}}_0^tB(t^{})e^{i\mathrm{\Omega }t^{}+i\omega _kt^{}}dt^{}.$$
(3)
Substituting $`A_k(t)`$ in Eq.(2a), we get

$`{\displaystyle \frac{B(t)}{t}}`$ $`=`$ $`i\chi {\displaystyle \underset{k}{}}{\displaystyle \frac{\widehat{e}_k\stackrel{}{\mu }_{cv}}{\sqrt{\mathrm{}ck}}}A_k(0)e^{i\omega _kt+i\mathrm{\Omega }t}`$ (4)
$``$ $`{\displaystyle _0^t}B(t^{})K(tt^{})𝑑t^{}`$
with the time-dependent kernel function

$$K(tt^{})=\chi ^2\underset{k}{}\frac{|\mu _{cv}|^2\mathrm{cos}^2\theta }{\mathrm{}ck}e^{i(\mathrm{\Omega }\omega _k)(t^{}t)},$$
(5)
where $`\theta `$ is the angle between the interband transition dipole moment $`\stackrel{}{\mu }_{cv}`$ and electric field polarization $`\widehat{e}_k`$. Without loss of generality, we assume that the interband transition dipole moment $`\stackrel{}{\mu }_{cv}`$ of the optically allowed exciton is along the $`z`$ axis and radiation is isotropic. In order to give the time-dependent kernel function $`K(tt^{})`$, we change the summation over $`k`$ into integral han

$$\underset{k}{}\frac{2V}{(2\pi )^3}_0^{\mathrm{}}_0^{2\pi }_0^\pi \frac{\omega ^2}{c^3}𝑑\omega \mathrm{sin}\theta d\theta d\phi ,$$
(6)
where the integration is taken only over the volume $`V`$ of the microcrystallite, because the interband transition dipole moment $`\stackrel{}{\mu }_{cv}`$ vanishes outside the microcrystallite. The assumption of $`R_0\lambda `$ makes the polariton effect negligible implying the rapid radiation of excitons due to the breakdown of the translation symmetry. Consequently, we can consider that the radiation light intensity of microcrystallite is going to be centered at the transition frequency $`\mathrm{\Omega }`$, which is known as the Weisskopf-Wigner approximation scully . Then the kernel function is found as

$`K(tt^{})`$ $`=`$ $`32\pi \left({\displaystyle \frac{R_0}{a_B}}\right)^3\gamma _s\delta (t^{}t)`$ (7)
with $`\gamma _s=\frac{4|\mu _{cv}|^2\mathrm{\Omega }^3}{3\mathrm{}(2\pi c)^3}`$ depending on the size of microcrystallite. Replacing the kernel function of Eq.(7) in Eq. (4) and taking the Laplace transform, the exciton operator $`B(t)`$ is found as

$$B(t)=B(0)e^{32\pi (\frac{R_0}{a_B})^3\gamma _st}i\underset{k}{}u_k(t)A_k(0),$$
(8)
$`u_k(t)`$ is given as

$$u_k(t)=\frac{\chi \widehat{e}_k\stackrel{}{\mu }_{cv}}{\sqrt{\mathrm{}ck}}\frac{\mathrm{exp}(64\pi \frac{R_0^3}{a^3}\gamma _st)\mathrm{exp}[i(\omega _k\mathrm{\Omega })t]}{64\pi \frac{R_0^3}{a^3}\gamma _s+i(\omega _k\mathrm{\Omega })}.$$
(9)
From Eq.(8), it can be found that the spontaneous emission rate of exciton is $`64\pi (R_0/a_B)^3`$ times higher than that of an atom which has the transition frequency $`\mathrm{\Omega }`$ and the transition dipole moment $`\stackrel{}{\mu }_{cv}`$ han . This increase in the spontaneous emission rate can be explained by the fact that the exciton is coherently excited over the whole quantum microcrystallite. Thus coherent excitation results in a coherent transition dipole moment and a superradiant character. It is obvious that the information, which is carried by the state of the exciton, is lost with the time evolution because of the energy dissipation due to spontaneous emission of the exciton. The loss rate of the information depends on the factor $`32\pi \left(R_0/a_B\right)^3\gamma _s`$.

Now lets analyze how the size-dependent decoherence affect a qubit defined in the computational basis of the vacuum state $`|0`$ and single-exciton state $`|1`$. If the exciton system is initially in a qubit state $`\alpha |0+\beta |1`$ with $`|\alpha |^2+|\beta |^2=1`$, and the radiation field is initially in the multimode vacuum state $`_k|0_k`$, after an evolution time of $`t`$, the state of the system will become liu ,

$`|\psi (t)=U(t)[\alpha |0+\beta |1]{\displaystyle \underset{k}{}}|0_k`$
$`=\alpha |0{\displaystyle \underset{k}{}}|0_k+\beta U(t)b^{}|0{\displaystyle \underset{k}{}}|0_k`$
$`=[\alpha |0+\beta e^{\{32\pi (\frac{R_0}{a_B})^3\gamma _sti\mathrm{\Omega }t\}}|1]{\displaystyle \underset{k}{}}|0_k`$
$`+\beta |0{\displaystyle \underset{k^{}}{}}u_k^{}(t)e^{i(\mathrm{\Omega }+\omega _k^{})t}|1_k^{}{\displaystyle \underset{kk^{}}{}}|0_k,`$ (10)
where the properties of the time evolution operator $`U^{}(t)bU(t)=b(t)`$ and $`U(t)|0=0`$ with $`U(t)=e^{iHt/\mathrm{}}`$ are applied. Because we are interested in the exciton system, the multimode radiation field degrees of freedom are traced out and the reduced density operator of the exciton system is found as

$`\rho (t)`$ $`=`$ $`(1\eta (t)|\beta |^2)|00|+\alpha \beta ^{}F(t)e^{i\mathrm{\Omega }t}|01|`$ (11)
$`+`$ $`\alpha ^{}\beta F(t)e^{i\mathrm{\Omega }t}|10|+\eta (t)|\beta |^2|11|`$
with $`\eta (t)=\mathrm{exp}\left\{64\pi (\frac{R_0}{a_B})^3\gamma _st\right\}`$. The slowly varying time-dependent factor $`F(t)`$ of the off-diagonal elements in Eq.(11), which can be written as

$$F(t)=\mathrm{exp}\left\{32\pi (\frac{R_0}{a_B})^3\gamma _st\right\}=\mathrm{exp}(t/\tau ),$$
(12)
is used to characterize the coherence of the superposed excitonic state $`\alpha |0+\beta |1`$. The characteristic time $`\tau `$ of the decoherence is given as,

$$\tau =\frac{3\mathrm{}^4\pi ^2c^3a_B^3M^3R_0^3}{2|\mu _{cv}|^2[2MR_0^2(E_gE_{exc}^b)+\mathrm{}^2\pi ^2]^3}.$$
(13)
To give a better insight to the problem, we give some numerical values for the chosen materials, CdS and GaAs. The following characteristic parameters for those materials are taken from references han ; tt . For CdS, $`E_g=2.583`$ eV, $`E_{exc}^b=30`$ meV, $`a_B=30`$ Å, $`\frac{|\mu _{cv}|^2}{(ϵ_0a_B^3)}=0.25`$ meV with the static dielectric constant of the bulk crystal $`ϵ_0=8`$, $`m_e=0.25m_0`$ and $`m_h=1.6m_0`$ where $`m_0`$ is the rest mass of electron. For GaAs, $`E_g=1.52`$ meV, $`E_{exc}^b=5`$ meV, $`a_B=100`$ Å, $`\frac{|\mu _{cv}|^2}{(ϵ_0a_B^3)}=0.025`$ meV with $`ϵ_0=12.53`$, $`m_e=0.0665m_0`$ and $`m_h=0.45m_0`$. The area of the microcrystallite size is taken as $`200`$Å$`R_0500`$Å in Fig. 1. In this range, the wavelength is around $`5000`$ Å for CdS, and $`8000`$ Å for GaAs, thus the condition $`a_BR_0\lambda `$ is satisfied.

In order to show how the characteristic time $`\tau `$ changes with the size $`R_0`$, we give Fig. 1. It is seen that a larger size of the microcrystallite corresponds to a shorter characteristic time $`\tau `$. So the larger is the size of microcrystallite, the faster is the decoherence of the superposition of two exciton states for a given material. But the exciton state for different materials have the different decoherence times even if the size of the microcrystallites are the same. This is due to the different couplings of the systems with the radiation field. Comparing the decoherence characteristic time of CdS and GaAs in Fig. 1, we find that the coherence time of the exciton state for GaAs is longer than that of CdS for a given size. This result shows the importance of material choice in obtaining longer coherence time.

Here, we consider another kind of qubit state formed by the superposition of coherent states, for example, we can define the even coherent state $`𝒩_+[|\alpha +|\alpha ]`$ as the logic zero state $`|0_L`$ and the odd coherent state $`𝒩_{}[|\alpha |\alpha ]`$ as the logic one state $`|1_L`$ where $`𝒩_\pm =(2\pm 2e^{2|\alpha |^2})^{1/2}`$ and $`|\alpha `$ is an eigenstate of the bosonic operator. These states can be prepared by the photon states in cavity quantum electrodynamics and by motional states of trapped ions haroche . Such logical qubit encoding can be used as the correction of the spontaneous emission errors ptc . We first assume that the exciton system is initially in a superposition state of two coherent states $`|\alpha _1`$ and $`|\alpha _2`$ of the exciton annihilation operator

$$|\psi =C|\alpha _1+D|\alpha _2,$$
(14)
and the radiation field is in the multimode vacuum state $`_k|0_k`$. By using the same approach as reference Yu-xi  and Eq.(8), we can find that the time-dependent reduced density operator for the exciton system is

$`\rho (t)`$ $`=`$ $`|C|^2|u(t)\alpha _1u(t)\alpha _1|+CD^{}F(t)|u(t)\alpha _1u(t)\alpha _2|`$ (15)
$`+`$ $`C^{}DF^{}(t)|u(t)\alpha _2u(t)\alpha _1|`$
$`+`$ $`|D|^2|u(t)\alpha _2u(t)\alpha _2|`$
where $`u(t)=\mathrm{exp}\{32\pi (\frac{R_0}{a_B})^3\gamma _sti\mathrm{\Omega }t\}`$ and the time-dependent decoherence factor is

$`F(t)`$ $`=`$ $`\mathrm{exp}\{[{\displaystyle \frac{|\alpha _1|^2}{2}}{\displaystyle \frac{|\alpha _2|^2}{2}}+\alpha _1\alpha _2^{}]`$ (16)
$`\times `$ $`[1\mathrm{exp}\{32\pi ({\displaystyle \frac{R_0}{a_B}})^3\gamma _st\}]\}.`$
It is understood that the decoherence of the superposition state of two coherent states is determined by both the properties of the microcrystallite and the overlap between two coherent states. Due to the existence of the vacuum state component in the excitonic coherent state, it is also observed that the decoherence factor $`F(t)`$ does not tend to zero in the long time limit $`t\mathrm{}`$.

For the qubit states which are defined by the even and odd coherent states (also referred as the Schrödinger cats), the decoherence factor is

$$F(t)=\mathrm{exp}\left\{2|\alpha |^2\left[1e^{\left\{32\pi (\frac{R_0}{a_B})^3\gamma _st\right\}}\right]\right\}.$$
(17)
For the behavior of the short time $`32\pi (\frac{R_0}{a_B})^3\gamma _st1`$, the characteristic time $`\tau `$ of the decoherence for the superposed excitonic coherent states is approximately $`1/(2|\alpha |^2)`$ times of that in Eq. (13). In order to discuss how the characteristic time depends on the size and the average number of the excitons in detail. We plot Fig. 2 with different average numbers of the excitons in ranges $`200`$ Å $`R_0500`$ Å for CdS and $`600`$ Å $`R_01000`$ Å for GaAs, in which the conditions of the bosonic descriptions of excitons and $`a_BR_0\lambda `$ are still valid. It is found that the larger average number of the excitons corresponds to the shorter characteristic time when the size of the microcrystallite is fixed, and the larger size of the microcrystallite corresponds to the faster decoherence when the average number of the excitons is fixed.

In summary, we have studied the size-dependent decoherence for the semiconductor microcrystallites. It is found that microcrystallites with larger sizes have shorter coherence time of the exciton states. If the system is initially in the superposition of two different excitonic coherent states, the coherence characteristic time depends on both the sizes of the microcrystallites and the overlap between the two coherent states. A numerical study of the decoherence of the exciton states for the materials GaAs and CdS is carried out based on our theoretical analysis. This numerical analysis clearly shows the importance of material choice on the decoherence characteristics of microcrystallites. It also should be pointed out that our study cannot simply be generalized to the small quantum dot whose effective radius $`R_0`$ is smaller than the Bohr radius $`a_B`$ in the bulk semiconductor when there exist many excitons in a quantum dot. Because the Pauli principle prohibits the two or more excitons from occupying the same energy state in the small quantum dot. The details need to be studied further.

Yu-xi Liu is supported by Japan Society for the Promotion of Science (JSPS).