# Transversal Diagonal Logical Operators for Stabiliser Codes

Mark A. Webster<EMAIL_ADDRESS>Centre for Engineered Quantum
Systems, School of Physics, University of Sydney, Sydney, NSW 2006, Australia
Sydney Quantum Academy, Sydney, NSW, Australia  Armanda O. Quintavalle
Department of Physics and Astronomy, University of Sheffield, Sheffield S3
7RH, United Kingdom  Stephen D. Bartlett  Centre for Engineered Quantum
Systems, School of Physics, University of Sydney, Sydney, NSW 2006, Australia

###### Abstract

Storing quantum information in a quantum error correction code can protect it
from errors, but the ability to transform the stored quantum information in a
fault tolerant way is equally important. Logical Pauli group operators can be
implemented on Calderbank-Shor-Steane (CSS) codes, a commonly-studied category
of codes, by applying a series of physical Pauli X and Z gates. Logical
operators of this form are fault-tolerant because each qubit is acted upon by
at most one gate, limiting the spread of errors, and are referred to as
transversal logical operators. Identifying transversal logical operators
outside the Pauli group is less well understood. Pauli operators are the first
level of the Clifford hierarchy which is deeply connected to fault-tolerance
and universality. In this work, we study transversal logical operators
composed of single- and multi-qubit diagonal Clifford hierarchy gates. We
demonstrate algorithms for identifying all transversal diagonal logical
operators on a CSS code that are more general or have lower computational
complexity than previous methods. We also show a method for constructing CSS
codes that have a desired diagonal logical Clifford hierarchy operator
implemented using single qubit phase gates. Our methods rely on representing
operators composed of diagonal Clifford hierarchy gates as diagonal XP
operators and this technique may have broader applications.

##  1 Overview

Quantum error correction has become a very active area of research because of
its potential to mitigate noise in complex quantum devices. Recent
experimental results have validated the storage of quantum information in the
codespace of a quantum error correction code as a practical way of protecting
it from noise (see [1], [2] and [3]). Many of these initial demonstrations
have made use of CSS codes [4], a well-studied class of quantum error
correction codes that are relatively simple to analyse and implement.

To implement algorithms on quantum computers, we also need to transform the
stored quantum information in a fault-tolerant way. One method of implementing
fault-tolerant logical operations on CSS codes is to use transversal logical
operators. Transversal logical operators have depth-one circuit
implementations involving single or multi-qubit gates. Such implementations
are considered fault-tolerant because an error on one physical qubit can only
spread to a limited number of other qubits when applying the logical operator.
Whilst the Eastin-Knill theorem rules out the existence of a quantum error
correcting code with a set of transversal operators that is universal [5],
determining the transversal gates of a quantum error correction code is key to
designing a fault-tolerant architecture.

Deeply connected to fault tolerance and universality is the Clifford hierarchy
[6] of unitary operators. The first level of the Clifford hierarchy is the
Pauli group $\mathcal{CH}_{1}:=\langle iI,X,Z\rangle$. Conjugation of Paulis
by operators at level $t+1$ results in an operator at level $t$. The level
$t+1$ operators $A\in\mathcal{CH}_{t+1}$ are then defined recursively as those
for which $ABA^{-1}\in\mathcal{CH}_{t}$ for all $B\in\mathcal{CH}_{1}$. Level
$2$ Clifford hierarchy gates include the single-qubit Hadamard and
$S:=\sqrt{Z}$ gates, as well as the 2-qubit controlled-Z ($CZ$) gates. Level
$3$ gates include the single-qubit $T:=\sqrt{S}$ gate as well as the multi-
qubit controlled-S ($CS$) and controlled-controlled-Z ($CCZ$) gates. A set of
gates that includes all level-2 gates and at least one level-3 gate is
universal [7].

Logical Pauli group operators can be implemented transversally on CSS codes
and identifying these is relatively straightforward. Identifying transversal
logical operators at higher levels of the Clifford hierarchy is more
challenging and existing methods are of exponential complexity in either the
number of physical or logical qubits in the code. Some classes of CSS codes
with high degrees of symmetry are known to have non-Pauli transversal logical
operators. Examples using single-qubit diagonal gates include the 7-qubit
Steane code [8], two-dimensional color codes [9] and triorthogonal codes [10].
Examples of CSS codes which have logical operators made from single and multi-
qubit gates include the two-dimensional toric code [11], codes with ZX-
symmetries [12] and symmetric hypergraph product codes [13].

In this paper, we present a suite of method and algorithms for identifying
diagonal transversal logical operators on any CSS code, without any knowledge
of any symmetries of the code. The building blocks of our logical operators
are physical single- or multi-qubit diagonal gates, at a given level $t$ of
the Clifford hierarchy. Our methods scale as a polynomial in the number of
physical and/or logical qubits in the code, with one exception. We also give a
method for constructing a CSS code that has a transversal implementation of a
desired diagonal logical Clifford hierarchy operator using single-qubit gates.
Our new algorithms use the XP formalism, introduced in Ref. [14], which is a
powerful tool for representing the logical operator structure of a stabiliser
code.

###  1.1 Existing Work on Transversal Logical Operators

We briefly review previous methods for identifying diagonal logical operators
of arbitrary CSS codes, and methods for constructing CSS codes with a desired
transversal logical operator. In Ref. [15], a method is given to find all
logical operators at level 2 of the Clifford hierarchy for a CSS code by
mapping it to a classical code over $GF(4)$. This method involves calculating
the automorphism group of the classical code, which has exponential complexity
in the number of qubits in the stabiliser code [16].

There has also been a significant amount of work on logical operators
constructed from single- and multi-qubit diagonal Clifford hierarchy gates. In
Ref. [17], operators composed of diagonal Clifford hierarchy gates on one or
two qubits are shown to be representable as symmetric matrices over
$\mathbb{Z}_{N}$, referred to as Quadratic Form Diagonal (QFD) gates.
Necessary and sufficient conditions for a QFD gate to act as a logical
operator on a CSS code are then presented. In Ref. [18], a method of
generating circuits using multi-qubit gates which implement arbitrary logical
operators at level 2 of the Clifford hierarchy is presented. A method for
generating CSS codes with transversal diagonal logical operators at increasing
levels of the Clifford hierarchy is presented in Ref. [19], along with a
method to increase the $Z$-distance of such codes. In Ref. [14], we
demonstrated an algorithm for finding all diagonal logical operators composed
of single-qubit phase gates which, for CSS codes, involves taking the kernel
modulo $N$ of a matrix with $n+2^{k}$ columns where $n$ and $k$ are the number
of physical and logical qubits respectively.

###  1.2 Contribution of this Work

In this work, we present efficient methods to identify and test diagonal
logical operators on CSS codes using both single and multi-qubit diagonal
Clifford hierarchy gates as building blocks. These methods generalise to non-
CSS stabiliser codes. We also present a technique for generating CSS codes
with implementations of any desired diagonal Clifford hierarchy logical
operator using single-qubit phase gates.

We first consider operators composed of single-qubit phase gates at level $t$
of the Clifford hierarchy. We show that these can be represented as diagonal
XP operators of precision $N=2^{t}$. For logical operators of this form, we
demonstrate the following algorithms that apply to any CSS code and at any
desired level of the Clifford hierarchy:

  1. 1.

Finding a generating set of diagonal logical identity operators for the code:
An XP operator may act as a logical identity, but may not be an element of the
stabiliser group of a CSS code. The logical identities are used as inputs to
several other algorithms (Section 3.1)

  2. 2.

Search for an implementation of a desired logical controlled-phase operator on
the code: useful for checking if a given CSS code has a transversal
implementation of a particular logical operator and for checking the results
of other algorithms (Section 3.2);

  3. 3.

Determining if a given diagonal operator acts as a logical operator on the
code: This method is of linear complexity in the number of independent
$X$-checks whereas existing methods are of exponential complexity (Section
3.3);

  4. 4.

Finding a generating set of diagonal logical operators on the code: The
generating set gives us a complete understanding of the diagonal logical
operator structure of a CSS code, and can be used on CSS codes with a large
number of physical and logical qubits at any desired level of the Clifford
hierarchy (Section 3.4);

  5. 5.

Expressing the action of a diagonal logical operator as a product of logical
controlled-phase gates: The action of a logical operator can be difficult to
interpret, particularly for codes with a large number of logical qubits. This
method greatly simplifies the interpretation of logical actions (Section 3.5).

We then show that multi-qubit diagonal Clifford hierarchy gates acting on a
codesepace can be represented as diagonal XP operators acting on a larger
Hilbert space via an embedding operator (Section 4.3). We demonstrate
algorithms for:

  1. 6.

Finding depth-one implementations of logical operators composed of diagonal
Clifford hierarchy gates: on small CSS codes, this allows us to identify and
verify the depth-one logical operators of [11, 12, 13] with no knowledge of
the symmetry of the code (Section 4.4);

  2. 7.

Canonical implementations of a desired logical controlled-phase operator
composed of multi-qubit controlled-phase gates: this allows us to write
closed-form expressions for arbitrary diagonal Clifford hierarchy logical
operators Section 5.1;

  3. 8.

Construction of CSS codes which have an implementation of a desired logical
controlled-phase operator composed of single qubit phase gates: the canonical
logical operator implementation allows us to construct families of CSS codes
which have transversal implementations of a desired diagonal Clifford
hierarchy logical operator Section 5.4.

Apart from the depth-one search algorithm, the eight algorithms have
complexity that is polynomial in the parameters $n,k,r$ of the CSS code (see
below). As a result, they can be applied to ‘large’ codes that have so far
been out of reach of existing methods. There are no restrictions on the level
of the Clifford hierarchy or maximum support size of the physical gates used
in the methods.

A summary of the characteristics and computational complexity of search and
test algorithms is presented in Table 1. Complexity is expressed in terms of
the following variables:

  * •

Required level of the Clifford hierarchy $t$;

  * •

Number of physical qubits $n$ in the CSS code;

  * •

Number of logical qubits $k$ in the CSS code;

  * •

Number of independent $X$-checks $r$ in the CSS code;

The space complexity of the algorithm is expressed in terms of the size of the
key matrices used. The time complexity is expressed in terms of the number of
kernel operations performed on the key matrices - these operations dominate
the complexity of the algorithms.

The algorithms have been implemented in a Python GitHub repository accessible
under the GNU General Public License. A range of sample codes are also
available for testing in this repository, including Reed-Muller codes,
hyperbolic surface codes, triorthogonal codes and symmetric hypergraph product
codes.

Algorithm |  Gate Type |  Space Complexity |  Time Complexity
---|---|---|---
1\. Diagonal Logical Identity Group Generators |  Single-qubit |  $\mathcal{O}((k+r)^{t}\times n)$ |  $\mathcal{O}(1)$
2\. Search by Logical Action |  Single-qubit |  $\mathcal{O}((k+r)^{t}\times n)$ |  $\mathcal{O}(1)$
3\. Logical Operator Test* |  Single-qubit |  $\mathcal{O}(1\times n)$ |  $\mathcal{O}(r)$
4\. Diagonal Logical Operator Group Generators* |  Single-qubit |  $\mathcal{O}(n\times n)$ |  $\mathcal{O}(r)$
5\. Determine Action of Diagonal Logical Operator |  Single-qubit |  $\mathcal{O}((k+r)^{t}\times n)$ |  $\mathcal{O}(1)$
6\. Depth-One Logical Operators** |  Multi-qubit |  $\mathcal{O}(n^{t}\times n^{t})$ |  $\mathcal{O}(2^{n})$
Table 1: Comparison of Search and Test Algorithms for Diagonal Logical
Operators. Note that entries annotated with * require the diagonal logical
identities of algorithm 1 as input. Entries annotated with ** require the
diagonal logical operators of algorithm 4 as input.

##  2 Background

This Section reviews the necessary background material for this work. We first
introduce the Clifford hierarchy of diagonal operators and introduce a vector
representation of these. We then outline notation and fundamental properties
of CSS codes. Next, we define what we mean by a diagonal logical operator on a
CSS code. We then present an example illustrating the types of diagonal
logical operators we consider in this work for the well-known $[[4,2,2]]$
code. We then review the XP stabiliser formalism and some fundamental
properties of the XP operators, which we will use to represent logical
operators composed of diagonal Clifford hierarchy gates. We explain the
logical operator group structure in the XP formalism, which is somewhat
different than in the Pauli stabiliser formalism.

###  2.1 Diagonal Clifford Hierarchy Operators

Here we review the properties of operators in the diagonal Clifford hierarchy.
We will use diagonal gates at level $t$ of the Clifford hierarchy on $n$
qubits as the building blocks for logical operators. The diagonal Clifford
hierarchy operators at each level form a group generated by the following
operators [20]:

  * •

Level 1: Pauli $Z$ gate on qubit $i:0\leq i<n$ denoted $Z_{i}$;

  * •

Level 2: Controlled-$Z$ ($CZ_{ij}$) and $S_{i}:=\sqrt{Z_{i}}$;

  * •

Level 3: $CCZ_{ijk},CS_{ij}$ and $T_{i}:=\sqrt{S_{i}}$;

  * •

Level $t+1$: Square roots and controlled versions of operators from level $t$.

At each level, we refer to the generators as level-$t$ controlled-phase gates.
Where an operator is an element of the diagonal Clifford hierarchy group at
level $t$, we say that it is composed of level-$t$ controlled-phase gates.

The single-qubit phase gate at level $t$ is of form $\text{diag}(1,\exp(2\pi
i/N))$ where $N:=2^{t}$. If an operator is an element of the group generated
by single-qubit phase gates at level $t$, we say it is composed of level-$t$
phase gates.

The matrix form of any diagonal transversal logical operator of a CSS code
must have entries of form $\exp(q\pi i/2^{t})$ for integers $q,t$, as shown in
Ref. [21]. Such matrices are elements of the diagonal Clifford hierarchy group
at some level, and so considering logical operators composed of controlled-
phase gates yields all possible diagonal transversal logical operators on a
CSS code.

###  2.2 Vector Representation of Controlled-Phase Operators

We now introduce a vector representation of controlled-phase operators that
underpins our analytical methods. Fix a level $t$ of the Clifford hierarchy
(Section 2.1) and let $N:=2^{t}$. Let $\omega:=e^{\pi i/N}$ be a $(2N)$-th
root of unity. The operator $\text{CP}_{N}(q,\mathbf{v})$, where
$q\in\mathbb{Z}_{2N}$ and $\mathbf{v}$ is a binary vector of length $n$, is
defined as follows by its action on a computational basis vectors
$|\mathbf{e}\rangle$ for $\mathbf{e}\in\mathbb{Z}_{2}^{n}$:

$\displaystyle\text{CP}_{N}(q,\mathbf{v})|\mathbf{e}\rangle:=\begin{cases}\omega^{q}|\mathbf{e}\rangle&\text{
if }\mathbf{v}\preccurlyeq\mathbf{e};\\\ |\mathbf{e}\rangle&\text{
otherwise}.\end{cases}$ (1)

The relation $\preccurlyeq$ is a partial order for binary vectors based on
their support (the set of indices where the vector is non-zero). The
expression $\mathbf{v}\preccurlyeq\mathbf{e}$ indicates
$\text{supp}(\mathbf{v})\subseteq\text{supp}(\mathbf{e})\iff\mathbf{e}\mathbf{v}=\mathbf{v}$
where vector multiplication is componentwise. For an integer $0\leq i<n$, we
will also write $i\preccurlyeq\mathbf{v}$ if $\mathbf{v}[i]=1$. The phase
applied can be expressed more concisely as follows:

$\displaystyle\text{CP}_{N}(q,\mathbf{v})|\mathbf{e}\rangle=\omega^{q\cdot
p_{\mathbf{v}}(\mathbf{e})}|\mathbf{e}\rangle\text{ where
}p_{\mathbf{v}}(\mathbf{e}):=\prod_{i\preccurlyeq\mathbf{v}}\mathbf{e}[i].$
(2)

Each generator of the diagonal Clifford hierarchy can be written in vector
form. To see this, we note that the phase gate at level $t$ can be written as
$P:=\text{diag}(1,\omega^{2})$. The phase operator acting on qubit $i$ can be
written in vector form as $P_{i}=\text{CP}_{N}(2,\mathbf{b}^{n}_{i})$ where
$\mathbf{b}^{n}_{i}$ is the length $n$ binary vector, which is all zero apart
from component $i$ which is one. Similarly, the operator
$CP_{ij}=\text{CP}_{N}(2,\mathbf{b}^{n}_{ij})$ where $\mathbf{b}^{n}_{ij}$ is
zero apart from components $i$ and $j$. The operators of form
$\text{CP}_{N}(2^{\text{wt}(\mathbf{v})},\mathbf{v})$ with
$1\leq\text{wt}(\mathbf{v})\leq t$ are the generators of the level-$t$
controlled-phase operators presented in Section 2.1.

######  Example 2.1 (Vector Representation of Level $3$ Controlled-Phase
Operators)

This example illustrates the vector representation of level $3$ diagonal
Clifford hierarchy operators. At level $t=3$ the generators have vector
representations as follows:

$\displaystyle T_{i}$ $\displaystyle=CP_{8}(2,\mathbf{b}^{n}_{i})$ (3)
$\displaystyle CS_{ij}$ $\displaystyle=CP_{8}(4,\mathbf{b}^{n}_{ij})$ (4)
$\displaystyle CCZ_{ijk}$ $\displaystyle=CP_{8}(8,\mathbf{b}^{n}_{ijk}).$ (5)

We also include $\omega I=CP_{8}(1,\mathbf{0})$ as a generator at the third
level of the hierarchy as phases of this form occur in the commutation
relation for controlled-phase operators - see Equations 30 and 31.

###  2.3 CSS Codes

Here we introduce some key notation and results for CSS codes. Our notation
for CSS codes is somewhat different to that in the literature and is used
because it simplifies the statement of our results. Although we focus on CSS
codes in this work, the methods are applicable to any stabiliser code as set
out in Appendix C. For our purposes, a CSS code on $n$ qubits is specified by
an $r\times n$ binary matrix $S_{X}$ the rows of which we refer to as the
$X$-checks and a $k\times n$ binary matrix $L_{X}$ whose rows are referred to
as the $X$-logicals. We assume that the rows of $S_{X}$ and $L_{X}$ are
independent binary vectors - otherwise we can use linear algebra modulo $2$ to
ensure this. The $Z$-checks can be calculated by taking the kernel modulo $2$
of the $X$-checks and $X$-logicals, i.e.,

$\displaystyle S_{Z}:=\ker_{\mathbb{Z}_{2}}\begin{pmatrix}S_{X}\\\
L_{X}\end{pmatrix}.$ (6)

In Equation 6, the notation $\ker_{\mathbb{Z}_{2}}$ refers to the basis in
reduced row echelon form of the kernel modulo $2$ of a binary matrix. We form
stabiliser generators $\mathbf{S}_{X},\mathbf{S}_{Z}$ from the rows of $S_{X}$
and $S_{Z}$ in the obvious way - if $\mathbf{x}$ is a row of $S_{X}$ then the
corresponding stabiliser generator is $\prod_{0\leq
i<n}X_{i}^{\mathbf{x}[i]}$. The codespace is the simultaneous $+1$ eigenspace
of the stabiliser group $\langle\mathbf{S}_{X},\mathbf{S}_{Z}\rangle$ and is a
subspace of $\mathcal{H}_{2}^{n}$. The codespace is spanned by $2^{k}$
canonical codewords which are indexed by binary vectors $\mathbf{v}$ of length
$k$ and are defined as follows:

