Homological Product Codes

This post is my report in verbatim for a quantum error correction course taught by Daniel Gottesman and Robert Kรถnig that i took in 2014 at the Institute for Quantum Computing / University of Waterloo.

The report is an exposition and summary of results in the paper "Homological Product Codes" by Sergey Bravyi and Matthew B. Hastings (2013). They are very very smart, unlike me, so assume any mistakes here are mine.



Abstract

Using the concept of a chain complex from homology theory a means of constructing CSS codes from chain complexes is described. The homological product of two chain complexes can be used to define a product of the respective CSS codes referred to as a homological product code introduced in \cite{Bravyi}. Code parameters of the constructed CSS codes are determined and randomization techniques are used to construct random CSS codes from random chain complexes. The main result is that with high probability a random homological product code on $n$ physical qubits has code parameters given by $[[n,\Omega(n),\Omega(n),O(\sqrt{n})]]$. Hence, homological product codes are one of the first examples of good quantum codes having relatively low stabilizer weight $O(\sqrt{n})$.




Quantum Error Correction

Computation, often considered entirely in the abstract, is a physical process, and although ideal faultless computations are an interesting idea to entertain, the need for active error correction seems inevitable. As physical systems undergoing physical processes, computers are subject to internal and external noise.  This is even more undeniable when comparing quantum computation to classical computation. Despite offering a seemingly more powerful paradigm of computing, controlling quantum computation is a much more challenging task.

The objective of quantum error correction is to encode desired information in a subspace of a larger space through means of redundancy. Such an encoding can serve the purpose of protecting quantum states and transforming quantum states in a hopefully robust manner. Various error correcting codes achieve this is different ways. The primary means used to describe a code is through its code parameters. These parameters are the number of actual physical qubits $n$ used in the system, the number of effectively encoded logical qubits $k$ (where $2^k$ is the dimension of the codespace), and the code distance $d$ which specifies certain limitations on what the code can correct. For a quantum error correcting code, denote its parameters as $[[n,k,d]]$. Other parameters may also be defined in terms of these or independent of them.

"Good'' Codes

Given the parameters $[[n,k,d]]$ of a quantum error correcting code, some notion of what it means for the code to be good or bad ought to be determined. A formal criterion for the properties of a ``good" quantum code is presented here. An important issue to address is how the code parameters scale as the number of physical qubits $n$ increase. A code can be characterized by considering how the various parameters behave in the asymptotic limit as $n$ grows large.  In this regard, consider the ratio $k/n$ called the encoding rate and the ratio $d/n$ called the relative distance. A $[[n,k,d]]$ quantum code is defined to be good if both of the following relations hold between the parameters in the limit as $n$ tends to infinity:
\[
k/n=\Omega(1) \Longleftrightarrow k=\Omega(n)
\]
and
\[
d/n=\Omega(1) \Longleftrightarrow k=\Omega(n).
\]
Thus, a code is good if both the encoding rate and relative distance are at least constant. This is equivalent to the condition that both $k$ and $d$ must grow at least linearly in $n$. Good codes defined in this way capture some desirable properties of a code. For instance, suppose it is required that additional logical qubits be involved in some error correcting scheme, or that the distance $d$ of the code needs to be increased to protect from more severe errors. Then for a good quantum code, both $k$ and $d$ can be increased at least linearly by only adding more physical qubits to the code. Good codes ensure that in order to increase parameters like $k$ and $d$, a large overhead in the number of physical qubits is not necessary in order to achieve the desired increase in parameter values.

Stabilizer Weight: $\mathbf{w}$

In addition to the standard code parameters $[[n,k,d]]$, another parameter known as the stabilizer weight $w$ becomes relevant for practical purposes. The stabilizer weight of a code is a concept that is defined for CSS codes and more generally for stabilizer codes. Intuitively, the stabilizer weight measures the degree of interaction between stabilizer operators and the physical qubits of the code. Each stabilizer operator acts nontrivially on some number of physical qubits, and each physical qubit is generally acted on by some number of stabilizer operators. A stabilizer code is said to have stabilizer weight $w$ (where $w$ is the smallest such number), if no stabilizer operator acts on more than $w$ physical qubits, and no more than $w$ different stabilizer operators act on any particular physical qubit.

In the CSS formalism, code spaces $C^X$ and $C^Z$ are spanned by columns of binary parity check matrices $A^X$ and $ A^Z$, which specify stabilizer operators consisting of only Pauli X or only Pauli Z operators, respectively. In this setting, the code $CSS(C^X,C^Z)$ is said to have stabilizer weight $w$ if every row and column of the parity check matrices $A^X$ and $A^Z$ has weight at most $w$. Here, the weight of a binary vector is given by the number of $1$s that comprise the vector.


LDPC Codes

Consider a code having stabilizer weight $w$. Then if it is the case that $w=O(1)$, the code is called an LDPC code (Low Density Parity Check code). Thus, in an LDPC code each stabilizer operator acts on at most a constant number of physical qubits. Moreover, each physical qubit is only acted on by a constant number of stabilizer operators.

For practical purposes, LDPC codes are ideal when compared to non LDPC codes having stabilizer weight which may scale with $n$. The reason why this is the case is ultimately due to fault tolerant considerations. Error correction generally requires measurements of some form. In the quantum setting, this is quite literally a sensitive issue. In practice operations and gates have a nonzero error probability, and the more gates or operations that are involved, the more this error is expected to accumulate. A common strategy for measuring quantum systems for error correction is to couple the system with an ancilla, and then measure the corresponding ancilla in order to read out syndrome information. This coupling is often achieved through, say, a two-qubit $CNOT$ gate which has the potential of propagating errors throughout the system. In an LDPC code, where the number of operators or qubits involved in direct interaction is small, there will naturally be less coupling required to actively perform error correction. Furthermore, in regards to fault tolerant computation, it has been shown that if the code distance of an LDPC code satisfies $d= \Omega(log \ n)$, then there exists a constant error threshold for stochastic error models \cite{Got}, \cite{Kovalev}.

In the classical framework, LDPC codes have had tremendous success. In fact, there exists classical LDPC codes which are also good in the technical sense. This serves as motivation for generalizing the notion of LDPC codes in the quantum setting. In the table below various quantum LDPC codes are given with their parameters $k,d$, and $w$, and their dependence on $n$. Note however, that none of these codes are good since the code distances of each grow strictly slower than $\Omega(n)$. It can also be seen that some of the codes have an encoding rate $k/n$ which approaches zero asymptotically.

Various examples of LDPC codes. References: [7]\cite{Kitaev}, [11] \cite{Zemor}, [13]\cite{Delfosse}, [6]\cite{Freedman}, [10]\cite{Tillich}, [5]\cite{FreedmanHas}.




Main Results

The principle objective of this paper is to introduce and outline new quantum error correcting codes known as homological product codes. By borrowing the mathematical framework and terminology of homology theory and algebraic topology, in particular the idea of chain complexes, CSS codes can be constructed in a straight forward manner. Moreover, the notion of a homological product of two chain complexes can be used to also define a homological product of CSS codes, in which a new code is constructed using two old codes. How these constructions are carried out, and what the parameters of these resulting codes are, will be discussed in more detail in what follows.

By defining random chain complexes, random CSS codes can be considered. Using these randomized constructions, it will be argued that with high probability the random CSS codes derived from random chain complexes are good codes. Likewise, it will also be argued that the product CSS code resulting from taking a product of two random chain complexes also gives a good code. Regardless, these CSS codes are not $LDPC$, but have stabilizer weight $w=O(\sqrt{n})$. Thus, in a certain sense it can be said that these codes are ``almost" LDPC. Besides a distinctively new way to construct new codes from old codes, the main contribution offered by homological product codes is that they are the first family of good codes to be introduced which have stabilizer weight smaller than $\Omega(n)$.


Homology Theory

In this section, some basic concepts and terminology in homology theory will be introduced. The main mathematical entity from homology theory, known as a chain complex or just complex for short, will be necessary to define the construction of CSS codes. In that regard, the notions to be introduced will be limited and highly specialized to suit these purposes. However, it should be acknowledged that many of these notions can be generalized to a broader setting.

The central object of study in homology theory is a chain complex $(C_i, \partial_i)$, which consists of:
  • A sequence of vector spaces $C_i$.
  • Linear transformations called boundary operators, $\partial_i:C_i\to C_{i+1}$ such that $\partial_i\partial_{i+1}=0$,
which can be schematically visualized as
\[
\dots \overset{\partial_{i+2}}\longrightarrow C_{i+1}\overset{\partial_{i+1}}\longrightarrow C_i \overset{\partial_{i}}\longrightarrow C_{i-1} \overset{\partial_{i-1}}\longrightarrow \dots
\]
 Here, $\partial_i\partial_{i+1}=0$ says that the composition of two consecutive maps is the zero mapping sending all elements to the zero element in the appropriate space. It is worth remarking that the restriction of  $(C_i,\partial_i)$ to vector spaces and linear transformations is a specialization of the definition of a chain complex. More generally, one could consider groups or modules for the $C_i$ and the appropriate structure preserving homomorphisms in their respective categories as the transformations $\partial_i$.

 To understand the consequences of the seemingly peculiar condition $\partial_i\partial_{i+1}=0$
 imposed on the boundary operators, define the following subspaces of $C_i$
