# Sequentially Encodable Codeword Stabilized Codes

Sowrabh Sudevan and Sourin Das  Indian Institute of Science Education and
Research, Kolkata
West Bengal, India
Email: {ss18ip003<EMAIL_ADDRESS>Thamadathil Aswanth and Navin
Kashyap  Indian Institute of Science, Bengaluru
Karnataka, India
Email: {aswantht<EMAIL_ADDRESS>
###### Abstract

An $m$-uniform quantum state on $n$ qubits is an entangled state in which
every $m$-qubit subsystem is maximally mixed. Such a state spans a pure
$[[n,0,m+1]]$ quantum error correcting code (QECC). Starting with an
$m$-uniform state realized as the graph state associated with an $m$-regular
graph, and a classical $[n,k,d\geq m+1]$ binary linear code with certain
additional properties, we construct codeword stabilized (CWS) codes that are
pure $[[n,k,m+1]]$ QECCs. We propose measurement-based protocols for encoding
into code states and for recovery of logical qubits from code states. Our
proposed protocols support sequential encoding and partial recovery of logical
qubits, which can be useful for quantum memory applications.

##  I Introduction

A quantum computer exploits the properties of quantum mechanics to do
computations and outperforms classical computers in solving certain
problems[1]. Any realistic physical realization of a quantum computer must
account for noise [2, 3, 4, 5]. In quantum computing, errors or noise can be
modeled as some extra, unknown unitaries stochastically introduced into the
intended quantum circuit [6]. Much like for classical information, the effects
of noise on quantum memories can be dealt with through error correction
procedures, the first of which was designed by Shor [7]. The theory of
stabilizer codes, developed by Gottesman [8], provided a general algebraic
framework for constructing quantum error correcting codes (QECCs). Codes
constructed via the stabilizer formalism are generally referred to as
“additive” codes. Following the development of stabilizer codes, much progress
has been made in quantum error correction, and finding new QECCs has been an
active area of research [9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21].
Furthermore, different methods to construct non-additive quantum codes have
been proposed (see [22]); examples of such codes include union stabilizer
codes [23, 24] and codeword stabilized (CWS) codes [25, 26].

In this paper, we propose a construction of CWS codes with a guaranteed
desired minimum distance, along with a measurement-based sequential encoding
procedure, which may be useful for quantum memory applications. Our code
construction utilizes classical error-correcting codes in a novel way. The
initial quantum resource for our construction is an $m$-uniform quantum state,
which is a multipartite entangled state within which any $m$-qubit subsystem
is maximally mixed [27]. Thus, such states span pure QECCs of dimension one
and minimum distance $m+1$ [28, 29]. Since these are one-dimensional QECCs,
they cannot by themselves store any logical information. However, in the
construction of CWS codes [25], such states can be used as a starting point
for constructing QECCs that can encode a positive number of logical qubits.

Any $m$-uniform state can be realized within a subclass of stabilizer states
called graph states. Sudevan et al. [30] showed that the graph state
associated with a $D$-dimensional regular lattice with periodic boundary
conditions is $2D$-uniform. Hence, such a graph state (also called a cluster
state) is a pure $[[n,0,2D+1]]$ QECC. Sudevan et al. also proposed a method
for constructing $2$-dimensional QECCs using cluster states, that can be
encoded in a measurement-based approach. We extend this idea to higher-
dimensional codes that can encode multiple logical qubits by making
connections to classical binary linear codes.

In a CWS code, the basis of the code space is formed by the states resulting
from the action of strings of Pauli-$Z$ operators on a graph state. Although
CWS codes are non-additive in general, our specific interest is in additive
CWS codes since they can be encoded in the proposed measurement-based
approach. Any additive CWS code can be identified with a classical binary
linear code that we call the tent peg code. The name tent peg is motivated by
the controlled-$Z$ gates in the encoding circuit that appear like lines of
tents (see Figure 2). We provide two conditions on the tent peg code to get
good QECCs, which are presented in Theorems 1 and 2. Theorem 3 uses a binary
cyclic code as the tent peg code to obtain a distance-3 QECC.

The proposed encoding procedure uses some ideas from measurement-based quantum
computing (MBQC) [31, 32]. MBQC started with the idea of a one-way quantum
computer, proposed by Raussendorf et al. [33], who showed that any quantum
operation can be realized through single qubit measurements on a cluster
state. The key idea we borrow from MBQC is a method called one-bit
teleportation [34]. Our encoding procedure teleports information from ancilla
qubits with arbitrary quantum information to some CWS code space using a
combination of controlled-$Z$ gates and $X$ measurements. In this procedure,
one can encode the logical qubits sequentially. When a subset of the logical
qubits is provided, the encoder maps them into a subcode (subspace) of the
full code space. This code state is transformed into a state of the full code
when the remaining qubits are encoded. This property requires the logical
qubits initially encoded to be unentangled with the remaining qubits. Partial
recovery of logical qubits is also possible: the initial subset of logical
qubits can be recovered from the final encoded state, leaving the remaining
logical qubits still encoded. This type of sequential encoding and recovery of
logical qubits may be desirable for quantum memory applications.

The next section introduces the basic definitions and notation used in this
paper. Section III presents our main results, including an explicit
construction of a family of quantum codes obtained from $2$-uniform quantum
states. The measurement-based protocols for encoding and recovery of logical
qubits are discussed in Section IV. The energy cost of encoding is discussed
in Section V. The appendix contains proofs of two theorems.

##  II Preliminaries

Throughout this paper, for a positive integer $n$, we set
$[n]:=\\{1,2,\ldots,n\\}$, and for integers $m\leq n$,
$[m:n]:=\\{m,m+1,\ldots,n\\}$. The _support_ of a binary vector
$\mathbf{x}=[x_{1},x_{2},\ldots,x_{n}]\in\\{0,1\\}^{n}$ is defined as
$\text{supp}(\mathbf{x}):=\\{i:x_{i}=1\\}$. The _characteristic vector_ of a
subset $A\subseteq[n]$ is the binary vector $\mathbf{a}\in\\{0,1\\}^{n}$ such
that $A=\text{supp}(\mathbf{a})$.

$\mathcal{P}_{n}$ denotes the Pauli group on $n$ qubits, and $X_{i}$ and
$Z_{i}$ respectively denote the Pauli-$X$ and Pauli-$Z$ operators acting on
$i^{th}$ qubit according to some index. A tensor product of Pauli-$Z$
operators is specified via a binary vector: for
$\mathbf{x}=[x_{1},x_{2},\ldots,x_{n}]\in{\\{0,1\\}}^{n}$, we use
$Z_{\mathbf{x}}$ to denote the Pauli string $\prod_{j=1}^{n}{Z_{j}^{x_{j}}}$.
Alternatively, for a subset of qubits $A\subseteq[n]$, we use $Z_{A}$ to
denote $\prod_{j\in A}Z_{j}$. Note that $Z_{A}=Z_{\mathbf{x}}$ if and only if
$\mathbf{x}=[x_{1},x_{2},\ldots,x_{n}]$ is the characteristic vector of $A$.
Analogous notation is used for tensor products of Pauli-X operators as well,
whenever needed.

For a Pauli operator $M$ of the form (ignoring the global phase factor)
$\sigma^{(1)}\otimes\sigma^{(2)}\otimes\ldots\otimes\sigma^{(n)}$, with
$\sigma^{(j)}\in\\{X,Y,Z,I\\}\hskip 5.0pt\forall j\in[n]$, we denote its
weight by $\mathrm{wt}(M)=|\\{i:\sigma^{(i)}\neq I\\}|$.

An $[n,k,d]$ binary linear code has length $n$, dimension $k$, and minimum
distance $d$. Similarly, an $[[n,k,d]]$ QECC bijectively maps the state of $k$
logical qubits to a subspace of the Hilbert space of $n$ physical qubits, and
has a minimum distance $d$. Following [29], we define a _pure_ $[[n,k,d]]$
quantum code to be a $2^{k}$-dimensional subspace, $\mathcal{Q}$, of
${(\mathbb{C}^{2})}^{\otimes n}$ such that for all Pauli operators
$E\in\mathcal{P}_{n}$ of weight strictly between $0$ and $d$, we have
$\braket{\psi}{E}{\psi}=0$ for all $\ket{\psi}\in\mathcal{Q}$.

######  Definition 1.

Consider a set of $n$ qubits and an undirected, simple graph $G$ on the vertex
set $[n]$. The graph state $\ket{\mathrm{G}}$ associated with $G$ is the
simultaneous $+1$ eigenstate of the stabilizers generated by
$\\{S_{i}:=X_{i}Z_{N(i)}:i\in[n]\\}$, where $N(i)$ is the set of neighbours of
vertex $i$ in the graph $G$.

Throughout this paper, we will use $S_{i}$ to denote the stabilizer generator
associated with the vertex $i$.

In the literature, we find the terms graph states and cluster states being
used interchangeably. In this work, we use _graph states_ to denote states
associated with arbitrary undirected simple graphs, and _cluster states_ for
graph states associated with regular lattices. Of particular significance to
our work are cluster states obtained from $D$-dimensional rectangular lattices
with periodic boundary conditions. For positive integers
$D,n_{1},n_{2},\ldots,n_{D}$, let $\Lambda_{n_{1},n_{2},\ldots,n_{D}}$ denote
the $D$-dimensional rectangular lattice with periodic boundary conditions and
side lengths $n_{1},n_{2},\ldots,n_{D}$. Mathematically, this is the
(undirected) graph on the vertex set
$[0:n_{1}-1]\times[0:n_{2}-1]\times\cdots\times[0:n_{D}-1]$, with an edge
drawn between vertices $\mathbf{x}=(x_{1},x_{2},\ldots,x_{D})$ and
$\mathbf{y}=(y_{1},y_{2},\ldots,y_{D})$ iff the Lee distance

$d_{L}(\mathbf{x},\mathbf{y}):=\sum_{i=1}^{D}\min(|x_{i}-y_{i}|,n_{i}-|x_{i}-y_{i}|)$

between $\mathbf{x}$ and $\mathbf{y}$ equals $1$.

In general, graph states can be highly entangled. The type of multipartite
entanglement that is relevant to us is $m$-uniformity.

######  Definition 2.

A quantum state $\ket{\psi}$ is said to be $m$-uniform if all possible
$m$-qubit marginals are maximally mixed. Further, a quantum code is said to be
$m$-uniform when every state it contains is $m$-uniform.

An equivalent characterization of an $m$-uniform state is as follows: An
$n$-qubit quantum state $\ket{\psi}$ is $m$-uniform iff
$\bra{\psi}\mathcal{O}\ket{\psi}=0$ for all non-identity operators
$\mathcal{O}\in\mathcal{P}_{n}$ with weight at most $m$ [27]. Expressed in the
language of quantum codes, an $m$-uniform state $\ket{\psi}$ spans a pure
$[[n,0,m+1]]$ QECC.

The following useful result, shown by Sudevan et al. [30, Appendix C],
demonstrates that cluster states associated with sufficiently large
rectangular lattices have the kind of multipartite entanglement we seek.

######  Proposition 1.

The cluster state associated with the $D$-dimensional rectangular lattice
$\Lambda_{n_{1},n_{2},\ldots,n_{D}}$ is $2D$-uniform when $n_{i}\geq 8$ for
all $i$.

Next, we state a simple necessary condition for a graph state to be
$m$-uniform.

######  Proposition 2.

If the graph state $\ket{\mathrm{G}}$ associated with a graph $G$ is
$m$-uniform, then every vertex of $G$ has degree at least $m$.

###### Proof.

For an $m$-uniform graph state $\ket{\mathrm{G}}$, every element of the
stabilizer group $\mathcal{S}$ must have symplectic weight at least $m+1$.
(This follows from the above characterization of $m$-uniformity, since for any
stabilizer $S$ of $\ket{\mathrm{G}}$, we have
$\braket{\mathrm{G}}{S}{\mathrm{G}}=\braket{\mathrm{G}}{\mathrm{G}}=1\neq 0$.)
Now, the stabilizer generators $S_{i}\in\mathcal{S}$ are of the form
$X_{i}Z_{N(i)}$. Since the symplectic weight of $S_{i}$ is at least $m+1$, we
must have $|N(i)|\geq m$, i.e., the degree of an vertex $i$ is at least $m$. ∎

In the sequel, we will sometimes find it convenient to use the symplectic
notation for Pauli operators, where a Pauli operator $M\in\mathcal{P}_{n}$ is
uniquely identified, up to a global phase factor, with a binary vector of the
form $\mathbf{v}=[\mathbf{v}^{(1)}|\mathbf{v}^{(2)}]$, with
$\mathbf{v}^{(1)},\mathbf{v}^{(2)}\in\\{0,1\\}^{n}$:

$M=(\text{global phase factor})\cdot X_{\mathbf{v}^{(1)}}\cdot
Z_{\mathbf{v}^{(2)}}.$

In this representation, the multiplication of operators is equivalent, up to a
global phase, to the coordinatewise modulo-$2$ addition of the corresponding
binary vectors. When using this representation, another important quantity is
the symplectic weight of $\mathbf{v}=[\mathbf{v}^{(1)}|\mathbf{v}^{(2)}]$,
defined as

$\mathrm{wt}_{\mathrm{s}}(\mathbf{v})=|\\{j:(v^{(1)}_{j},v^{(2)}_{j})\neq(0,0)\\}|,$

where $\mathbf{v}^{(1)}=[v^{(1)}_{1},v^{(1)}_{2},\ldots,v^{(1)}_{n}]$ and
$\mathbf{v}^{(2)}=[v^{(2)}_{1},v^{(2)}_{2},\ldots,v^{(2)}_{n}]$. This is equal
to the weight of the Pauli operator corresponding to $\mathbf{v}$.

##  III Main Results

Starting from a graph state, we generate one-dimensional orthogonal subspaces
of the Hilbert space through Pauli-$Z$ operations, which can be combined to
obtain a higher-dimensional subspace referred to as a CWS code [25]. This is
formally stated in the lemma below.

######  Lemma 1.

Consider an $n$-qubit graph state, $\ket{\mathrm{G}}$, whose stabilizers are
constructed from a graph $G$. Let $\mathcal{C}$ be a binary linear code of
length $n$ and dimension $k$. Then,
$\text{span}\bigl{(}\\{Z_{\mathbf{c}}\ket{\mathrm{G}}:\mathbf{c}\in\mathcal{C}\\}\bigr{)}$
forms a $2^{k}$-dimensional QECC.

###### Proof.

For codewords $\mathbf{c}_{1},\mathbf{c}_{2}\in\mathcal{C}$ such that
$\mathbf{c}=\mathbf{c}_{1}+\mathbf{c}_{2}\neq\mathbf{0}$,

$\begin{split}\bra{\mathrm{G}}Z_{\mathbf{c}_{1}}^{\dagger}Z_{\mathbf{c}_{2}}\ket{\mathrm{G}}&=\bra{\mathrm{G}}Z_{\mathbf{c}}\ket{\mathrm{G}}\\\
&=0.\end{split}$

The second equality follows because the centralizer is identical to the
stabilizer of $\ket{\mathrm{G}}$ and contains no non-identity operator
consisting only of Pauli-$Z$s. Hence, the $2^{k}$ distinct states of the form
$Z_{\mathbf{c}}\ket{\mathrm{G}}$ form the basis of a $2^{k}$-dimensional QECC.
∎

Owing to the encoding procedure, which is discussed in Section IV, the binary
linear code $\mathcal{C}$ used to construct the QECC is hereafter referred to
as the tent peg code (see Figure 2). The QECC is completely characterized by
the tent peg code $\mathcal{C}$, and it needs to be chosen wisely to obtain a
good QECC.

We use the symplectic binary vector representation of Pauli operators to give
a necessary and sufficient condition for the CWS code to have a minimum
distance of $m+1$, given that $\ket{\mathrm{G}}$ is $m$-uniform.

######  Theorem 1.

Let $\mathcal{S}$ denote the stabilizer group corresponding to an $m$-uniform
graph state $\ket{\mathrm{G}}$, and let $\mathcal{V}_{\mathcal{S}}$ be the
corresponding binary vector space in the symplectic representation. Let
$\mathcal{C}$ be a binary linear code of length $n$ and dimension $k$, and
consider its length-$2n$ extension $\mathcal{C}^{\prime}:=\\{[0,0,\ldots,0\ |\
\mathbf{c}]:\mathbf{c}\in\mathcal{C}\\}$. Define
$\mathcal{W}:=\mathcal{V}_{\mathcal{S}}+\mathcal{C}^{\prime}=\\{\mathbf{v}+\mathbf{c}^{\prime}:\mathbf{v}\in\mathcal{V}_{\mathcal{S}}\text{
and }\mathbf{c}^{\prime}\in\mathcal{C}^{\prime}\\}$. Then,
$\mathcal{Q}:=\text{span}\bigl{(}\\{Z_{\mathbf{c}}\ket{\mathrm{G}}:\mathbf{c}\in\mathcal{C}\\}\bigr{)}$
is a pure $[[n,k,m+1]]$ QECC if and only if the minimum symplectic weight of a
non-zero vector in $\mathcal{W}$ is at least $m+1$.

###### Proof.

Suppose that there is no operator of symplectic weight at most $m$ in
$\mathcal{W}$. Then, for any $E\in\mathcal{P}_{n}$ of weight at most $m$, we
must have $Z_{\mathbf{c}}E\notin\mathcal{S}$ for all
$\mathbf{c}\in\mathcal{C}$. This implies

$\bra{\mathrm{G}}Z_{\mathbf{c}}E\ket{\mathrm{G}}=0\hskip
14.22636pt\forall\mathbf{c}\in\mathcal{C},$ (1)

and consequently,

$\bra{\mathrm{G}}Z_{\mathbf{c}_{1}}^{\dagger}EZ_{\mathbf{c}_{2}}\ket{\mathrm{G}}=0\hskip
14.22636pt\forall\mathbf{c}_{1},\mathbf{c}_{2}\in\mathcal{C}.$ (2)

Therefore,
$\mathcal{Q}:=\text{span}\\{Z_{\mathbf{c}}\ket{\mathrm{G}}:\mathbf{c}\in\mathcal{C}\\}$
is a pure $[[n,k,m+1]]$ QECC.

Conversely, if $\mathcal{Q}$ is a pure $[[n,k,m+1]]$ QECC, then for any
$E\in\mathcal{P}_{n}$ of weight at most $m$, Eq. (2) must hold. This implies
that Eq. (1) also holds, from which it follows that the minimum weight of an
operator in $\mathcal{W}$ is at least $m+1$. ∎

Given $n$ and $m$, one can ask what the maximum dimension is of a QECC that
can be constructed in this way. However, this is not easy to compute. Consider
a set, $\mathcal{B}(\mathcal{S})$, of all vectors within a symplectic distance
of $m$ from $\mathcal{V}_{\mathcal{S}}$. Let $\mathcal{V}_{X}$ denote the
binary vectors corresponding to the Pauli operators containing at least one
$X$. In order to get the tent peg code that maximizes the dimension of the
resulting QECC, we need to find the largest subspace of $\mathbb{F}_{2}^{2n}$
that has no intersection with $\mathcal{B}(\mathcal{S})\cup\mathcal{V}_{X}$
except $\mathbf{0}$. This problem reduces to the 4-colorability problem, which
is known to be NP-hard [35]. So, instead of trying to find the QECC of largest
dimension that can be constructed in this way, we aim to identify some simple
conditions on the linear code $\mathcal{C}$ that will result in QECCs of
reasonably large dimension.

Construction of higher-dimensional code spaces, as noted in Lemma 1, only
requires $\ket{\mathrm{G}}$ to be an $n$-qubit graph state. Theorem 1 further
requires that $\ket{\mathrm{G}}$ be an $m$-uniform state and therefore a
nondegenerate QECC of minimum distance $m+1$. As we saw in Proposition 2,
$m$-uniformity of a graph state implies that the degree of every vertex in $G$
is at least $m$. If we further insist that the $m$-uniform graph state
$\ket{\mathrm{G}}$ arises from a graph $G$ in which every vertex has degree
equal to $m$ (i.e., an $m$-regular graph), then we obtain a construction that
meets the requirement of Theorem 1.

######  Theorem 2.

Let $\ket{\mathrm{G}}$ be an $m$-uniform state constructed from an $m$-regular
graph. Then, for any $[n,k,d]$ binary linear code $\mathcal{C}$ with
$d>m(m+1)$, the quantum code
$\mathcal{Q}:=\text{span}\bigl{(}\\{Z_{\mathbf{c}}\ket{\mathrm{G}}:\mathbf{c}\in\mathcal{C}\\}\bigr{)}$
is a pure $[[n,k,m+1]]$ QECC.

###### Proof.

The idea is to show that in the vector space $\mathcal{W}$ defined in the
statement of Theorem 1, there are no non-zero vectors of symplectic weight at
most $m$, so that we can draw the desired conclusion from Theorem 1. We will
show the equivalent statement that for any $E\in\mathcal{P}_{n}$ of weight at
most $m$, the operator $Z_{\mathbf{c}}E$ is not a stabilizer of
$\ket{\mathrm{G}}$, for all $\mathbf{c}\in\mathcal{C}$. To this end, consider
any $E\in\mathcal{P}_{n}$ of weight at most $m$. Note first that $E$ itself
cannot be a stabilizer of $\ket{\mathrm{G}}$, since by the characterization of
$m$-uniformity given after Definition 2, we have
$\braket{\mathrm{G}}{E}{\mathrm{G}}=0$.

Now, consider $E^{\prime}=Z_{\mathbf{c}}E$, for some
$\mathbf{c}\in\mathcal{C}$, $\mathbf{c}\neq\mathbf{0}$. Since $\mathbf{c}$ has
Hamming weight strictly greater than $m(m+1)$ and the weight of $E$ is at most
$m$, the number of $Z$s in $E^{\prime}$ must be strictly greater than $m^{2}$.
On the other hand, the number of $X$s in $E^{\prime}$ is at most $m$, since
all of these have to be contributed by $E$. Suppose that $E^{\prime}$ were in
fact a stabilizer of $\ket{\mathrm{G}}$. Then, it is a product of stabilizer
generators of the form $S_{i}=X_{i}Z_{N(i)}$. Since the number of $X$s in
$E^{\prime}$ is at most $m$, $E^{\prime}$ is a product of at most $m$
generators $S_{i}$. Moreover, each such generator contributes at most $N(i)=m$
$Z$s to $E^{\prime}$. So, the total number of $Z$s in $E^{\prime}$ cannot
exceed $m\times m=m^{2}$, which contradicts the lower bound derived earlier
for the number of $Z$s in $E^{\prime}$. Hence, $Z_{\mathbf{c}}E$ cannot be a
stabilizer of $\ket{\mathrm{G}}$, which proves the theorem. ∎

Since Proposition 1 gives us a concrete construction of a graph state that
satisfies the requirement of the above theorem, we have the following
corollary.

######  Corollary 1.

Let $\ket{\mathrm{G}}$ be the cluster state associated with the
$D$-dimensional rectangular lattice $\Lambda_{n_{1},n_{2},\ldots,n_{D}}$, with
$n_{i}\geq 8$ for all $i$. Then, for any $[n,k,d]$ binary linear code
$\mathcal{C}$ with $d>2D(2D+1)$, the quantum code
$\mathcal{Q}:=\text{span}\bigl{(}\\{Z_{\mathbf{c}}\ket{\mathrm{G}}:\mathbf{c}\in\mathcal{C}\\}\bigr{)}$
is a pure $[[n,k,2D+1]]$ QECC.

The lower bound of $m(m+1)$ on the minimum distance of the linear code
$\mathcal{C}$ in Theorem 2 is a sufficient, but not necessary, condition for
the conclusion of the theorem to hold. Indeed, Theorem 1 shows that only a
weaker lower bound of $m+1$ is necessary (note that the minimum distance of
$\mathcal{C}$ bounds from above the minimum symplectic weight of a non-zero
vector in $\mathcal{W}$). It would thus be useful to try to find linear codes
$\mathcal{C}$ with minimum distance that is of the order of $m$ rather than of
the order of $m^{2}$, from which we can still obtain the same conclusion as in
Theorem 2. Linear codes with a less stringent requirement on minimum distance
will have larger dimension $k$, which directly translates to a larger
dimension for the resulting QECCs.

Given an $m$-uniform graph state $\ket{\mathrm{G}}$, to weaken the minimum
distance requirement on the tent peg code $\mathcal{C}$, we need to
incorporate the condition on $\mathcal{W}$ in Theorem 1 into the design of the
tent peg code. While this seems difficult to do for arbitrary $m$-uniform
graph states, we show how this strategy can be successfully implemented for
the cluster state obtained from the one-dimensional lattice $\Lambda_{n}$.
Note that, in this case, Corollary 1 requires a minimum distance of $d>6$ for
the tent peg code.

Consider the cluster state on $n$ qubits associated with the one-dimensional
lattice $\Lambda_{n}$. It can be verified that such a cluster state is
$2$-uniform for $n\geq 5$. Using Theorem 1 applied to $2$-uniform states, we
want to construct a tent peg code $\mathcal{C}$ of length $n$ such that
$\mathcal{W}$ does not contain a nonzero vector of symplectic weight up to 2.
Equivalently, we should not be able to get a stabilizer element of
$\mathcal{V}_{\mathcal{S}}$ from a codeword
$\mathbf{c}^{\prime}\in\mathcal{C}^{\prime}$ by adding a binary vector of
symplectic weight up to 2. This demands the tent peg code to have a minimum
distance of at least 3 and to not contain codewords of the following form:

$\displaystyle\text{\rule[2.5pt]{28.45274pt}{0.5pt}}\,1\ast\ast\,1\,\text{\rule[2.5pt]{28.45274pt}{0.5pt}}$
(3) $\displaystyle\text{\rule[2.5pt]{28.45274pt}{0.5pt}}\,1\ast 0\ast
1\,\text{\rule[2.5pt]{28.45274pt}{0.5pt}}$ (4)
$\displaystyle\text{\rule[2.5pt]{28.45274pt}{0.5pt}}\,1\ast
1\,\text{\rule[2.5pt]{28.45274pt}{0.5pt}}\,1\ast
1\,\text{\rule[2.5pt]{28.45274pt}{0.5pt}}$ (5)
$\displaystyle\text{\rule[2.5pt]{28.45274pt}{0.5pt}}\,1\ast
1\,\text{\rule[2.5pt]{28.45274pt}{0.5pt}}\,\ast\,\text{\rule[2.5pt]{28.45274pt}{0.5pt}}$
(6)

Here, each ‘ ’ represents a run of 0s, possibly empty, and each $\ast$ can be
a $0$ or a $1$. Also, cyclic shifts of such codewords are not allowed, i.e.,
the coordinates of these codewords are assumed to lie on a circle. We give a
construction of a tent peg code satisfying the above conditions.

Let $r\geq 2$ be an integer. Set $n=2^{2r}-1$, and $b=(2^{2r}-1)/3$. Consider
the binary code $\mathcal{C}_{r}$ with parity-check matrix

$H=\begin{bmatrix}1&\alpha&\alpha^{2}&\alpha^{3}&\cdots&\alpha^{n-1}\\\
1&\alpha^{b}&{(\alpha^{b})}^{2}&{(\alpha^{b})}^{3}&\cdots&{(\alpha^{b})}^{n-1}\end{bmatrix}$
(7)

where $\alpha$ is a primitive element in $\mathbb{F}_{2^{2r}}$. By choice of
$b$, the second row of the $H$ matrix above is simply

$[1\ \ \ \alpha^{b}\ \ \ \alpha^{2b}\ \ \ 1\ \ \ \alpha^{b}\ \ \ \alpha^{2b}\
\ \ \cdots\ \ \ 1\ \ \ \alpha^{b}\ \ \ \alpha^{2b}]$

We also have $1+\alpha^{b}+\alpha^{2b}=\frac{\alpha^{3b}-1}{\alpha^{b}-1}=0$,
so $\alpha^{b}$ has $x^{2}+x+1$ as its minimal polynomial over
$\mathbb{F}_{2}$.

The code $\mathcal{C}_{r}$ is the cyclic code generated by
$g(x)=M_{\alpha}(x)M_{\alpha^{b}}(x)$, where $M_{\alpha}(x)$ and
$M_{\alpha^{b}}(x)$ are the minimal polynomials over $\mathbb{F}_{2}$ of
$\alpha$ and $\alpha^{b}$, respectively. Thus, $\deg g(x)=2r+2$, so that

$\begin{split}\dim(\mathcal{C}_{r})&=n-\deg g(x)\\\ &=2^{2r}-2r-3.\end{split}$

Moreover, $d_{\min}(\mathcal{C}_{r})\geq 3$, as the row of the $H$ matrix
consists of distinct and nonzero elements of $\mathbb{F}_{2^{2r}}$.

######  Remark 1.

Note that $b=(4^{r}-1)/3=\sum_{i=0}^{r-1}4^{i}\equiv r\pmod{3}$, since
$4^{i}\equiv 1\pmod{3}$. So, if we assume that $r$ is not a multiple of $3$,
we get $b\equiv 1\text{ or }2\pmod{3}$. In this case, we obtain that

$\mathbf{c}=(1,\underbrace{0,\ldots,0}_{b-1\,0\text{s}},1,\underbrace{0,\ldots,0}_{b-1\,0\text{s}},1,\underbrace{0,\ldots,0}_{b-1\,0\text{s}})$

is a codeword of $\mathcal{C}_{r}$, since we have

$\begin{split}H\mathbf{c}^{T}&=[1+\alpha^{b}+\alpha^{2b},\ \
1+({\alpha^{b}})^{b}+({\alpha^{b}})^{2b}]^{T}\\\ &=[0\ \ 0]^{T}.\end{split}$

Indeed, the fact that $b\equiv 1\text{ or }2\pmod{3}$ implies that
$\\{({\alpha^{b}})^{b},({\alpha^{b}})^{2b}\\}=\\{\alpha^{b},\alpha^{2b}\\}$,
so that $1+({\alpha^{b}})^{b}+({\alpha^{b}})^{2b}=0$. Thus, $\mathcal{C}_{r}$
contains a codeword of weight equal to $3$, which proves that
$d_{\min}(\mathcal{C}_{r})=3$ whenever $r$ is not a multiple of $3$.

The main result here is the theorem stated next. In the statement of the
theorem, $\operatorname{Log}$ stands for the discrete logarithm in the field
$\mathbb{F}_{2^{2r}}$ with respect to a fixed primitive element $\alpha$:
$\operatorname{Log}(\beta)=\ell\ \Longleftrightarrow\ \beta=\alpha^{\ell}$.

######  Theorem 3.

Let $\ket{\mathrm{G}}$ be the cluster state associated with the
$1$-dimensional rectangular lattice $\Lambda_{n}$, with $n\geq 5$. Suppose
that the primitive element $\alpha$ of $\mathbb{F}_{2^{2r}}$ chosen to
construct the $H$ matrix in (7) has the property that
$\operatorname{Log}(1+\alpha)\not\equiv 2\pmod{3}$. Then, for the binary
cyclic code $\mathcal{C}_{r}$ obtained as above, the quantum code
$\mathcal{Q}:=\text{span}\bigl{(}\\{Z_{\mathbf{c}}\ket{\mathrm{G}}:\mathbf{c}\in\mathcal{C}_{r}\\}\bigr{)}$
is a pure $[[2^{2r}-1,2^{2r}-2r-3,3]]$ QECC.

A proof of this theorem is given in Appendix A. For the construction in the
theorem to work, we need a primitive element $\alpha$ in $\mathbb{F}_{2^{2r}}$
satisfying $\operatorname{Log}(1+\alpha)\neq 2\pmod{3}$. Using the
computational algebra system Magma [36], we were able to verify the existence
of such a primitive element in $\mathbb{F}_{2^{2r}}$, for all values of $r$
between $2$ and $100$ (both inclusive). We conjecture that such a primitive
element exists for any $r$, but have been unable to find a proof. We leave the
resolution of this conjecture, formally stated below, as an open problem.

######  Conjecture 1.

For any integer $r\geq 2$, there exists a primitive element
$\alpha\in\mathbb{F}_{2^{2r}}$ such that
$\operatorname{Log}(1+\alpha)\not\equiv 2\pmod{3}$.

All QECCs constructed in this work, including the one in Theorem 3, are
nondegenerate codes, hence need to respect the quantum Hamming bound [37,
Section 10.3.4]:

$Q:=\frac{\sum_{i=0}^{\lfloor(d-1)/2\rfloor}\binom{n}{i}3^{i}}{2^{n-k}}\leq 1$

For the codes constructed from our Theorem 3, as $r\rightarrow\infty$,
$Q\rightarrow 3/4$ and code rate, $k/n\rightarrow 1$.

The constructions we have presented in this section are all additive CWS
codes. Such codes have a structure that enables us to encode them in a
measurement-based approach. The next section discusses the encoding procedure
and its other practical aspects.

##  IV Measurement-Based Encoding and Recovery Protocols

In this section, we explain our tent peg protocols for encoding and recovery
of logical information for additive CWS codes. Sections IV-A and IV-B explain
the encoding protocol, which uses $n$ physical qubits that are initially in a
graph state $\ket{\mathrm{G}}$. Sections IV-C and IV-D explain the protocol
for recovering the logical qubits from the encoded state.

###  IV-A Encoding

Figure 1: Encoding one logical qubit. The top qubit represents the ancilla
containing the information to be encoded, and the bottom ancillas belong to a
graph state. Each solid line represents a controlled-$Z$ gate between those
two qubits.

For clarity, we first revisit the protocol for encoding a single qubit [30]
into a $2$-dimensional CWS code
$\text{span}\\{\ket{\mathrm{G}},Z_{A}\ket{\mathrm{G}}\\}$. As shown in Figure
1, we have $n$ physical qubits, referred to hereafter as target qubits,
prepared in the graph state $\ket{\mathrm{G}}$, and an ancilla qubit in the
state $\alpha\ket{0}+\beta\ket{1}$, which needs to be encoded. We use the
ancilla as the control qubit of a set of controlled-$Z$ ($CZ$) gates that act
on a subset $A$ of the target qubits. These $CZ$ gates bring the joint state
of the system into the form given below:

$\displaystyle\prod_{i\in
A}CZ_{i}\big{(}\alpha\ket{0}+\beta\ket{1}\big{)}\ket{\mathrm{G}}=\ket{+}\ket{\mathrm{e}_{+}}+\ket{-}\ket{\mathrm{e}_{-}},$

where $CZ_{i}$ is a $CZ$ gate acting on the $i^{th}$ target qubit, and
$\ket{\mathrm{e}_{\pm}}=\alpha\ket{\mathrm{G}}\pm\beta Z_{A}\ket{\mathrm{G}}$.
Applying a projective measurement on the ancilla qubit in the $X$-basis
transforms the target qubits to either the desired encoding
$\ket{\mathrm{e}}=\ket{\mathrm{e}_{+}}$ or a different state
$\ket{\mathrm{e}_{-}}$ depending on the measurement outcome. It is easy to see
that $\ket{\mathrm{e}_{-}}$ can be transformed to $\ket{\mathrm{e}}$ by
performing a logical-$Z$ operation. Note that the graph stabilizer generator,
$S_{i}$, corresponding to any qubit $i\in A$, anti-commutes with $Z_{A}$.
Therefore, $S_{i}\ket{\mathrm{e}_{-}}=\ket{\mathrm{e}}$, and hence, $S_{i}$ is
a logical-$Z$ operator for the code. Since the stabilizers
$S_{i}\in\mathcal{P}_{n}$ consist of tensor products over local unitaries,
they are not difficult to implement.

This measurement-based approach can be generalized to construct higher-
dimensional codes following the visual guide in Figure 2. We again start with
$n$ physical qubits, indexed by $[n]$, that are jointly in a graph state
$\ket{\mathrm{G}}$. But we now have $k$ ancilla qubits (shown at the top of
the figure), with the $i$-th ancilla qubit controlling $CZ$ gates that act on
a subset $A_{i}\subseteq[n]$ of the $n$ physical qubits, which we will again
refer to as target qubits. The figure motivates the “tent peg” nomenclature we
use for the encoding protocol, as the figure brings to mind a row of tents
whose tops are the ancillas and whose pegs are the target qubits with which
the ancillas interact. It should be clarified, however, that the “tent peg
sets” $A_{i}$ need not be disjoint.

Figure 2: Tent peg protocol: The top horizontal array of dots represents $k$
ancilla qubits holding logical information. The bottom horizontal array of
dots represents the $n$ target qubits, initially in a graph state. Each solid
line between a pair of qubits represents a controlled-$Z$ gate between the two
qubits.

The choice of the tent peg sets $A_{i}$ is governed by an $[n,k]$ binary
linear code $\mathcal{C}$, which we refer to as the “tent peg code”. Let
$\mathbf{A}$ be a $k\times n$ generator matrix for $\mathcal{C}$, which,
without loss of generality, we will assume to be in systematic form. Thus,
$\mathbf{A}=[\mathbf{I}\mid\mathbf{B}]$, where $\mathbf{I}$ is the $k\times k$
identity matrix and $\mathbf{B}$ is a binary $k\times(n-k)$ matrix. Denoting
the rows of $\mathbf{A}$ by $\mathbf{a}_{1},\ldots,\mathbf{a}_{k}$, we take
$A_{i}=\text{supp}(\mathbf{a}_{i})$ for $i=1,\ldots,k$.

Let the $k$ logical qubits to be encoded be in an arbitrary pure state

$\ket{\phi}=\sum_{\mathbf{x}\in\\{0,1\\}^{k}}a_{\mathbf{x}}\ket{\mathbf{x}},$
(8)

We prepare $k$ ancilla qubits in the state
$\sum_{\mathbf{x}\in\\{0,1\\}^{k}}a_{\mathbf{x}}\ket{\mathbf{x}}_{\mathrm{a}}$,
where the subscript $\mathrm{a}$ is used for clarity to identify the ancilla
qubits. Then, the ancillas and target qubits are jointly in the state

$\displaystyle\ket{\psi}=\sum_{\mathbf{x}\in\\{0,1\\}^{k}}{a_{\mathbf{x}}\ket{\mathbf{x}}_{\mathrm{a}}\ket{\mathrm{G}}}.$
(9)

Applying the $CZ$ gates controlled by the ancilla qubits, the joint state of
the $k$ ancilla and $n$ target qubits becomes

$\displaystyle\ket{\psi^{\prime}}=\sum_{\mathbf{x}\in\\{0,1\\}^{k}}{a_{\mathbf{x}}\ket{\mathbf{x}}_{\mathrm{a}}\Big{(}Z_{\mathbf{x}\mathbf{A}}\ket{\mathrm{G}}\Big{)}}.$

Here, the subscript $\mathbf{x}\mathbf{A}$ on $Z$ refers to the binary vector
obtained as the modulo-$2$ product of the vector $\mathbf{x}$ and the matrix
$\mathbf{A}$.

Next, the ancilla qubits are measured sequentially in the $X$-basis. The joint
state of the $n$ target qubits is then transformed to

$\displaystyle\ket{\mathrm{e}^{\prime}}=\sum_{\mathbf{x}\in\\{0,1\\}^{k}}{{(-1)}^{\mathbf{x}\cdot\mathbf{y}}a_{\mathbf{x}}Z_{\mathbf{x}\mathbf{A}}\ket{\mathrm{G}}},$

where $\mathbf{y}\in\\{0,1\\}^{k}$ is a vector whose $i^{th}$ entry is $0$ if
the $i^{th}$ ancilla measurement resulted in the $\ket{+}$ state, and $1$ if
the measurement resulted in the $\ket{-}$ state.

Similar to the case where a single qubit was encoded, for each
$i\in\text{supp}(\mathbf{y})$, applying the logical-$Z$ operator, $Z^{L}_{i}$,
corresponding to the $i^{th}$ logical qubit transforms the post-measurement
state $\ket{\mathrm{e}^{\prime}}$ to the desired form

$\ket{\mathrm{e}}=\sum_{\mathbf{x}\in\\{0,1\\}^{k}}{a_{\mathbf{x}}Z_{\mathbf{x}\mathbf{A}}\ket{\mathrm{G}}}.$
(10)

Explicitly, $Z^{L}_{i}=S_{i}$, the stabilizer generator associated with the
$i$th vertex of the graph underlying $\ket{\mathrm{G}}$. This is because, for
each $i\in[k]$, $S_{i}=X_{i}Z_{N(i)}$ anti-commutes with $Z_{A_{i}}$ and
commutes with $Z_{A_{j}}$ for all $j\neq i$. This is due to the fact that we
chose the generator matrix $\mathbf{A}$ to be of the form
$[\mathbf{I}\mid\mathbf{B}]$, so that only $Z_{A_{i}}$ contains the operator
$Z_{i}$, for each $i\in[k]$.

We summarize in Algorithm 1 below the tent peg protocol for encoding $k$
logical qubits into a CWS code

$\mathcal{Q}:=\text{span}\bigl{(}\\{Z_{\mathbf{x}\mathbf{A}}\ket{\mathrm{G}}:\mathbf{x}\in\\{0,1\\}^{k}\\}\bigr{)}$
(11)

obtained from a graph state $\ket{\mathrm{G}}$ and a tent peg code with a
systematic generator matrix $\mathbf{A}$.

Algorithm 1 The tent peg protocol for encoding $k$ logical qubits in a CWS
code.

  1. 1.

Prepare $k$ ancilla qubits in the joint state of the $k$ logical qubits to be
encoded

  2. 2.

Prepare $n$ physical qubits in the graph state $\ket{\mathrm{G}}$

  3. 3.

For $i=1\text{ to }k$:

     * apply a $CZ$ gate with the $i$th ancilla qubit as control and the subset $A_{i}$ of the $n$ physical qubits as the target

  4. 4.

For $i=1\text{ to }k$:

    1. (a)

measure the $i^{th}$ ancilla qubit in the $X$-basis

    2. (b)

if the measurement outcome is ‘$-1$’, apply $Z_{i}^{L}=S_{i}$ on the physical
qubits

Alternatively, instead of transforming the post-measurement state to the
desired form, we may use $k$ classical bits to store the measurement outcome,
along with the state $\ket{\mathrm{e}^{\prime}}$. A party without access to
the classical bits cannot decode the correct logical information only from
$\ket{\mathrm{e}^{\prime}}$.

###  IV-B Sequential encoding

Among the $k$ logical qubits, suppose that there is a qubit that is not
entangled with the remaining $k-1$ logical qubits. Without loss of generality,
assume that the $k$th logical qubit is separable from (i.e., not entangled
with) the first $k-1$ logical qubits. Then, the entire set of $k$ logical
qubits can be sequentially encoded by first applying the tent peg protocol to
the initial set of $k-1$ logical qubits, and then encoding the $k$th logical
qubit. To describe this in more detail, let us assume that the logical qubits
are in a product state

$\ket{\phi}=\left(\sum_{\mathbf{x}^{\prime}\in\\{0,1\\}^{k-1}}a_{\mathbf{x}^{\prime}}\ket{\mathbf{x}^{\prime}}\right)\otimes(b_{0}\ket{0}+b_{1}\ket{1}),$
(12)

where $b_{0}\ket{0}+b_{1}\ket{1}$ is the state of the $k$th logical qubit.
Comparing with (8), we see that
$a_{\mathbf{x}^{\prime}0}=a_{\mathbf{x}}^{\prime}b_{0}$ and
$a_{\mathbf{x}^{\prime}1}=a_{\mathbf{x}^{\prime}}b_{1}$. When we apply the
protocol in Algorithm 1 to the first $k-1$ logical qubits, we get an
intermediate encoded state

$\ket{\mathrm{f}}=\sum_{\mathbf{x}^{\prime}\in\\{0,1\\}^{k-1}}{a_{\mathbf{x}^{\prime}}Z_{\mathbf{x}^{\prime}\mathbf{A}^{\prime}}\ket{\mathrm{G}}},$
(13)

where $\mathbf{A}^{\prime}$ is the submatrix of $\mathbf{A}$ consisting of all
but the last row of $\mathbf{A}$. Observe that the state $\ket{\mathrm{f}}$
belongs to the subcode

$\mathcal{Q}^{\prime}:=\text{span}\bigl{(}\\{Z_{\mathbf{x}^{\prime}\mathbf{A}^{\prime}}\ket{\mathrm{G}}:\mathbf{x}^{\prime}\in\\{0,1\\}^{k-1}\\}\bigr{)}$
(14)

of the overall CWS code $\mathcal{Q}$ in (11). With the $n$ target qubits in
state $\ket{\mathrm{f}}$, if we further apply the encoding protocol for the
$k$th logical qubit (i.e., apply $CZ$s controlled by the $k$th logical qubit,
then measure that qubit in the $X$-basis, and finally, if the measurement
outcome is $-1$, apply $X_{k}^{L}=S_{k}$ on the target qubits), then it can be
verified that we will get the final encoding to be $\ket{\mathrm{e}}$ as in
(10).

###  IV-C Recovering the logical qubits

We propose a similar measurement-based approach to recover the $k$ logical
qubits encoded in a state of the CWS code $\mathcal{Q}$. Note that any
correctable errors affecting the physical qubits will first need to be
corrected using the standard error-correcting techniques for a stabilizer code
before we apply the recovery protocol.

Consider a CWS encoding $\ket{\mathrm{e}}$ of $k$ logical qubits as given in
(10), obtained using an $n$-qubit graph state $\ket{\mathrm{G}}$ and an
$[n,k]$ tent peg code with systematic generator matrix $\mathbf{A}$. Start by
preparing $k$ ancilla qubits in the product state $\ket{+}^{\otimes k}$, so
that the joint state of the composite system is

$|\psi\rangle=\frac{1}{2^{k/2}}\sum_{\mathbf{x},\mathbf{y}\in\\{0,1\\}^{k}}a_{\mathbf{x}}\ket{\mathbf{y}}_{\mathrm{a}}Z_{\mathbf{x}\mathbf{A}}\ket{\mathrm{G}},$

the subscript $\mathrm{a}$ being used to distinguish the ancilla qubits. Next,
as in the encoding protocol, apply $CZ$ gates controlled by the ancillas, with
targets determined by the supports of the rows of $\mathbf{A}$. This results
in the joint state

$\ket{\psi^{\prime}}=\frac{1}{2^{k/2}}\sum_{\mathbf{x},\mathbf{y}\in\\{0,1\\}^{k}}a_{\mathbf{x}}\ket{\mathbf{y}}_{\mathrm{a}}Z_{(\mathbf{x}+\mathbf{y})\mathbf{A}}\ket{\mathrm{G}}.$
(15)

Observe that, if we now apply the projector $\ket{\mathrm{G}}\bra{\mathrm{G}}$
to the state of the $n$ physical qubits, then the joint state of the composite
system becomes

$\sum_{\mathbf{x},\mathbf{y}\in\\{0,1\\}^{k}}a_{\mathbf{x}}\bra{\mathrm{G}}Z_{(\mathbf{x}+\mathbf{y})\mathbf{A}}\ket{\mathrm{G}}\ket{\mathbf{y}}_{\mathrm{a}}\ket{\mathrm{G}}.$
(16)

Arguing as in the proof of Lemma 1, since the stabilizer of $\ket{\mathrm{G}}$
is equal to the centralizer and contains no non-identity operators consisting
only of Pauli-$Z$s,
$\bra{\mathrm{G}}Z_{(\mathbf{x}+\mathbf{y})\mathbf{A}}\ket{\mathrm{G}}$ is
non-zero iff $\mathbf{x}=\mathbf{y}$. Therefore, the right-hand side of (16)
simplifies to

$\sum_{\mathbf{x}\in\\{0,1\\}^{k}}a_{\mathbf{x}}\ket{\mathbf{x}}_{\mathrm{a}}\ket{\mathrm{G}}.$
(17)

Note that this is the same as the state $\ket{\psi}$ in (9). Thus, we have
reconstructed the original graph state and extracted the $k$ logical qubits of
information onto the $k$ ancilla qubits.

One way to effect the projection onto $\ket{\mathrm{G}}$ required to obtain
(16) is as follows. Starting from the state $\ket{\phi^{\prime}}$ in (15), we
sequentially measure the $n$ independent stabilizer generators
$S_{1},S_{2},\ldots,S_{n}$. If, for a particular $S_{i}$ in the sequence, the
measurement outcome is ‘$+1$’, then we retain the post-measurement state and
measure $S_{i+1}$ next. On the other hand, if the outcome of the measurement
is ‘$-1$’, then we pick any Pauli operator that anti-commutes with that
$S_{i}$, but commutes with all other $S_{j}$, $j\neq i$, and apply that Pauli
operator to the post-measurement state. Note that, since
$S_{i}=X_{i}Z_{N(i)}$, the Pauli operator $Z_{i}$ (i.e., Pauli-$Z$ acting on
the $i$th physical qubit) anti-commutes with only $S_{i}$ among all the
stabilizer generators. The procedure of measuring $S_{i}$ followed by applying
$Z_{i}$ conditioned on the $S_{i}$ measurement outcome is mathematically
equivalent to the action of the projection operator $\frac{1}{2}(I+S_{i})$.
Therefore, repeating this for all $S_{i}$’s results in the action of

$\frac{1}{2^{n}}\prod_{i=1}^{n}(I+S_{i})=\ket{\mathrm{G}}\bra{\mathrm{G}}$

on the physical qubits.

###  IV-D Partial recovery of logical qubits

As in Section IV-B, we consider here the situation when the $k$th logical
qubit that is separable from (i.e., not entangled with) the first $k-1$
logical qubits), as in (12). In this case, the encoded state
$\ket{\mathrm{e}}$ in (10) can be expressed as

$\ket{\mathrm{e}}=\sum_{\mathbf{x}^{\prime}\in\\{0,1\\}^{k-1}}\bigg{(}a_{\mathbf{x}^{\prime}}b_{0}\,Z_{\mathbf{x}^{\prime}\mathbf{A}^{\prime}}\ket{\mathrm{G}}+a_{\mathbf{x}^{\prime}}b_{1}\,Z_{\mathbf{a}_{k}}Z_{\mathbf{x}^{\prime}\mathbf{A}^{\prime}}\ket{\mathrm{G}}\bigg{)}.$

We prepare an ancilla qubit in the $\ket{+}_{\mathrm{a}}$ state and apply the
same set of $CZ$ gates that were used for encoding the $k$th logical qubit.
This results in the joint state

$\ket{\psi^{\prime}}=\frac{1}{\sqrt{2}}\left(\ket{0}_{\mathrm{a}}\ket{\mathrm{e}}+\ket{1}_{\mathrm{a}}Z_{\mathbf{a}_{k}}\ket{\mathrm{e}}\right).$

We then measure the $k$th stabilizer generator $S_{k}=X_{k}Z_{N(k)}$. If the
measurement outcome is ‘$+1$’, then the post-measurement state,
$\ket{\zeta_{+}}$, is the appropriately normalized projection
$\frac{1}{2}\Big{(}I+S_{k}\Big{)}\ket{\psi^{\prime}}$. Note that, since the
generator matrix $\mathbf{A}$ was chosen to be in systematic form, $S_{k}$
anti-commutes with $Z_{\mathbf{a}_{k}}$ and commutes with all other
$Z_{\mathbf{a}_{i}}$’s for $i\neq k$. Using this, we can compute

$\displaystyle\ket{\zeta_{+}}$
$\displaystyle=\sum_{\mathbf{x}^{\prime}\in\\{0,1\\}^{k-1}}\Big{(}a_{\mathbf{x}^{\prime}}b_{0}\ket{0}_{\mathrm{a}}Z_{\mathbf{x}^{\prime}\mathbf{A}^{\prime}}\ket{\mathrm{G}}+a_{\mathbf{x}^{\prime}}b_{1}\ket{1}_{\mathrm{a}}Z_{\mathbf{x}^{\prime}\mathbf{A}^{\prime}}\ket{\mathrm{G}}\Big{)}$
$\displaystyle=\
\ket{\mathrm{f}}\otimes\left(b_{0}\ket{0}_{\mathrm{a}}+b_{1}\ket{1}_{\mathrm{a}}\right)$
(18)

On the other hand, if the measurement outcome is ‘$-1$’, then the post-
measurement state $\ket{\zeta_{-}}$ is
$\frac{1}{2}(I-S_{k})\ket{\psi^{\prime}}$, appropriately normalized. This can
be shown to be related to $\ket{\zeta_{+}}$ as below:

$\ket{\zeta_{+}}=\left(X\otimes Z_{\mathbf{a}_{k}}\right)\ket{\zeta_{-}}.$
(19)

Thus, the state $\ket{\zeta_{-}}$ can be transformed to $\ket{\zeta_{+}}$ by
applying $X$ on the ancilla and $Z_{\mathbf{a}_{k}}$ on the physical qubits.

In summary, at the end of the recovery protocol, the composite system of
physical qubits and ancilla is as in (IV-D). The $k$th logical qubit has thus
been extracted into the ancilla and the remaining $k-1$ logical qubits are
left encoded in the state $\ket{\mathrm{f}}\in\mathcal{Q}^{\prime}$.

###  IV-E Connection between recovery procedure and code distance

In the decoding subsection, we used $CZ$ gates between ancillas and the
physical qubits in the encoded state. We see that the number of $CZ$s used in
encoding and recovery are identical. In fact, we apply the exact same tent
pegs, and the difference between encoding and recovery only lies in whether we
measure the ancillas or the graph state qubits. In this section, we show how
recovery can involve a smaller number of interactions than what is needed for
the encoding if one allows controlled-$X,Y,Z$ gates with the control qubit on
the ancillas.

Since any stabilizer for the graph state contains at least one $X$, strings of
$Z$s can never be in the graph stabilizer and, hence, are chosen for
constructing CWS codes. This restricts us to using only $CZ$ gates in the
encoding procedure. However, this is not the case for the recovery procedure.
We can use a mix of controlled gates to retrieve information without any loss.

For instance, consider recovering the single logical qubit
$\alpha\ket{0}+\beta\ket{1}$ from its encoding
$\ket{\mathrm{e}}=\alpha\ket{\mathrm{G}}+\beta Z_{A}\ket{\mathrm{G}}$. Similar
to the recovery procedure discussed in Subsection IV-C, we append the physical
qubits in state $\ket{\mathrm{e}}$ with an ancilla qubit in state
$\ket{+}_{a}$. Let $U\in\mathcal{P}_{n}$ be a Pauli string acting on the $n$
physical qubits. Let $CU$ denote the controlled-$U$ gate controlled by the
ancilla, with the $n$ physical qubits as the target. The action of $CU$ on the
joint system results in the state

$\ket{\psi_{1}}=\frac{1}{2}\left(\ket{0}_{a}\ket{\mathrm{e}}+\ket{1}_{a}U\ket{\mathrm{e}}\right).$

Measuring all the stabilizer generators of $\ket{\mathrm{G}}$ on the physical
qubits as done in (16) gives the state

$\ket{\psi_{2}}=\Big{[}\alpha\ket{0}_{a}+\Big{(}\alpha\bra{\mathrm{G}}U\ket{\mathrm{G}}+\beta\bra{\mathrm{G}}UZ_{A}\ket{\mathrm{G}}\Big{)}\ket{1}_{a}\Big{]}\ket{\mathrm{G}}.$
(20)

This expression reduces to the required product state
$\left(\alpha\ket{0}_{a}+\beta\ket{1}_{a}\right)\ket{\mathrm{G}}$ when the
following two conditions are satisfied.

$\bra{\mathrm{G}}UZ_{A}\ket{\mathrm{G}}=1\ \ \ (\text{i.e.,
}UZ_{A}\in\mathcal{S})$ (21) $\bra{\mathrm{G}}U\ket{\mathrm{G}}=0\ \ \
(\text{i.e., }U\notin\mathcal{S})$ (22)

Conditions 21 and 22 are not independent, and in fact, we prove the following
proposition in Appendix B,

######  Proposition 3.

If $\mathcal{S}$ is the stabilizer group of a graph state, then for any Pauli
operator $U$,

$UZ_{A}\in\mathcal{S}\implies U\notin\mathcal{S}$

Therefore, in Eq. (20), the logical state is recovered on the ancilla when
$UZ_{A}\in\mathcal{S}$. Comparing conditions in Eq. (21) and (22) to Theorem 1
for one logical qubit, we can see that the support of $U$ or the number of
qubits that the ancilla needs to interact with for the recovery can be as
small as the distance of the code. This can be smaller than the number of
$CZ$s used in encoding.

##  V Energy Cost of Encoding Information in a CWS Code

Landauer’s principle finds a connection between information and thermodynamics
by deriving a minimum energy cost to delete one classical bit of information.
The original paper[38] performed an analysis to arrive at a minimum energy
cost by suggesting that particle in a double well potential within a thermal
bath is a minimal physical realization of a register storing one bit of
information. Here, we attempt a similar analysis by first considering that the
graph states that we use in our protocol can be the nondegenerate ground
states of certain spin Hamiltonians. It is natural to consider frustration-
free Hamiltonians since any graph state $\ket{\mathrm{G}}$ with a set of
stabilizer generators $\\{S_{i}\\}$ can be realized as the ground state of the
Hamiltonian $H$ given by

$\hat{H}=-\sum_{i=1}^{n}S_{i}.$ (23)

$Z_{A_{i}}\ket{\mathrm{G}}$ is an eigenstate of $H$ for any tent peg $A_{i}$.
Assuming that our starting graph state is realized as the ground state of its
associated stabilizer Hamiltonian not only ensures that any CWS code is some
linear combination of the eigenstates of the Hamiltonian but also makes the
energy associated with each possible code simple to evaluate. Now, one can
make a connection between the properties, such as the distance of a CWS code
and the energy cost of realizing the code.

Not all stabilizer states are realizable as nondegenerate ground states of
spin Hamiltonians subject to physical constraints such as some maximum range
of interactions [32]. We put aside this concern with the justification that
driven systems and their associated effective Hamiltonians can realize a wide
variety of ground states [39, 40, 41, 42, 43, 44].

In the rest of this section, we assume that it is straightforward to
physically realize $\ket{\mathrm{G}}$ as the nondegenerate ground state of the
Hamiltonian in (23). The energy of the graph state is
$E=\bra{\mathrm{G}}\hat{H}\ket{\mathrm{G}}=-n$. The energy of the eigenstate
$Z_{A_{i}}\ket{\mathrm{G}}$ is $-n+2|A_{i}|$. The energy of an encoded state
as in (10) is

$\begin{split}\bra{e}\hat{H}\ket{\mathrm{e}}&=\sum_{\mathbf{x}\in\\{0,1\\}^{k}}|a_{\mathbf{x}}|^{2}\bra{\mathrm{G}}Z_{\mathbf{x}\mathbf{A}}\hat{H}Z_{\mathbf{x}\mathbf{A}}\ket{\mathrm{G}}\\\
&=-n+2\sum_{\mathbf{x}\in\\{0,1\\}^{k}}|a_{\mathbf{x}}|^{2}w_{\mathrm{H}}(\mathbf{x}\mathbf{A}),\end{split}$

where $w_{\mathrm{H}}(\mathbf{x}A)$ is the Hamming weight of the codeword
corresponding to $\mathbf{x}A$. The energy cost of arriving at
$\ket{\mathrm{e}}$ when all the qubits are initialized in the joint state
$\ket{\mathrm{G}}$ is at least

$\bra{e}\hat{H}\ket{\mathrm{e}}-\bra{\mathrm{G}}\hat{H}\ket{\mathrm{G}}=2\sum_{\mathbf{x}\in\\{0,1\\}^{k}}|a_{\mathbf{x}}|^{2}w_{\mathrm{H}}(\mathbf{x}\mathbf{A}).$
(24)

It can be noted that this energy cost is strictly positive and that the energy
cost for encoding generic information increases with the Hamming weights of
all codewords in the CWS code.

Deffner [45] determined the energy cost of constructing the Shor code and
Steane code from the energy cost of implementing the Hamiltonian unitary gates
needed to realize such codes. In contrast, we compute the cost by looking at
the difference in energy between the initial and final state. It is not
obvious how this relates to the number of $CZ$ gates used in the tent peg
protocol for encoding, since all $2^{k}$ codewords in the tent peg code
contribute to the extra energy, and therefore, two choices of tent peg codes
involving the same number of $CZ$ gates can result in encodings with different
energies. For example, consider $\mathcal{C}_{1}=\\{110000,001100$} and
$\mathcal{C}_{2}=\\{110000,011000\\}$. Tent peg encoding using
$\mathcal{C}_{1}$ or $\mathcal{C}_{2}$ requires the same number of gates.
However, the Hamming weights of all codewords in $\mathcal{C}_{1}$ and
$\mathcal{C}_{2}$ are $\\{0,2,2,4\\}$ and $\\{0,2,2,2\\}$, and so,
$\mathcal{C}_{2}$ has a lower encoding cost.

To summarise, the energy cost of a CWS encoding can be reduced by choosing a
tent peg code with a smaller average Hamming weight.

## Acknowledgment

This work is supported in part by a Prime Minister’s Research Fellowship and
in part by the grant DST/INT/RUS/RSF/P-41/2021 from the Department of Science
and Technology, Government of India. We would also like to acknowledge
productive discussions we had with Tania Sidana.

## References

  * [1] R. P. Feynman, “Simulating physics with computers,” _International Journal of Theoretical Physics_ , vol. 21, no. 6-7, pp. 467–488, Jun. 1982.
  * [2] I. L. Chuang, R. Laflamme, P. W. Shor, and W. H. Zurek, “Quantum computers, factoring, and decoherence,” _Science_ , vol. 270, no. 5242, pp. 1633–1635, Dec. 1995. [Online]. Available: https://www.science.org/doi/abs/10.1126/science.270.5242.1633
  * [3] M. B. Plenio and P. L. Knight, “Decoherence limits to quantum computation using trapped ions,” _Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences_ , vol. 453, no. 1965, pp. 2017–2041, Oct. 1997. [Online]. Available: https://doi.org/10.1098/rspa.1997.0109
  * [4] G. M. Palma, K.-A. Suominen, and A. Ekert, “Quantum computers and dissipation,” _Proceedings of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences_ , vol. 452, no. 1946, pp. 567–584, Jan. 1996. [Online]. Available: https://royalsocietypublishing.org/doi/abs/10.1098/rspa.1996.0029
  * [5] W. G. Unruh, “Maintaining coherence in quantum computers,” _Physical Review A_ , vol. 51, pp. 992–997, Feb. 1995. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.51.992
  * [6] E. Knill, R. Laflamme, and L. Viola, “Theory of quantum error correction for general noise,” Aug. 1999, arXiv:quant-ph/9908066.
  * [7] P. W. Shor, “Scheme for reducing decoherence in quantum computer memory,” _Physical Review A_ , vol. 52, pp. R2493–R2496, Oct. 1995. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.52.R2493
  * [8] D. Gottesman, “Stabilizer codes and quantum error correction,” Ph.D. dissertation, California Institute of Technology, 1997. [Online]. Available: arXiv:quant-ph/9705052
  * [9] A. Kitaev, “Fault-tolerant quantum computation by anyons,” _Annals of Physics_ , vol. 303, no. 1, pp. 2–30, Jan. 2003. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0003491602000180
  * [10] E. Dennis, A. Kitaev, A. Landahl, and J. Preskill, “Topological quantum memory,” _Journal of Mathematical Physics_ , vol. 43, no. 9, pp. 4452–4505, Aug. 2002. [Online]. Available: https://doi.org/10.1063/1.1499754
  * [11] A. G. Fowler, M. Mariantoni, J. M. Martinis, and A. N. Cleland, “Surface codes: Towards practical large-scale quantum computation,” _Physical Review A_ , vol. 86, no. 3, Sep. 2012. [Online]. Available: https://doi.org/10.1103/physreva.86.032324
  * [12] N. P. Breuckmann and J. N. Eberhardt, “Quantum low-density parity-check codes,” _PRX Quantum_ , vol. 2, no. 4, Oct. 2021. [Online]. Available: https://doi.org/10.1103/prxquantum.2.040101
  * [13] C.-Y. Lai and T. A. Brun, “Entanglement-assisted quantum error-correcting codes with imperfect ebits,” _Physical Review A_ , vol. 86, no. 3, Sep. 2012\. [Online]. Available: https://doi.org/10.1103/physreva.86.032319
  * [14] M. Grassl, T. Beth, and T. Pellizzari, “Codes for the quantum erasure channel,” _Physical Review A_ , vol. 56, no. 1, pp. 33–38, Jul. 1997. [Online]. Available: https://doi.org/10.1103/physreva.56.33
  * [15] M. Grassl and T. Beth, “Quantum BCH codes,” Oct. 1999, arXiv:quant-ph/9910060.
  * [16] M. Barkeshli, Y.-A. Chen, P.-S. Hsin, and R. Kobayashi, “Higher-group symmetry in finite gauge theory and stabilizer codes,” Jul. 2023, arXiv:2211.11764.
  * [17] T. Brun, I. Devetak, and M.-H. Hsieh, “Correcting quantum errors with entanglement,” _Science_ , vol. 314, no. 5798, pp. 436–439, Oct. 2006. [Online]. Available: https://www.science.org/doi/abs/10.1126/science.1131563
  * [18] W. Wang and J. Li, “Two classes of entanglement-assisted quantum MDS codes from generalized Reed–Solomon codes,” _Quantum Information Processing_ , vol. 21, no. 7, p. 245, Jul. 2022. [Online]. Available: https://doi.org/10.1007/s11128-022-03595-6
  * [19] D. Gottesman, A. Kitaev, and J. Preskill, “Encoding a qubit in an oscillator,” _Physical Review A_ , vol. 64, p. 012310, Jun. 2001. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.64.012310
  * [20] A. L. Grimsmo and S. Puri, “Quantum error correction with the Gottesman-Kitaev-Preskill code,” _PRX Quantum_ , vol. 2, p. 020101, Jun. 2021. [Online]. Available: https://link.aps.org/doi/10.1103/PRXQuantum.2.020101
  * [21] J. Zhang, J. Zhao, Y.-C. Wu, and G.-P. Guo, “Quantum error correction with the color-Gottesman-Kitaev-Preskill code,” _Physical Review A_ , vol. 104, no. 6, Dec. 2021. [Online]. Available: https://doi.org/10.1103/physreva.104.062434
  * [22] M. Grassl and M. Rötteler, “Nonadditive quantum codes,” in _Quantum Error Correction_ , D. A. Lidar and T. A. Brun, Eds. Cambridge University Press, Sep. 2013, pp. 261–278.
  * [23] ——, “Non-additive quantum codes from Goethals and Preparata codes,” in _2008 IEEE Information Theory Workshop_ , 2008, pp. 396–400.
  * [24] ——, “Quantum Goethals-Preparata codes,” in _2008 IEEE International Symposium on Information Theory_ , 2008, pp. 300–304.
  * [25] A. Cross, G. Smith, J. A. Smolin, and B. Zeng, “Codeword stabilized quantum codes,” _IEEE Transactions on Information Theory_ , vol. 55, no. 1, pp. 433–438, 2009.
  * [26] X. Chen, B. Zeng, and I. L. Chuang, “Nonbinary codeword-stabilized quantum codes,” _Physical Review A_ , vol. 78, p. 062315, Dec. 2008. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.78.062315
  * [27] L. Arnaud and N. J. Cerf, “Exploring pure quantum states with maximally mixed reductions,” _Physical Review A_ , vol. 87, p. 012319, Jan. 2013. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.87.012319
  * [28] A. J. Scott, “Multipartite entanglement, quantum-error-correcting codes, and entangling power of quantum evolutions,” _Physical Review A_ , vol. 69, p. 052330, May 2004. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.69.052330
  * [29] F. Huber and M. Grassl, “Quantum codes of maximal distance and highly entangled subspaces,” _Quantum_ , vol. 4, p. 284, Jun. 2020. [Online]. Available: http://dx.doi.org/10.22331/q-2020-06-18-284
  * [30] S. Sudevan, D. Azses, E. G. Dalla Torre, E. Sela, and S. Das, “Multipartite entanglement and quantum error identification in $d$-dimensional cluster states,” _Physical Review A_ , vol. 108, p. 022426, Aug. 2023. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.108.022426
  * [31] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest, “Measurement-based quantum computation,” _Nature Physics_ , vol. 5, no. 1, pp. 19–26, Jan. 2009. [Online]. Available: https://doi.org/10.1038/nphys1157
  * [32] M. A. Nielsen, “Cluster-state quantum computation,” _Reports on Mathematical Physics_ , vol. 57, no. 1, pp. 147–161, Feb. 2006. [Online]. Available: https://www.sciencedirect.com/science/article/pii/S0034487706800145
  * [33] R. Raussendorf and H. J. Briegel, “A one-way quantum computer,” _Physical Review Letters_ , vol. 86, pp. 5188–5191, May 2001. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.86.5188
  * [34] X. Zhou, D. W. Leung, and I. L. Chuang, “Methodology for quantum logic gate construction,” _Physical Review A_ , vol. 62, p. 052316, Oct. 2000. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.62.052316
  * [35] A. Blass, “Largest subspace that doesn’t intersect a given set,” MathOverflow, 2010. [Online]. Available: https://mathoverflow.net/q/33407
  * [36] W. Bosma, J. Cannon, and C. Playoust, “The Magma algebra system. I. The user language,” _J. Symbolic Comput._ , vol. 24, no. 3-4, pp. 235–265, 1997\. [Online]. Available: http://dx.doi.org/10.1006/jsco.1996.0125
  * [37] M. A. Nielsen and I. L. Chuang, _Quantum Computation and Quantum Information: 10th Anniversary Edition_. Cambridge University Press, 2010.
  * [38] R. Landauer, “Irreversibility and heat generation in the computing process,” _IBM Journal of Research and Development_ , vol. 5, no. 3, pp. 183–191, 1961\.
  * [39] S. K. Mishra, A. Lakshminarayan, and V. Subrahmanyam, “Protocol using kicked ising dynamics for generating states with maximal multipartite entanglement,” _Physical Review A_ , vol. 91, p. 022318, Feb. 2015. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevA.91.022318
  * [40] F. Petiziol, M. Sameti, S. Carretta, S. Wimberger, and F. Mintert, “Quantum simulation of three-body interactions in weakly driven quantum systems,” _Physical Review Letters_ , vol. 126, p. 250504, Jun. 2021. [Online]. Available: https://link.aps.org/doi/10.1103/PhysRevLett.126.250504
  * [41] S. J. Glaser, U. Boscain, T. Calarco, C. P. Koch, W. Köckenberger, R. Kosloff, I. Kuprov, B. Luy, S. Schirmer, T. Schulte-Herbrüggen, D. Sugny, and F. K. Wilhelm, “Training Schrödinger’s cat: quantum optimal control,” _The European Physical Journal D_ , vol. 69, no. 12, p. 279, Dec. 2015. [Online]. Available: https://doi.org/10.1140/epjd/e2015-60464-1
  * [42] D. Guéry-Odelin, A. Ruschhaupt, A. Kiely, E. Torrontegui, S. Martínez-Garaot, and J. G. Muga, “Shortcuts to adiabaticity: concepts, methods, and applications,” _Reviews of Modern Physics_ , vol. 91, p. 045001, Oct. 2019. [Online]. Available: https://link.aps.org/doi/10.1103/RevModPhys.91.045001
  * [43] X. Gu, J. Fernández-Pendás, P. Vikstål, T. Abad, C. Warren, A. Bengtsson, G. Tancredi, V. Shumeiko, J. Bylander, G. Johansson, and A. F. Kockum, “Fast multiqubit gates through simultaneous two-qubit gates,” _PRX Quantum_ , vol. 2, p. 040348, Dec. 2021. [Online]. Available: https://link.aps.org/doi/10.1103/PRXQuantum.2.040348
  * [44] B. Andrade, Z. Davoudi, T. Graß, M. Hafezi, G. Pagano, and A. Seif, “Engineering an effective three-spin hamiltonian in trapped-ion systems for applications in quantum simulation,” _Quantum Science and Technology_ , vol. 7, no. 3, p. 034001, Apr. 2022. [Online]. Available: https://dx.doi.org/10.1088/2058-9565/ac5f5b
  * [45] S. Deffner, “Energetic cost of hamiltonian quantum gates,” _Europhysics Letters_ , vol. 134, no. 4, p. 40002, Jul. 2021. [Online]. Available: https://dx.doi.org/10.1209/0295-5075/134/40002

##  Appendix A Proof of Theorem 3

We have already seen that $d_{\min}(\mathcal{C}_{r})\geq 3$. The fact that
$\mathcal{C}_{r}$ does not contain codewords of the form in (3)–(6) is proved
in Claims 1–4 below. Claims 1–3 do not require the condition that
$\operatorname{Log}(1+\alpha)\not\equiv 2\pmod{3}$, but Claim 4 does.

######  Claim 1.

$\mathcal{C}_{r}$ contains no codewords of the form in $\eqref{pattern1}$.

###### Proof.

Suppose $\mathbf{x}$ is of the form in $\eqref{pattern1}$. For $\mathbf{x}$ to
be in $\mathcal{C}$, it must have Hamming weight at least $3$, so at least one
of the $\ast$’s in $\mathbf{x}$ is a $1$. However, it is then easily checked
that such an $\mathbf{x}$ cannot be in the nullspace of the second row of the
$H$ matrix. ∎

######  Claim 2.

$\mathcal{C}_{r}$ contains no codewords of the form in $\eqref{pattern2}$.

###### Proof.

Suppose $\mathbf{x}$ is of the form in $\eqref{pattern2}$. Now, it can be
checked that such an $\mathbf{x}$ is in the nullspace of the second row of the
$H$ matrix iff both the $\ast$’s in $\mathbf{x}$ are $1$s. In this case, we
would have
$H\mathbf{x}^{T}=[\alpha^{i}+\alpha^{i+1}+\alpha^{i+3}+\alpha^{i+4},\ \
0]^{T}$. So, for $\mathbf{x}$ to be in $\mathcal{C}_{r}$, we would need
$\alpha^{i}+\alpha^{i+1}+\alpha^{i+3}+\alpha^{i+4}=0$, or equivalently,
$\alpha^{i}(1+\alpha)(1+\alpha^{3})=0$. But this is impossible as $\alpha$ is
a primitive element of $\mathbb{F}_{2^{2r}}$ with $r\geq 2$. ∎

######  Claim 3.

$\mathcal{C}_{r}$ contains no codewords of the form in $\eqref{pattern3}$.

###### Proof.

Suppose $\mathbf{x}$ is of the form in $\eqref{pattern3}$. For such an
$\mathbf{x}$ to be in the nullspace of the second row of the $H$ matrix,
either both the $\ast$’s in $\mathbf{x}$ are $0$s or both are $1$s. In either
case, we obtain that $H\mathbf{x}^{T}$ is of the form
$[\alpha^{i}+c\,\alpha^{i+1}+\alpha^{i+2}+\alpha^{i+3+j}+c\,\alpha^{i+3+j+1}+\alpha^{i+3+j+2},\
\ 0]^{T}$, for some $c\in\\{0,1\\}$ and $i,j\geq 0$. (Here, $j$ is the length
of the run of $0$s between the two ‘$1\ast 1$’ blocks, so $j\leq n-6$.) So,
for $\mathbf{x}$ to be in $\mathcal{C}_{r}$, we would need
$\alpha^{i}+c\,\alpha^{i+1}+\alpha^{i+2}+\alpha^{i+3+j}+c\,\alpha^{i+3+j+1}+\alpha^{i+3+j+2}=0$,
or equivalently, $\alpha^{i}(1+c\,\alpha+\alpha^{2})(1+\alpha^{j+3})=0$. By
primitivity of $\alpha$, we cannot have $\alpha^{i}=0$ or $1+\alpha^{j+3}=0$
(note that $j+3<2^{2r}-1$). Moreover, $1+c\,\alpha+\alpha^{2}=0$ would mean
that $\alpha$ is a root of a degree-$2$ polynomial in $\mathbb{F}_{2}[x]$,
which is impossible, as the minimal polynomial of $\alpha$ has degree $2r>2$.
We thus conclude that we cannot have
$\alpha^{i}(1+c\,\alpha+\alpha^{2})(1+\alpha^{j+3})=0$, and so no $\mathbf{x}$
of the form in (5) can be in the code $\mathcal{C}_{r}$. ∎

######  Claim 4.

If $\operatorname{Log}(1+\alpha)\not\equiv 2\pmod{3}$, then $\mathcal{C}_{r}$
contains no codewords of the form in $\eqref{pattern4}$.

###### Proof.

Suppose $\mathbf{x}$ is of the form in $\eqref{pattern4}$. Such an
$\mathbf{x}$ can be in the nullspace of the second row of the $H$ matrix only
if exactly one of the two $\ast$’s in $\mathbf{x}$ is a $1$. In other words,
an $\mathbf{x}$ of the form in (6) is in $\mathcal{C}_{r}$ only if
$\mathbf{x}=0\cdots 01110\cdots 0$ or $\mathbf{x}=0\cdots 01010\cdots
010\cdots 0$. (Here, the $0\cdots 0$ blocks represent runs, possibly empty, of
$0$s.)

If $\mathbf{x}=0\cdots 01110\cdots 0$, then
$H\mathbf{x}^{T}=[\alpha^{i}(1+\alpha+\alpha^{2}),\ \ 0]^{T}$ for some $i$.
So, for this $\mathbf{x}$ to be in $\mathcal{C}_{r}$, we need
$1+\alpha+\alpha^{2}=0$, which is impossible since $\alpha$ is a primitive
element of $\mathbb{F}_{2^{2r}}$, so its minimal polynomial over
$\mathbb{F}_{2}$ has degree $2r>2$.

So, consider $\mathbf{x}=0\cdots 01010\cdots 010\cdots 0$. We then have
$H\mathbf{x}^{T}=[\alpha^{i}(1+\alpha^{2}+\alpha^{j}),\ \
\alpha^{bi}(1+\alpha^{2b}+\alpha^{bj})]^{T}$ for some $i\geq 0$ and $j\geq 3$.
For the second entry in $H\mathbf{x}^{T}$ to be $0$, we need
${(\alpha^{b})}^{j}=\alpha^{b}$, which (by choice of $b$) happens iff $j\equiv
1\pmod{3}$. For the first entry in $H\mathbf{x}^{T}$ to also be $0$, we
further need $1+\alpha^{2}=\alpha^{j}$. Thus, we can have
$\mathbf{x}\in\mathcal{C}_{r}$ (i.e., $H\mathbf{x}^{T}=[0,\ 0]^{T}$) iff
$1+\alpha^{2}=\alpha^{j}$ for some $j\equiv 1\pmod{3}$. In other words,
$\mathbf{x}\in\mathcal{C}_{r}$ iff $\operatorname{Log}(1+\alpha^{2})\equiv
1\pmod{3}$. We next show that the latter condition is equivalent to
$\operatorname{Log}(1+\alpha)\equiv 2\pmod{3}$, which will suffice to prove
the claim.

Let $\operatorname{Log}(1+\alpha)=\ell$, meaning that
$\alpha^{\ell}=1+\alpha$. Squaring both sides we get
$\alpha^{2\ell\mod(4^{r}-1)}=1+\alpha^{2}$, i.e.,
$\operatorname{Log}(1+\alpha^{2})=2\ell\mod(4^{r}-1)$. Since $4^{r}-1$ is a
multiple of $3$, we have $2\ell\mod(4^{r}-1)\equiv 1\pmod{3}$ iff $2\ell\equiv
1\pmod{3}$, which in turn holds iff $\ell\equiv 2\pmod{3}$. In other words,
$\operatorname{Log}(1+\alpha^{2})\equiv 1\pmod{3}$ iff
$\operatorname{Log}(1+\alpha)\equiv 2\pmod{3}$. ∎

This completes the proof of the Theorem.

##  Appendix B  Proof of Proposition 3

Suppose that $U$ is a Pauli operator and $\mathcal{S}$ is the stabilizer group
of a graph state $\ket{\mathrm{G}}$. We wish to prove that for any non-empty
subset of indices $A$,

$UZ_{A}\in\mathcal{S}\implies U\notin\mathcal{S}.$

We first note that $Z_{A}\notin\mathcal{S}$, since it anti-commutes with the
stabilizer generator $X_{i}Z_{N(i)}$ for any $i\in A$. Hence,
$\braket{\mathrm{G}}{Z_{A}}{\mathrm{G}}=0$.

Now, suppose that $UZ_{A}\in\mathcal{S}$. Then,

$UZ_{A}=S_{i_{1}}\cdot S_{i_{2}}\cdot S_{i_{3}}\cdots\ S_{i_{r}},$

for some choice of $r$ stabilizer generators of $\mathcal{S}$. Right
multiplication with $Z_{A}$ on both sides yields

$U=S_{i_{1}}\cdot S_{i_{2}}\cdot S_{i_{3}}\cdots\ S_{i_{r}}\cdot Z_{A}$

We then have

$\displaystyle\braket{\mathrm{G}}{U}{\mathrm{G}}$
$\displaystyle=\braket{\mathrm{G}}{S_{i_{1}}\cdot S_{i_{2}}\cdot
S_{i_{3}}\cdots\ S_{i_{r}}\cdot Z_{A}}{\mathrm{G}}$
$\displaystyle=\braket{\mathrm{G}}{Z_{A}}{\mathrm{G}}\ =\ 0.$

Therefore $U\notin\mathcal{S}$.