$\displaystyle|\mathbf{v}\rangle_{L}:=\sum_{\mathbf{u}\in\mathbb{Z}_{2}^{r}}|\mathbf{e_{uv}}\rangle:=\sum_{\mathbf{u}\in\mathbb{Z}_{2}^{r}}|\mathbf{u}S_{X}+\mathbf{v}L_{X}\rangle.$
(7)

In the above expression, matrix operations are modulo $2$. For simplicity, we
are not concerned with normalising codeword states.

###  2.4 Logical Operators of CSS Codes

We now describe what we mean by a logical operator on a CSS code. Let
$\mathcal{C}:\mathcal{H}_{2}^{k}\rightarrow\mathcal{H}_{2}^{n}$ be the
encoding operator which takes computational basis vectors to canonical
codewords of Equation 7 i.e.
$\mathcal{C}\lvert\mathbf{v}\rangle=\lvert\mathbf{v}\rangle_{L}$ for
$\mathbf{v}\in\mathbb{Z}_{2}^{k}$. Now let $B$ be a unitary operator acting on
$k$ qubits. We say that an operator $\overline{B}$ acting on $n$ qubits is a
logical $B$ operator if

$\displaystyle\overline{B}\mathcal{C}=\mathcal{C}B.$ (8)

A unitary operator $B$ is diagonal if we can write
$B:=\text{diag}(\mathbf{c})$ for some complex-valued vector $\mathbf{c}$ of
length $2^{k}$ representing the phase applied to each computational basis
vector, i.e. $B\lvert\mathbf{v}\rangle=\mathbf{c_{v}}\lvert\mathbf{v}\rangle$
for $\mathbf{v}\in\mathbb{Z}_{2}^{k}$ and $\mathbf{c_{v}}\in\mathbb{C}$. If
$\overline{B}$ is a diagonal logical operator, then $B$ is diagonal as well,
though the converse is not necessarily true. From Equation 8 and Equation 7,
we have:

$\displaystyle\overline{B}\mathcal{C}\lvert\mathbf{v}\rangle$
$\displaystyle=\overline{B}\lvert\mathbf{v}\rangle_{L}=\overline{B}\sum_{\mathbf{u}\in\mathbb{Z}_{2}^{r}}|\mathbf{e_{uv}}\rangle=\sum_{\mathbf{u}\in\mathbb{Z}_{2}^{r}}\overline{B}|\mathbf{e_{uv}}\rangle$
(9)
$\displaystyle=\mathcal{C}B\lvert\mathbf{v}\rangle=\mathbf{c_{v}}\lvert\mathbf{v}\rangle_{L}=\sum_{\mathbf{u}\in\mathbb{Z}_{2}^{r}}\mathbf{c_{v}}|\mathbf{e_{uv}}\rangle.$
(10)

As a result, we can check if $\overline{B}$ is a logical $B$ operator by doing
the following:

  1. 1.

For each $\mathbf{v}\in\mathbb{Z}_{2}^{k}$, calculate
$\mathbf{c_{v}}\in\mathbb{C}$ such that
$B\lvert\mathbf{v}\rangle=\mathbf{c_{v}}\lvert\mathbf{v}\rangle$;

  2. 2.

For each $\mathbf{u}\in\mathbb{Z}_{2}^{r}$, check that
$\overline{B}\lvert\mathbf{e_{uv}}\rangle=\mathbf{c_{v}}\lvert\mathbf{e_{uv}}\rangle$.

This method of checking whether a diagonal unitary is a logical operator
involves $\mathcal{O}(2^{r+k})$ steps; we present a method in Section 3.3 with
linear complexity in $r$.

We say that an operator $\overline{B}$ is a logical identity if
$\overline{B}\lvert\mathbf{v}\rangle_{L}=\lvert\mathbf{v}\rangle_{L}$ for all
$\mathbf{v}\in\mathbb{Z}_{2}^{k}$ \- that is, it fixes each canonical codeword
and hence each element of the codespace. If $\overline{B}$ is diagonal, as a
consequence of Equation 10, it is a logical identity if and only if
$\overline{B}\lvert\mathbf{e_{uv}}\rangle=\lvert\mathbf{e_{uv}}\rangle$ for
all $\mathbf{u}\in\mathbb{Z}_{2}^{r},\mathbf{v}\in\mathbb{Z}_{2}^{k}$.

######  Example 2.2 (Transversal Logical Operators of [[4,2,2]] Code)

We use the [[4,2,2]] code to illustrate the types of transversal logical
operators we consider in this work. Using the notation introduced in Section
2.3, the $X$-checks and $X$-logicals of the code are:

$\displaystyle S_{X}$ $\displaystyle:=\begin{pmatrix}1111\end{pmatrix}$ (11)
$\displaystyle L_{X}$ $\displaystyle:=\begin{pmatrix}0101\\\
0011\end{pmatrix}$ (12)

In this case, there are $r=1$ $X$-checks and $k=2$ $X$-logicals. There are
$2^{k}=4$ canonical codewords which we calculate using Equation 7:

$\displaystyle\begin{matrix}|00\rangle_{L}&:=|0000\rangle+|1111\rangle\\\
|01\rangle_{L}&:=|0011\rangle+|1100\rangle\\\
|10\rangle_{L}&:=|0101\rangle+|1010\rangle\\\
|11\rangle_{L}&:=|0110\rangle+|1001\rangle\end{matrix}$ (13)

We can calculate the single $Z$-check as follows:

$\displaystyle S_{Z}$
$\displaystyle:=\ker_{\mathbb{Z}_{2}}\begin{pmatrix}S_{X}\\\
L_{X}\end{pmatrix}=\begin{pmatrix}1111\end{pmatrix}.$ (14)

Readers can verify that $Z^{\otimes 4}$ acts as a logical identity by checking
that $Z^{\otimes 4}\lvert\mathbf{v}\rangle_{L}=\lvert\mathbf{v}\rangle_{L}$
for each of the canonical codewords.

The following are examples of transversal diagonal logical operators composed
of controlled-phase gates at level $2$ whose actions can be verified by
applying the method of Section 2.4:

  1. 1.

Single-qubit phase gates Controlled-Z:
$\overline{CZ_{01}}=S_{0}^{3}S_{2}S_{2}S_{3}^{3}$

  2. 2.

Multi-qubit controlled-phase gates S operator on both logical qubits:
$\overline{S_{0}S_{1}}=S_{1}S_{2}CZ_{03}$

###  2.5 The XP Formalism

The XP formalism is a generalisation of the Pauli stabiliser formalism, and we
will show that diagonal Clifford hierarchy operators can be represented as
diagonal XP operators. In the XP formalism, we fix an integer precision $N\geq
2$ and let $\omega=\exp(\pi i/N)$ be a $(2N)$-th root of unity. We define a
diagonal phase operator $P=\text{diag}(1,\omega^{2})$ which is a $1/N$
rotation around the Z axis and consider the group of XP operators
$\mathcal{XP}^{n}_{N}$ that is generated by $\omega I,X_{i},P_{i}$ where
$P_{i}$ is a $P$ operator applied to qubit $i$. By setting $N:=2^{t}$, it is
easy to see that the $P_{i}$ correspond to the level $t$ phase gates of
Section 2.1, and so any operator composed of single-qubit phase gates can be
represented as a diagonal XP operator. For example, setting $t=1$ results in
$N=2,\omega=i$ and $P=Z$ so $\mathcal{XP}_{2}^{n}$ is the Pauli group on $n$
qubits.

The XP formalism has a fundamental commutation relation that allows us to move
$P$ operators to the right of $X$ operators:

$\displaystyle PX=\omega^{2}XP^{-1}.$ (15)

All XP operators have a unique vector representation with a phase component
$p\in\mathbb{Z}_{2N}$, an $X$-component $\mathbf{x}\in\mathbb{Z}_{2}^{n}$ and
a $Z$-component $\mathbf{z}\in\mathbb{Z}_{N}^{n}$. The $Z$-component is modulo
$N$, for instance, because $P^{N}=I$. The XP operator formed from these
components is:

$\displaystyle XP_{N}(p|\mathbf{x}|\mathbf{z}):=\omega^{p}\prod_{0\leq
i<n}X_{i}^{\mathbf{x}[i]}P_{i}^{\mathbf{z}[i]}.$ (16)

Diagonal XP operators are those with a zero $X$-component. The vector form of
XP operators allows us to perform algebraic operations efficiently via
componentwise addition and multiplication of vectors - examples are given in
Table 4 of [14]. In particular, the action of an XP operator on a
computational basis element $|\mathbf{e}\rangle$ where
$\mathbf{e}\in\mathbb{Z}_{2}^{n}$ is determined as follows:

$\displaystyle
XP_{N}(p|\mathbf{x}|\mathbf{z})|\mathbf{e}\rangle=\omega^{p+2\mathbf{e}\cdot\mathbf{z}}|\mathbf{e}\oplus\mathbf{x}\rangle.$
(17)

Where $N=2^{t}$, we can determine the lowest level of the Clifford hierarchy
at which a diagonal operator $B:=XP_{N}(0|\mathbf{0|z})$ occurs. Let
$g:=GCD(N,\mathbf{z})$ be the GCD of $N$ and each component of $\mathbf{z}$.
As $N=2^{t},g$ is a power of $2$ and $B=XP_{N/g}(p/g|\mathbf{0|z}/g)$.
Accordingly, $B$ occurs at level $t-\log_{2}(g)$ of the diagonal Clifford
hierarchy.

######  Example 2.3 (Determining Clifford Hierarchy Level of XP operators)

Let $t=3$ and $B=XP_{8}(0|\mathbf{0}|4444)$, so that $g=GCD(8,4)=4$. Hence
$B=XP_{2}(0|\mathbf{0}|1111)=Z^{\otimes 4}$ and occurs at level
$t-\log_{2}(4)=3-2=1$ of the Clifford hierarchy.

###  2.6 Logical Identity and Logical Operator Groups in the XP Formalism

We now look at the logical group structure of a CSS code in the XP formalism
with reference to the definitions of logical operators in Section 2.4. In the
stabiliser formalism, a Pauli operator acts as a logical identity if and only
if it is in the stabiliser group
$\langle\mathbf{S}_{X},\mathbf{S}_{Z}\rangle$. In the XP stabiliser formalism,
an XP operator may act as a logical identity but not be in the stabiliser
group - we will see an instance of this in Example 3.1. The logical XP
identity group, $\mathcal{I}_{\text{XP}}$, are the XP operators of precision
$N$ which fix each element of the codespace. The stabiliser group is a
subgroup of $\mathcal{I}_{\text{XP}}$ but may not be equal to it.

The logical XP operator group, $\mathcal{L}_{\text{XP}}$, are the XP operators
of precision $N$ that are logical $B$ operators for some unitary $B$ acting on
$k$ qubits. Logical XP operators may have actions outside the Pauli group, and
the logical $\overline{CZ_{01}}$ operator of Example 2.2 is an instance of
such an operator. Logical identities are elements of $\mathcal{L}_{\text{XP}}$
that have a trivial action. The logical groups in the XP formalism are
summarised in Figure 1.

$\mathcal{XP}^{n}_{N}$$\mathcal{L}_{\text{XP}}$$\mathcal{I}_{\text{XP}}$$\langle\mathbf{S}_{X},\mathbf{S}_{Z}\rangle$
Figure 1: Relationship between XP Operator Groups: Here,
$\mathcal{XP}^{n}_{N}$ is the group of all XP operators of precision $N$ on
$n$ qubits. The stabiliser group $\langle\mathbf{S}_{X},\mathbf{S}_{Z}\rangle$
of a CSS code is a subgroup of the logical XP identity group
$\mathcal{I}_{\text{XP}}$ which fixes all elements of the codespace which, in
turn, is a subgroup of the logical operators of XP form
$\mathcal{L}_{\text{XP}}$.

##  3 Logical Operators Composed of Single-Qubit Phase Gates

In this Section, we present methods for identifying and testing logical
operators composed of single-qubit phase gates at a given level $t$ of the
Clifford hierarchy. Operators of this form can be identified with diagonal XP
operators of precision $N=2^{t}$. The algorithms in this Section are of
polynomial complexity in the code parameters $n,k,r$ (Section 2.3), so they
can be used on CSS codes with a large number of physical or logical qubits.

This Section is structured as follows. We first show how to calculate
generators for the diagonal logical identity XP group. This is an important
first step for a number of our algorithms. We then demonstrate an algorithm
that searches for a diagonal XP operator with a desired logical action. Next,
we set out an efficient method for testing if a given diagonal XP operator is
a logical operator on a CSS code. We then show how to use this test to find
all diagonal logical operators of XP form. Finally, we show how to express the
action of a diagonal logical XP operator in terms of a product of logical
controlled phase operators. We use the Hypercube code of [22, 23] which has a
rich logical operator structure an example throughout this Section. We also
demonstrate the use of the algorithms on larger codes such as hyperbolic color
codes [24], poset codes [25] and triorthogonal codes [10].

###  3.1 Diagonal Logical XP Identity Group Generators

Calculating generators for the logical identity group of a CSS code is an
important first step for several of the algorithms discussed in this paper. An
algorithm for determining the logical identity group is set out in Section 6.2
of [14]. Here, we present a simplified version for CSS codes.

Due to the discussion in Section 2.4, a diagonal logical identity operator
fixes all $\lvert\mathbf{e_{uv}}\rangle$ in the canonical codewords of
Equation 7. Now let $N:=2^{t}$ and let $B:=XP_{N}(2p|\mathbf{0}|\mathbf{z})$
be a diagonal XP operator. Using Equation 17, the action of $B$ on the
computational basis vector $\lvert\mathbf{e_{uv}}\rangle$ is
$B|\mathbf{e_{uv}}\rangle=\omega^{2p+2\mathbf{e_{uv}}\cdot\mathbf{z}}|\mathbf{e_{uv}}\rangle$.
Considering the action of $B$ on
$\lvert\mathbf{e_{00}}\rangle=\lvert\mathbf{0}\rangle$, we see that
$p=0\operatorname{mod}2N$. As $\omega^{2N}=1$, $B$ applies a trivial phase to
$\lvert\mathbf{e_{uv}}\rangle$ if and only if
$\mathbf{e_{uv}}\cdot\mathbf{z}=0\operatorname{mod}N$. We can find all such
solutions by taking the kernel of a suitably constructed matrix modulo $N$.
This is done via the Howell matrix form [26] which is a generalisation of the
reduced row echelon form for modules over rings such as $\mathbb{Z}_{N}$. The
notation $\ker_{\mathbb{Z}_{N}}(E_{M})$ means the Howell basis of the kernel
of the matrix $E_{M}$ modulo $N$.

##### Algorithm 1: Logical Identity Group Generators

##### Input:

  1. 1.

The $X$-checks $S_{X}$ and $X$-logicals $L_{X}$ of a CSS code (Section 2.3);

  2. 2.

The desired level of the Clifford hierarchy $t$ (Section 2.1).

##### Output:

A matrix $K_{M}$ whose rows are the $Z$-components of a set of generators for
the diagonal logical identity XP group of precision $N=2^{t}$ (Section 2.6).

##### Method:

  1. 1.

Let $E_{M}$ be the binary matrix whose rows are the
$\mathbf{e_{uv}}:=\mathbf{u}S_{X}+\mathbf{v}L_{X}$ of Equation 7;

  2. 2.

Let $N:=2^{t}$ and calculate $K_{M}:=\ker_{\mathbb{Z}_{N}}(E_{M})$ in Howell
matrix form;

  3. 3.

Return $K_{M}$

Because $E_{M}$ has $2^{r+k}$ rows, the complexity of the logical identity
algorithm is highly sensitive to the number of $X$-checks $r$ and logical
qubits $k$. However, due to Proposition E.13 of Ref. [14], we only need to
consider $\mathbf{e_{uv}}$ where
$\text{wt}(\mathbf{u})+\text{wt}(\mathbf{v})\leq t$ to determine the logical
identity group up to level $t$ of the Clifford hierarchy. Hence, we only
require $\genfrac{[}{]}{0.0pt}{2}{r+k}{t}:=\sum_{0\leq j\leq
t}\genfrac{(}{)}{0.0pt}{2}{r+k}{j}$ rows from $E_{M}$ and so the dimensions of
the matrix and scale as a polynomial of degree $t$ in $r+k$.

######  Example 3.1 (Logical Identity Algorithm - Hypercube Code)

Figure 2: Hypercube Code of Dimension $3$: qubits reside on the vertices of a
cube. The blue-coloured $X$-logicals are associated with the 2D faces, whilst
the $X$-check is associated with the single 3D volume. The red-coloured
$Z$-checks are associated with the 2D faces.

In this example, based on Refs [23] and [22], qubits reside on the eight
vertices of a cube. The single $X$-check is the all-ones vector indicating an
X operator on all vertices of the cube:

$\displaystyle S_{X}=\begin{pmatrix}11111111\end{pmatrix}.$ (18)

The three $X$-logicals are weight 4 vectors associated with three faces
meeting at a point which we write in the notation of Section 2.3 as follows:

$\displaystyle L_{X}=\begin{pmatrix}01010101\\\ 00110011\\\
00001111\end{pmatrix}.$ (19)

We calculate the $Z$-checks by applying Equation 6 and find that the
$Z$-checks also correspond to faces:

$\displaystyle S_{Z}:=\ker_{\mathbb{Z}_{2}}\begin{pmatrix}S_{X}\\\
L_{X}\end{pmatrix}=\begin{pmatrix}10010110\\\ 01010101\\\ 00110011\\\
00001111\end{pmatrix}.$ (20)

This process is exactly the same as finding the diagonal logical identities at
level $t=1$ as outlined in Section 3.1. In this case, $E_{M}$ has $r+k=1+3=4$
rows and the logical identities are the kernel of $E_{M}$ modulo $2$. Now
applying the logical identity algorithm at level $t=3$, $E_{M}$ has $15$ rows
representing the sum modulo 2 of up to $3$ rows from $S_{X}$ and $L_{X}$.
Taking the kernel of $E_{M}$ modulo $N=2^{3}=8$, we find:

$\displaystyle K_{M}:=\ker_{\mathbb{Z}_{8}}(E_{M})=\begin{pmatrix}22222222\\\
04040404\\\ 00440044\\\ 00004444\end{pmatrix}$ (21)

The rows of $K_{M}$ are the $Z$-components of diagonal XP operators which act
as logical identities, and form a generating set of all such operators of
precision $N$. For instance, the operator
$XP_{8}(0|\mathbf{0}|22222222)=S^{\otimes 8}$ acts as a logical identity, but
is not in the stabiliser group $\langle\mathbf{S}_{X},\mathbf{S}_{Z}\rangle$.
An interactive version of this example is in the linked Jupyter notebook.

###  3.2 Algorithm 2: Search for Diagonal XP Operator by Logical Action