\[
 \begin{align*}
im\partial_i &:=\{\partial_i\vec{v}\in C_{i-1} \mid \vec{v}\in C_i\}, \\
ker\partial_i &:=\{\vec{w}\in C_i \mid \partial_i\vec{v}=\vec{0}\in C_{i-1}\}. 
 \end{align*}
\]
Thus, for any $\vec{v}\in C_{i+1}$ we have $\vec{w}:=\partial_{i+1}\vec{v}\in im\partial_{i+1}\subseteq C_i$. Then the condition $\partial_i\partial_{i+1}=0$ implies that $\partial_i\partial_{i+1}\vec{v}=\partial_i\vec{w}=0$ so $\vec{w}\in ker\partial_i$. Hence, for any chain complex it is always the case that $im\partial_{i+1}\subseteq ker\partial_i$. Now since $im\partial_i$ is a vector subspace of $ker\partial_i$, the quotient space $\ker\partial_i/im\partial_{i+1}$ can be defined as the set of equivalence classes $[\vec{w}]$, for $\vec{w}\in ker\partial_i$, where for two classes $[\vec{w}]=[\vec{w}']$ if and only if $\vec{w}-\vec{w}'\in im\partial_{i+1}$. The space $\ker\partial_i/im\partial_{i+1}$,called the $i^{th}$ \emph{homology space}, can be given a vector space structure by defining the vector addition and scalar multiplication as $[\vec{v}]+[\vec{w}]=[\vec{v}+\vec{w}]$ and $\alpha[\vec{w}]=[\alpha\vec{w}]$ for scalar elements $\alpha$ in the underlying field of $C_i$. Understanding these homology spaces in some chain complex is one of the main focuses of homology theory.

In a similar manner, to every complex $(C_i,\partial_i)$ there is an associated cocomplex $(C_i,\partial^{T}_i)$, defined in terms of the transpose maps $\partial^{T}_i: C_{i-1}\to C_i$ (or more generally the adjoints of $\partial_i$)., which satisfy $\partial^{T}_{i+1}\partial^{T}_{i}=0$. This can essentially be understood in terms of the standard complex by simply reversing arrows in the chain diagram:
\[
 \dots \overset{\partial^{T}_{i+2}}\longleftarrow C_{i+1}\overset{\partial^{T}_{i+1}}\longleftarrow C_i \overset{\partial^{T}_{i}}\longleftarrow C_{i-1} \overset{\partial^{T}_{i-1}}\longleftarrow \dots
\]
 In this way, the condition  $\partial^{T}_{i+1}\partial^{T}_{i}=0$ implies that $im\partial^{T}_i \subseteq ker\partial^{T}_{i+1}$ so that the $i^{th}$ cohomology group is given by the quotient $ker\partial^T_{i+1}/im\partial^{T}_i$.


 
CSS codes from Complexes
 
 General Construction: $\mathbf{CSS(C_i,\partial_i)}$
 
  In what follows, when referring to some chain complex $(C_i,\partial_i)$, all vector spaces $C_i$ will be over the binary field $\mathbb{F}_2$ where addition and multiplication are carried out modulo $2$. Furthermore, for the purposes of defining a CSS code from the chain complex, it will suffice to restrict the discussion to short chain complexes of the form
\[
  C_{2}\overset{\partial_{2}}\longrightarrow C_1 \overset{\partial_{1}}\longrightarrow C_{0},
\]  consisting of just three spaces $C_0,C_1,C_2$ and boundary maps $\partial_1,\partial_2$ in the chain satisfying $\partial_1\partial_2=0$. Temporarily refraining from any
  motivation, consider making the following definitions
\[
  C^Z:=im\partial_2 \ \ \text{and} \ \ C^X:=im\partial^{T}_1,
\]
  where $\partial_2: C_2\to C_1$ and $\partial^{T}_1 : C_0\to C_1$. Note that $C^Z,C^X\subseteq C_1$.
 
  Suppose $C_1=\mathbb{F}^{n}_2$ for some $n$, and define the standard inner product between $\vec{v},\vec{w}\in C_1$ as
\[
  <\vec{v},\vec{w}>:=\displaystyle\sum^{n}_{i=1}v_i w_i \ (mod \ 2),
\]
  where $\vec{v}=(v_1,\dots,v_n)$ and $\vec{w}=(w_1,\dots,w_n)$ are the corresponding vector components in some basis. With respect to this inner product and for any subspace $S\subseteq C_1$ define the orthogonal complement of $S$ as the space
\[
  S^\perp:=\{\vec{v}\in C_1 \mid <\vec{v},\vec{w}>=0 \ \text{for all } \ \vec{w}\in S\} .
\]
The space $S^\perp$ is indeed a vector subspace of $C_1$.

It will now be shown that with the definitions given above, $C^Z\subseteq (C^X)^\perp$. For any vectors $\vec{v}\in C^Z:=im\partial_2$ and $\vec{w}\in C^X:=im\partial^{T}_1$, there exists $\vec{x}\in C_2$ and $\vec{y}\in C_0$ such that $\partial_2\vec{x}=\vec{v}$ and $\partial^{T}_1\vec{y}=\vec{w}$. Then the inner product between $\vec{v}$ and $\vec{w}$ satisfies
\[
  <\vec{v},\vec{w}>=<\partial_2\vec{x},\partial^{T}_1\vec{y}>=<\partial_1\partial_2\vec{x},\vec{y}>=<\vec{0},\vec{y}>=0
\]
  since $\partial_1\partial_2=0$. Thus for any $\vec{v}\in C^Z$ it is also the case that $\vec{v}\in(C^X)^\perp$.
 
  The boundary operator condition $\partial_1\partial_2=0$ implies that $C^Z\subseteq(C^X)^{\perp}$, or equivalently that $C^X\subseteq (C^Z)^\perp$. This condition, together with the underlying assumption that the the spaces under consideration are over the field $\mathbb{F}^{n}_2$ (so that $C^X,C^Z\subseteq C_1=\mathbb{F}^{n}_2$) is enough to completely specify a valid CSS code on $n=dim(C_1)$ physical qubits with code spaces given by $C^X$ and $C^Z$. Let $CSS(C^X,C^Z)$ or $CSS(C_i,\partial_i)$ denote the CSS code that results from the complex $(C_i,\partial_i)$. By choosing a basis for the code spaces $C^X$ and $C^Z$, the basis vectors can be used to specify stabilizer generators acting on the $n$ physical qubits consisting of either Pauli $X$ operators or Pauli $Z$ operators, respectively. In this case, since the code spaces are defined in terms of the images of $\partial_2$ and $\partial^{T}_1$, a basis can be specified by taking linearly independent columns of $\partial_2$ as a basis of $C^Z:=im\partial_2$, and linearly independent columns of $\partial^{T}_1$ to form a basis for $C^X=im\partial^{T}_1$. In this way, the essential condition for CSS codes $C^Z\subseteq(C^X)^{\perp}$ implies that all $X$-type stabilizers commute with all $Z$-type stabilizers---a necessary condition in the stabilizer formalism of quantum error correcting codes. More details regarding this construction will be explained in what follows.
 
The Single-Sector Theory: $\mathbf{CSS(C,\partial)}$

 In the general construction of the code $CSS(C_i,\partial_i)$ from a chain complex, three different spaces $C_0,C_1,$ and $C_2$ were at play. The rest of this paper will be restricted to a more specialized setting known as the single-sector theory. In the \emph{single-sector theory}, only a single vector space $C=\mathbb{F}^{n}_2$ and boundary operator $\partial: C\to C$ is considered with $C=C_0,C_1,C_2$. This gives a chain complex $(C,\partial)$ of the form
\[
   C\overset{\partial}\longrightarrow C \overset{\partial}\longrightarrow C ,
\]
  which in the present context can be viewed as
\[
   C\overset{\partial}\longrightarrow C \overset{\partial^{T}}\longleftarrow C.
\]
  Then in this case the code spaces of the corresponding CSS code are defined to be
\[
  C^Z:=im\partial \ \ \text{and} \ \ C^X:=im\partial^{T}.
\]
  Moreover, it can be shown that
\[
  (C^Z)^\perp=ker\partial^T \ \ \text{and} \ \ (C^X)^\perp=ker\partial.
\]
  Let $A^Z$ and $A^X$ be the parity check matrices spanning $C^Z$ and $C^X$, and make the identification
\[
  A^Z=\partial \ \ \text{and} \ \ A^X=\partial^T.
\]
Thus, the columns of $\partial$ span the code space $C^Z$ and the columns of $\partial^T$ (or equivalently the rows of $\partial$) span the code space $C^X$. Note that the columns and rows of $\partial$ may not be linearly independent. If this is the case then not every row of the parity check matrices $A^Z$ and $A^X$ will yield an independent stabilizer. In some conventions party check matrices that generate some CSS code are required to have full rank (where all columns are linearly independent). This restriction will not be imposed here in this paper in defining the parity check matrices in terms of $\partial$. Then in general, since it is possible to have distinct boundary operators $\partial\neq\partial'$, with $im\partial=im\partial'$, the correspondence in this translation of chain complexes $(C,\partial)$ to codes $CSS(C,\partial)$ is many-to-one. That is, different chain complexes may define equivalent CSS codes.

To make the construction of $CSS(C,\partial)$ more explicit consider, for example, the boundary operator $\partial : C\to C$, where $C=\mathbb{F}^{5}_2$, is expressed in some basis as
\[
\partial=\begin{pmatrix}
1&1&1&0&0 \\
0&0&1&1&1 \\
1&1&0&1&1 \\
1&1&1&0&0 \\
0&0&1&1&1 \\
\end{pmatrix} .
\]
Regard each column of $\partial$ as a vector $\vec{v}=(v_1,\dots, v_5)$. Then a $Z$-type stabilizer acting on the $dim(C)=5$ qubit space can be obtained using a column $\vec{v}$ as
\[
S^Z=Z^{v_1}_1Z^{v_2}_2Z^{v_3}_3Z^{v_4}_4Z^{v_5}_5.
\]
Hence, $S^Z$ acts nontrivially on qubits that correspond to the nontrivial support of $\vec{v}$. From the columns of $A^Z=\partial$, three $Z$-type stabilizers are obtained in this way:
\[
   \begin{align*}
S^{Z}_1&=Z_1Z_3Z_4  \\
S^{Z}_2&=Z_2Z_3Z_5  \\
S^{Z}_3&=S^{Z}_1S^{Z}_2,  \\
\end{align*}
\]
Similarly, from the columns of $A^X=\partial^{T}$ three  $X$-type stabilizers are obtained:
\[
   \begin{align*}
S^{X}_1&=X_1X_2X_3 \\
S^{X}_2&=X_3X_4X_5 \\
S^{X}_3&=S^{X}_1S^{X}_2. \\
\end{align*}
\]
For this particular $\partial$, it is seen that there are only two linearly independent columns and rows: $rank(\partial)=rank(\partial^T)=2$. This corresponds to the fact that there are only two independent stabilizer generators of each type. Given some stabilizer group $S$, recall that there are generally multiple ways to specify a generating set for $S$. This freedom implies that a conversion that begins with an arbitrary CSS code and translates to a corresponding chain complex $(C,\partial)$ will also be many-to-one in general.

Justification for why a complex $(C,\partial)$ defined in this setting naturally translates to a corresponding CSS code can be given by observing that the underlying condition $\partial^2=0$ is equivalent to the commutativity constraints demanded by CSS codes and stabilizer codes. Write $\partial=(\partial_{ij})_{ij}$ to express the matrix coefficients of $\partial$ in a particular basis, and note that $A^Z=\partial=(\partial_{ij})_{ij}$ and $A^X=\partial^T=(\partial_{ji})_{ij}$. Then
\[
\partial^2=0  \Longleftrightarrow   A^Z(A^X)^{T}=\displaystyle\sum_{k}^{}\partial_{ik}\partial_{kj}=0  (mod \ 2)   \Longleftrightarrow  S^{X}_iS^{Z}_j=S^{Z}_jS^{X}_i.
\]

Here, the first statement is the relevant constraint in the context of chain complexes, while the second statement can be interpreted as a condition that implies $C^Z\subseteq(C^X)^T$ in the setting of CSS codes. The last statement gives the commutativity constraints imposed on the different types of stabilizer generators that result from the construction described above.


Equivalent Terminology

      Outlined below is analogous terminology of various entities in homology theory and the corresponding concepts in the quantum error correction setting. For a chain complex, $(C,\partial)$, the main spaces of interest are $ker\partial$, $im\partial$, and the quotient $ker\partial/im\partial$, which correspond to $Z$-type operators of the code $CSS(C,\partial)$; and the same spaces for $\partial^T$ that correspond to $X$-type operators of the code. In the table below, the middle column gives the nomenclature used for elements in these spaces.




    
     The relations that hold between the various spaces in the homology setting are analogous to the relationships between the different groups that arise in the stabilizer formalism. Let $S_Z$ be the stabilizer group defined by the $Z$-type part of $CSS(C,\partial)$, and denote $N(S_Z)$ as the normalizer group of $S_Z$ in the Pauli group for $n=dim(C)$ qubits. In this way,  elements of $ker\partial$, called cycles, correspond to elements of $N(S_Z)$. Elements of $im\partial\subseteq ker\partial$ are trivial cycles that correspond to operators that are elements of the stabilizer $S_Z\subseteq N(S_Z)$. Furthermore, $ker\partial\backslash im\partial$ contains all cycles in $ker\partial$ that are not in $im\partial$, which corresponds to the nontrivial logical operators in $N(S_Z)$ that are not in $S_Z$. The homology space $ker\partial/im\partial$ is analogous to the quotient group $N(S_Z)/S_Z$, where in the stabilizer setting different elements of the quotient correspond to an equivalence class of logical operators. Operators in the same class can be distinct operators when expressed in terms of Pauli operators (up to a product of stabilizer elements), but in effect have the same \emph{logical} action on the encoded qubits.
    
      An similar translation between concepts and their interpretations can be made for the $X$-type part of $CSS(C,\partial)$ by simply replacing the boundary operator with the transpose operator $\partial^T$ as indicated in the table. The acquainted reader may recognize some of these concepts coming from homology theory from their experience with the toric code \cite{Kitaev},where historically  speaking, some of the intimate relations between homology theory and error correction were first manifested.


Code Parameters of $\mathbf{CSS(C,\partial)}$

Having developed the framework to construct a code $CSS(C,\partial)$ from a chain complex $(C,\partial)$, let us determine the code parameters $[[n,k,d,w]]$ of $CSS(C,\partial)$. The number of physical qubits $n$ that define the global space of the code is given by
\[
n=dim(C)=dim(\mathbb{F}^{n}_2).
\]   
This can equivalently be determined through $\partial$ by simply counting the number of rows/columns that comprise $\partial$.

For a stabilizer code with $r$ generators the number of encoded qubits is given by $k=n-r$, and since the number of $X$-type and $Z$-type generators are both given by the number $rank(\partial)$ of linearly independent rows/columns of $\partial$ we have
\[
k=n-2rank(\partial).
\]

The stabilizer weight $w$ and distance $d$ of $CSS(C,\partial)$ are not so readily determined from $\partial$. By definition, the stabilizer weight is the smallest $w$ such that every column and row of $\partial$ has weight at most $w$. In regards to the LDPC criterion, $CSS(C,\partial)$ will be an LDPC code if $\partial$ is a ``sparse'' matrix. More specifically, $CSS(C,\partial)$ is LDPC if each row and column of $\partial$ has $O(1)$ nonzero entries.

To determine the distance $d=min\{d^X,d^Z\}$, it is necessary to know the respective distances $d^X$ and $d^Y$, which are defined in this setting to be
\[
\begin{align*}
d^Z:=&min\{weight(\vec{v}) \mid \vec{v} \in ker\partial \backslash  im\partial \} \\
d^X:=&min\{weight(\vec{v}) \mid \vec{v} \in ker\partial^T \backslash  im\partial^T \}.
\end{align*}
\]
Thus, $d^Z$ and $d^X$ represents the minimum weight of nontrivial cycles in $ker\partial$ and $ker\partial^T$, respectively.  It will be argued later that when considering a uniformly random distribution of possible boundary operators $\partial$ the corresponding code $CSS(C,\partial)$ will has linear distance ($d=\Omega(n)$) with high probability.
    
    
Homological Dimension $\mathbf{H(\partial)}$

 Here we introduce the homological dimension of a complex $(C,\partial)$ and its relation to the number of encoded qubits $k$ of the code $CSS(C,\partial)$, which will become more relevant in later discussions. Define the homological dimension $H(\partial)$ of a complex $(C,\partial)$ to be the dimension of the homology space of the complex:
\[
 H(\partial):=dim(ker\partial/im\partial).
\]
 The following relations hold:
\[
 \begin{align*}
 H(\partial)&=dim(ker\partial/im\partial) \\
&=dim(ker\partial)-dim(im\partial) \\
&=(n-dim(im\partial))-dim(im\partial) \\
&=n-2dim(im\partial) \\
&=n-2rank(\partial) \\
  &=k
 \end{align*}
\]

 Hence, the homological dimension of the complex is equal to the number of encoded qubits of the code: $H(\partial)=k$.  The second identity is a general relationship that holds for quotient spaces which essentially follows from the fact that given a basis of a vector subspace $V\subseteq W$, a basis of $W$ can be obtained from a basis of  $V$ and $W/V$.  The third identity follows from the rank-null theorem of linear algebra which states that $dim(ker\partial)+dim(im\partial)=n$. The last two identities follow merely from the definition $rank(\partial):=dim(im\partial)$ and the previous relationship derived for $k$.

   
Homological Product
   
    Given two chain complexes $(C_1,\partial_1)$ and $(C_2,\partial_2)$, a natural construction to consider is some notion of a product defined on the complexes that yields another chain complex $(C,\partial)$. The homological product to be introduced here achieves precisely this. The product complex $(C_1,\partial_1)\times (C_2,\partial_2)=:(C,\partial)$ will express the space $C$ and boundary operator $\partial$ in terms of the spaces $C_1,C_2$ and boundary operators $\partial_1,\partial_2$ of the factors. Moreover, the K\"{u}nneth formula will provide a means of expressing $ker\partial$ in terms of $ker\partial_1$ and $ker\partial_2$, and the homological dimension $H(\partial)$ in terms of $H(\partial_1)$ and $H(\partial_2)$. This theory will then be applied to define a product of two codes $CSS(C_1,\partial_1)$ and $CSS(\partial_2)$ and to calculate its parameters.
  
   
$\mathbf{(C_1,\partial_1)\times (C_2,\partial_2)=(C,\partial)}$
       
    The homological product, denoted by $\times$, of two complexes $(C_1,\partial_1)$ and $(C_2,\partial_2)$ gives a product complex
\[
    (C,\partial):=(C_1,\partial_1)\times (C_2,\partial_2),
\]
    where $C=C_1\otimes C_2$ is given by the tensor product of $C_1$ and $C_2$, and the boundary operator by
\[
    \partial=\partial_1\otimes I +I\otimes \partial_2.
\]
    To verify that $\partial$ is indeed a valid boundary operator observe the following:
\[
    \begin{align*}
    \partial^2&=(\partial_1)^2\otimes I +2\partial_1\otimes\partial_2 + I\otimes (\partial_2)^2 \\
&=0\otimes I +0\cdot\partial_1\otimes\partial_2 + I\otimes 0 \\
&=0
    \end{align*}
\]
    Here, the assumptions $\partial^{2}_1=0$ and $\partial^{2}_2=0$ were used together with $2\equiv 0 \ (mod \ 2)$ since all spaces under consideration are taken to be over the field $\mathbb{F}_2$.
   
   
Kunneth Formula
       
    The Kunneth formula is a standard result in homology theory that, for a product complex $(C,\partial)=(C_1,\partial_1)\times (C_2,\partial_2)$, relates $ker\partial$ and the homological dimension $H(\partial)$ in terms of the corresponding entities of $(C_1,\partial_1)$ and  $(C_2,\partial_2)$. The theorem statement reads:
   
    For any boundary operators $\partial_1,\partial_2$ and $\partial=\partial_1\otimes I +I\otimes \partial_2$,
\[
    ker\partial=ker\partial_1\otimes ker\partial_2+im\partial
\]
    and
\[
  H(\partial)=H(\partial_1)H(\partial_2).
\]

Although a proof of  the Kunneth formula will not be given here, the results will be used to derive certain properties of the product complex and resulting product code. In particular, the identity $H(\partial)=H(\partial_1)H(\partial_2)$ will be useful. The first statement says the any element $\vec{v}\in ker\partial$ can be expressed in the form $\vec{v}=\vec{v_1}\otimes\vec{v_2} +\vec{w}$ where $\vec{v_i}\in ker\partial_i$ and $\vec{w}\in im\partial$, and that any vector of such form is always in $ker\partial$.
   
   

Homological Product Codes
       
    Previously, it was described how a complex $(C,\partial)$ can be used to specify a code $CSS(C,\partial)$. By considering a product complex $(C,\partial)=(C_1,\partial_1)\times (C_2,\partial_2)$ that results from taking the homological product of two chain complexes, and then translating the resulting product complex $(C,\partial)$ into the corresponding code $CSS(C,\partial)$ a homological product code can be defined. In the following sections, the parameters of the product code will be calculated in terms of the parameters of the input codes.
     
   
$\mathbf{CSS(C_1,\partial_1)\times CSS(C_2,\partial_2)=CSS(C,\partial)}$
   
 Consider two codes $CSS(C_1, \partial_1)$ and $CSS(C_2,\partial_2)$ defined by two complexes $(C,\partial_1)$ and $(C_2,\partial_2)$. Define the homological product of $CSS(C_1, \partial_1)$ and $CSS(C_2,\partial_2)$ to be the code
\[
CSS(C,\partial):=CSS(C_1,\partial_1)\times CSS(C_2,\partial_2),
\]
where $(C,\partial)=(C_1,\partial_1)\times (C_2,\partial_2)$ so that $C=C_1\otimes C_2$ and $\partial=\partial_1\otimes I +I\otimes \partial_2$. Even though the resulting product code does share some properties in common with codes constructed through code concatenation, the homological product offers a way to create a new code from two older codes in a way that is distinct from code concatenation. How the parameters of the product code are related to the code parameters of the input codes is the focus of the following sections.
   
     
Parameters of the Product Code $\mathbf{CSS(C,\partial)}$
   
Let $[[n_i,k_i,d_i,w_i]]$ be the code parameters of two codes $CSS(C_i,\partial_i)$ for $i=1,2$, and let $[[n,k,d,w]]$ be the parameters of the resulting product code $CSS(C,\partial)=CSS(C_1,\partial_1)\times CSS(C_2,\partial_2)$. The objective here will be to determine the parameters $[[n,k,d,w]]$ in terms of the parameters of the input codes.

Since $C=C_1\otimes C_2$, the number of physical qubits $n$ in the product code is given by

\[
n=dim(C)=dim(C_1\otimes C_2)=dim(C_1)dim(C_2)=n_1n_2.
\]
The number of encoded qubits $k$ of the product code is calculated through the K\"{u}nneth formula:
\[
k=H(\partial)=H(\partial_1)H(\partial_2)=k_1k_2.
\]
    Hence, the homological product of two codes always increases the number of physical and logical qubits provided that both input codes have parameters $n_i,k_i > 1$.
   
    Recall from the definition that  if $CSS(C_i,\partial_i)$ have stabilizer weights $w_i$, the weight of rows and columns of $\partial_i$ is no greater than $w_i$. Then since taking the tensor product of any operator with the identity does not increase row or column weight, the stabilizer weights of $\partial_1\otimes I$ is no greater than $w_1$ and the stabilizer weight of $I\otimes \partial_2$ is no greater than $w_2$. Therefore the stabilizer weight of the product boundary operator $\partial=\partial_1\otimes I +I\otimes \partial_2$ must satisfy $w\leq w_1+w_2$, implying that the stabilizer weight of the product code is no greater than the sum of the stabilizer weights of the input codes.
   
    Calculating the distance $d$ of the product code $CSS(C,\partial)$ is highly non trivial, and only bounds are known. Let $d^{Z}_i, d^{X}_i$ be the  $Z$ and $X$-type distances of CSS$(C_i,\partial_i)$ for $i=1,2$ so that the distances are given by $d_i=min\{d^{Z}_i, d^{X}_i\}$. Without complete proof we state the following relationship:
\[
    max\{d^{\alpha}_1,d^{\alpha}_2\}\leq d^{\alpha} \leq d^{\alpha}_1d^{\alpha}_2  (\text{for} \alpha=X,Z).
\]
    Then the distance of the product code will be given by $d=min\{d^X,d^Z\}$. To justify the upper bound, consider non trivial cycles $\vec{v}_i\in ker\partial_i\backslash im\partial_i$. Then $\vec{v}_1\otimes\vec{v}_2\in C$ will be a nontrivial cycle in $ker\partial\backslash im\partial$. So if $\vec{v}_i$ has weight greater than $d^{\alpha}_i$ for type $\alpha$, then $\vec{v}_1\otimes\vec{v}_2$ will have weight given by $d^{\alpha}_1d^{\alpha}_2$. Thus, $d^{\alpha}\leq d^{\alpha}_1d^{\alpha}_2$. Proving the lower bound is a little more involved, but can be done by invoking the K\"{u}nneth formula. This bound can be interpreted as stating that the distance $d^{\alpha}$ of the product code in no worse than the best of the distances $d^{\alpha}_1$ and $d^{\alpha}_2$ of the input codes.
   
    The parameters $n$ and $k$ regarding the number of physical and encoded qubits of the product code $CSS(C,\partial)$ are readily determined from the parameters of the input code. On the contrary, the stabilizer weight $w$ and the code distance $d$ of the product code are more subtle matters. Determining exact values for $w$ and $d$ is specific to the more detailed structure of the input boundary operators $\partial_1$ and $\partial_2$ and how they combine to form the product boundary operator $\partial$. However, it will be shown in the following section that with high probability, most  homological product codes have a linear distance: $d=\Omega(n)$.
   
  
Distance Bounds on $\mathbf{CSS(C,\partial)}$
      
  In order to better determine a stronger lower bound on the distance $d$ of a homological product code, it is necessary to make use of probabilistic arguments regarding random chain complexes $(C,\partial)$ with fixed $n=dim(C)$ and homological dimension $k=H(\partial)$.  The main objective of this section is to sketch a proof that the homological product of two random complexes whose corresponding CSS codes have  linear distance will yield a product code that also has linear distance $d=\Omega(\partial)$ with high probability. The statistical nature of this argument, shows that such a result holds in a ``typical case''. First, what is meant by a random complex will be made more precise. Then, a few logical reductions involved in the analysis of the distance bounds will be discussed. The interested reader can find further details regarding the proof in \cite{Bravyi} .


Random Complexes

A way of generating a random ensemble of complexes satisfying certain properties is discussed in what follows. Fix integers $H$ and $L$, and consider an arbitrary complex $(C,\partial)$ having homological dimension $H(\partial)=H$ and $rank(\partial)=L$. Define a \emph{canonical boundary operator} as the block matrix
\[\hat{\partial}=\begin{pmatrix}0&0&0 \\
0&0&I \\
0&0&0 \\
\end{pmatrix},
\]
  where the rows and columns are grouped into blocks of sizes $H$, $L$, $L$. Then it can be shown \cite{Bravyi} that there exists an invertible matrix $U$ such that $\partial=U\hat{\partial}U^{-1}$. In this way, starting with a canonical boundary operator $\hat{\partial}$ a random boundary operator can be generated by choosing a random invertible matrix $U$ having the appropriate dimension of $M:=H+2L$. If such a $U$ is chosen uniformly at random, then the resulting boundary operator $\partial=U\hat{\partial}U^{-1}$ will also be distributed uniformly. Then by starting with random complexes $(C,\partial)$, random codes $CSS(C,\partial)$.

Consider the "encoding rate'' $H/M$, and the limiting scenario where $H,M\to\infty$ while $H/M$ remains constant. In this limit, a random complex $(C,\partial)$ with $M=dim(C)$ and homological dimension $H(\partial)=H$ will translate to a code $CSS(C,\partial)$ that has linear distance $d=\Omega(M)$ with high probability. This can be argued by observing that the number of low weight cycles in $ker\partial$ is small, which implies that with high probability $ker\partial$ does not contain any low weight cycles. Although this result shows that a random code $CSS(C,\partial)$ tends to have linear distance, it is not immediately obvious that the homological product of two random codes will also have linear distance. More work must be done in order to determine this.


Random Product Complexes

  Here, the notion of random complexes discussed in the previous section is extended to random product complexes. Consider two canonical boundary operators $\hat{\partial}_1$ and $\hat{\partial}_2$, and two invertible matrices $U_1$ and $U_2$ chosen independently at random. Then two random boundary operators can be constructed as
\[
  \partial_1=U_1\hat{\partial}_1U^{-1}_1 \ \ \text{and} \ \ \partial_2=U_2\hat{\partial}_1U^{-1}_2,
\]
 and the boundary operator $\partial=\partial_1\otimes I + I\otimes \partial_2$ resulting from the homological product will be randomly distributed. Equivalently, a \emph{canonical boundary operator} can be defined as
\[
 \hat{\partial}=\hat{\partial}_1\otimes I + I\otimes \hat{\partial}_2,
\]
 Then random boundary operator can be constructed through the transformation
\[
  \partial=(U_1\otimes U_2)\hat{\partial}(U^{-1}_1\otimes U^{-1}_2),
\]
  where $U_1$ and $U_2$ are random invertible matrices. Note that from these relations it readily follows that
\[ker\partial=(U_1\otimes U_2)ker\hat{\partial} \ \ \text{and} \ \ im\partial=(U_1\otimes U_2)im\hat{\partial}.\]
 
 

The Event $\mathbf{E_c}$

In what follows, we consider two random complexes $(C_i,\partial_i)$ (as discussed in the previous section) having the same size $M=dim(C_i)$ and homological dimension $H=H(\partial_i)$ for $i=1,2$. Let $r=H/M$ be the encoding rate. The random complex $(C,\partial)=(C_1,\partial_1)\times(C_2,\partial_2)$ then has size $n=M^2$. The desired result pertaining to the code distance of the random product code $CSS(C,\partial)$ can then be stated as follows: for sufficiently small constants $c,r>0$, the random product code has distance $d>cM^2$ with high probability. Hence, for this to be the case it must be shown that every nontrivial cycle $\vec{v}\in ker\partial\backslash im\partial$ satisfies $weight(\vec{v})>cM^2$ with high probability.

In this regard, for some constant $c$, define the event
\[E_c=\{\exists \vec{v}\in ker\partial\backslash im\partial \mid weight(\vec{v})<cM^2\}.
\]
Then if it can be shown that the probability $Pr[E_c]<1/2$ for sufficiently small $c$  and large enough $M$ , the desired result will follow. The objective then comes down to bounding the probability $Pr[E_c]$ from above by an amount that is exponentially small in $M$. Note that this result can be equivalently obtained by considering the complementary event
\[\overline{E}_c=\{\forall \vec{v}\in ker\partial\backslash im\partial \mid weight(\vec{v})>cM^2\},\]
 and showing that the probability $Pr[\overline{E}_c]>1/2$ instead and tends to $1$ in the limiting case. However, in the analysis that follows it will be preferable to work with $E_c$ as opposed to $\overline{E}_c$.

 As described above, consider the random product complex that results from taking the canonical bipartite boundary operator $\hat{\partial}$ and transforming it to $\partial=(U_1\otimes U_2)\hat{\partial}(U^{-1}_1\otimes U^{-1}_2)$ for random invertible matrices $U_1$ and $U_2$. Recall that $ker\partial=(U_1\otimes U_2)ker\partial$. Then the probability of interest can be bounded by
\[Pr[E_c]\leq \displaystyle\sum^{}_{\vec{v}\in ker\hat{\partial}\backslash im\hat{\partial}} Pr[weight( \ (U_1\otimes U_2)\vec{v} \ )<cM^2].\]

 Since $\vec{v}\in C=C_1\otimes C_2$, interpret $\vec{v}$ as a $M\times M$ matrix $v$ with rows corresponding to the space $C_1$ and columns corresponding to $C_2$. Throughout, we will freely interpret $\vec{v}\in C$ as either a vector or a matrix depending on context. In the latter situation when the vector $\vec{v}$ is to be interpreted as a matrix it will be written as $v$ without the $  \vec{}  $ designation. Suppose the matrix $v$ has rank $R$. Then $(U_1\otimes U_2)v$ will be distributed uniformly over all rank $R$ matrices. Now let $\eta(R)$ be the number of rank $R$ "matrices" of size $M\times M$ in $ker\hat{\partial}\backslash im\hat{\partial}$, and $Pr[R]$ be the probability that such a matrix has weight less than $cM^2$. Then
\[Pr[E_c]\leq \displaystyle\sum^{}_{R\geq 1} \eta(R)Pr[R].\]
 Although the quantities $\eta(R)$ and $Pr[R]$ are relatively straightforward to compute, expressing the bound on the probability $Pr[E_c]$ in this way results in a sum that is exponentialy large in $M$.

 This failure in attempting to bound the probability $Pr[E_c]$ is partly due to the possibility that one of the input codes may be bad. If this is the case, then the resulting product code will have exponentially many low weight cycles. In a certain sense, bounding the probability as above exponentially amplifies bad choices of the input codes. In order to overcome this issue, it will be necessary to define a more refined condition that is only satisfied when both input codes are good.


Uniform Low Weight Condition 
  For some $M\times M$ matrix $A$, say that $A$ has \emph{uniform low weight} with constant $c$ if and only if every row and column of $A$ has weight at most $cM$. To denote that $A$ has uniform low weight, we will write $A$ has $ULW(c)$ for short.
 
  Motivated by the uniform low weight condition, for a constant $c>0$ define the event
\[
E^{ULW}_c=\{\exists \vec{v}\in ker\partial\backslash \vec{0} \mid v  \ \  \text{has} \ \   ULW(c)\},
\]
  and now let $\eta(R)$ be the number of rank $R$ matrices in $ker\partial\backslash \vec{0}$ with $Pr[R]$ denoting the probability that a random rank $R$ matrix of size $M$ has $ULW(c)$. Then  
\[
 Pr[E^{ULW}_c]\leq \displaystyle\sum^{}_{R\geq 1} \eta(R)Pr[R].
\]
Although this time the sum bounding the probability is exponentially small in $M$ as desired, the issue now is that the original low weight event $E_c$ does not imply this uniform low weight event $E^{ULW}$. Hence, attempting to bound the probability in this way is also insufficient for our purposes.

To further refine the analysis, let $t$ be some constant such that $c<t<1$. Suppose that $\vec{v}\in ker\partial$ is a nontrivial cycle with $weight(\vec{v})<cM^2$. Observe that, as a matrix, $v$ has at least $(1-t)M$ rows and columns with weight $\frac{c}{t}M$. Let $M'=(1-t)M$, and consider the \emph{reduced matrix} $v_{red}$ of size $M'$ that consists of precisely these rows and columns. Then $v_{red}$ has $ULW(c')$ where $c'=\frac{c}{t(1-t)}$.

 
The relevance of this reduced submatrix satisfying the uniform low weight condition is made apparent through the following lemma proved in \cite{Bravyi} using results from \cite{Terhal}. If the two random input codes have distances greater than$M-M'+1$, and $\vec{v}\in ker\partial$ is cycle such that $v$ has a vanishing reduced matrix $v_{red}$, then $\vec{v}\in im\partial$ is a trivial cycle. This statement can be equivalently interpreted as saying: if $\vec{v}\in ker\partial$ is a nontrivial cycle, then $v$ must contain a nonvanishing reduced matrix $v_{red}$. Note that a similar result holds for cocycles.

By defining a reduced low weight event
\[E^{RULW}_c=\{\exists \vec{v}\in ker\partial\backslash \vec{0} \mid v_{red} \ \    \text{has}   \ \ ULW(c)\},\]
 and applying the aforementioned lemma, it is seen that the originally defined event $E_c$ implies the event $E^{RULW}_c$. Therefore $Pr[E_c]\leq Pr[E^{RULW}_c]$, and any upper bound on $Pr[E^{RULW}_c]$ yields an upper bound on $Pr[E_c]$. Now let $\eta(R)$ be the number of reduced submatrices $v_{red}$ that can be extended to a valid matrix $v$ that corresponds to a cycle $\vec{v}\in ker\partial$, and let $Pr[R]$ be the probability that such a rank $R$ matrix of size $M'$ has $ULW(c)$. Then,
\[
Pr[E^{RULW}_c]\leq \displaystyle\sum^{}_{R\geq 1} \eta(R)Pr[R].
\]

 In \cite{Bravyi}, bounds on the quantity $\eta(R)$ are calculated to be
\[
\eta(R)\leq O(1)\cdot 2^{(M+H)R-R^2} \ \   \text{if} \ \    R\leq H
\]
 and
\[\eta(R)\leq O(1)\cdot 2^{(M+H/2)R-R^2/2}  \ \  \text{if} \ \  R\geq H,\]
 where $H=H(\partial_1)=H(\partial_2)$ is the homological dimension of the input codes used to construct the product code. Furthermore, it is calculated that the probability $Pr(R)$ is bounded by
\[Pr(R)\leq O(1)\cdot 2^{R^2-2(1-\epsilon)MR},\]
 for any $\epsilon>0$ provided that $c$ is chosen accordingly.

 These two results imply that $Pr[E^{RULW}_c]$, and hence $Pr[E_c]$, are bounded above by an exponentially small quantity in $M$. Therefore, with high probability the product code will not contain nontrivial cycles having weight less than $cM^2$. Since the same argument holds for the cocycles of the code, this implies that the product code of size $n=M^2=dim(C)$ has linear distance $d=\Omega(n)$ with high probability as desired.


Conclusion

We have seen here how chain complexes from homology theory can naturally be used to define CSS codes, and how the homological product of two complexes can be used to define a product code with nice parameters. Code parameters for the CSS codes resulting from both a single chain complex and a product of two complexes were derived. By considering random complexes, it was argued that a single random complex yields a good code with linear distance with high probability. Through a more involved analysis it was also shown that under some typical conditions, the code that results through the homological product will also have linear distance with high probability. In summary, if $[[n_i,k_i,d_i,w_i]]$ are the parameters of two CSS codes constructed from two chain complexes, then the parameters of the resulting product code are given by $[[n_1n_2,k_1k_2,d, w]]$ where in general $d\leq d_1d_2$ and $w\leq w_1+w_2$. By taking a pair of random CSS codes with $n_1=n_2$ physical qubits, $k_1=k_2$ logical qubits such that $k_i=cn_i$ for some small constant $c$, the resulting product code on $n=n_1n_2$ physical qubits has (with high probability) parameters of the form $[[n,\Omega(n),\Omega(n), O(\sqrt{n})]]$. Thus, homological product codes are an example of good quantum codes, which are almost LDPC.
 

Tranversal gates in permutation-invariant codes and CSS codes

Let $S_n$ be the group of permutations of the $n$-element set $[n]:=\{1 , 2, \dots, n\}$, and let $\pi\in S_n$. Define the unitary $U_\pi: (\mathbb{C}^2)^{\otimes n}\mapsto(\mathbb{C}^2)^{\otimes n}$ by
\[
U_\pi(\ket{\varphi_1}\otimes\cdots\otimes\ket{\varphi_n})=\ket{\varphi_{\pi^{-1}(1)}}\otimes\cdots\otimes\ket{\varphi_{\pi^{-1}(n)}}
\]
for all product states $\ket{\varphi_1}\otimes\cdots\otimes\ket{\varphi_n}$ (and extended linearly to all of $(\mathbb{C})^{\otimes{n}}$). Denote by $(i j)$ the transposition of $i,j\in[n]$ for $i\neq j$, and define the subspace
\[
Q_n=\{\ket{\Psi}\in(\mathbb{C})^2)^{\otimes{n}} \mid U_{(i j)}\ket{\Psi}=\ket{\Psi} \  \text{for all} \ i\neq j \}.
\]

 Let $\vec{b}=b_1b_2\dots b_n \in\{0,1\}^n$ with $b_i\in\{0,1\}$, and let $\ket{\vec{b}}\in(\mathbb{C}^2)^{\otimes n}$ be a $n$-qubit computational basis state. More explicitly, $\ket{\vec{b}}=\bigotimes_{i=1}^{n}\ket{b_i}$, describes the $n$-qubit state where each qubit is either in the state $\ket{0}$ or $\ket{1}$. Now define the map
 \[
  \omega: \{0,1\}^n\to \{0,1,\dots,n\} \ \ \text{given as} \ \  \omega(\vec{b})=\SUM{i=1}{n}b_i,
  \]
  which simply counts the number of $1$s appearing in the bit string $\vec{b}$, and call $\omega(\vec{b})$ the \emph{weight} of $\vec{b}$.
 
It was shown in a previous post that a basis of $Q_n$ is given by the $n+1$ states of the form
 
  \[
  \ket{\omega_k}=\frac{1}{\sqrt{\binom{n}{k}}}\SUM{ \ \ \vec{b} \  : \  \omega(\vec{b})=k}{}\ket{\bar{b}},
    \]
   
  where each basis state $\ket{\omega_k}$, for $k\in\{0,1,\dots, n\}$, consists of an equally weighted superposition of the $\binom{n}{k}$ computational basis states $\ket{\vec{b}}$ with weight $\omega(\vec{b})=k$.


 Consider the two dimensional subspace of $Q_n$ which is spanned by the following two states:
 \[\begin{align*}
 \ket{\overline{0}}&:=\ket{\omega_0}=\TENSOR{i=1}{n}\ket{0}=\ket{\vec{0}}, \\
 \ket{\overline{1}}&:=\frac{1}{\sqrt{2^n-1}}\SUM{k=1}{n}\sqrt{\binom{n}{k}}\ket{\omega_k} \\
 &=\frac{1}{\sqrt{2^n-1}}\SUM{\vec{b}\neq\vec{0}}{}\ket{\vec{b}},
 \end{align*}  \]
 and note that $\ip{\overline{0}}{\overline{1}}=0$. Moreover, since each of $\ket{\overline{0}}$ and $\ket{\overline{1}}$ are given by superpositions of basis states of $Q_n$ each state is left invariant under the action of $U_{(ij)}$ for any transposition $(ij)\in S_n$. Therefore, the two dimensional subspace spanned by $\ket{\overline{0}}$ and $\ket{\overline{1}}$ is a valid subcode of $Q_n$. 

  Now, observe the action of the transversal Hadamard gate applied to each of the $n$ qubits of the state $\ket{\overline{0}}$

\[ \begin{align*}
 H^{\otimes n}\ket{\overline{0}}&= H^{\otimes n}\ket{\vec{0}} \\
  &=\frac{1}{\sqrt{2^n}}\SUM{\vec{b}\in\{0,1\}^n}{}\ket{\vec{b}} \\
  &=\frac{1}{\sqrt{2^n}}\ket{\vec{0}}+\frac{1}{\sqrt{2^n}}\SUM{\vec{b}\neq \vec{0}}{}\ket{\vec{b}} \\
  =&\frac{1}{\sqrt{2^n}}\ket{\vec{0}}+\frac{\sqrt{2^n-1}}{\sqrt{2^n}}\left(\frac{1}{\sqrt{2^n-1}}\SUM{\vec{b}\neq \vec{0}}{}\ket{\vec{b}}\right) \\
  &=\sqrt{2^{-n}}\ket{\overline{0}}+\sqrt{1-2^{-n}}\ket{\overline{1}}. \\
 \end{align*}\]

 Instead, observe the action of $H^{\otimes n}$ on the state $\ket{\overline{1}}$:
\[  \begin{align*}
 H^{\otimes n}\ket{\overline{1}}&= \frac{1}{\sqrt{2^n-1}}\SUM{\vec{b}\neq\vec{0}}{}H^{\otimes n}\ket{\vec{b}} \\
 &= \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}\SUM{ \ \vec{c}\in\{0,1\}^n}{}(-1)^{\vec{b}\cdot\vec{c}}\ket{\vec{c}} \\
 &= \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{0}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}\SUM{ \ \vec{c}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{c}}\ket{\vec{c}}  \\
  &= \frac{2^n-1}{\sqrt{2^n-1}\sqrt{2^n}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}\SUM{ \ \vec{c}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{c}}\ket{\vec{c}}  \\
  &= \sqrt{1-2^{-n}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{b}\neq\vec{0}}{}\SUM{ \ \vec{c}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{c}}\ket{\vec{c}}  \\
 &= \sqrt{1-2^{-n}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n-1}\sqrt{2^n}}\SUM{\vec{c}\neq\vec{0}}{}\left(\SUM{ \ \vec{b}\neq\vec{0}}{}(-1)^{\vec{b}\cdot\vec{c}}\right)\ket{\vec{c}}  \\
  &= \sqrt{1-2^{-n}}\ket{\vec{0}} + \frac{1}{\sqrt{2^n}}\frac{1}{\sqrt{2^n-1}}\SUM{\vec{c}\neq\vec{0}}{}\left(-1\right)\ket{\vec{c}}  \\
    &= \sqrt{1-2^{-n}}\ket{\overline{0}} - \sqrt{2^{-n}}\ket{\overline{1}}.  \\
 \end{align*}\]

 Thus, in summary the action of $H^{\otimes n}$ on $\ket{\overline{0}}$ and $\ket{\overline{1}}$ is given by:
 \[\begin{align*}
 \ket{\overline{0}}&\overset{H^{\otimes n}}\mapsto \sqrt{2^{-n}}\ket{\overline{0}}+\sqrt{1-2^{-n}}\ket{\overline{1}} \\
  \ket{\overline{1}}&\overset{H^{\otimes n}}\mapsto \sqrt{1-2^{-n}}\ket{\overline{0}}-\sqrt{2^{-n}}\ket{\overline{1}},
 \end{align*}\]

 which is given by the logical operation $\overline{U}$ given by the matrix expressed in the logical basis as
 \[
 \overline{U}=\begin{pmatrix}
 \sqrt{2^{-n}} & \sqrt{1-2^{-n}}\\
  \sqrt{1-2^{-n}}&-\sqrt{2^{-n}} \\
 \end{pmatrix}.
 \]

