## Saturday, 29 March 2014

### 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.