We now demonstrate a method that searches for diagonal logical operators of XP
form with a desired action. Aside from verifying if a CSS code has a
transversal implementation of a particular logical operator, this is a useful
method for cross-checking other algorithms.

##### Algorithm 2: Search for Diagonal XP Operator by Logical Action

##### Input:

  1. 1.

The $X$-checks $S_{X}$ and $X$-logicals $L_{X}$ of a CSS code (Section 2.3);

  2. 2.

A level-$t$ controlled-phase operator $B$ on $k$ qubits (Section 2.1) such
that $B\lvert\mathbf{0}\rangle=\lvert\mathbf{0}\rangle$ .

##### Output:

A diagonal XP operator of precision $N=2^{t}$ which acts as a logical $B$
operator or FALSE if this is not possible.

##### Method:

  1. 1.

For $\mathbf{v}\in\mathbb{Z}_{2}^{k}$ calculate the phase
$\mathbf{q_{v}}\in\mathbb{Z}_{N}$ such that
$B\lvert\mathbf{v}\rangle=\omega^{2\mathbf{q_{v}}}\lvert\mathbf{v}\rangle$;

  2. 2.

Form the matrix $E_{B}$ that has rows of form
$(-\mathbf{q_{v}}|\mathbf{e_{uv}})$ where
$\mathbf{e_{uv}}:=\mathbf{u}S_{X}+\mathbf{v}L_{X}$;

  3. 3.

Calculate the kernel $K_{B}:=\ker_{\mathbb{Z}_{N}}(E_{B})$;

  4. 4.

If there is an element $(1|\mathbf{z})\in K_{B}$ then $\mathbf{z}$ is the
$Z$-component of a logical $B$ operator
$\overline{B}:=XP_{N}(0|\mathbf{0|z})$. This is because
$(1|\mathbf{z})\cdot(-\mathbf{q_{v}}|\mathbf{e_{uv}})=0\operatorname{mod}N\iff\mathbf{e_{uv}}\cdot\mathbf{z}=\mathbf{q_{v}}\,\operatorname{mod}N$
for all $\mathbf{e_{uv}}$, which corresponds to the action of a logical $B$
operator on the codewords $\lvert\mathbf{v}\rangle_{L}$.

The above algorithm requires that $B|\mathbf{0}\rangle=|\mathbf{0}\rangle$. If
this is not the case, let $B|\mathbf{0}\rangle=\omega^{p}|\mathbf{0}\rangle$,
run the algorithm using $B^{\prime}:=\omega^{-p}B$ and adjust for phase on the
result.

The logical action search algorithm involves finding the kernel of a matrix
$E_{B}$ of dimension $2^{r+k}\times(n+1)$. Hence the complexity of the
algorithm is sensitive to the number of logical qubits $k$ and independent
$X$-checks $r$, but can be reduced as follows. Due to Proposition B.1, where
$N=2^{t}$ the dot product $\mathbf{e_{uv}\cdot z}$ can always be written as a
$\mathbb{Z}_{N}$ linear combination of terms of form
$\mathbf{e_{u^{\prime}v^{\prime}}\cdot z}$ where
$\text{wt}(\mathbf{u^{\prime}})+\text{wt}(\mathbf{u^{\prime}})\leq t$. Hence,
we only need to consider $\mathbf{e_{uv}}$ where
$\text{wt}(\mathbf{u})+\text{wt}(\mathbf{v})\leq t$ and $\mathbf{q_{v}}$ where
$\text{wt}(\mathbf{v})\leq t$. The number of rows required in $E_{M}$ is
therefore $\genfrac{[}{]}{0.0pt}{2}{k+r}{t}$ where
$\genfrac{[}{]}{0.0pt}{2}{r}{t}:=\sum_{0\leq j\leq
t}\genfrac{(}{)}{0.0pt}{2}{r}{j}$. The dimensions of the matrix $E_{M}$ are
polynomial rather than exponential in $n,k$ and $r$.

######  Example 3.2 (Search for Diagonal XP Operator by Logical Action)

The linked Jupyter notebook illustrates the operation of the search algorithm
on the hypercube code of Example 3.1. Users can enter the desired logical
operator to search for in text form - for example CZ[1,2], S[1] or CCZ[0,1,2].
The script either returns a diagonal XP operator with the desired logical
action, or FALSE if there is no such operator. We find logical operators
$\overline{CZ_{12}}=XP_{8}(0|\mathbf{0}|02060602)$ and
$\overline{CCZ_{012}}=XP_{8}(0|\mathbf{0}|13313113)$ but no solutions for
transversal logical $S$ operators.

###  3.3 Logical Operator Test for Diagonal XP Operators

We now present an efficient method for determining whether a given diagonal XP
operator acts as a logical operator on a CSS code, which relies on a
commutator property of logical operators. This is used to find a generating
set of all diagonal logical XP operators of a given precision and to check the
results of other algorithms.

Due to proposition E.2 of Ref. [14], an XP operator $B$ acts as a logical
operator on the codespace if and only if the group commutator with any logical
identity $A$ is again an element of the logical identity group
$\mathcal{I}_{\text{XP}}$ (see 2.6). That is:

$\displaystyle[[A,B]]:=ABA^{-1}B^{-1}\in\mathcal{I}_{\text{XP}},\forall
A\in\mathcal{I}_{\text{XP}}.$ (22)

When $B:=XP_{N}(0|\mathbf{0}|\mathbf{z})$ is diagonal and
$A:=XP_{N}(0|\mathbf{x}|\mathbf{0})$ is non-diagonal, by applying the COMM
rule of Table 4 in Ref. [14] we have:

$\displaystyle[[A,B]]=XP_{N}(2\mathbf{x}\cdot\mathbf{z}|\mathbf{0}|-2\mathbf{x}\mathbf{z}).$
(23)

As $B$ is a diagonal operator, we only need to consider commutators with non-
diagonal elements of the logical identity group. In Proposition B.2 we show
that this reduces to finding $\mathbf{z}\in\mathbb{Z}_{N}^{n}$ such that for
all $X$-checks $\mathbf{x}$, both
$\mathbf{x}\cdot\mathbf{z}=0\operatorname{mod}N$ and
$2\mathbf{x}\mathbf{z}\in\langle K_{M}\rangle_{\mathbb{Z}_{N}}$ where $K_{M}$
is a generating set of $Z$-components of the diagonal logical identities as
defined in Section 3.1 and $\langle K_{M}\rangle_{\mathbb{Z}_{N}}$ the row
span of $K_{M}$ over $\mathbb{Z}_{N}$.

As $2\mathbf{xz}$ and $N$ are both divisible by 2, we apply the method of
Section 2.5 and see that the group commutator must be at most a level $t-1$
Clifford hierarchy operator. For instance, for $t=2,N=4$ logical operators
must commute up to level $t=1,N=2$ logical identities which are the $Z$-checks
(see Example 3.1). This observation either eliminates the need to calculate
the logical identities (for $t\leq 2$) or reduces the complexity of
calculating them (the number of rows in the matrix $E_{M}$ of Section 3.1 is a
polynomial of degree $t$).

Hence, we have an $\mathcal{O}(r)$ algorithm for checking whether a diagonal
XP operator is a logical operator of a CSS code where $r$ is the number of
independent $X$-checks, but we may need to first run the diagonal logical
identity algorithm of Section 3.1 at level $t-1$.

##### Algorithm 3: Logical Operator Test for Diagonal XP Operators

##### Input:

  1. 1.

The $X$-checks $S_{X}$ of a CSS code (Section 2.3);

  2. 2.

The matrix $K_{M}$ corresponding to the $Z$-components of the level $t-1$
diagonal logical identity generators (Section 3.1;

  3. 3.

A diagonal XP operator $B=XP_{N}(0|\mathbf{0|z})$ on $n$ qubits of precision
$N=2^{t}$ (Section 2.5).

##### Output:

TRUE if $B$ acts as a logical operator on the code or FALSE otherwise.

##### Method:

  1. 1.

For each row $\mathbf{x}$ of $S_{X}$:

    1. (a)

Check if $\mathbf{x\cdot z}=0\operatorname{mod}N$; and

    2. (b)

Check if $2\mathbf{xz}$ is in the rowspan of $K_{M}$ over $\mathbb{Z}_{N}$;

    3. (c)

If either is not the case, return FALSE.

  2. 2.

Return TRUE.

######  Example 3.3 (Logical Operator Test)

In this example, we apply the logical operator test to the logical
$\overline{CZ_{12}}$ found for the hypercube code in Example 3.2. As
$\overline{CZ_{12}}:=XP_{8}(0|\mathbf{0}|02060602)$, we let
$\mathbf{z}=02060602$. Let $\mathbf{x}=11111111$ corresponding to the single
$X$-check. We calculate the group commutator
$C:=(2\mathbf{x}\cdot\mathbf{z}|\mathbf{0}|-2\mathbf{x}\mathbf{z})$. We find
that $\mathbf{x}\cdot\mathbf{z}=16=0\operatorname{mod}8$ and
$-2\mathbf{xz}=04040404\operatorname{mod}8$. Referring to Example 3.1, we see
that this vector is a row of $K_{M}$. As both
$\mathbf{x}\cdot\mathbf{z}=0\operatorname{mod}8$ and
$-2\mathbf{x}\mathbf{z}\in\langle K_{M}\rangle_{\mathbb{Z}_{N}}$, $C$ is a
logical identity. Accordingly, we have verified that $\overline{CZ_{12}}$ is a
diagonal logical operator on the code. Applying the method of Section 2.5, we
note that $\overline{CZ_{12}}$ is at level $2$ of the Clifford hierarchy and
the group commutator $C$ is at level $1$.

###  3.4 Diagonal Logical XP Operator Group Generators

We now show how to apply the test for diagonal logical XP operators of Section
3.3 to find all diagonal logical operators of XP form for a CSS code.

##### Algorithm 4: Diagonal Logical XP Operator Group Generators

##### Input:

  1. 1.

The $X$-checks $S_{X}$ of a CSS code (Section 2.3);

  2. 2.

The desired level of the Clifford hierarchy $t$ (Section 2.1);

  3. 3.

The matrix $K_{M}$ corresponding to the $Z$-components of the level $t-1$
diagonal logical identity generators (Section 3.1).

##### Output:

A matrix $K_{L}$ over $\mathbb{Z}_{N}$ representing the $Z$-components of a
generating set of diagonal logical operators of XP form (Section 2.6).

##### Method:

  1. 1.

For each $X$-check $\mathbf{x}\in S_{X}$, find solutions
$\mathbf{z}\in\mathbb{Z}_{N}^{n}$ such that both $\mathbf{x}\cdot\mathbf{z}=0$
and $2\mathbf{x}\mathbf{z}\in\langle K_{M}\rangle_{\mathbb{Z}_{N}}$. Details
of solving within these constraints are set out in Section B.3. Denote the
solutions $\text{Comm}_{N}(K_{M},\mathbf{x})$;

  2. 2.

Find the intersection of all such solution sets $K_{L}:=\bigcap_{\mathbf{x}\in
S_{X}}\text{Comm}_{N}(K_{M},\mathbf{x})$. The method for determining
intersections of spans over $\mathbb{Z}_{N}$ is covered in Appendix A.4 of
[14];

  3. 3.

Return $K_{L}$.

The rows of $K_{L}$ correspond to the $Z$-components of a generating set of
the logical XP group (Section 2.6), which includes the logical identity XP
group. Determining the logical action of the operators is discussed in Section
3.5.

###  3.5 Determine Action of Diagonal Logical XP Operator

Here we demonstrate an algorithm expressing the action of a diagonal logical
XP operator in terms of logical controlled-phase operators. This is important
because the algorithm in Section 3.4 does not yield any information on the
action of the resulting diagonal logical operators.

##### Algorithm 5: Determine Action of Diagonal Logical XP Operator

##### Input:

  1. 1.

The $X$-logicals $L_{X}$ of a CSS code (Section 2.3) with $k$ logical qubits;

  2. 2.

A diagonal XP operator $\overline{B}$ of precision $N:=2^{t}$ that acts as a
logical operator on the code (Section 2.4).

##### Output:

A diagonal Clifford hierarchy operator $B$ on $k$ qubits representing the
logical action of $\overline{B}$.

##### Method:

  1. 1.

Let $V:=\\{\mathbf{v}\in\mathbb{Z}_{2}^{n}:\text{wt}(\mathbf{v})\leq t\\}$;

  2. 2.

For each $\mathbf{v}\in V$, calculate $\mathbf{q_{v}}$ such that
$\overline{B}\lvert\mathbf{v}L_{X}\rangle=\omega^{\mathbf{q_{v}}}\lvert\mathbf{v}L_{X}\rangle$;

  3. 3.

Loop over each $\mathbf{v}\in V$ ordered by weight. For any
$\mathbf{v}\preccurlyeq\mathbf{u}\in V\setminus\\{\mathbf{v}\\}$, update
$\mathbf{q_{u}}:=(\mathbf{q_{u}}-\mathbf{q_{v}})\operatorname{mod}2N$;

  4. 4.

Return $B:=\prod_{\mathbf{v}\in V}CP_{N}(\mathbf{q_{v}},\mathbf{v})$ in terms
of the vector form of controlled-phase operators of Section 2.2.

The above algorithm involves calculating $\mathcal{O}(k^{t})$ phase components
$\mathbf{q_{v}}$, and this is sufficient due to Proposition B.1. A naive
approach which calculates the phase applied to each codeword would involve
calculating $\mathcal{O}(2^{k})$ such phase components, and would be
impractical for CSS codes with a large number of logical qubits.

######  Example 3.4 (Action of Diagonal Logical XP Operators - Hypercube
Codes)

In this example, we apply the method of Section 3.4 to the Hypercube code of
Example 3.1 at level $t=3$. The output of the method of Section 3.4 is a set
of length $8$ vectors over $\mathbb{Z}_{8}$ corresponding to $Z$-components of
diagonal logical XP operators. Using the method of Section 3.5, we obtain the
following list of logical actions corresponding to the $Z$-components:

$\begin{array}[]{|l|l|l|}\hline\cr\mathbf{z}&\textbf{Logical
Action}&\textbf{Clifford level}\\\ \hline\cr 00000044&Z_{0}&1\\\
00000404&Z_{1}&1\\\ 00040004&Z_{2}&1\\\ 00002662&CZ_{01}&2\\\
00260062&CZ_{02}&2\\\ 02060602&CZ_{12}&2\\\ 13313113&CCZ_{012}&3\\\
\hline\cr\end{array}$

In Figure 3 we display the resulting logical operators on the cube and notice
that that the Clifford hierarchy level of the logical operator corresponds to
the dimension of the support of the operator. An interactive version of this
example is available in the linked Jupyter notebook.

Figure 3: Diagonal Logical Operators of Hypercube Code of Dimension $3$:
Logical XP operators returned by the method of Section 3.4 are plotted on the
cube. We note that Clifford hierarchy level 1 logical Z operators have support
on 1D edges, level 2 CZ operators have support on 2D faces and level 3 CCZ
operators have support on the entire 3D cube.

######  Example 3.5 (Hyperbolic Quantum Color Codes and Poset Codes)

In the linked Jupyter notebook, we illustrate the application of the method of
Section 3.4 to codes that have a large number of logical qubits. We choose
examples of self-orthogonal codes that are known to have transversal
implementations of diagonal level 2 Clifford hierarchy logical operators.

Hyperbolic quantum color codes [24] involve constructing codes from
tesselations of the 2D hyperbolic plane. The tesselations are formed from
polygons with an even number of edges, and each vertex is shared by 3 such
polygons. We place a qubit on each vertex of the tesselation. For each
polygonal face, we have an $X$-check corresponding to the adjacent vertices.
The $Z$-checks are the same as the $X$-checks. Applying the method of Section
3.4, we find that the codes have a transversal level $2$ logical operator with
action which can be expressed as a product of controlled-Z operators.

(a) [[56,14,6]] Code

(b) [[64,20,4]] Code

Figure 4: {8,3} Hyperbolic Color Codes: above are tesselations corresponding
to two hyperbolic color codes from Example 3.5. The [[56,14,6]] code is not
globally 3-colourable as there is no valid colour assignment for faces 2 and 4
in the diagram above. Each code has a transversal level 2 diagonal logical
operator whose action is a product of logical CZ operators.

There are various methods in the literature for constructing classical self-
orthogonal codes and these can also be used to make quantum codes with
$Z$-checks which are the same as the $X$-checks which we expect to have
transversal level 2 diagonal logical operators. In [25], self-orthogonal codes
are constructed from partially ordered sets (posets). Analysing poset codes
using our methods, we see that they have transversal level $2$ logical
operators with actions which can be expressed as products of $S$ and $CZ$
operators.

######  Example 3.6 (Triorthogonal Codes)

For triorthogonal codes [10], there is always a logical operator of form
$\overline{T^{\otimes k}}:=UT^{\otimes n}$ where $U$ is a product of $CZ$ and
$S$ operators and $k$ is the number of logical qubits of the code. In the
linked Jupyter notebook, we apply the method of Section 3.4 to find generating
sets of diagonal logical operators for the 38 triorthogonal code classes in
Table II of Ref. [27]. In this example, we consider codes with $k=3$ logical
qubits (this choice can be modified by the user).

Applying our method, we see that the logical operator structure of
triorthogonal codes varies widely. In some cases, the code has a transversal
logical $\overline{T_{i}}$ operator for each logical qubit $0\leq i<k$. For
most of the codes, we find a logical $\overline{T^{\otimes k}}$ operator of XP
form. The exceptions are codes which require the application of $CZ$ operators
to form $\overline{T^{\otimes k}}$, and so would not be identified by our
method. We do not see any instances of logical CCZ or CS operators.

##  4 Transversal Logical Operators Composed of Multi-Qubit Controlled-Phase
Gates

In the previous Section, we have shown how to find a generating set of all
logical operators of a CSS code that can be constructed from single-qubit
phase gates at any level of the Clifford hierarchy. This relied on
representing operators composed of single-qubit phase gates as diagonal XP
operators. In this Section, we show how to find all transversal (depth-one)
logical operators of a CSS code composed of multi-qubit controlled-phase
gates. The method relies on representing controlled-phase operators acting on
a codespace as diagonal XP operators acting on a larger Hilbert space via an
embedding operator.

The structure of this Section is as follows. We first introduce phase-rotation
gates and discuss some of their elementary properties. We then prove a duality
result that transforms controlled-phase operators to phase-rotation operators
and vice versa. Hence phase-rotation gates are an alternative generating set
for diagonal Clifford hierarchy gates. We then describe an embedding operator
from the codespace into a larger Hilbert space such that phase-rotation
operators in the codespace correspond to diagonal XP operators in the embedded
codespace. As a result, any diagonal Clifford hierarchy operator can be
represented as a diagonal XP operator in the embedded codespace.

Finally, we demonstrate an algorithm that searches for transversal logical
operators composed of single- and multi-qubit controlled-phase gates for a
given CSS code. Such implementations are depth one and use operators with
bounded support size and so have fault-tolerant properties. Logical operators
of this type have recently been studied in Refs. [12], [13] and [28] and we
provide examples of the application of the algorithm to codes in these papers.

###  4.1 Phase-Rotation Operators