Transitioning now into the setting of CSS codes, let $H_1, H_2$ be parity check matrices such that $Q=CSS(H_1,H_2)$ is a $[[n,k,d]]$-CSS code. The matrix of stabilizers for this code is given by the binary symplectic matrix
  \[
 S= \left(\begin{array}{c | c}
  0&H_1 \\
  H_2 & 0
  \end{array}\right)
  \]
 
  The action of conjugation by a transversal Hadamard applied to the symplectic matrix $S$ transforms it to 
    \[
 S'=H^{\otimes n}SH^{\otimes n \dagger} \left(\begin{array}{c | c}
  0&H_2 \\
  H_1 & 0
  \end{array}\right)
  \]
 
  Suppose that $H^{\otimes n}$ preserves the code space so that $H^{\otimes n}Q=Q$. This action must send codewords of $Q$ to codewords of $Q$ and only permute the set of stabilizers of the code.  Since $H^{\otimes n}$ effectively turns $X$-type generators into $Z$-type generators, then it must be the case that any row $r_i$ of $H_1$ lies in the span of the rows of $H_2$, and likewise that any row $r'_i$ of $H_2$ lies in the span of the rows of $H_1$. That is, $Row(H_1)\subseteq Row(H_2)$ and $Row(H_2)\subseteq Row(H_1)$, which is equivalent to the condition that
  \[
  Row(H_1)=Row(H_2),
  \] 
  where $row(H_i)$ represents the space spanned by rows of $H_i$.
 
  Now, suppose instead that $Row(H1)=Row(H_2)$. This implies that a row of $H_1$ (or $H_2$) can be expressed in terms of the rows of $H_2$ (or $H_1$). Then after the action of a transversal Hadamard $H^{\otimes n }$, each $X$-type (or $Z$-type) stabilizer will be transformed into a $Z$-type ($X$-type) stabilizer that can be generated by the original set of $Z$-type ($X$-type) stabilizers. Hence, the action of $H^{\otimes n}$ preserves the codespace: $H^{\otimes n}Q=Q$.
 