Phase-rotation operators are single or multi-qubit diagonal gates that form an
alternative generating set for the diagonal Clifford hierarchy operators of
Section 2.1. Phase-rotation operators are defined as follows. Let
$A:=XP_{2}(0|\mathbf{0}|\mathbf{v})$ be a tensor product of $Z$ operators and
let $\omega:=\exp(\pi i/N)$. Let $A_{\pm 1}:=(I\pm A)/2$ be the projectors
onto the $\pm 1$ eigenspaces of $A$ and let $q\in\mathbb{Z}_{2N}$. The phase-
rotation operator is:

$\displaystyle\text{RP}_{N}(q,\mathbf{v})=\exp(\frac{q\pi i}{N}A_{-1}).$ (24)

This form is similar to the Pauli product rotations of Ref. [29] and operators
of this type arise as fundamental gates in NMR [30] and quantum dot systems
[31]. In Proposition A.4, we show that the action of
$\text{RP}_{N}(q,\mathbf{v})$ on the computational basis element
$|\mathbf{e}\rangle$ for $\mathbf{e}\in\mathbb{Z}_{2}^{n}$ is:

$\displaystyle\text{RP}_{N}(q,\mathbf{v})|\mathbf{e}\rangle=\begin{cases}\omega^{q}|\mathbf{e}\rangle&\text{
if }\mathbf{e}\cdot\mathbf{v}\operatorname{mod}2=1\\\
|\mathbf{e}\rangle&\text{ otherwise}.\end{cases}$ (25)

We can express the phase applied more concisely as follows:

$\displaystyle\text{RP}_{N}(q,\mathbf{v})|\mathbf{e}\rangle=\omega^{q\cdot
s_{\mathbf{v}}(\mathbf{e})}|\mathbf{e}\rangle\text{ where
}s_{\mathbf{v}}(\mathbf{e}):=\bigoplus_{i\preccurlyeq\mathbf{v}}\mathbf{e}[i].$
(26)

Single qubit phase gates of precision $N$ in this notation are of form
$P_{i}=\text{RP}_{N}(2,\mathbf{b}^{n}_{i})$ where $\mathbf{b}^{n}_{i}$ is the
length $n$ binary vector which is all zero, apart from component $i$ which is
one.

Where the precision and number of qubits are fixed, we use a more concise
notation for phase-rotation operators analogous to the notation for
controlled-phase operators. For example, on $n=3$ qubits, the following are
examples of precision $N=8$ operators:
$RRZ_{012}:=RP_{8}(8,111),RS_{01}:=RP_{8}(4,110),T_{0}=RP_{8}(2,100)$.

###  4.2 Duality of Controlled-Phase and Phase-Rotation Operators

In Proposition A.5, we prove a duality result that allows us to convert vector
form controlled-phase operators to products of phase-rotation operators and
vice versa:

$\displaystyle\text{CP}_{N}(2^{\text{wt}(\mathbf{v})},\mathbf{v})=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}\text{RP}_{N}(2\cdot(-1)^{\text{wt}(\mathbf{u})-1},\mathbf{u});$
(27)
$\displaystyle\text{RP}_{N}(2,\mathbf{v})=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}\text{CP}_{N}(2\cdot(-2)^{\text{wt}(\mathbf{u})-1},\mathbf{u}).$
(28)

In Section 2.2, we saw that operators of form
$\text{CP}_{N}(2^{\text{wt}(\mathbf{v})},\mathbf{v})$ with
$\text{wt}(\mathbf{v})\leq t$ and $N:=2^{t}$ generate the level $t$ diagonal
Clifford hierarchy operators. As a consequence of the duality result, phase-
rotation operators of form $\text{RP}_{N}(2,\mathbf{v})$ where
$\text{wt}(\mathbf{v})\leq t$ are an alternative generating set. In the linked
Jupyter notebook we show that
$RS_{01}=CZ_{01}S_{1}S_{2}=RS^{3}_{01}Z_{1}Z_{2}$ by applying the duality
result twice - hence phase-rotation operators may have more than one vector
representation.

###  4.3 Embedded Code Method

The embedded code method involves constructing an embedding operator on the
codespace of a CSS code such that phase-rotation operators in the original
codespace correspond to diagonal XP operators in the embedded codespace. The
embedding technique is similar to the one used to represent weighted
hypergraph states in Section 5.4 of Ref. [14]. We first define the embedding
operator in terms of its action on computational basis states, then show how
to extend it to phase rotation operators and strings of Pauli X operators. As
an example, we show how the embedding operator transforms repetition codes.

####  4.3.1 Action of Embedding Operator on Computational Basis States and CSS
Codespaces

Let $M^{n}_{t}$ be the matrix whose rows are the binary vectors of length $n$
of weight between $1$ and $t$. Let $V$ be a matrix whose rows are a subset of
the rows of $M^{n}_{t}$. We define the embedding operator
$\mathcal{E}_{V}:\mathcal{H}_{2}^{n}\rightarrow\mathcal{H}_{2}^{|V|}$ that has
the following action on computational basis vectors
$\lvert\mathbf{e}\rangle,\mathbf{e}\in\mathbb{Z}_{2}^{n}$:

$\displaystyle\mathcal{E}_{V}|\mathbf{e}\rangle=|\mathbf{e}V^{T}\operatorname{mod}2\rangle.$
(29)

Now let $S_{X},L_{X}$ be the $X$-checks and $X$-logicals of a CSS code
$\mathbf{C}$ on $n$ qubits (see Section 2.3). The image of the codespace of
$\mathbf{C}$ under $\mathcal{E}_{V}$ is the codespace of the embedded code
$\mathbf{C}_{V}$ defined as follows:

  * •

$X$-checks $S^{V}_{X}:=S_{X}V^{T}$

  * •

$X$-logicals $L^{V}_{X}:=L_{X}V^{T}$

  * •

$Z$-checks $S^{V}_{Z}:=\ker_{\mathbb{Z}_{2}}\begin{pmatrix}S^{V}_{X}\\\
L^{V}_{X}\end{pmatrix}$

Providing $V$ is full rank, the $X$-checks and $X$-logicals of the embedded
code are independent (for instance if $V$ includes all rows of $I_{n}$). We
will show that phase-rotation operators acting on the codespace correspond to
diagonal XP operators in the embedded codespace. Because operators of form
$RP_{N}(2,\mathbf{v})$ for $\mathbf{v}\in M^{n}_{t}$ and $N=2^{t}$ generate
all controlled-phase operators of level $t$ on $n$ qubits (see Section 4.2),
choosing $V=M^{n}_{t}$ allows any such operator to be represented. By limiting
$V$ to a subset of $M^{n}_{t}$, we can place restrictions on the phase-
rotation operators we wish to work with in the embedded codespace. For
instance, we can allow only nearest neighbour interactions for a lattice-based
code or cater for ZX symmetries and qubit partitions as discussed in Refs.
[12] and [13].

####  4.3.2 Action of Embedding Operator on Phase-Rotation and Pauli X
Operators

We now demonstrate an extension of the embedding operator $\mathcal{E}_{V}$ to
phase-rotation and Pauli X operators which acts as a group homomorphism. A
group homomorphism must respect commutation relations, and this is much
simpler to achieve for phase-rotation operators than for controlled-phase
operators. In Proposition A.7, we prove the following commutation relation for
controlled-phase and Pauli X operators:

$\displaystyle\text{CP}_{N}(q,\mathbf{v})X_{i}=\begin{cases}X_{i}\text{CP}_{N}(-q,\mathbf{v})\text{CP}_{N}(q,\mathbf{v}\oplus\mathbf{b}^{n}_{i})&\text{
if }\mathbf{v}[i]=1\\\ X_{i}\text{CP}_{N}(q,\mathbf{v})&\text{
otherwise.}\end{cases}$ (30)

In Equation 30, $\mathbf{b}^{n}_{i}$ is the binary vector of length $n$ which
is zero apart from entry $i$ which is one. Extending this to arbitrary strings
of $X$ operators we obtain the following:

$\displaystyle\text{CP}_{N}(q,\mathbf{v})XP_{2}(0|\mathbf{x}|\mathbf{0})$
$\displaystyle=XP_{2}(0|\mathbf{x}|\mathbf{0})\prod_{\mathbf{0}\preccurlyeq\mathbf{u}\preccurlyeq\mathbf{xv}}\text{CP}_{N}(q\cdot(-1)^{\text{wt}(\mathbf{xv})+\text{wt}(\mathbf{u})},\mathbf{v}\oplus\mathbf{u}).$
(31)

In Proposition A.6, we prove the much simpler commutation relation for phase-
rotation operators which corresponds closely to the commutation relation for
XP operators in Equation 15:

$\displaystyle\text{RP}_{N}(q,\mathbf{v})X_{i}=\begin{cases}\omega^{q}X_{i}\text{RP}_{N}(-q,\mathbf{v})&\text{
if }\mathbf{v}[i]=1\\\ X_{i}\text{RP}_{N}(q,\mathbf{v})&\text{
otherwise}\end{cases}$ (32)

The relation in Equation 32 also implies that for any $V\subset M^{n}_{t}$, we
have closure under conjugation with any Pauli $X$ string, which is not the
case for controlled-phase operators.

Now consider the group $\mathcal{XRP}^{V}_{N}$ generated by operators of form
$\omega I$, $X_{i}$ and $\text{RP}_{N}(2,\mathbf{v})$ for $\mathbf{v}$ a row
of $V$. Elements of $\mathcal{XRP}^{V}_{N}$ can be written in terms of
components $p\in\mathbb{Z}_{2N}$, $\mathbf{x}\in\mathbb{Z}_{2}^{n}$,
$\mathbf{q}\in\mathbb{Z}_{N}^{|V|}$ such that:

$\displaystyle\text{XRP}^{V}_{N}(p|\mathbf{x}|\mathbf{q}):=\omega^{p}\prod_{0\leq
i<n}X_{i}^{\mathbf{x}[i]}\prod_{\mathbf{v}\in
V}\text{RP}_{N}(2\mathbf{q}[\mathbf{v}],\mathbf{v}).$ (33)

We define an embedding map for XRP operators with respect to $V$ as follows:

$\displaystyle\mathcal{E}_{V}(\text{XRP}^{V}_{N}(p|\mathbf{x}|\mathbf{q})):=XP_{N}(p|\mathbf{x}V^{T}|\mathbf{q})$
(34)

In Proposition B.4, we show that the embedding operator $\mathcal{E}_{V}$
respects group operations and so acts as a group homomorphism. As a result, we
can use the diagonal logical identity and logical operator algorithm in
Section 3.1 and Section 3.4 to find logical operators in the embedded
codespace. The results can be interpreted as phase-rotation operators in the
original codespace. One application of this method is to better understand
what kinds of coherent noise a CSS code is inherently protected against as in
[32]. The logical identity group of the embedded code represents the
correlated noise that the code protects against up to configurable constraints
(for example connectivity and the level of Clifford hierarchy).

######  Example 4.1 (Embedding the Repetition Code)

In this example we show how to construct an embedded code based on the
repetition code. For example, let $S_{X}$ be the check matrix of the classical
repetition code on $3$ bits and let $L_{X}$ be a weight one vector. This forms
a CSS code $\mathbf{C}$ with:

$\displaystyle S_{X}$ $\displaystyle:=\begin{pmatrix}110\\\ 011\end{pmatrix},$
(35) $\displaystyle L_{X}$ $\displaystyle:=\begin{pmatrix}001\end{pmatrix}.$
(36)

Let $V:=M^{3}_{2}$ be the matrix whose rows are binary vectors of length $3$
and weight $1$ or weight $2$. The embedded code $\mathbf{C}_{V}$ is defined by
setting $S^{V}_{X}:=S_{X}V^{T}$ and $L^{V}_{X}:=L_{X}V^{T}$ so that:

$\displaystyle V^{T}$ $\displaystyle:=\begin{pmatrix}100110\\\ 010101\\\
001011\end{pmatrix},$ (37) $\displaystyle S^{V}_{X}$
$\displaystyle:=S_{X}V^{T}=\begin{pmatrix}101101\\\ 011110\end{pmatrix},$ (38)
$\displaystyle L^{V}_{X}$
$\displaystyle:=L_{X}V^{T}=\begin{pmatrix}001011\end{pmatrix}.$ (39)

Applying the method of Section 3.4, we find that the embedded code has a
logical $S$ operator given by
$\overline{S}_{V}:=XP_{4}(0|\mathbf{0}|113133)=S_{0}S_{1}S_{2}^{3}S_{3}S_{4}^{3}S_{5}^{3}$.
In the original codespace, this corresponds to the following product of phase-
rotation gates (Section 4.1):

$\displaystyle\overline{S}:=RP_{4}(2,100)RP_{4}(2,010)RP_{4}(6,001)RP_{4}(2,110)RP_{4}(6,101)RP_{4}(6,011).$
(40)

In the linked Jupyter notebook, users can verify that using a repetition code
on $d$ bits and $V=M^{d}_{t}$ the matrix whose rows are binary vectors of
length $d$ of weight between $1$ and $t$, the embedded code has a transversal
logical phase gate at level $t$ of the Clifford hierarchy.

###  4.4 Algorithm 6: Depth-One Logical Operators

We now show how to find the transversal logical operators composed of single
and multi-qubit diagonal Clifford hierarchy gates (i.e., depth-one circuit
implementations where each physical qubit is involved in at most one gate) for
a CSS code. It relies on the method of representing phase-rotation operators
on a codespace as XP operators in an embedded codespace of Section 4.3.

##### Algorithm 6: Depth-One Logical Operators

##### Input:

  1. 1.

The $X$-checks $S_{X}$ and $X$-logicals $L_{X}$ of a CSS code (Section 2.3);

  2. 2.

The desired level $t$ of the Clifford hierarchy (Section 2.1).

##### Output:

A depth-one implementation of a logical controlled-phase operator at level
$t$, or FALSE if there is no such implementation.

##### Method:

  1. 1.

Use the embedding $V=M^{n}_{t}$ – all binary vectors of length $n$ of weight
between $1$ and $t$;

  2. 2.

For the embedded code $\mathbf{C}_{V}$ (Section 4.3), calculate $K_{L}$ the
rows of which are the $Z$-components of a generating set of the diagonal
logical XP operator group (Section 3.4);

  3. 3.

For each row of $K_{L}$, determine the logical action and the level of the
Clifford hierarchy (Section 3.5);

  4. 4.

From the rows of $K_{L}$, choose a vector $\mathbf{z}$ corresponding to a
logical operator at level $t$ of the Clifford hierarchy. If there is no such
operator, return FALSE. Otherwise, perform the following steps:

    1. (a)

Remove $\mathbf{z}$ from $K_{L}$;

    2. (b)

For each element $\mathbf{q}$ of the rowspan of $K_{L}$ over $\mathbb{Z}_{N}$,
check if $\mathbf{z}^{\prime}:=(\mathbf{q}+\mathbf{z})\operatorname{mod}N$
represents a depth-one operator. If so, return $\mathbf{z}^{\prime}$;

    3. (c)

If no depth-one operator is found, go to Step 4.

When the CSS code has a known symmetry, we can search for depth-one logical
operators more efficiently by modifying the embedding operator. The depth-one
algorithm can take as input a permutation of the physical qubits in cycle form
such that the cycles partition the $n$ physical qubits. Let
$\mathbf{c}=(c_{1},c_{2},\dots,c_{l})$ be a cycle in the permutation and let
$\mathbf{b}^{n}_{\mathbf{c}}$ be the length $n$ binary vector which is zero
apart from the components $i\in\mathbf{c}$ that are one. The rows of the
embedding matrix $V$ are the vectors $\mathbf{b}^{n}_{\mathbf{c}}$ for the
cycles $c$ in the permutation.

The algorithm as outlined above yields logical operators composed of physical
phase-rotation gates. To search for logical operators composed of controlled-
phase gates, transform the matrix $K_{L}$ by using the duality result of
Section 4.2. In this case, due to the commutation relation in Equation 31, we
need to ensure that for all $\mathbf{v}\in V$ any length $n$ binary vector
whose support is a subset of the support of $\mathbf{v}$ is also in $V$ – that
is if $\mathbf{v}\in V$ and $\mathbf{u}\preccurlyeq\mathbf{v}$ then
$\mathbf{u}\in V$.

Note that $M^{n}_{t}$ has $\genfrac{[}{]}{0.0pt}{2}{n}{t}:=\sum_{1\leq j\leq
t}\genfrac{(}{)}{0.0pt}{2}{n}{j}$ rows, so we would generally apply the
algorithm only to small codes of around 30 physical qubits (e.g., for $t=2$
and $n=30,M^{n}_{t}$ has $465$ rows, but for $n=100,M^{n}_{t}$ has $5,050$
rows). In Section B.4 we describe a method for more efficiently exploring the
search space.

######  Example 4.2 (Depth-One Algorithm)

In the linked Jupyter notebook, we illustrate the depth-one search algorithm
for small codes. For a given code and a desired level of the Clifford
hierarchy $t$, the output is a logical operator with a depth-one circuit
implementation whose logical action is at level $t$ of the diagonal Clifford
hierarchy, or FALSE if no such operator exists. This is done with no knowledge
of the logical action of the operator or symmetries of the code. For example,
we identify the depth-one implementation of the logical
$\overline{S}_{0}\overline{S}_{1}^{3}$ of the 2D toric code as discussed in
Refs. [11], [12] and [13]. Users can also apply the algorithm to Bring’s code
which is a 30-qubit LDPC code discussed in Ref. [12] and various examples of
morphed codes which are discussed in Ref. [28]. Users can also choose to use a
known symmetry of the code to speed up the search – this can be used for
instance to verify the partitioned logical operators of the symmetric
hypergraph product codes of Ref. [13].

##  5 Other Applications of Embedded Codes

In this Section, we discuss other applications of the embedded code method of
Section 4.3. We first show that for any CSS code with $k$ logical qubits and
any diagonal Clifford hierarchy operator $B$ on $k$ qubits, we can write a
closed-form expression for a logical $\overline{B}$ operator on the codespace
composed of phase-rotation gates (see Section 4.1). As a consequence, the
embedded code has a logical $B$ operator composed of single-qubit phase gates.
This leads to a method of generating CSS codes that have transversal
implementations of any desired diagonal logical Clifford hierarchy operator.

###  5.1 Canonical Implementations of Logical Controlled-Phase Operators

Here, we show how to implement a desired logical controlled-phase operator on
an arbitrary CSS code via a canonical form composed of the phase-rotation
gates of Section 4.1. We demonstrate implementations of logical $S,T,CZ$ and
$CS$ operators using the 2D toric code as an example. As the canonical
implementation is in terms of phase-rotation operators, we can apply the
embedded code method of Section 4.3 and implement the logical operator in the
embedded codespace using single qubit phase gates. We use this fact to
generate families of CSS codes that have transversal implementations of a
desired logical controlled-phase operator using single-qubit phase gates. The
methodology is illustrated in Figure 5.