Therefore, the condition that $Row(H_1)=Row(H_2)$ is both a necessary and sufficient condition for $H^{\otimes n}Q=Q$. If $H_1=H_2$, then trivially $Row(H_1)=Row(H_2)$ so that $H^{\otimes n}Q=Q$.


Suppose that $H=H_1=H_2$ and $n$ is odd. Let $Row(H)$ be the space spanned by the rows of $H$, and assume that $|v|=\sum_{j=1}^{n}=0 \ (mod \ 2)$ for every $v\in Row(H)$. Note that this implies that $\vec{1}\in Row(H)^\perp\backslash Row(H)$, where $\vec{1}=(1,\dots,1)$ ($n$ times).

Therefore, the operators given by $X^{\otimes n}$ and $Z^{\otimes n}$ are in the normalizer of the stabilizer for $Q$, because each stabilizer will commute with $X^{\otimes n}$ and $Z^{\otimes n}$ as the size of the intersection of the supports of any stabilizer with either $X^{\otimes n}$ and $Z^{\otimes n}$ is even. Moreover, $X^{\otimes n}$ and $Z^{\otimes n}$ are not in the stabilizer since every stabilizer acts nontrivially only on an even number of physical qubits whereas $X^{\otimes n}$ and $Z^{\otimes n}$ acts on all $n$ qubits (where $n$ is odd). Hence, the operators $X^{\otimes n}$ and $Z^{\otimes n}$ yield a logical operation on $Q$ on some encoded qubit. Without loss of generality associate these logical operations to act on the first encoded qubit:
\[\begin{align*}
\overline{X}_1&=X^{\otimes n} \\
\overline{Z}_2&=Z^{\otimes n}
\end{align*}\]