$\begin{CD}\mathcal{H}_{2}^{k}@>{\mathcal{C}}>{}>\mathcal{H}_{2}^{n}@>{\mathcal{E}_{V}}>{}>\mathcal{H}_{2}^{|V|}\\\
@V{B}V{}V@V{\overline{B}}V{}V@V{\overline{B}_{V}}V{}V\\\
\mathcal{H}_{2}^{k}@>{\mathcal{C}}>{}>\mathcal{H}_{2}^{n}@>{\mathcal{E}_{V}}>{}>\mathcal{H}_{2}^{|V|}\end{CD}$
Figure 5: Logical Operators of CSS Codes and Embedded Codes: A CSS encoding
maps $k$ logical qubits into $n$ physical qubits via
$\mathcal{C}:\mathcal{H}_{2}^{k}\rightarrow\mathcal{H}_{2}^{n}$, which takes
computational basis elements $|\mathbf{v}\rangle$ to codewords
$|\mathbf{v}\rangle_{L}$. Consider a level-$t$ controlled-phase operator $B$
acting on $\mathcal{H}_{2}^{k}$. An operator $\overline{B}$ acting on
$\mathcal{H}_{2}^{n}$ is a logical $B$ operator if
$\overline{B}\mathcal{C}=\mathcal{C}B$. We show how to construct a canonical
logical $B$ operator $\overline{B}$ from level-$t$ phase-rotation gates. Let
$V$ be the matrix whose rows are length $n$ binary vectors representing the
support of the controlled-phase operators making up $\overline{B}$. The
embedded codespace is formed by applying the embedding
$\mathcal{E}_{V}:\mathcal{H}_{2}^{n}\rightarrow\mathcal{H}_{2}^{|V|}$ which
takes the computational basis element $\lvert\mathbf{e}\rangle$ to
$\lvert\mathbf{e}V^{T}\operatorname{mod}2\rangle$. This enables us to
construct a logical $B$ operator $\overline{B}_{V}$ on the embedded codespace
from single qubit phase gates.

###  5.2 Canonical Form for Logical Phase Operators

In the proposition below, we show that logical phase operators have a
particularly simple form in terms of the phase-rotation gates of Section 4.1.

######  Proposition 5.1 (Canonical Logical $P$ Operator)

Let $\mathbf{z}_{i}\in\mathbb{Z}_{2}^{n}$ be the $Z$-component of a logical
$Z_{i}$ operator $\overline{Z_{i}}:=XP_{2}(0|\mathbf{0}|\mathbf{z}_{i})$. The
operator $\overline{P_{i}}:=RP_{N}(2,\mathbf{z}_{i})$ is a logical $P_{i}$
operator.

###### Proof.

The action of a $P_{i}$ operator on a computational basis element
$\lvert\mathbf{v}\rangle$ where $\mathbf{v}\in\mathbb{Z}_{2}^{k}$ can be
written
$P_{i}\lvert\mathbf{v}\rangle=\omega^{2\mathbf{v}[i]}\lvert\mathbf{v}\rangle$.
Let $\mathcal{C}:\mathcal{H}_{2}^{k}\rightarrow\mathcal{H}_{2}^{n}$ be the
encoding operator
$\mathcal{C}\lvert\mathbf{v}\rangle=\lvert\mathbf{v}\rangle_{L}$ for
$\mathbf{v}\in\mathbb{Z}_{2}^{k}$. From Equation 8, $\overline{P_{i}}$ is a
logical $P_{i}$ operator if $\overline{P_{i}}\mathcal{C}=\mathcal{C}P_{i}$.
Hence:

$\displaystyle\mathcal{C}P_{i}\lvert\mathbf{v}\rangle$
$\displaystyle=\omega^{2\mathbf{v}[i]}\lvert\mathbf{v}\rangle_{L}=\sum_{\mathbf{u}\in\mathbb{Z}_{2}^{r}}\omega^{2\mathbf{v}[i]}\lvert\mathbf{e_{uv}}\rangle$
(41)
$\displaystyle=\overline{P_{i}}\lvert\mathbf{v}\rangle_{L}=\sum_{\mathbf{u}\in\mathbb{Z}_{2}^{r}}\overline{P_{i}}\lvert\mathbf{e_{uv}}\rangle.$
(42)

Hence, we require
$\overline{P_{i}}\lvert\mathbf{e_{uv}}\rangle=\omega^{2\mathbf{v}[i]}\lvert\mathbf{e_{uv}}\rangle$.
Set the precision $N=2$, and we have
$\overline{Z_{i}}\lvert\mathbf{e_{uv}}\rangle=(-1)^{\mathbf{v}[i]}\lvert\mathbf{e_{uv}}\rangle$.
Applying Equation 17, we have
$\overline{Z_{i}}\lvert\mathbf{e_{uv}}\rangle=XP_{2}(0|\mathbf{0}|\mathbf{z}_{i})\lvert\mathbf{e_{uv}}\rangle=(-1)^{\mathbf{e_{uv}}\cdot\mathbf{z}_{i}}\lvert\mathbf{e_{uv}}\rangle$.
Therefore,
$\mathbf{e_{uv}}\cdot\mathbf{z}_{i}\operatorname{mod}2=\mathbf{v}[i]$. Now
consider the action of $\overline{P_{i}}:=RP_{N}(2,\mathbf{z}_{i})$ on
$\lvert\mathbf{e_{uv}}\rangle$ using Proposition A.4:

$\displaystyle
RP_{N}(2,\mathbf{z}_{i})\lvert\mathbf{e_{uv}}\rangle=\omega^{2(\mathbf{e_{uv}}\cdot\mathbf{z}_{i}\operatorname{mod}2)}\lvert\mathbf{e_{uv}}\rangle=\omega^{2\mathbf{v}[i]}\lvert\mathbf{e_{uv}}\rangle,$
(43)

as required for $\overline{P_{i}}$ to act as a logical $P$ operator. ∎

Using the duality of RP and CP operators of Section 4.2, we can write
$\overline{P}_{i}$ as a product of CP gates:

$\displaystyle\overline{P}_{i}:=RP_{N}(2,\mathbf{z}_{i})=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{z}_{i}}\text{CP}_{N}(2\cdot(-2)^{\text{wt}(\mathbf{u})-1},\mathbf{u}).$
(44)

As $N=2^{t}$, any terms with $\text{wt}(\mathbf{u})>t$ disappear. Hence the
support of the CP gates in the implementation are of maximum size $t$. The
implementation may not be transversal, as a qubit may be acted upon by more
than one gate.

######  Example 5.1 (Logical Phase Operators of the 2D Toric Code)

We illustrate the canonical form of logical controlled-phase operators by
considering the 2D toric code. Using the XP operator notation of Equation 16,
let
$Z_{0}:=XP_{2}(0|\mathbf{0}|\mathbf{z}_{0}),Z_{1}:=XP_{2}(0|\mathbf{0}|\mathbf{z}_{1})$
be logical $Z$ operators on logical qubit 0 and 1 respectively with
$d:=\text{wt}(\mathbf{z}_{0})=\text{wt}(\mathbf{z}_{1})\geq 3$. Applying
Equation 44 and using the notation of Equation 1 for controlled-phase
operators, the canonical forms for the logical $S$ and $T$ operators on qubit
0 are as follows:

$\displaystyle\overline{S}_{0}$
$\displaystyle:=RP_{4}(2,\mathbf{z}_{0})=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{z}_{0}}\text{CP}_{4}(2\cdot(-2)^{\text{wt}(\mathbf{u})-1},\mathbf{u})$
(45)
$\displaystyle=\prod_{\begin{subarray}{c}\mathbf{u}\preccurlyeq\mathbf{z}_{0}\\\
\text{wt}(\mathbf{u})=2\end{subarray}}\text{CP}_{4}(-4,\mathbf{u})\prod_{\begin{subarray}{c}\mathbf{u}\preccurlyeq\mathbf{z}_{0}\\\
\text{wt}(\mathbf{u})=1\end{subarray}}\text{CP}_{4}(2,\mathbf{u})$ (46)
$\displaystyle=\prod_{i<j\preccurlyeq\mathbf{z}_{0}}CZ_{ij}\prod_{i\preccurlyeq\mathbf{z}_{0}}S_{i}$
(47) $\displaystyle\overline{T}_{0}$
$\displaystyle:=RP_{8}(2,\mathbf{z}_{0})=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{z}_{0}}\text{CP}_{8}(2\cdot(-2)^{\text{wt}(\mathbf{u})-1},\mathbf{u})$
(48)
$\displaystyle=\prod_{\begin{subarray}{c}\mathbf{u}\preccurlyeq\mathbf{z}_{0}\\\
\text{wt}(\mathbf{u})=3\end{subarray}}\text{CP}_{8}(8,\mathbf{u})\prod_{\begin{subarray}{c}\mathbf{u}\preccurlyeq\mathbf{z}_{0}\\\
\text{wt}(\mathbf{u})=2\end{subarray}}\text{CP}_{8}(-4,\mathbf{u})\prod_{\begin{subarray}{c}\mathbf{u}\preccurlyeq\mathbf{z}_{0}\\\
\text{wt}(\mathbf{u})=1\end{subarray}}\text{CP}_{8}(2,\mathbf{u})$ (49)
$\displaystyle=\prod_{i<j<k\preccurlyeq\mathbf{z}_{0}}CCZ_{ijk}\prod_{i<j\preccurlyeq\mathbf{z}_{0}}CS^{-1}_{ij}\prod_{i\preccurlyeq\mathbf{z}_{0}}T_{i}$
(50)

These results hold for any CSS code with $\text{wt}(\mathbf{z}_{0})\geq 3$, as
no other special properties of the toric code have been used.

###  5.3 Canonical Form of Logical Phase-Rotation and Controlled-Phase
Operators

We now generalise the method in Section 5.2 and show how to implement logical
phase-rotation operators for CSS codes using physical phase-rotation gates.
Let $L_{Z}$ be the $k\times n$ binary matrix representing logical $Z$
operators such that $L_{Z}L_{X}^{T}\operatorname{mod}2=I_{k}$ where
$k=|L_{X}|$. This means that $XP_{2}(0|\mathbf{0}|\mathbf{z}_{i})$ anti-
commutes with $XP_{2}(0|\mathbf{x}_{j}|\mathbf{0})$ if and only if $i=j$. Let
$\mathbf{u}$ be a binary vector of length $k$. In Proposition B.5 we show that
the following is a logical phase-rotation operator:

$\displaystyle\overline{\text{RP}_{N}(2,\mathbf{u})}:=\text{RP}_{N}(2,\mathbf{u}L_{Z})$
(51)

By the duality result of Section 4.2, we can write logical phase-rotation
operators as follows:

$\displaystyle\overline{\text{CP}_{N}(2^{\text{wt}(\mathbf{v})},\mathbf{v})}$
$\displaystyle:=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}\overline{\text{RP}_{N}(2\cdot(-1)^{\text{wt}(\mathbf{u})-1},\mathbf{u})}$
(52)
$\displaystyle=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}\text{RP}_{N}(2\cdot(-1)^{\text{wt}(\mathbf{u})-1},\mathbf{u}L_{Z})$
(53)

This in turn can be converted into products of physical controlled-phase gates
by applying the duality result a second time.

##### Algorithm 7: Canonical Logical Controlled-Phase Operators

##### Input:

  1. 1.

The $Z$-logicals $L_{Z}$ of a CSS code (see above);

  2. 2.

A level-$t$ diagonal Clifford hierarchy operator $B$ on $k$ qubits (Section
2.1).

##### Output:

A logical $\overline{B}$ operator (Section 2.4) on the code composed of
physical phase rotation gates (Section 4.1) with maximum support size $t$.

##### Method:

  1. 1.

Express $B=\prod_{\mathbf{u}}RP_{N}(\mathbf{q_{u},u})$ as a product of phase
rotation gates using the duality result of Section 4.2 where $N=2^{t}$ and
$\mathbf{u}\in\mathbb{Z}_{2}^{k}$;

  2. 2.

The operator $\overline{B}=\prod_{\mathbf{u}}RP_{N}(\mathbf{q_{u},u}L_{Z})$ is
a logical $B$ operator;

  3. 3.

Apply the duality result of Section 4.2 twice to express $\overline{B}$ as a
product of phase-rotation gates of maximum support size $t$.

######  Example 5.2 (Logical Controlled-Phase Operators of Toric Code)

We now demonstrate a canonical implementation of a logical CZ operator on the
2D toric code of Example 5.1 composed of physical controlled-phase gates.
Using Equation 53 and the fact that
$\text{RP}_{4}(2,\mathbf{z}_{0})=\prod_{i<j\preccurlyeq\mathbf{z}_{0}}CZ_{ij}\prod_{i\preccurlyeq\mathbf{z}_{0}}S_{i}$
from Example 5.1:

$\displaystyle\overline{\text{CZ}_{01}}$
$\displaystyle:=\overline{CP_{4}(4,11)}$ (54)
$\displaystyle=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq
11}\text{RP}_{4}(2\cdot(-1)^{\text{wt}(\mathbf{u})-1},\mathbf{u}L_{Z})$ (55)
$\displaystyle=\text{RP}_{4}(-2,\mathbf{z}_{0}\oplus\mathbf{z}_{1})\text{RP}_{4}(2,\mathbf{z}_{0})\text{RP}_{4}(2,\mathbf{z}_{1})$
(56)
$\displaystyle=\Big{(}\prod_{i<j\preccurlyeq\mathbf{z}_{0}\oplus\mathbf{z}_{1}}CZ_{ij}\prod_{i\preccurlyeq\mathbf{z}_{0}\oplus\mathbf{z}_{1}}S_{i}\Big{)}^{-1}\Big{(}\prod_{i<j\preccurlyeq\mathbf{z}_{0}}CZ_{ij}\prod_{i\preccurlyeq\mathbf{z}_{0}}S_{i}\Big{)}\Big{(}\prod_{i<j\preccurlyeq\mathbf{z}_{1}}CZ_{ij}\prod_{i\preccurlyeq\mathbf{z}_{1}}S_{i}\Big{)}$
(57)

We can choose logical Z operators for the 2D toric code such that
$\text{supp}(\mathbf{z}_{0})\cap\text{supp}(\mathbf{z}_{1})=\emptyset$. In
this case, all $S$ operators in Equation 57 cancel, as do any CZ operators
which lie entirely on the support of either $\mathbf{z}_{0}$ or
$\mathbf{z}_{1}$, and so we have:

$\displaystyle\overline{\text{CZ}_{01}}$
$\displaystyle:=\prod_{i\preccurlyeq\mathbf{z}_{0},j\preccurlyeq\mathbf{z}_{1}}CZ_{ij}$
(58)

This is an instance of Claim 2 in [33] for logical multi-controlled-$Z$
operators. Our method applies to arbitrary diagonal Clifford hierarchy logical
operators and we can also show:

$\displaystyle\overline{\text{CS}_{01}}$
$\displaystyle:=\overline{CP_{8}(4,11)}$ (59)
$\displaystyle=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq
11}\text{RP}_{8}(2\cdot(-1)^{\text{wt}(\mathbf{u})-1},\mathbf{u}L_{Z})$ (60)
$\displaystyle=\prod_{i\preccurlyeq\mathbf{z}_{0},j\preccurlyeq\mathbf{z}_{1}}CS_{ij}\prod_{i\preccurlyeq\mathbf{z}_{0},j<k\preccurlyeq\mathbf{z}_{1}}CCZ_{ijk}\prod_{i<j\preccurlyeq\mathbf{z}_{0},k\preccurlyeq\mathbf{z}_{1}}CCZ_{ijk}$
(61)

Note that the number of physical gates used in the implementation is
$\mathcal{O}(d^{t})$. As we are not guaranteed that
$\text{supp}(\mathbf{z}_{0})\cap\text{supp}(\mathbf{z}_{1})=\emptyset$ for
arbitrary CSS codes, the above identities are not completely general. In the
linked Jupyter notebook, users can calculate identities of this kind for any
desired CSS code for any diagonal Clifford hierarchy logical operator.

###  5.4 Constructing a CSS Code with a Desired Diagonal Logical Clifford
Hierarchy Operator

In this Section, we apply the canonical logical operator form of Section 5.3
to generate a CSS code with a transversal implementation of a desired logical
controlled-phase operator using single-qubit phase gates.

##### Algorithm 8: Constructing CSS Codes with a Desired Diagonal Logical
Clifford Hierarchy Operator

##### Input:

A controlled-phase operator $B$ on $k$ qubits (Section 2.1) and a target
distance $d$.

##### Output:

A CSS code with a logical $\overline{B}$ operator (Section 2.4) composed of
single-qubit phase gates.

##### Method:

  1. 1.

Let $\mathbf{C}$ be a $k$-dimensional toric code of distance $d$. We construct
the stabiliser generators of $\mathbf{C}$ using the total complex of the
tensor product of $k$ classical repetition codes on $d$ bits (see Section II.D
of [34]). The resulting CSS code has $k$ non-overlapping logical Z operators
of weight $d$;

  2. 2.

Find the canonical implementation of $\overline{B}=\prod_{\mathbf{v}\in
V}RP_{N}(q_{\mathbf{v}},\mathbf{v})$ composed of phase-rotation gates of
maximum support size $t$ using Algorithm 7;

  3. 3.

Remove any elements of $V$ where $q_{\mathbf{v}}=0$ and apply the embedding
$\mathcal{E}_{V}$ to find the $X$-checks and $X$-logicals of the embedded code
$\mathbf{C}_{V}$ as in Section 4.3;

  4. 4.

The resulting code has a logical $B$ operator $\overline{B}_{V}$ composed of
level-$t$ phase gates acting on the embedded codespace.

######  Example 5.3 (Constructing CSS Codes with Transversal Logical
Controlled Phase Operators)

In Table 2, we list the parameters of CSS codes with transversal
implementations of various target logical controlled phase operators using the
method in Section 5.4. The CSS codes are generated from toric codes as
follows. For a target operator acting on $k$ logical qubits, we use a
$k$-dimensional toric code. We generate a series of codes by increasing the
distance $d$ of the toric code. Looking at the CZ column we have a family of
$[[4m^{2},2,2m]]$ codes with a transversal CZ operator, the first member of
which is the $[[4,2,2]]$ code of Example 2.2. Looking at the CCZ column, we
have a family of $[[8m^{3},3,2m]]$ codes which have a transversal CCZ
operator, the first member of which is the hypercube code of Example 3.1. The
6-qubit code in the S column is the 6-qubit code discussed in Example 4.1. The
15-qubit code in the T column is the 15-qubit Reed-Muller code. The first
entry in the CS column is the $[[12,2,2]]$ code with the following $X$-checks
and $X$-logicals:

$\displaystyle S_{X}$ $\displaystyle:=\begin{pmatrix}111100001111\\\
000011111111\end{pmatrix};$ $\displaystyle L_{X}$
$\displaystyle:=\begin{pmatrix}010101010101\\\ 001100110011\end{pmatrix}.$
(62)

An interactive version is available in the linked Jupyter notebook.

d | Logical S | Logical CZ | Logical T | Logical CS | Logical CCZ
---|---|---|---|---|---
| n | $\mathbf{d_{X}}$ | $\mathbf{d_{Z}}$ | n | $\mathbf{d_{X}}$ | $\mathbf{d_{Z}}$ | n | $\mathbf{d_{X}}$ | $\mathbf{d_{Z}}$ | n | $\mathbf{d_{X}}$ | $\mathbf{d_{Z}}$ | n | $\mathbf{d_{X}}$ | $\mathbf{d_{Z}}$
2 | 1 | 1 | 1 | 4 | 2 | 2 | 1 | 1 | 1 | 12 | 6 | 2 | 8 | 4 | 2
3 | 6 | 3 | 2 | 15 | 4 | 3 | 1 | 1 | 1 | 33 | 14 | 2 | 63 | 16 | 3
4 | 6 | 3 | 2 | 16 | 4 | 4 | 14 | 7 | 2 | 64 | 22 | 2 | 64 | 16 | 4
5 | 15 | 5 | 3 | 35 | 6 | 5 | 15 | 7 | 3 | 155 | 40 | 3 | 215 | 36 | 5
6 | 15 | 5 | 3 | 36 | 6 | 6 | 35 | 15 | 2 | 228 | 52 | 4 | 216 | 36 | 6
7 | 28 | 7 | 4 | 63 | 8 | 7 | 36 | 15 | 3 | 385 | 76 | 4 | 511 | 64 | 7
8 | 28 | 7 | 4 | 64 | 8 | 8 | 92 | 29 | 3 | 512 | 92 | 5 | 512 | 64 | 8
9 | 45 | 9 | 5 | 99 | 10 | 9 | 93 | 29 | 3 | 819 | 126 | 5 | 999 | 100 | 9
10 | 45 | 9 | 5 | 100 | 10 | 10 | 165 | 45 | 4 | 1020 | 146 | 6 | 1000 | 100 | 10
Table 2: Parameters of CSS codes generated by the embedded code method when
searching for implementations of logical operators based on the toric code of
distance $d$. For a logical operator acting on $k$ qubits, we use a
$k$-dimensional toric code.

##  6 Conclusion and Open Questions

We have presented efficient new methods to identify and test diagonal logical
operators on CSS codes using both single- and multi-qubit diagonal Clifford
hierarchy gates as building blocks. In addition, we provided a technique for
generating CSS codes with implementations of any desired diagonal Clifford
hierarchy logical operator using single-qubit phase gates. The methods
generalise to non-CSS stabiliser codes as demonstrated in Appendix C. The
algorithms are available in a GitHub repository and are intended to be of
benefit to researchers in understanding the logical operator structure of
stabiliser codes.

Our methods rely on representing diagonal Clifford hierarchy operators as
diagonal XP operators. Our algorithms use the vector representation of XP
operators and linear algebra modulo $N$, and so have reduced computational
complexity compared to existing work in this area.

The ability to represent diagonal Clifford hierarchy operators as XP operators
may have a number of other possible applications. Custom design of CSS codes
for devices that have known coherent noise models is one possibility. If the
noise can be represented as a series of multi-qubit diagonal operators, we
could design a CSS code where these operators are in the logical identity
group and so mitigate coherent noise. The simulation of quantum circuits could
be another application. A circuit composed of multi-qubit diagonal operators,
such as those used for measuring the stabiliser generators of a CSS code,
could be amenable to simulation using XP representations of the gates used. As
any diagonal Clifford hierarchy operator can be represented as a diagonal XP
operator, there could also be implications for computational complexity
theory.

## Acknowledgements

This research was supported by the Australian Research Council via the Centre
of Excellence in Engineered Quantum Systems (EQUS) project number CE170100009.
MW was supported by the Sydney Quantum Academy, Sydney, NSW, Australia. MW and
AOQ were students at the 2022 IBM Quantum Error Correction Summer School and
the idea for this paper originated there; we wish to express our thanks to IBM
for the opportunity to attend the Summer School. MW thanks Robert Calderbank
for hosting his visit to Duke University in August 2022 – the basic structure
of this paper was developed during the visit.

##  Appendix A Controlled-Phase and Phase-Rotation Operators

In this Appendix, we give the detailed proofs of results relating to
controlled-phase and phase-rotation operators. The action and duality property
of these operators derive from sum/product duality properties for binary
vectors and binary variables, and we start by proving these results. We then
prove results relating to phase-rotation operators. We first show that phase-
rotation operators can be written as a sum of projectors. This allows us to
calculate the logical action of phase-rotation operators. We then prove the
duality result between controlled-phase and phase-rotation operators. Finally
we prove the key commutation relations for phase-rotation and controlled-phase
operators.

###  A.1 Product/Sum Duality Results for Binary Vectors and Variables

######  Proposition A.1 (Sum/Product Duality of Binary Vectors)

Let $L$ be a binary matrix with rows $\mathbf{x}_{i}$ for $0\leq i<r$ and
$\mathbf{v}$ a binary vector of length $r$. Define:

$\displaystyle\mathbf{s_{v}}(L)$
$\displaystyle:=\bigoplus_{i\preccurlyeq\mathbf{v}}\mathbf{x}_{i};$ (63)
$\displaystyle\mathbf{p_{v}}(L)$
$\displaystyle:=\prod_{i\preccurlyeq\mathbf{v}}\mathbf{x}_{i}.$ (64)

Then over the integers:

$\displaystyle\mathbf{s_{v}}(L)$
$\displaystyle=\sum_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}(-2)^{\text{wt}(\mathbf{u})-1}\mathbf{p_{u}}(L);$
(65) $\displaystyle 2^{\text{wt}(\mathbf{v})-1}\mathbf{p_{v}}(L)$
$\displaystyle=\sum_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}(-1)^{\text{wt}(\mathbf{u})-1}\mathbf{s_{u}}(L).$
(66)

###### Proof.

Restatement of Proposition E.10 of [14]. ∎

######  Proposition A.2 (Sum/Product Duality of Binary Variables)

Let $\mathbf{e}$ be a vector of $r$ binary variables and let $\mathbf{v}$ a
binary vector of length $r$. Define:

$\displaystyle s_{\mathbf{v}}(\mathbf{e})$
$\displaystyle:=\bigoplus_{i\preccurlyeq\mathbf{v}}\mathbf{e}[i];$ (67)
$\displaystyle p_{\mathbf{v}}(\mathbf{e})$
$\displaystyle:=\prod_{i\preccurlyeq\mathbf{v}}\mathbf{e}[i].$ (68)

Then over the integers:

$\displaystyle s_{\mathbf{v}}(\mathbf{e})$
$\displaystyle=\sum_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}(-2)^{\text{wt}(\mathbf{u})-1}p_{\mathbf{u}}(\mathbf{e});$
(69) $\displaystyle 2^{\text{wt}(\mathbf{v})-1}p_{\mathbf{v}}(\mathbf{e})$
$\displaystyle=\sum_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}(-1)^{\text{wt}(\mathbf{u})-1}s_{\mathbf{u}}(\mathbf{e}).$
(70)

###### Proof.

Application of Proposition A.1 with $L$ the single-column matrix
$\mathbf{e}^{T}$. ∎

###  A.2 Phase-Rotation Operators

######  Proposition A.3 (Projector Form of RP Operators)

Phase-rotation operators can be written in terms of projectors $A_{\pm
1}:=(I\pm A)/2$:

$\displaystyle\text{RP}_{N}(q,\mathbf{v}):=\exp(\frac{q\pi
i}{N}A_{-1})=A_{+1}+\omega^{q}A_{-1}.$ (71)

###### Proof.

Because $A_{-1}$ is a projector, $A_{-1}^{m}=A_{-1}$ for integers $m>0$. Also
$A_{-1}^{0}=I=A_{+1}+A_{-1}$. Hence:

$\displaystyle\exp((q\pi i/N)A_{-1})$ $\displaystyle=I+A_{-1}\sum_{m>0}(q\pi
i/N)^{m}/m!$ (72) $\displaystyle=A_{+1}+A_{-1}\sum_{m\geq 0}(q\pi i/N)^{m}/m!$
(73) $\displaystyle=A_{+1}+e^{q\pi i/N}A_{-1}$ (74)

∎

######  Proposition A.4 (Action of RP Operators)

The action of a phase-rotation operator on a computational basis element
$|\mathbf{e}\rangle$ where $\mathbf{e}\in\mathbb{Z}_{2}^{n}$ and
$\omega:=\exp(\pi i/N)$ is:

$\displaystyle\text{RP}_{N}(q,\mathbf{v})|\mathbf{e}\rangle=\begin{cases}\omega^{q}|\mathbf{e}\rangle&\text{
if }\mathbf{e}\cdot\mathbf{v}\operatorname{mod}2=1\\\
|\mathbf{e}\rangle&\text{ otherwise}.\end{cases}$ (75)

###### Proof.

Straightforward application of projector form of phase-rotation operators in
Proposition A.3. ∎

###  A.3 Duality of Controlled-Phase and Phase-Rotation Operators

The proposition below allows us to express controlled-phase operators (Section
2.1) as products of phase-rotation operators (Section 4.1) and vice-versa.

######  Proposition A.5 (Duality of Controlled-Phase and Phase-Rotation
Operators)

For $N=2^{t}$ and $\mathbf{u,v}$ binary vectors of length $n$ the following
identities hold:

$\displaystyle\text{RP}_{N}(2,\mathbf{v})=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}\text{CP}_{N}(2\cdot(-2)^{\text{wt}(\mathbf{u})-1},\mathbf{u})$
(76)
$\displaystyle\text{CP}_{N}(2^{\text{wt}(\mathbf{v})},\mathbf{v})=\prod_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}\text{RP}_{N}(2\cdot(-1)^{\text{wt}(\mathbf{u})-1},\mathbf{u})$
(77)

###### Proof.

Using Equation 26 and the notation of Proposition A.2, we can write
$\text{RP}_{N}(2,\mathbf{v})\lvert\mathbf{e}\rangle=\omega^{2s_{\mathbf{v}}(\mathbf{e})}\lvert\mathbf{e}\rangle$.
From Proposition A.2, we have
$2s_{\mathbf{v}}(\mathbf{e})=\sum_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}2\cdot(-2)^{\text{wt}(\mathbf{u})-1}p_{\mathbf{u}}(\mathbf{e})$.

Similarly, from Equation 2, we can write
$\text{CP}_{N}(2^{\text{wt}(\mathbf{v})},\mathbf{v})\lvert\mathbf{e}\rangle=\omega^{2^{\text{wt}(\mathbf{v})}p_{\mathbf{v}}(\mathbf{e})}\lvert\mathbf{e}\rangle$
and due to Proposition A.2, we have
$2^{\text{wt}(\mathbf{v})}p_{\mathbf{v}}(\mathbf{e})=\sum_{\mathbf{0}\neq\mathbf{u}\preccurlyeq\mathbf{v}}2\cdot(-1)^{\text{wt}(\mathbf{u})-1}s_{\mathbf{u}}(\mathbf{e})$.

Hence the phases applied on the RHS and LHS are the same and the result
follows. ∎

###  A.4 Commutator Relations for Controlled-Phase and Phase-Rotation
Operators

In this Section, we prove the commutation relations for Pauli X operators with
controlled-phase operators (Section 2.1) and phase-rotation operators (Section
4.1).

######  Proposition A.6 (Commutator Relation for Phase-Rotation Operators)

Let $X_{i}$ denote a Pauli $X$ operator on qubit $i$. The following identity
applies for phase-rotation operators:

$\displaystyle\text{RP}_{N}(q,\mathbf{v})X_{i}=\begin{cases}\omega^{q}X_{i}\text{RP}_{N}(-q,\mathbf{v})&\text{
if }\mathbf{v}[i]=1\\\ X_{i}\text{RP}_{N}(q,\mathbf{v})&\text{
otherwise}\end{cases}$ (78)

###### Proof.

If $\mathbf{v}[i]=0$, the support of the operators do not overlap and hence
the operators commute and the second case follows.

For the case where $\mathbf{v}[i]=1$, let $\mathbf{b}^{n}_{i}$ be the length
$n$ vector which is zero apart from component $i$ which is one. Then, for a
computational basis vector $|\mathbf{e}\rangle$, we have:

$\displaystyle\text{RP}_{N}(q,\mathbf{v})X_{i}|\mathbf{e}\rangle$
$\displaystyle=\text{RP}_{N}(q,\mathbf{v})|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle$
(79)
$\displaystyle=\begin{cases}|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle&\text{
if
}(\mathbf{e}\oplus\mathbf{b}^{n}_{i})\cdot\mathbf{v}=0\operatorname{mod}2\\\
\omega^{q}|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle&\text{
otherwise}.\end{cases}$ (80)
$\displaystyle\omega^{q}X_{i}\text{RP}_{N}(-q,\mathbf{v})|\mathbf{e}\rangle$
$\displaystyle=\begin{cases}\omega^{q}|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle&\text{
if }\mathbf{e}\cdot\mathbf{v}=0\operatorname{mod}2\\\
\omega^{q}\omega^{-q}|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle&\text{
otherwise}.\end{cases}$ (81)

Since, by assumption $\mathbf{v}[i]=1$,
$\mathbf{e}\cdot\mathbf{v}=0\operatorname{mod}2\iff(\mathbf{e}\oplus\mathbf{b}^{n}_{i})\cdot\mathbf{v}=1\operatorname{mod}2$.
Hence, the action on computational basis vectors is identical and the result
follows. ∎

######  Proposition A.7 (Commutation Relation for Controlled-Phase Operators)

$\displaystyle\text{CP}_{N}(q,\mathbf{v})X_{i}=\begin{cases}X_{i}\text{CP}_{N}(q,\mathbf{v})&\text{
if }\mathbf{v}[i]=0\\\
X_{i}\text{CP}_{N}(-q,\mathbf{v})\text{CP}_{N}(q,\mathbf{v}\oplus\mathbf{b}^{n}_{i})&\text{
otherwise}\end{cases}$ (82)

Where $\mathbf{b}^{n}_{i}$ is the length $n$ binary vector which is zero apart
from component $i$ which is one.

###### Proof.

If $\mathbf{v}[i]=0$ then $\text{CP}_{N}(q,\mathbf{v})$ has no support in
common with $X_{i}$ so the operators commute. Now assume $\mathbf{v}[i]=1$
then the operator on the LHS acts on the computational basis element
$|\mathbf{e}\rangle$ as follows:

$\displaystyle\text{CP}_{N}(q,\mathbf{v})X_{i}|\mathbf{e}\rangle$
$\displaystyle=\text{CP}_{N}(q,\mathbf{v})|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle$
(83)
$\displaystyle=\begin{cases}\omega^{q}|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle&\text{
if }\mathbf{v}\preccurlyeq(\mathbf{e}\oplus\mathbf{b}^{n}_{i})\\\
|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle&\text{ otherwise}.\end{cases}$ (84)

Since by assumption $\mathbf{v}[i]=1$, a phase of $\omega^{q}$ is applied
$\iff\mathbf{v}\preccurlyeq(\mathbf{e}\oplus\mathbf{b}^{n}_{i})\iff\mathbf{e}[i]=0\text{
AND }(\mathbf{v}\oplus\mathbf{b}^{n}_{i})\preccurlyeq\mathbf{e}$. Now consider
the RHS and assume $\mathbf{e}[i]=0\text{ AND
}(\mathbf{v}\oplus\mathbf{b}^{n}_{i})\preccurlyeq\mathbf{e}$. In this case, we
do not have $\mathbf{v}\preccurlyeq\mathbf{e}$ because $\mathbf{v}[i]=1$ but
$\mathbf{e}[i]=0$. Hence:

$\displaystyle
X_{i}\text{CP}_{N}(-q,\mathbf{v})\text{CP}_{N}(q,\mathbf{v}\oplus\mathbf{b}^{n}_{i})|\mathbf{e}\rangle$
$\displaystyle=\omega^{q}X_{i}\text{CP}_{N}(-q,\mathbf{v})|\mathbf{e}\rangle$
(85)
$\displaystyle=\omega^{q}X_{i}|\mathbf{e}\rangle=\omega^{q}|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle$
(86)

We now show that all other cases result in a trivial phase. Assume
$\mathbf{e}[i]=1\text{ AND
}(\mathbf{v}\oplus\mathbf{b}^{n}_{i})\preccurlyeq\mathbf{e}$. In this case,
$\mathbf{v}\preccurlyeq\mathbf{e}$ and so:

$\displaystyle
X_{i}\text{CP}_{N}(-q,\mathbf{v})\text{CP}_{N}(q,\mathbf{v}\oplus\mathbf{b}^{n}_{i})|\mathbf{e}\rangle$
$\displaystyle=\omega^{q}X_{i}\text{CP}_{N}(-q,\mathbf{v})|\mathbf{e}\rangle$
(87)
$\displaystyle=\omega^{q}\omega^{-q}X_{i}|\mathbf{e}\rangle=|\mathbf{e}\oplus\mathbf{b}^{n}_{i}\rangle$
(88)

Now assume that $(\mathbf{v}\oplus\mathbf{b}^{n}_{i})\preccurlyeq\mathbf{e}$
is not true. In this case, we can never have
$\mathbf{v}\preccurlyeq\mathbf{e}$ and so neither of the controlled-phase
operators apply a phase, regardless of the value of $\mathbf{e}[i]$. Hence the
LHS and RHS have the same action on computational basis elements and the
result follows. ∎

######  Example A.1 (Commutation Relation for Controlled-Phase Operators)

Using Proposition A.7, we can conjugate controlled-phase operators by strings
of X operators and vice versa. We first compute
$\text{CS}_{01}X_{1}\text{CS}_{01}^{-1}$ where $\text{CS}_{01}$ is a
controlled-$S$ operator on qubits 0 and 1. Using the notation of Equation 1:

$\displaystyle\text{CS}_{01}X_{1}\text{CS}_{01}^{-1}$
$\displaystyle=\text{CP}_{8}(4,11)X_{1}\text{CP}_{8}(-4,11)$ (89)
$\displaystyle=X_{1}\text{CP}_{8}(-4,11)\text{CP}_{8}(4,10)\text{CP}_{8}(-4,11)$
(90) $\displaystyle=X_{1}\text{CP}_{8}(-8,11)\text{CP}_{8}(4,10)$ (91)
$\displaystyle=X_{1}\text{CZ}_{01}S_{0}$ (92)

We now compute $(X_{0}X_{1}X_{2})\text{CCZ}_{012}(X_{0}X_{1}X_{2})^{-1}$.
Using Equation 31 with $\mathbf{x}=\mathbf{v}=111$, and letting
$\mathbf{w}:=\mathbf{u}\oplus\mathbf{v}$:

$\displaystyle(X_{0}X_{1}X_{2})\text{CCZ}_{012}(X_{0}X_{1}X_{2})^{-1}$
$\displaystyle=XP_{2}(0|111|\mathbf{0})\text{CP}_{8}(8,111)XP_{2}(0|111|\mathbf{0})$
(93) $\displaystyle=\prod_{\mathbf{u}\preccurlyeq
111}\text{CP}_{8}(8\cdot(-1)^{3+\text{wt}(\mathbf{u})},\mathbf{v}\oplus\mathbf{u})$
(94) $\displaystyle=\prod_{0\leq\text{wt}(\mathbf{w})\leq
3}\text{CP}_{8}(8,\mathbf{w})$ (95)
$\displaystyle=CP_{8}(8,\mathbf{0})\prod_{0<\text{wt}(\mathbf{w})\leq
3}\text{CP}_{8}(8,\mathbf{w})$ (96)
$\displaystyle=-Z_{0}Z_{1}Z_{2}\text{CZ}_{01}\text{CZ}_{02}\text{CZ}_{12}\text{CCZ}_{012}$
(97)