Consider then the logical basis states for the $1$st encoded qubit: $\ket{\overline{0}}_1$ and $\ket{\overline{1}}_1$. In this basis, these states can be expressed as:
\[\begin{align*}
\ket{\overline{0}}_1\bra{\overline{0}}_1&=\frac{I+\overline{Z}}{2} \\
\ket{\overline{1}}_1\bra{\overline{1}}_1&=\frac{I-\overline{Z}}{2}.
\end{align*}\]

Then since $HXH^\dagger=Z$ and $HZH\dagger=X$, this implies that $H^{\otimes n}\overline{X}H^{\otimes n \dagger}=\overline{Z}$ and $H^{\otimes n}\overline{Z}H^{\otimes n \dagger}=\overline{X}$. Therefore,
\[\begin{align*}
H^{\otimes n}\left(\frac{I+\overline{Z}}{2}\right)H^{\otimes n \dagger}&=\frac{I+\overline{X}}{2}=\ket{\overline{+}}_1\bra{\overline{+}}_1 \\
H^{\otimes n}\left(\frac{I-\overline{Z}}{2}\right)H^{\otimes n \dagger}&=\frac{I-\overline{X}}{2}=\ket{\overline{-}}_1\bra{\overline{-}}_1,
\end{align*}\]
  where $\ket{\overline{+}}=\frac{1}{\sqrt{2}}(\ket{\overline{0}}_1+\ket{\overline{1}}_1)$ and $\ket{\overline{-}}=\frac{1}{\sqrt{2}}(\ket{\overline{0}}_1-\ket{\overline{1}}_1)$. Hence, the action of $H^{\otimes n}$ on the logical computational basis of the first encoded qubit is given by a logical Hadamard on that encoded qubit:
\[  \begin{align*}
  \ket{\overline{0}}&\overset{\overline{H}}\mapsto\ket{\overline{+}},\\
  \ket{\overline{1}}&\overset{\overline{H}}\mapsto\ket{\overline{-}}.
  \end{align*}\]
 
  In regards to the action of $H^{\otimes n}$ on the rest of the $k-1$ encoded qubits, recall that $H^{\otimes n}$ preserves the code space. Therefore, $H^{\otimes n}$ merely permutes the individual stabilizers. More generally, $H^{\otimes n}$ is in the Clifford group $C_n$. Thus, it must be the case that $H^{\otimes n}=\overline{H}\otimes \overline{C}$, where $\overline{C}$ is some logical Clifford operation since $H^{\otimes n}$ is a Clifford operation.    
 

Probabilistic implementation of gates by cyclic permutation and measurement

Given an $n$- qubit Pauli operator $P=P_1\otimes \cdots \otimes P_n$, with $P_j\in\{I,X,Y,Z\}$, let $\eta(P)=P_2\otimes P_3\otimes\cdots\otimes P_n\otimes P_1$ be the Pauli operator obtained by cyclically permuting the factors. Let $S$ be a stabilizer with generators $\{M_j\}_j$, and let $\{\overline{X}_l,\overline{Z}_l\}_l$ be generators of $N(S)/S$. Consider the stabilizer $\eta(S)$ defined by generators $\{M'_j:=\eta(M_j)\}_j$, and the associated generators $\{\overline{X}'_l=\eta(\overline{X}_l), \overline{Z}'_l=\eta(\overline{Z}_l)\}_l$ of $N(\eta(S))/\eta(S)$.
Consider the following process:
  1. Start with some encoded state $\ket{\overline{\Psi}}$ for $S$.
  2. Measure all the stabilizer generators of $\eta(S)$.
  3. Output `success' and the post-measurement state if all outcomes are $+1$.

Let $S$ be the stabilizer of the $[[5,1,3]]$-code, and let $\ket{\overline{\Psi}}\in\mathcal{T}(S)$ be an arbitrary encoded state.

The stabilizer generators $S=<M_1,M_2,M_3,M_4>$ for this 5-qubit code, are given by
\[\begin{align*}
M_1=&X \ Z \ Z \ X \ I \\
M_2=& I \ X \ Z \ Z \ X \\
M_3=& X \ I \ X \ Z \ Z \\
M_4=& Z \ X \ I \ X \ Z ,
\end{align*}\]
and so the resulting generators for $\eta(S)=<M'_1,M'_2,M'_3,M'_4>$ are given by
\[\begin{align*}
M'_1=&Z \ Z \ X \ I \ X \\
M'_2=&X \ Z \ Z \ X \ I \\
M'_3=& I \ X \ Z \ Z \ X \\
M'_4=& X \ I \ X \ Z \ Z. \\
\end{align*}\]

Observe that $M'_2=M_1$, $M'_3=M_2$, $M'_4=M_3$, and that $M'_1=M_1M_2M_3M_4$. Thus, each of the generators $M'_j$ can be expressed in terms of the generators of $S$, which implies that $\eta(S)=S$. Since each $M\in S=\eta(S)$ satisfies $M\ket{\overline{\Psi}}=\ket{\overline{\Psi}}$, measuring the stabilizer generators $M'_j$ will always yield an outcome corresponding to $+1$, and the state will be left invariant as $\ket{\overline{\Psi}}$.  In regards to the procedure outlined above, the success probability will be $1$, and the post-measurement state will be $\ket{\overline{\Psi}}$.


Consider the set of stabilizers $S=<M_1,M_2>$ and generators of $N(S)/S=<\overline{X}_1,\overline{Z}_1,\overline{X}_2,\overline{Z}_2>$ given by
\[\begin{align*}
M_1=&X \ X \ X \ I  \\
M_2=& I \ Z \ Z \ I  \\
\overline{X}_1=& I \ X \ X \ I \\
\overline{Z}_1=& Z \ I \ Z \ I   \\
\overline{X}_2=& I \ I \ I \ X \\
\overline{Z}_3=&I \ I \ I \ Z.
\end{align*}\]

Then the stabilizer generators of $\eta(S)=<M'_1,M'_2>$ are given by
\[\begin{align*}
M'_1=&X \ X \ I \ X  \\
M'_2=& Z \ Z \ I \ I.  \\
\end{align*}\]
It is readily seen that $\{M'_1,M_i\}=0$ and $[M'_2,M_i]=0$, for $i=1,2$, implying that $M'_1\notin N(S)$, and that $M'_2\in N(S)$ but $M'_2\notin S$.


Consider the set of stabilizer generators of $S=<M_1,M_2>$ and generators of \\ $N(S)/S=<\overline{X}_1,\overline{Z}_1,\overline{X}_2,\overline{Z}_2>$ given by
\[\begin{align*}
M_1 =& X \ X \ X \ I \\
M_2 =& I \ Z \ Z \ I \\
\overline{X}_1=& I \ X \ X \ I \\
\overline{Z}_1=& Z \ I \ Z \ I \\
\overline{X}_2=& I \ I \ I \ X \\
\overline{Z}_2=& I \ I \ I \ Z, \\
\end{align*}\]

and the generators of $\eta(S)$ and $N(\eta(S))/\eta(S)$ given by

\[\begin{align*}
M'_1 =& X \ X \ I \ X \\
M'_2 =& Z \ Z \ I \ I \\
\overline{X}'_1=& X \ X \ I \ I \\
\overline{Z}'_1=& I \ Z \ I \ Z \\
\overline{X}'_2=& I \ I \ X \ I \\
\overline{Z}'_2=& I \ I \ Z \ I. \\
\end{align*}\]

Suppose the initial state is an encoded state $\ket{\overline{\Psi}}=\ket{\overline{+}}_1\otimes\ket{\overline{0}}_2$. Here, $\ket{\overline{+}}_1$ is interpreted as an encoded state of $3$ physical qubits, and the other encoded state $\ket{\overline{0}}_2$ in the tensor product is an encoded state represented by a single qubit.

More explicitly, consider the state $\frac{1}{\sqrt{2}}(\ket{000}+\ket{111})$ and observe that
\[
\overline{X}_1\frac{1}{\sqrt{2}}(\ket{000}+\ket{111})=\frac{1}{\sqrt{2}}(\ket{011}+\ket{100}),
\]
 which suggests the encoded basis is given by
 \[
\ket{\overline{0}}_1= \frac{1}{\sqrt{2}}(\ket{000}+\ket{111}) \ \ \text{and} \ \ \ket{\overline{1}}_1=\frac{1}{\sqrt{2}}(\ket{011}+\ket{100}).
 \]
 For the second encoded qubit, it must be that $\ket{\overline{0}}_2=\ket{0}$ and $\ket{\overline{1}}_2=\ket{1}$.

 Hence, the intitial encoded state is of the form
\[ \begin{align*}
 \ket{\overline{\Psi}}=&\ket{\overline{+}}_1\ket{\overline{0}}_2 \\
 =&\frac{1}{\sqrt{2}}(\ket{\overline{0}}_1+\ket{\overline{1}}_1)\ket{\overline{0}}_2 \\
 =&\frac{1}{\sqrt{2}}(\ket{000}+\ket{111}+\ket{011}+\ket{100})\ket{0} \\
 =&\frac{1}{\sqrt{2}}(\ket{0000}+\ket{1110}+\ket{0110}+\ket{1000}).
 \end{align*}\]

Consider the two permuted stabilizer $M'_1$ and $M'_2$. Note that $M'_1$ anticommutes with all of the logical Pauli operators in $N(S)/S$ so that $M'_1\notin N(S)$.  On the contrary, note that $M'_2$ does commute with all generators of $N(S)/S$, yet is not in the stabilizer $S$ since it cannot be generated by $M_1$ and $M_2$. Therefore, $M'_2\in N(S)\backslash S$, and can be expressed as a logical operation as $M'_2=\overline{Z}_1M_2$.

 Now suppose the operator $M'_2$ is measured on the encoded state $\ket{\overline{\Psi}}$. Since $M'_2=\overline{Z}_1M_2$ has the effect of applying a logical $Z$ operation on the first encoded qubit, which is in the state $\ket{\overline{+}}$, the probability of observing a $+1$ eigenvalue is $1/2$. In this case, the state after measuring $M'_2$ can be determined by applying the projector into the $+1$ eigenstate of $M'_2$:
\[ \begin{align*}
 \frac{1}{2}(I+M'_2)\ket{\overline{\Psi}}=&\frac{1}{2}(I+\overline{Z}_1M_2)(\ket{\overline{+}}_1\ket{\overline{0}}_2)\\
 =&\frac{1}{2}(\ket{\overline{+}}_1\ket{\overline{0}}_2+\ket{\overline{-}}_1\ket{\overline{0}}_2) \\
 =&\frac{1}{2}\ket{\overline{0}}_1\ket{\overline{0}}_2
\end{align*} \]

Thus, after renormalization the resulting state is given by $\ket{\overline{0}}_1\ket{\overline{0}}_2$.

Now, consider measuring $M'_1$. Since $M'_1\notin N(S)$, it commutes with exactly half of the Paulis and anticommutes with the other half. This gives a $1/2$ probability of measuring a $+1$ eigenvalue. Hence, the overall success probability of measuring a $+1$ outcome for both operators $M'_1$ and $M'_2$ is given by $1/4$.

Moreover, the resulting state after this second measurement is made is determined via the projector:
\[ \begin{align*}
 \frac{1}{2}(I+M'_1)\ket{\overline{0}}_1\ket{\overline{0}}_2=&\frac{1}{2\sqrt{2}}(I+M'_1)(\ket{000}\ket{0}+\ket{111}\ket{0}) \\
 =&\frac{1}{2\sqrt{2}}(\ket{000}\ket{0}+\ket{111}\ket{0}+\ket{110}\ket{1}+\ket{001}\ket{1})\\
 \rightarrow& \ \frac{1}{2}(\ket{000}\ket{0}+\ket{111}\ket{0}+\ket{110}\ket{1}+\ket{001}\ket{1}),
\end{align*} \]
 where the resulting state has been normalized accordingly.

 In the context of the permuted stabilizer $\eta(S)$, the $2$nd encoded qubit now appears physically in the $3$rd register of the system. Then by effectively permuting the qubits cyclically, the final state can be expressed in the form
  \[\begin{align*}
\ket{\psi_{final}}=& \frac{1}{2}(\ket{000}\ket{0}+\ket{011}\ket{1}+\ket{111}\ket{0}+\ket{100}\ket{1}) \\
=&\frac{1}{2}((\ket{000}+\ket{111})\ket{0}+(\ket{011}+\ket{100})\ket{1})\\
=&\frac{1}{2}(\ket{\overline{0}}_1\ket{\overline{0}}_2+\ket{\overline{1}}_1\ket{\overline{1}}_2),
 \end{align*}\]
 showing that the state is entangled between logical qubits.

Clifford circuits for stabilizer codes

 Consider the quantum code $T(S)$ defined by the encoding circuit shown below:



The initial state is of the form $\ket{\psi}\ket{0}\ket{+}$, where $\ket{\psi}$ is an arbitrary single qubit state to be encoded. Two stabilizers $M_1$ and $M_2$ acting on the three qubits can be associated to this initial state such that $\ket{0}$ is a $+1$ eigenstate of $M_1$ and $\ket{+}$ is a $+1$ eigenstate of $M_2$. Since $Z\ket{0}=\ket{0}$ and $X\ket{+}=\ket{+}$, then $M_1=IZI$ and $M_2=IIX$. The ``logical" Pauli operators in this case are simply $\overline{X}=XII$ and $\overline{Z}=ZII$.

When passing through some gate $U$ in an encoding circuit the stabilizer generators and logical Pauli operators after the action of the gate $U$ can be updated to new stabilizer generators $M'_1, M'_2$ and new logical Paulis $\overline{X}', \overline{Z}'$ given by conjugation by $U$:
\[
M'_1=UM_1U^\dagger , M'_2=UM_2U^\dagger, \overline{X}'=U\overline{X}U^\dagger, \overline{Z}'=U\overline{Z}U^\dagger.
\]

In the table shown below, such an updating procedure is shown for every gate in the encoding circuit. The following relations were used throughout
\[\begin{align*}
&HXH=Z, \ \  HZH=X , \ \ \ \  RXR^\dagger=Y, \ \  RZR^\dagger=Z \\
&CNOT(X\otimes I)CNOT=X\otimes X, \  \  CNOT(I\otimes X)CNOT=I\otimes X \\
&CNOT(Z\otimes I)CNOT=Z\otimes I, \ \  CNOT(I\otimes Z)CNOT=Z
\otimes Z
\end{align*}\]



Therefore, the stabilizer generators of $S$ are $M_1=-YZY$ and $M_2=-XXY$, and the logical Pauli operators corresponding to generators of $N(S)/S$ are $\overline{X}=IYX$ and $\overline{Z}=-XXY$.


Let $\delta$ be an $n\times n$ matrix and $S$ a $2n\times 2n$ matrix given as
\[
S=\begin{pmatrix}
0 & \delta \\
\delta & 0
\end{pmatrix},
\]
where here $0$ is an $n\times n$ matrix. By definition, $S$ is symplectic if and only if $J=S^TJS$, where
\[
J=\begin{pmatrix}
0 &I \\
I & 0
\end{pmatrix}.
\]
Then since
\[
\begin{pmatrix}
0 &I \\
I & 0
\end{pmatrix}=\begin{pmatrix}
0 &\delta^T \\
\delta^T & 0
\end{pmatrix}\begin{pmatrix}
0 &I \\
I & 0
\end{pmatrix}
\begin{pmatrix}
0 &\delta \\
\delta & 0
\end{pmatrix}
=\begin{pmatrix}
0 &\delta^T\delta \\
\delta^T\delta & 0
\end{pmatrix},
\]
in order for $S$ to be a symplectic matrix it must be the case that $I=\delta^T\delta$. Let the columns of the matrix $\delta$ be given by $\vec{r}_i\in\mathbb{Z}^n_2$ for $i\in\{1,\dots,n\}$. Then the condition $I=\delta^T\delta$ can then be interpreted as requiring each row $\vec{r}_i$ to have unit norm, $\vec{r}_i\cdot\vec{r}_i=1 (mod \ 2)$, and also that distinct rows be orthogonal, $\vec{r}_i\cdot\vec{r}_j=0 (mod \ 2)$ for $i\neq j$.

Now let the matrix $\delta=(d_{a,b})_{a,b}$ be given by
\[
d_{a,b}=
\left\{
\begin{array}{ll}
1 \ \ \text{for} \ \ a \neq b\\
\\
0\ \ \text{for} \ \ a=b\\

\end{array}
\right.
\]

Then the condition $\delta^T\delta=I$, implies that  $\delta^T\delta=\delta^2=(\sum_{i=1}^{n}d_{a,i}d_{i,b})_{a,b}=(\delta_{a,b})_{a,b}=I$. Therefore, $\sum_{i=1}^{n}d_{a,i}d_{i,a}=\sum_{i=1}^{n}d^2_{a,i}=n-1(mod 2)=1$ and $\sum_{i=1}^{n}d_{a,i}d_{i,b}=n-2(mod 2)=0$, which implies that $n$ must be even. Hence the matrix
\[
S=\begin{pmatrix}
0 & \delta \\
\delta & 0
\end{pmatrix},
\]
is symplectic if and only if $n$ is even.

Consider the case $n=4$ with $\delta$ defined as above. Then
\[
S=\begin{pmatrix}
0 &0 & 0& 0 & 0 & 1 & 1&1 \\
0 &0 & 0& 0 & 1 & 0 & 1&1 \\
0 &0 & 0& 0 & 1 & 1 & 0&1 \\
0 &0 & 0& 0 & 1 & 1 & 1&0 \\
0 &1 & 1& 1 & 0 & 0 & 0&0 \\
1 &0 & 1& 1 & 0 & 0 & 0&0 \\
1 &1 & 0& 1 & 0 & 0 & 0&0 \\
1 &1 & 1& 0 & 0 & 0 & 0&0 \\
\end{pmatrix}
\]
The objective here will be to find symplectic matrices $V_{L,k},V_{R,k}\in\{H, CNOT\}$ such that
\[
\left(\PROD{k=1}{g_L}V_{L,k} \right)S\left(\PROD{k=1}{g_R}V_{R,k} \right)=I.
\]
This would then imply that
\[
\left(\PROD{k=g_l}{1}V^\dagger_{L,k} \right)\left(\PROD{k=g_R}{1}V^\dagger_{R,k} \right)=S,
\]
giving a decomposition of $S$ in terms of $H$ and $CNOT$ gates alone. Actually, in what follows, only matrices acting from the left will be considered, so that $g_R=0$ and
\[
\left(\PROD{k=1}{g_L}V_{L,k} \right)S=I \ \ \text{so that} \ \ \left(\PROD{k=g_L}{1}V^\dagger_{L,k} \right)=S
\]
In general, for a symplectic matrix in the block form:
\[
U=\begin{pmatrix}
A & B \\
C & D
\end{pmatrix},
\]
the action of multiplying on the left by $H_i$ has the effect of switching the $i$th rows of $(A | B )$ and $(C | D )$. The action of $CNOT_{i,j}$ has the effect of adding the $i$th row of $(A |B)$ to the $j$th row of $(A | B )$, and adding the $j$th row of $( C | D ) $ to the $i$th row of $(C|D)$.

Consider the following sequence of transformations:
\[\begin{align*}
S=\begin{pmatrix}
0 &0 & 0& 0 & 0 & 1 & 1&1 \\
0 &0 & 0& 0 & 1 & 0 & 1&1 \\
0 &0 & 0& 0 & 1 & 1 & 0&1 \\
0 &0 & 0& 0 & 1 & 1 & 1&0 \\
0 &1 & 1& 1 & 0 & 0 & 0&0 \\
1 &0 & 1& 1 & 0 & 0 & 0&0 \\
1 &1 & 0& 1 & 0 & 0 & 0&0 \\
1 &1 & 1& 0 & 0 & 0 & 0&0 \\
\end{pmatrix}
\overset{CN_{4,1}CN_{3,1}CN_{2,1}}\rightarrow&
\begin{pmatrix}
0 &0 & 0& 0 & 1 & 1 & 1&1 \\
0 &0 & 0& 0 & 1 & 0 & 1&1 \\
0 &0 & 0& 0 & 1 & 1 & 0&1 \\
0 &0 & 0& 0 & 1 & 1 & 1&0 \\
0 &1 & 1& 1 & 0 & 0 & 0&0 \\
1 &1 & 0& 0 & 0 & 0 & 0&0 \\
1 &0 & 1& 0 & 0 & 0 & 0&0 \\
1 &0 & 0& 1 & 0 & 0 & 0&0 \\
\end{pmatrix}
\\
\overset{CN_{1,4}CN_{1,3}CN_{1,2}}\rightarrow&
\begin{pmatrix}
0 &0 & 0& 0 & 1 & 1 & 1&1 \\
0 &0 & 0& 0 & 1 & 0 & 0&0 \\
0 &0 & 0& 0 & 0 & 0 & 1&0 \\
0 &0 & 0& 0 & 0 & 0 & 0&1 \\
1 &0 & 0& 0 & 0 & 0 & 0&0 \\
1 &1 & 0& 0 & 0 & 0 & 0&0 \\
1 &0 & 1& 0 & 0 & 0 & 0&0 \\
1 &0 & 0& 1 & 0 & 0 & 0&0 \\
\end{pmatrix}
\\
\overset{CN_{4,1}CN_{3,1}CN_{2,1}}\rightarrow&
\begin{pmatrix}
0 &0 & 0& 0 & 1 & 0 & 0&0 \\
0 &0 & 0& 0 & 0 & 1 & 0&0 \\
0 &0 & 0& 0 & 0 & 0 & 1&0 \\
0 &0 & 0& 0 & 0 & 0 & 0&1 \\
1 &0 & 0& 0 & 0 & 0 & 0&0 \\
0 &1 & 0& 0 & 0 & 0 & 0&0 \\
0 &0 & 1& 0 & 0 & 0 & 0&0 \\
0 &0 & 0& 1 & 0 & 0 & 0&0 \\
\end{pmatrix}
\\
\overset{H_{1}H_{2}H_{3}H_{4}}\rightarrow&
\begin{pmatrix}
1 &0 & 0& 0 & 0 & 0 & 0&0 \\
0 &1 & 0& 0 & 0 & 0 & 0&0 \\
0 &0 & 1& 0 & 0 & 0 & 0&0 \\
0 &0 & 0& 1 & 0 & 0 & 0&0 \\
0 &0 & 0& 0 & 1 & 0 & 0&0 \\
0 &0 & 0& 0 & 0 & 1 & 0&0 \\
0 &0 & 0& 0 & 0 & 0 & 1&0 \\
0 &0 & 0& 0 & 0 & 0 & 0&1 \\
\end{pmatrix}=I
\end{align*}\]

Recalling that $H^\dagger=H$ and $CNOT^\dagger=CNOT$, and reversing the order of the operations used above then yields a sequence of operations that implements $S$ (the rightmost operation is applied first) :

\[
S=CN_{2,1}CN_{3,1}CN_{4,1}CN_{1,2}CN_{1,3}CN_{1,4}CN_{2,1}CN_{3,1}CN_{4,1}H_{4}H_{3}H_{2}H_{1}.
\]

A circuit diagram depicting this sequence is shown below:




CSS codes and the 9-qubit Shor code

In the 9-qubit Shor code, the stabilizer $S$ is generated by the following operators

\[\begin{align*}
S_1=& Z_1Z_2 \\
S_2=&Z_2Z_3 \\
S_3=&Z_4Z_5 \\
S_4=&Z_5Z_6 \\
S_5=&Z_7Z_8 \\
S_6=&Z_8Z_9 \\
S_7=&X_1X_2X_3X_4X_5X_6 \\
S_8=&X_4X_5X_6X_7X_8X_9. \\
\end{align*}\]
 Thus, the the dimension of the code space is $2^{9-8}=2$, which implies that the code only encodes one logical qubit. In this case, $\hat{N}(S)/S\cong \hat{P}_1$, so $\hat{N}/S$ will be generated by some elements $\overline{X}, \overline{Z}\in\hat{N}(S)\backslash S$, satisfying the usual Pauli commutation relations:
 \[
\overline{X}^2=\overline{Z}^2=\overline{I}, \  \text{and} \  \overline{X} \ \overline{Z}=-\overline{Z} \ \overline{X}
 \]
 In this regard, let
\[\begin{align*}
 \overline{Z}=&X_1X_2X_3X_4X_5X_6X_7X_8X_9 \\
  \overline{X}=& Z_1Z_2Z_3Z_4Z_5Z_6Z_7Z_8Z_9 \\
\end{align*}\]
 which satisfy the commutation relations described above. Moreover, $\overline{Z}\in\hat{N}(S)\backslash S$. To see this, note that
\[ \begin{align*}
 [\overline{Z},S_i]=0&, \ \text{for} \  i=7,8 \\
  [\overline{X},S_i]=0&, \ \text{for} \  i=1,2,3,4,5,6 \\
 \end{align*}\]
 because each of these ease either a product of only $X$ operators or only $Z$ operators. The less trivial relations
 \[ \begin{align*}
 [\overline{Z},S_i]=0&, \ \text{for} \ i=1,2,3,4,5,6  \\
  [\overline{X},S_i]=0&, \ \text{for} \ i=7,8  \\
 \end{align*}\]

also hold, because the intersection of the supports of $\overline{Z}$ and $S_i$ ( for $ i=1,2,3,4,5,6 $) is always an even number of qubits. Likewise, the intersection of the supports of $\overline{X}$ and $S_i$ ( for $ i=7,8 $) is also always an even number of qubits. Thus, $\overline{X},\overline{Z}\in \hat{N}(S)$.

 Now, to see that $\overline{X},\overline{Z}\notin S$ observe that the product$S_7S_8=X_1X_2X_3X_7X_8X_9\neq\overline{Z}$, which implies $\overline{Z}\notin S$. For $\overline{X}$, it is impossible to even generate an operator that contains all the factors $Z_1Z_2Z_3$ since the only stabilizers that even have nontrivial support on these first three qubits are $S_1$ and $S_2$, but yet  $S_1S_2=Z_1Z_3\neq Z_1Z_2Z_3$. Therefore, $\overline{X}\notin S$.


Consider the binary matrix
\[
\delta=\begin{pmatrix}
1&1&1&0&0 \\
0&0&1&1&1\\
1&1&0&1&1 \\
1&1&1&0&0 \\
0&0&1&1&1\\
\end{pmatrix}.
\]
 Associate to each row $j$ an $X$-type stbilizer
 \[
 M_j=\PROD{l=1}{5}X_l^{\delta_{jl}},
 \]
 and to each column a $Z$-stabilizer
 \[
  N_j=\PROD{l=1}{5}Z_l^{\delta_{lj}}.
 \]
 The product of the matrix $\delta$ with itself (modulo $2$) effectively computes products of  all the $M_j$ operators with all the $N_j$ operators. The $i,j$th coefficient in the matrix of $\delta^2$,  has a value of $0$ if $M_iN_j$ commute and has a value of $1$ if $M_iN_j$ anticommute. In fact, since $\delta^2$ gives the matrix with all coefficients $0$, each $M_i$ commutes with each $N_j$. Therefore, the set $Q$ generated by all such products of $M_j$ and $N_i$ forms an abelian subgroup of the Pauli group $\hat{P}_5$. Moreover, since each $M_j$ and $N_j$ square to $+I$, it is necessarily the case that $-I\notin Q$. Hence, $Q$ actually defines a stabilizer group. By choosing linearly independent operators $M_j$ and $N_i$, it is seen that the stabilizer $Q$ can be generated by $\{M_1,M_2,N_1, N_4\}$.


Let $C_1$ and $C_2$ be a classical linear codes with parity check matrices $H_1$ and $H_2$ given by

  \[
 H_1=\begin{pmatrix}
 1&0&1&1&0 \\
 0&1&1&0&1
 \end{pmatrix}
  \ \ \text{and} \  \
  H_2=\begin{pmatrix}
 1&1&1&0&0 \\
 0&0&1&1&1
 \end{pmatrix}.
 \]

Notice that $H_1$ consists of the two $Z$-type stabilizer generators $N_1$ and $N_4$, and $H_2$ consists of the two $X$-type stabilizer generators $M_1$ and $M_2$ defined in (2) that together generate the stabilizer group $Q$. In this way, $Q$ is the CSS code $CSS(H_1,H_2)$. Here, $Q=<S_1\cup S_2>$, where $S_1$ and $S_2$ are the stabilizer groups generated by the $Z$-type and $X$-type operators, respectively.  Namely,
  \[
 S_1=\begin{pmatrix}
  0&0&0&0&0 \\
 1&0&1&1&0 \\
 0&1&1&0&1 \\
  1&1&0&1&1
 \end{pmatrix}
  \ \ \text{and} \  \
 S_2=\begin{pmatrix}
  1&0&1&1&0 \\
 1&1&1&0&0 \\
 0&0&1&1&1\\
  1&1&0&1&1 \\
 \end{pmatrix}.
 \]

Let $G_1$ and $G_2$ be corresponding generator matrices of the codes $C_1$ and $C_2$, respectively. For each code, since there are $5$ physical bits and $3$ encoded bits ($H_1$ and $H_2$ are $2 \times 5$ matrices), both generator matrices have dimensions $3\times 5$. These generators must satisfy the constraints
\[
G_iH_i^T=0 \  \ \text{and} \ \ H_iG_i^T=0.
\]
for $i=1,2$. The constraints form a set of $k$ non-singular equations on $n$ bits. It can be checked that the following two particular matrices satisfy these constraints:
\[
 G_1=\begin{pmatrix}
 1&0&0&1&0 \\
 1&1&0&1&1 \\
  0&1&1&1&0
 \end{pmatrix}
  \ \ \text{and} \  \
G_2=\begin{pmatrix}
 1&0&1&0&1 \\
 1&1&0&0&0 \\
  0&1&1&1&0
 \end{pmatrix}.
\]

The rows of $G_1$ and $G_2$ form a basis of the code spaces $C_1$ and $C_2$, respectively. Hence, the span of each generates the entire code spaces. The elements of these code spaces are then
\[
 C_1=\begin{pmatrix}
 0&0&0&0&0 \\
 1&0&0&1&0 \\
 1&1&0&1&1 \\
  0&1&1&1&0 \\
 0&1&0&0&1 \\
  1&0&1&0&1 \\
   1&1&1&0&0 \\
    0&0&1&1&1
 \end{pmatrix}
  \ \ \text{and} \  \
C_2=\begin{pmatrix}
 0&0&0&0&0 \\
 1&0&1&0&1 \\
 1&1&0&0&0 \\
  0&1&1&1&0 \\
   1&0&1&1&0 \\
    0&1&1&0&1 \\
     1&1&0&1&1 \\
      0&0&0&1&1 \\
 \end{pmatrix}.
\]

By associating a $Z$-type (or $X$-type) operator $\overline{Z}$ (or $\overline{X}$) to each row of $C_2$ (or $C_1$), and demanding that $\overline{Z}\notin S_1$ (and $\overline{X}\notin S_2$) and also that $\overline{Z} \ \overline{X}=-\overline{X} \ \overline{Z}$, then the pair $(\overline{X},\overline{Z})$ can be made to correspond to a logical operation on a logical qubit. In this case, since there is only $1$ logical qubit a single pair satisfying these properties is all that is needed. In this regard, choose
\[
\overline{X}=X_1X_4 \ \ \text{and} \ \ \overline{Z}=Z_1Z_3Z_5
\]
corresponding to the second rows of $C_2$ and $C_1$. Then indeed, $\overline{X}\notin S_2$ and $\overline{Z}\notin S_1$, and $\overline{Z} \ \overline{X}=-\overline{X} \ \overline{Z}$. Therefore, the pair $(\overline{X},\overline{Z})$ function as logical operators on the encoded qubit, and hence generate $\mathcal{N}(S)/S\cong P_1$.


In the classical linear code context, the distances of codes $C_1$ and $C_2$ are both given by $d_1=d_2=2$, which can be seen by examining the elements of $C_1$ and $C_2$ and finding the minimum weight of any non-identity codeword. For $CSS(H_1,H_2)$, the distance of the code $Q$ must satisfy $d\geq min\{d_1,d_2\}=2$. In this context, the distance of $Q$ will be the minimum weight of an operator in $\mathcal{N}(S)\backslash S$, which by inspection is seen to be $d=2$.


In what follows, an algorithm will be described which begins with two parity check matrices $H_1$ and $H_2$ of a general CSS code, and computes a set of generators for $\hat{\mathcal{N}}(S)/S$ grouped into pairs $\{(\overline{X}_i,\overline{Z}_i)\}$.

First, using $H_1$ and $H_2$ (matrices with dimensions $(n-k)\times n$ construct generator matrices $G_1$ and $G_2$ (of dimensions $k\times n$) satisfying the constraints $G_iH_i^T=0$ and $H_iG^T=0$ for each $i=1,2$. Moreover, the rows of such $G_i$ should be linearly independent. Such a procedure can be done in general using the Gram-Schmidt process.

Next, consider the codes paces $C_i$ defined as the span of the rows of $G_i$, and also the stabilizer spaces $S_i$ defined as the span of the rows of $H_i$. Then to find generators of $\hat{\mathcal{N}}(S)/S$, it suffices to choose pairs $(\overline{X}_l,\overline{Z}_l)$ with $\overline{Z}_l\in C_1\backslash S_1$ and $\overline{X}_l\in C_2\backslash S_2$, such that $\overline{X}_l$ and $\overline{Z}_l$ anti commute, and all pairs $(\overline{X}_l,\overline{Z}_l)$ and$(\overline{X}_l',\overline{Z}_l')$ with $l\neq l'$ commute. For $k$ encoded qubits, there will be $k$ many many pairs, corresponding to the logical operations applied to each of the $k$ logical qubits.