Interactive versions of these examples are available in the linked Jupyter
notebook.

##  Appendix B Additional Details for Logical Operator Algorithms

This Appendix provides further details on the various logical operator
algorithms. We first prove results that reduce the complexity of the logical
action and logical operator test algorithms of Sections 3.2, 3.5 and 3.3. We
then show how to calculate valid $\mathbf{z}$ vectors that result in diagonal
operators that commute with the $X$-checks up to a logical identity for use in
Section 3.4. We then demonstrate a method for more efficiently searching for
depth-one logical operators composed of multi-qubit controlled phase gates for
use in Section 4.4. We then show that the embedding operator of Section 4.3
acts as a group homomorphism on the group generated by phase-rotation and
Pauli $X$ operators. Finally, we show that the canonical form of Section 5.3
results in a logical operator with the required action.

###  B.1 Reducing Complexity of Logical Action Algorithms

In this Section we show how to reduce the complexity of algorithms which work
with the logical action of diagonal XP operators on the canonical codewords.
If $B:=XP_{N}(0|\mathbf{0|z})$ is a diagonal logical operator of precision
$N:=2^{t}$, then the action of $B$ on the computational basis vectors
$\mathbf{e_{uv}}:=\mathbf{u}S_{X}+\mathbf{v}L_{X}$ making up the canonical
codewords of Equation 7 can be written as
$B\lvert\mathbf{e_{uv}}\rangle=\omega^{2\mathbf{e_{uv}}\cdot\mathbf{z}}\lvert\mathbf{e_{uv}}\rangle$.
In the proposition below, we show that the phase component
$\mathbf{e_{uv}}\cdot\mathbf{z}$ is completely determined by terms of form
$\mathbf{e_{u^{\prime}v^{\prime}}}\cdot\mathbf{z}$ where
$\text{wt}(\mathbf{u^{\prime}})+\text{wt}(\mathbf{v^{\prime}})\leq t$. As a
result, when working with logical actions, we do not need to consider all
$2^{k+r}$ of the $\mathbf{e_{uv}}$ vectors, just a limited set which is of
size polynomial in $k$ and $r$. This reduces the computational complexity of
the algorithms in Section 3.2 and Section 3.5.

###### Proposition B.1

Let $N:=2^{t}$ and $\mathbf{z}\in\mathbb{Z}_{N}^{n}$. The phase component
$\mathbf{e_{uv}}\cdot\mathbf{z}$ can be expressed as a $\mathbb{Z}_{N}$ linear
combination of $\mathbf{e_{u^{\prime}v^{\prime}}}\cdot\mathbf{z}$ where
$\text{wt}(\mathbf{u^{\prime}})+\text{wt}(\mathbf{v^{\prime}})\leq t$.

###### Proof.

Let $G_{X}:=\begin{pmatrix}S_{X}\\\ L_{X}\end{pmatrix}$ and let
$\mathbf{a}:=(\mathbf{u|v})$. Noting that
$\mathbf{e_{uv}}=\mathbf{a}G_{X}=\mathbf{s_{a}}(G_{X})$ and applying
Proposition A.1 we have:

$\displaystyle\mathbf{a}G_{X}=\mathbf{s_{a}}(G_{X})$
$\displaystyle=\sum_{\mathbf{0}\neq\mathbf{b}\preccurlyeq\mathbf{a}}(-2)^{\text{wt}(\mathbf{b})-1}\mathbf{p_{b}}(G_{X})$
(98)

Terms with $\text{wt}(\mathbf{b})>t$ disappear modulo $N=2^{t}$. Using the
linearity of dot product and expressing the $\mathbf{p_{b}}(G_{X})$ in terms
of $\mathbf{s_{c}}(G_{X})$:

$\displaystyle\mathbf{a}G_{X}\cdot\mathbf{z}\operatorname{mod}N$
$\displaystyle=\Big{(}\sum_{\begin{subarray}{c}\mathbf{0}\neq\mathbf{b}\preccurlyeq\mathbf{a}\\\
\text{wt}(\mathbf{a})\leq
t\end{subarray}}(-2)^{\text{wt}(\mathbf{b})-1}\mathbf{p_{b}}(G_{X})\Big{)}\cdot\mathbf{z}\operatorname{mod}N$
(99)
$\displaystyle=\Big{(}\sum_{\begin{subarray}{c}\mathbf{0}\neq\mathbf{b}\preccurlyeq\mathbf{a}\\\
\text{wt}(\mathbf{a})\leq
t\end{subarray}}(-2)^{\text{wt}(\mathbf{b})-1}\sum_{\mathbf{0}\neq\mathbf{c}\preccurlyeq\mathbf{b}}(-1)^{\text{wt}(\mathbf{c})-1}\mathbf{s_{c}}(G_{X})\Big{)}\cdot\mathbf{z}\operatorname{mod}N$
(100)
$\displaystyle=\Big{(}\sum_{\begin{subarray}{c}\mathbf{0}\neq\mathbf{b}\preccurlyeq\mathbf{a}\\\
\text{wt}(\mathbf{a})\leq
t\end{subarray}}(-2)^{\text{wt}(\mathbf{b})-1}\sum_{\mathbf{0}\neq\mathbf{c}\preccurlyeq\mathbf{b}}(-1)^{\text{wt}(\mathbf{c})-1}\mathbf{c}G_{X}\cdot\mathbf{z}\Big{)}\operatorname{mod}N$
(101)

As
$\text{wt}(\mathbf{c})\leq\text{wt}(\mathbf{b})\leq\text{wt}(\mathbf{a})\leq
t$, the result follows. ∎

###  B.2 Test for Diagonal Logical XP Operators

In this Section, we prove that the algorithm in Section 3.3 correctly
identifies diagonal logical operators of XP form. We first show that if the
group commutator of an operator $B$ with each of the logical identities
$A_{1},A_{2}$ is a logical identity, then the group commutator of the product
$A_{1}A_{2}$ is a logical identity.

######  Proposition B.2 (Commutators of Logical Identities)

Let $\mathcal{I}_{\text{XP}}$ be the logical identity group as defined in
Section 2.6 and let $A_{1},A_{2}\in\mathcal{I}_{\text{XP}}$. Let $B$ be an XP
operator such that $[[A_{1},B]]$ and $[[A_{2},B]]\in\mathcal{I}_{\text{XP}}$.
Then $[[A_{1}A_{2},B]]\in\mathcal{I}_{\text{XP}}$

###### Proof.

As $\mathcal{I}_{\text{XP}}$ is a group,
$A_{1},A_{2}\in\mathcal{I}_{\text{XP}}\implies[[A_{1},A_{2}]]\in\mathcal{I}_{\text{XP}}$.
Hence we can write $A_{1}A_{2}=CA_{2}A_{1}$ for some
$C\in\mathcal{I}_{\text{XP}}$. Calculating $[[A_{1}A_{2},B]]$, for some
$C,C^{\prime},C^{\prime\prime}\in\mathcal{I}_{\text{XP}}$:

$\displaystyle[[A_{1}A_{2},B]]$
$\displaystyle=A_{1}A_{2}BA_{2}^{-1}A_{1}^{-1}B^{-1}$ (102)
$\displaystyle=A_{1}(A_{2}BA_{2}^{-1}B^{-1})BA_{1}^{-1}B^{-1}$ (103)
$\displaystyle=A_{1}CBA_{1}^{-1}B^{-1}$ (104)
$\displaystyle=C^{\prime}A_{1}BA_{1}^{-1}B^{-1}$ (105)
$\displaystyle=C^{\prime}C^{\prime\prime}\in\mathcal{I}_{\text{XP}}$ (106)

∎

We now show that for a diagonal XP operator $B$, it is sufficient to check
group commutators with the $r:=|S_{X}|$ operators of form
$XP_{N}(0|\mathbf{x}_{i}|\mathbf{0})$ where $\mathbf{x}_{i}$ are the rows of
the $X$-checks $S_{X}$.

###### Proposition B.3

Let $\mathbf{C}$ be a CSS code with $X$-checks $S_{X}$ and logical identity XP
group $\mathcal{I}_{XP}$ of precision $N$. Let $B:=XP_{N}(0|\mathbf{0|z})$ be
a diagonal XP operator. $B$ is a logical operator if and only if
$[[XP_{N}(0|\mathbf{x}_{i}|\mathbf{0}),B]]\in\mathcal{I}_{\text{XP}}$ for all
rows $\mathbf{x}_{i}$ of $S_{X}$.

###### Proof.

$B$ is a logical operator if and only if $[[A,B]]\in\mathcal{I}_{\text{XP}}$
for all $A\in\mathcal{I}_{\text{XP}}$. If $B$ is a logical operator then
$[[XP_{N}(0|\mathbf{x}_{i}|\mathbf{0}),B]]\in\mathcal{I}_{\text{XP}}$ because
$XP_{N}(0|\mathbf{x}_{i}|\mathbf{0})\in\mathcal{I}_{\text{XP}}$.

Conversely, assume
$[[XP_{N}(0|\mathbf{x}_{i}|\mathbf{0}),B]]\in\mathcal{I}_{\text{XP}}$ for all
rows $\mathbf{x}_{i}$ of $S_{X}$. Let $K_{M}$ be the matrix whose rows are a
generating set of the $Z$-components of the logical identities as defined in
Section 3.1. Any logical identity $A$ can be written as a product of terms of
form $XP_{N}(0|\mathbf{x_{i}|0})$ and $XP_{N}(0|\mathbf{0}|\mathbf{z}_{j})$
where $\mathbf{z}_{j}$ is a row of $K_{M}$. By assumption,
$[[XP_{N}(0|\mathbf{x}_{i}|\mathbf{0}),B]]\in\mathcal{I}_{\text{XP}}$ and
$[[XP_{N}(0|\mathbf{0}|\mathbf{z}_{j}),B]]=I$. Due to Proposition B.2, the
commutator of the product is a logical identity and the result follows. ∎

###  B.3 Algorithm to Determine Commutators of a Given $X$-Check

In the method of Section 3.4, for a given $X$-check $\mathbf{x}\in S_{X}$ we
seek all $Z$-components $\mathbf{z}\in\mathbb{Z}_{N}^{n}$ such that the group
commutator $[[XP_{N}(0|\mathbf{0|z}),XP_{N}(0|\mathbf{x|0})]]$ is a logical
identity. This reduces to solving for $\mathbf{z}$ such that both
$\mathbf{x\cdot z}=0\operatorname{mod}N$ and $2\mathbf{xz}\in\langle
K_{M}\rangle_{\mathbb{Z}_{N}}$ where the rows of $K_{M}$ are the
$Z$-components of the diagonal logical identities as in Section 3.1. In this
Section, we show how to solve for these constraints using linear algebra
modulo $N$. The method is as follows:

Without loss of generality, reorder qubits so that the first $m$ components of
$\mathbf{x}$ are one and the remaining $n-m$ components are zero. In the
matrices of form $(\mathbf{a|b})$ below, the first component has $m$ columns
corresponding to the non-zero components of $\mathbf{x}$, the next $n-m$
columns correspond to the zero components of $\mathbf{x}$. For
$\mathbf{v}\in\mathbb{Z}_{N}$, let $\mathbf{v\cdot 1}:=(\sum_{0\leq
i<n}\mathbf{v}[i])\operatorname{mod}N$.

  1. 1.

The vector $2\mathbf{xz}$ is of the form $(2\mathbf{u|0})$ where $\mathbf{u}$
is of length $m$ and the row span of $C_{0}:=(2I_{m}|0)$ over $\mathbb{Z}_{N}$
represents all vectors of this form;

  2. 2.

Group commutators which are also logical identities are in $\langle
C_{0}\rangle_{\mathbb{Z}_{N}}\bigcap\langle K_{M}\rangle_{\mathbb{Z}_{N}}$ and
a Howell basis $C_{1}$ is calculated via the intersection of spans method in
Appendix 4.1 of [14];

  3. 3.

The rows of $C_{1}$ are of form $(\mathbf{u|0})\in\langle
K_{M}\rangle_{\mathbb{Z}_{N}}$ for $\mathbf{u}$ divisible by $2$ modulo $N$.
Now let $\mathbf{v}:=\mathbf{u}/2$. Because
$2(\mathbf{v}+N/2)=2\mathbf{v}=\mathbf{u}\operatorname{mod}N$,
$(\mathbf{v}\cdot\mathbf{1})\operatorname{mod}N$ is either $0$ or $N/2$.
Adjust the $m$th component of $\mathbf{v}$ by subtracting
$(\mathbf{v}\cdot\mathbf{1})\operatorname{mod}N$. Let $C_{2}$ be the matrix
formed from rows of form $(\mathbf{v|0})$;

  4. 4.

Adding pairs of $N/2$ to the first $m$ components does not change
$2\mathbf{x}\mathbf{z}$ or $\mathbf{x}\cdot\mathbf{z}\operatorname{mod}N$. Let
$A$ be $I_{m-1}$ with a column of ones appended. Add the rows $(N/2\cdot
A|\mathbf{0})$ to $C_{2}$;

  5. 5.

Columns $i$ where $\mathbf{x}[i]=0$ can have arbitrary values, as these do not
contribute to $2\mathbf{x}\mathbf{z}$ or $\mathbf{x}\cdot\mathbf{z}$. Add the
rows $(\mathbf{0}|I_{n-m})$ to $C_{2}$;

  6. 6.

Return qubits to their original order. The valid $Z$-components are given by
the row span of $C_{2}$ over $\mathbb{Z}_{N}$.

###  B.4 Algorithm for Depth-One Operators

In the depth-one algorithm, we find transversal logical operators by starting
with a level-$t$ logical XP operator acting on the embedded codespace, then
multiplying by all possible elements of the diagonal logical XP group of the
embedded code. If the order of the diagonal logical XP group is large, this
method can be computationally expensive. In this Section, we demonstrate an
algorithm for more efficiently exploring the search space and checking if an
operator acting on the embedded codespace acts transversally on the codespace.
We use the residue function defined in Eq. 142 of [14] \- we say that
$\mathbf{z}^{\prime}=\text{Res}_{\mathbb{Z}_{N}}(K_{L},\mathbf{z})$ if:

$\displaystyle\text{How}_{\mathbb{Z}_{N}}\begin{pmatrix}1&\mathbf{z}\\\
0&K_{L}\end{pmatrix}=\begin{pmatrix}1&\mathbf{z}^{\prime}\\\
0&K_{L}^{\prime}\end{pmatrix}$ (107)

The input to this algorithm is the following:

  * •

A binary matrix $V$ for the embedding operator $\mathcal{E}_{V}$;

  * •

A matrix $K_{L}$ representing the $Z$-components of the generators of the
diagonal logical XP group of the embedded code (see Section 3.4).

  * •

A row vector $\mathbf{z}$ of $K_{L}$ which represents the $Z$-component of a
non-trivial logical operator at level $t$ of the diagonal Clifford hierarchy
acting on the embedded codespace. This corresponds to a product of phase-
rotation gates acting on the original codespace;

The output is a depth-one implementation of a non-trivial logical operator at
level $t$ of the diagonal Clifford hierarchy, or FALSE if no such operator
exists. The algorithm method is as follows:

  1. 1.

Remove $\mathbf{z}$ from $K_{L}$;

  2. 2.

Let todo be a list containing only the all ones vector of length $|V|$. The
vectors $\mathbf{a}$ in todo have columns indexed by rows of $V$ and represent
partial partitions of the $n$ qubits. The value of $\mathbf{a}[\mathbf{v}]$
encodes the following information:

     * •

$0$: $\text{supp}(\mathbf{v})$ is not a partition;

     * •

$1$: whether $\text{supp}(\mathbf{v})$ is a partition has not yet been
determined;

     * •

$2$: $\text{supp}(\mathbf{v})$ is a partition. For depth-one operators, any
$\mathbf{u}$ with overlapping support (i.e. $\mathbf{u}\cdot\mathbf{v}\geq 0$
is not a partition).

  3. 3.

While todo is not empty:

    1. (a)

Pop the vector $\mathbf{a}$ from the end of todo;

    2. (b)

Reorder the columns of $\mathbf{z}$ and $K_{L}$ by moving the columns with
$\mathbf{a}[\mathbf{v}]=0$ to the far left, the columns with
$\mathbf{a}[\mathbf{v}]=1$ to the middle and the columns with
$\mathbf{a}[\mathbf{v}]=2$ to the far right.

    3. (c)

Calculate
$\mathbf{z}^{\prime}:=\text{Res}_{\mathbb{Z}_{N}}(K_{L},\mathbf{z})$. If
$\mathbf{z}^{\prime}[\mathbf{v}]>0$ for any $\mathbf{v}$ where
$\mathbf{a}[\mathbf{v}]=0$ then the partition is not valid. This is because
taking the residue will eliminate the leftmost entries of $\mathbf{z}$ if
possible by adding rows of $K_{L}$;

    4. (d)

If the partition is valid, find the the first $\mathbf{v}$ such that
$\mathbf{z}^{\prime}[\mathbf{v}]>0$ and $\mathbf{a}[\mathbf{v}]=1$;

    5. (e)

If there is no such $\mathbf{v}$, we have a depth-one implementation. Return
the qubits to their original order and return $\mathbf{z}^{\prime}$;

    6. (f)

Otherwise, let $\mathbf{a}_{1}$ be the same as $\mathbf{a}$ but where
$\mathbf{a}[\mathbf{v}]=2$ and $\mathbf{a}[\mathbf{u}]=0$ for all $\mathbf{u}$
such that $\mathbf{u}\cdot\mathbf{v}>0$. Let $\mathbf{a}_{2}$ be the same as
$\mathbf{a}$ but with $\mathbf{a}[\mathbf{v}]=2$. The vectors $\mathbf{a}_{1}$
and $\mathbf{a}_{2}$ represent the two possible scenarios where either
$\mathbf{v}$ is or is not a partition - append them to todo;

    7. (g)

Return to Step 3.

  4. 4.

Return FALSE as all possible configurations have been explored.

The above algorithm yields depth-one operators composed of physical phase-
rotation gates. If implementations using physical controlled-phase gates are
required, convert $\mathbf{z}$ and $K_{L}$ to controlled-phase representations
using the method in Section 4.2. If we require a logical operator with exactly
the same action as the original operator with $Z$-component $\mathbf{z}$,
substitute the $Z$-components of the diagonal logical identity generators
$K_{M}$ of Section 3.1 for $K_{L}$.

###  B.5 Representation of Controlled-Phase Operators as XP Operators via
Embedding Operator

In this Section we prove that the phase-rotation operators of Section 4.1
acting on a codespace correspond to diagonal XP operators in the embedded
codespace defined in Section 4.3.2. We do this by demonstrating that the
mapping of phase-rotation operators acting on the codespace to XP operators in
the embedded codespace of Section 4.3.2 is a group homomorphism.

######  Proposition B.4 (Embedding operator induces a group homomorphism)

The embedding operator $\mathcal{E}_{V}$ defined as follows is a group
homomorphism between $\mathcal{XRP}^{V}_{N}$ and $\mathcal{XP}_{N}^{|V|}$:

$\displaystyle\mathcal{E}_{V}(\text{XRP}^{V}_{N}(p|\mathbf{x}|\mathbf{q})):=XP_{N}(p|\mathbf{x}V^{T}|\mathbf{q})$
(108)

###### Proof.

We prove this by considering generators of the group $\mathcal{XRP}^{V}_{N}$.
Let $\mathbf{b}^{n}_{i}$ be the length $n$ binary vector which is zero apart
from component $i$ which is one and consider $X_{i},X_{j}$ for $0\leq i,j<n$:

$\displaystyle\mathcal{E}_{V}(X_{i}X_{j})$
$\displaystyle=\mathcal{E}_{V}\big{(}\text{XRP}_{V}(0|\mathbf{b}^{n}_{i}+\mathbf{b}^{n}_{j}|\mathbf{0})\big{)}$
(109)
$\displaystyle=XP_{N}(0|(\mathbf{b}^{n}_{i}+\mathbf{b}^{n}_{j})V^{T}|\mathbf{0})$
(110)
$\displaystyle=XP_{N}(0|(\mathbf{b}^{n}_{i}V^{T}|\mathbf{0})XP_{N}(0|(\mathbf{b}^{n}_{j}V^{T}|\mathbf{0})$
(111) $\displaystyle=\mathcal{E}_{V}(X_{i})\mathcal{E}_{V}(X_{j}).$ (112)

By a similar argument,
$\mathcal{E}_{V}\big{(}\text{RP}_{N}(2,\mathbf{u})\text{RP}_{N}(2,\mathbf{v})\big{)}=\mathcal{E}_{V}\big{(}\text{RP}_{N}(2,\mathbf{u})\big{)}\mathcal{E}_{V}\big{(}\text{RP}_{N}(2,\mathbf{v})\big{)}$
for $\mathbf{u},\mathbf{v}\in V$. Where $X$ operators precede diagonal
operators we have:

$\displaystyle\mathcal{E}_{V}(X_{i}\text{RP}_{N}(2,\mathbf{v}))$
$\displaystyle=\mathcal{E}_{V}(\text{XRP}_{V}(0|\mathbf{b}^{n}_{i}|\mathbf{b}^{|V|}_{\mathbf{v}}))$
(113)
$\displaystyle=XP_{N}(0|\mathbf{b}^{n}_{i}V^{T}|\mathbf{b}^{|V|}_{\mathbf{v}})$
(114)
$\displaystyle=\mathcal{E}_{V}(X_{i})\mathcal{E}_{V}\big{(}\text{RP}_{N}(2,\mathbf{v})\big{)}$
(115)

Where diagonal operators precede X operators, we first consider the case where
$\mathbf{v}[i]=0$. In this case, the operators commute so we can swap the
order of operators so that the X operators precede the diagonal operator. Now
consider the case $\mathbf{v}[i]=1$ where the operators do not commute:

$\displaystyle\mathcal{E}_{V}\big{(}\text{RP}_{N}(2,\mathbf{v})X_{i}\big{)}$
$\displaystyle=\mathcal{E}_{V}\big{(}\omega^{2}X_{i}\text{RP}_{N}(-2,\mathbf{v})\big{)}$
(116)
$\displaystyle=XP_{N}(2|\mathbf{b}^{n}_{i}V^{T}|-\mathbf{b}^{|V|}_{\mathbf{v}})$
(117)

Due to the commutation relation of Equation 15 and because
$(\mathbf{b}^{n}_{i}V^{T})\mathbf{b}^{|V|}_{\mathbf{v}}=\mathbf{b}^{|V|}_{\mathbf{v}}$
when $\mathbf{v}[i]=1$:

$\displaystyle\mathcal{E}_{V}\big{(}\text{RP}_{N}(2,\mathbf{v})\big{)}\mathcal{E}_{V}(X_{i})$
$\displaystyle=XP_{N}(0|\mathbf{0}|\mathbf{b}^{|V|}_{\mathbf{v}})XP_{N}(0|\mathbf{b}^{n}_{i}V^{T}|\mathbf{0})$
(118)
$\displaystyle=XP_{N}(2|\mathbf{b}^{n}_{i}V^{T}|-\mathbf{b}^{|V|}_{\mathbf{v}})$
(119) $\displaystyle=\mathcal{E}_{V}(\text{RP}_{N}(2,\mathbf{v})X_{i})$ (120)

Because group operations are preserved for generators of the group, the
embedding is a group homomorphism. ∎

###  B.6 Canonical Form of Logical Phase-Rotation Operators

In this Section, we show that the canonical form of logical phase-rotation
operators discussed in Section 5.1 acts as a logical operator as claimed.

######  Proposition B.5 (Logical Phase Rotation Operator)

Let $L_{Z}$ be a binary matrix representing the $Z$-components of logical Z
operators such that $L_{Z}^{T}L_{X}=I_{k}$ and let $\mathbf{w}$ be a binary
vector of length $k$.

The operator $\text{RP}_{N}(2,\mathbf{w}L_{Z})$ acts as a logical
$\overline{\text{RP}_{N}(2,\mathbf{w})}$ operator.

###### Proof.

This can be seen by considering the action of the operator on the
computational basis element $|\mathbf{e}_{\mathbf{uv}}\rangle$ where
$\mathbf{e}_{\mathbf{uv}}:=\mathbf{u}S_{X}+\mathbf{v}L_{X}$. From the argument
in Proposition 5.1,
$\mathbf{e}_{\mathbf{uv}}\cdot\mathbf{z}_{j}\operatorname{mod}2=1\iff\mathbf{v}[j]=1$.
Hence:

$\displaystyle\mathbf{e}_{\mathbf{uv}}\cdot(\bigoplus_{j\preccurlyeq\mathbf{w}}\mathbf{z}_{j})\operatorname{mod}2=1$
$\displaystyle\iff\bigoplus_{j\preccurlyeq\mathbf{w}}\mathbf{v}[j]=1$ (121)
$\displaystyle\iff\mathbf{v}\cdot\mathbf{w}\operatorname{mod}2=1$ (122)

Hence, the phases applied by the operators are the same and the result
follows. ∎

##  Appendix C Application of Methods to Non-CSS Stabiliser Codes

In this work, we have focused on identifying diagonal logical operators for
CSS codes in the form defined in Section 2.3. In this Section, we show how to
find diagonal logical operators for arbitrary non-CSS stabiliser codes. We
will prove the following main proposition:

######  Proposition C.1 (Mapping Non-CSS Stabiliser Codes to CSS Codes)

Let $\mathbf{C}$ be the codespace of a Pauli stabiliser code on $n$ qubits.
There exists a CSS code on $n$ qubits with codespace $\mathbf{C}^{\prime}$
such that $\mathbf{C}=DQ\mathbf{C}^{\prime}$ where
$Q:=XP_{2}(0|\mathbf{q}|\mathbf{0})$, $\mathbf{q}$ is a length $n$ binary
vector and $D$ is a diagonal level 2 Clifford operator. Furthermore, a
diagonal operator $\overline{B}$ is a logical $B$ operator of
$\mathbf{C}^{\prime}$ if and only if $Q\overline{B}Q^{-1}$ is a logical $B$
operator of $\mathbf{C}$.

The CSS code $\mathbf{C}^{\prime}$ in Proposition C.1 may have different error
correction properties to $\mathbf{C}$ (i.e. weight of stabiliser generators
and logical operators), but allows us to determine the diagonal logical
operator structure of $\mathbf{C}$. In this Section, we first introduce some
background material on non-CSS stabiliser codes. CSS codes of the form of
Section 2.3 have diagonal stabiliser generators with zero phase components and
non-diagonal stabiliser generators with zero phase and $Z$-components. This is
not the case for arbitrary stabiliser codes, and we show how to eliminate
these components in two steps to yield the operators $Q$ and $D$ in the above
proposition. We illustrate Proposition C.1 by applying it to the perfect
5-qubit code of Ref. [35].

###  C.1 Background on Non-CSS Codes

Arbitrary Pauli stabiliser codes have stabiliser generators from the Pauli
group $\langle iI,X,Z\rangle^{\otimes n}=\mathcal{XP}_{2}^{n}$. A method of
determining a canonical set of independent stabiliser generators, logical $X$
and logical $Z$ operators is given on page 477 of Ref. [36]. Let
$\mathbf{S}_{X}$ and $\mathbf{S}_{Z}$ be the canonical stabiliser generators
and let $\mathbf{L}_{X}$ be the canonical logical $X$ operators. Elements of
$\mathbf{S}_{Z}$ may have signs of $\pm 1$ and elements of $\mathbf{S}_{X}$
may have non-trivial phase and $Z$-components. For Proposition C.1, we require
that $\mathbf{C}^{\prime}:=(DQ)^{-1}\mathbf{C}$ is stabilised by diagonal
generators with trivial phase components and non-diagonal generators with
trivial phase and $Z$-components.

We now set out a canonical form for the codewords of the stabiliser code
$\mathbf{C}$. Let $r$ be the number of operators in $\mathbf{S}_{X}$ and $k$
the number of operators in $\mathbf{L}_{X}$ and let
$\mathbf{v}\in\mathbb{Z}_{2}^{k}$. Let $\mathbf{q}$ be a binary vector of
length $n$ such that $B\lvert\mathbf{q}\rangle=\lvert\mathbf{q}\rangle$ for
all $B\in\mathbf{S}_{Z}$. Define
$\mathbf{L}_{X}^{\mathbf{v}}:=\prod_{i\preccurlyeq\mathbf{v}}\mathbf{L}_{X}[i]$
where $\mathbf{L}_{X}[i]$ is the $i$th operator in $\mathbf{L}_{X}$. Due to
the arguments in Sections 4.2 and 6.2 of [14], the following codewords span
the codespace $\mathbf{C}$ and define the encoding map $C$ of $\mathbf{C}$
(Section 2.4):

$\displaystyle\lvert\mathbf{v}\rangle_{L}=\sum_{\mathbf{u}\in\mathbb{Z}_{2}^{r}}\mathbf{S}_{X}^{\mathbf{u}}\mathbf{L}_{X}^{\mathbf{v}}\lvert\mathbf{q}\rangle.$
(123)

We now discuss how the codewords and logical operators of a stabiliser code
$\mathbf{C}$ transform when the codespace is acted upon by a unitary operator
$U$. The codewords of the transformed code $\mathbf{C}^{\prime}:=U\mathbf{C}$
are given by $U\lvert\mathbf{v}\rangle_{L}$ so the encoding map of
$\mathbf{C}^{\prime}$ is given by $U\mathcal{C}$. The operator $A$ is a
logical identity of $\mathbf{C}$ if and only if $UAU^{-1}$ is a logical
identity of $\mathbf{C}^{\prime}$. This is because:

$\displaystyle(UAU^{-1})U\lvert\mathbf{v}\rangle_{L}=UA\lvert\mathbf{v}\rangle_{L}=U\lvert\mathbf{v}\rangle_{L}.$
(124)

As the stabiliser generators $\mathbf{S}_{X}$ and $\mathbf{S}_{Z}$ are
elements of the logical identity group, they also update via conjugation. The
operator $\overline{B}$ is a logical $B$ operator on $\mathbf{C}$ if and only
if $U\overline{B}U^{-1}$ is a logical $B$ operator on $\mathbf{C}^{\prime}$
because for all logical identities $A$ of $\mathbf{C}$ the requirements of
Section 3.3 and Section 2.4 are met as follows:

$\displaystyle[[U\overline{B}U^{-1},UAU^{-1}]]$
$\displaystyle=U[[\overline{B},A]]U^{-1};\text{ and}$ (125)
$\displaystyle(U\overline{B}U^{-1})U\mathcal{C}$
$\displaystyle=U\overline{B}\mathcal{C}=(U\mathcal{C})B.$ (126)

###  C.2 Eliminating Phase Components from Diagonal Stabiliser Generators

We now show how to find the vector $\mathbf{q}$ in Equation 123 which allow us
to eliminate signs from the diagonal stabiliser generators of the non-CSS code
$\mathbf{C}$ via conjugation by the operator
$Q:=XP_{2}(0|\mathbf{q}|\mathbf{0})$.

The canonical diagonal stabiliser generators $\mathbf{S}_{Z}$ are of form
$XP_{2}(2p_{i}|\mathbf{0}|\mathbf{z}_{i})$ where $p_{i}\in\mathbb{Z}_{2}$ and
$\mathbf{z}_{i}\in\mathbb{Z}_{2}^{n}$. Let $E_{s}$ be the binary matrix with
rows of form $(p_{i}|\mathbf{z}_{i})$ and let
$K_{s}:=\ker_{\mathbb{Z}_{2}}(E_{s})$. If $p_{i}=1$ for any $i$, the top row
of $K_{s}$ is of form $(1|\mathbf{q})$ and satisfies
$p_{i}+\mathbf{q}\cdot\mathbf{z}_{i}=0\operatorname{mod}2$ for all $i$. Now
let $Q:=XP_{2}(0|\mathbf{q}|\mathbf{0})$ then we also have
$QXP_{2}(2p_{i}|\mathbf{0}|\mathbf{z}_{i})Q=XP_{2}(2p_{i}+2\mathbf{q}\cdot\mathbf{z}_{i}|\mathbf{0}|\mathbf{z}_{i})=XP_{2}(0|\mathbf{0}|\mathbf{z}_{i})$.
Hence conjugation by $Q$ eliminates the phase components of the diagonal
stabiliser generators as required. As $Q$ is non-diagonal, the diagonal
logical operators and identities may update on conjugation by $Q$.

###  C.3 Eliminating Phase and $Z$-Components from Non-Diagonal Stabiliser
Generators

We now show how to find a diagonal level 2 Clifford operator $D$ from
Proposition C.1 which allows us to eliminate the phase and $Z$-components of
the non-diagonal stabilisers $\mathbf{S}_{X}$. Let $\lvert S\rangle$ be the
state stabilised by the set of $n$ independent operators
$\mathbf{S}_{X},\mathbf{S}_{Z}$ and $\mathbf{L}_{X}$. We can write $\lvert
S\rangle$ as follows:

$\displaystyle\lvert
S\rangle=\sum_{\mathbf{u}\in\mathbb{Z}_{2}^{r},\mathbf{v}\in\mathbb{Z}_{2}^{k}}\mathbf{S}_{X}^{\mathbf{u}}\mathbf{L}_{X}^{\mathbf{v}}\lvert\mathbf{q}\rangle=\sum_{\mathbf{v}}\lvert\mathbf{v}\rangle_{L}.$
(127)

Let $S_{X}$ and $L_{X}$ be the binary matrices formed from the X-components of
$\mathbf{S}_{X}$ and $\mathbf{L}_{X}$ respectively. Using the terminology of
Proposition 5.1 of Ref. [14], $\lvert S\rangle$ is an XP state of precision
$N=2$ and so is a weighted hypergraph state of form:

$\displaystyle\lvert
S\rangle=D\sum_{\mathbf{u,v}}\lvert\mathbf{u}S_{X}+\mathbf{v}L_{X}+\mathbf{q}\rangle=DQ\sum_{\mathbf{u,v}}\lvert\mathbf{u}S_{X}+\mathbf{v}L_{X}\rangle.$
(128)

The operator $D$ is a product of diagonal level 2 Clifford operators and can
calculated via the method in Algorithm 5.3.1 of Ref. [14]. Now let
$\mathbf{C}^{\prime}$ be the CSS code specified by the X-checks $S_{X}$ and
X-logicals $L_{X}$. Due to Section 2.3, codewords of $\mathbf{C}^{\prime}$ are
of form
$\lvert\mathbf{v}\rangle^{\prime}_{L}:=\sum_{\mathbf{u}}\lvert\mathbf{u}S_{X}+\mathbf{v}L_{X}\rangle$
and so the codewords of $\mathbf{C}$ can be written:

$\displaystyle\lvert\mathbf{v}\rangle_{L}=DQ\sum_{\mathbf{u}}\lvert\mathbf{u}S_{X}+\mathbf{v}L_{X}\rangle=DQ\lvert\mathbf{v}\rangle^{\prime}_{L}.$
(129)

Hence, $\mathbf{C}=DQ\mathbf{C}^{\prime}$ as required. Transforming a CSS code
$\mathbf{C}^{\prime}$ by the diagonal operator $D$ has no effect on the
diagonal stabiliser generators, logical identities or logical operators.
However, it can increase the weight of non-diagonal stabiliser generators and
logical X operators, and so increase the code distance.

######  Example C.1 (Perfect 5-Qubit Code)

Let $\mathbf{C}$ be the perfect 5-qubit code of [35] with stabiliser
generators and logical $X$ operator as follows:

$\displaystyle\mathbf{S}$ $\displaystyle:=\begin{pmatrix}XZZXI\\\ IXZZX\\\
XIXZZ\\\ ZXIXZ\end{pmatrix};$ $\displaystyle\overline{X}$
$\displaystyle:=ZIIZX$ (130)

. Let $\mathbf{C}^{\prime}$ be the CSS code with $X$-checks and $X$-logicals:

$\displaystyle S_{X}$ $\displaystyle:=\begin{pmatrix}10010\\\ 01001\\\
10100\\\ 01010\end{pmatrix};$ $\displaystyle L_{X}$
$\displaystyle:=\begin{pmatrix}00001\end{pmatrix}.$ (131)

We find that $D=CZ_{01}CZ_{12}CZ_{23}CZ_{01}CZ_{34}CZ_{40}$ satisfies
$\mathbf{C}=D\mathbf{C}^{\prime}$ using the conjugation rule
$CZ_{01}X_{0}CZ_{01}=X_{0}Z_{1}$. Whilst $\mathbf{C}$ has distance 3,
$\mathbf{C}^{\prime}$ has distance 1. In the linked Jupyter notebook, users
can use the above method to find $D,Q$ and $\mathbf{C}^{\prime}$ for various
non-CSS stabiliser codes from www.codetables.de.

## References

  * [1] Rajeev Acharya, Igor Aleiner, Richard Allen, et al.  Suppressing quantum errors by scaling a surface code logical qubit.  Nature, 614:676–681, Feb 2023.
  * [2] Ciarán Ryan-Anderson, Justin G. Bohnet, et al.  Realization of real-time fault-tolerant quantum error correction.  Phys. Rev. X, 11:041058, Dec 2021.
  * [3] Sebastian Krinner, Nathan Lacroix, Ants Remm, et al.  Realization of real-time fault-tolerant quantum error correction.  Nature, 605:669–674, May 2022.
  * [4] Robert Calderbank and Peter W. Shor.  Good quantum error-correcting codes exist.  Phys. Rev. A, 54:1098–1105, Aug 1996.
  * [5] Bryan Eastin and Emanuel Knill.  Restrictions on transversal encoded quantum gate sets.  Phys. Rev. Lett., 102:110502, Mar 2009.
  * [6] Daniel Gottesman and Isaac L. Chuang.  Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations.  Nature, 402:390–393, Nov 1999.
  * [7] Gabriele Nebe, E. M. Rains, and N. J. A. Sloane.  The invariants of the clifford groups.  Designs, Codes and Cryptography, 24:99–122, Sep 2001.
  * [8] Andrew M. Steane.  Error correcting codes in quantum theory.  Phys. Rev. Lett., 77:793–797, Jul 1996.
  * [9] Hector Bombin and Miguel A. Martin-Delgado.  Topological quantum distillation.  Phys. Rev. Lett., 97:180501, Oct 2006.