# A family of permutationally invariant quantum codes

Arda Aydin  ,  Max A. Alekseyev  and  Alexander Barg

###### Abstract.

We construct a new family of permutationally invariant codes that correct $t$
Pauli errors for any $t\geq 1$. We also show that codes in the new family
correct spontaneous decay errors as well as deletion errors. In many cases the
codes in this family are shorter than the best previously known explicit
families of permutationally invariant codes for Pauli errors, deletions, and
for the amplitude damping channel. As a separate result, we generalize the
conditions for permutationally invariant codes to correct $t$ Pauli errors
from the previously known results for $t=1$ to any number of errors. For small
$t$, these conditions can be used to construct new examples of codes by
computer.

Arda Aydin and Alexander Barg are with the Department of ECE and Institute for
Systems Research, University of Maryland, College Park, MD 20742. Emails:
<EMAIL_ADDRESS>Research supported by NSF grants CCF-2110113 (NSF-BSF)
and CCF-2104489.

Max A. Alekseyev is with the Department of Mathematics, The George Washington
University, Washington, DC 20052.

##  1\. Introduction

Quantum error correction is one of the essential fields of quantum computing,
which aims to protect quantum information from errors caused by quantum noise,
such as decoherence. A subspace of the Hilbert space of a physical system is
called a quantum code for a given type of errors if it satisfies certain
specific conditions for error correction [12]. Mapping a quantum state to be
protected into a higher-dimensional Hilbert space of the physical system is a
significant part of quantum error correction. In many applications, it is
desirable to construct quantum codes that lie within the ground space of the
system. Motivated by this goal, in this paper we study permutation-invariant
quantum codes whose codewords form ground states of the Hamiltonian of a
physical system called the ferromagnetic Heisenberg model.

Recall that Heisenberg’s model characterizes interactions between spins in the
system. Two spin-$1/2$ particles are coupled by an interaction described by
the Hamiltonian given by $\propto\;{\boldsymbol{S}}_{i}{\boldsymbol{S}}_{j},$
where ${\boldsymbol{S}}_{i}$ and ${\boldsymbol{S}}_{j}$ are spin operators for
the particles $i$ and $j$, respectively. In the absence of an external
magnetic field, the Heisenberg ferromagnetic model is described by the
Hamiltonian that can be written in the form

$\displaystyle\hat{H}=-2\sum\limits_{i<j}J_{ij}\boldsymbol{S}_{i}\boldsymbol{S}_{j},$

where $J_{ij}$ is the exchange (coupling) constant between particles $i$ and
$j$ in the system. Note that $J_{ij}>0$ since we are considering the
ferromagnetic model. See [2, Ch. 1,4] for a detailed discussion of this model.
It can be shown that

$\displaystyle{\boldsymbol{P}}_{ij}=\frac{1}{2}{{\boldsymbol{I}}}+2\boldsymbol{S}_{i}\boldsymbol{S}_{j},$

where ${\boldsymbol{I}}$ is the identity and where ${\boldsymbol{P}}_{ij}$ is
the swap operator that exchanges spin $i$ and spin $j$, essentially swapping
the spin-$\frac{1}{2}$ particles $i$ and $j$, e.g.,
${\boldsymbol{P}}_{12}\lvert\updownarrows\upuparrows\rangle=\lvert\downuparrows\upuparrows\rangle$.
The Hamiltonian of the Heisenberg model can be written in terms of the swap
operators in the following way:

$\displaystyle\hat{H}=-\sum\limits_{i<j}J_{ij}\left({\boldsymbol{P}}_{ij}-\frac{1}{2}{{\boldsymbol{I}}}\right).$

A state $\lvert\psi\rangle$ is called permutation-invariant if it is preserved
by all swap operators ${\boldsymbol{P}}_{ij},$ i.e., $\lvert\psi\rangle$ is a
common eigenstate of the swap operators with eigenvalue 1. Denoting
$J=\sum_{i<j}J_{ij}$, we observe that for any permutation-invariant state
$\lvert\psi\rangle,$

$\displaystyle\left(\hat{H}-\frac{J}{2}{{\boldsymbol{I}}}\right)\lvert\psi\rangle=-\sum_{i<j}J_{ij}{\boldsymbol{P}}_{ij}\lvert\psi\rangle=-J\lvert\psi\rangle.$

Since $J_{ij}>0$, the spectral norm of $\hat{H}-\frac{J}{2}{{\boldsymbol{I}}}$
is bounded above by $J$, so the smallest eigenvalue of the Hamiltonian is
$-J/2,$ and its corresponding eigenstate is $\lvert\psi\rangle$. Therefore,
any permutation-invariant state is a ground state of the Hamiltonian in the
ferromagnetic Heisenberg model [20].

Permutation-invariant codes were introduced in the works of Ruskai and
Pollatsek [28, 26]. The codes they constructed encode a single logical qubit,
and are capable of correcting all one-qubit errors and certain types of two-
qubit errors. In particular, Ruskai’s $((9,2,3))$ code [28] has the basis

$\displaystyle\lvert 0_{L}\rangle$ $\displaystyle=\lvert
0^{9}\rangle+\frac{1}{\sqrt{28}}\sum_{\pi}\lvert 1^{6}0^{3}\rangle$
$\displaystyle\lvert 1_{L}\rangle$ $\displaystyle=\lvert
1^{9}\rangle+\frac{1}{\sqrt{28}}\sum_{\pi}\lvert 0^{6}1^{3}\rangle,$

where the sum is extended to all permutations of the argument state. This code
is obtained as a symmetrized version of Shor’s 9-qubit code  [32].
Generalizing this construction, Ouyang [20] found a family of permutation-
invariant codes that correct $t$ arbitrary errors and $t$ spontaneous decay
errors. The family is parameterized by integers $g$, $n$, and $u$ (hence the
name “gnu codes”), and the shortest $t$-error-correcting codes in it are of
length $(2t+1)^{2}$. Ouyang subsequently showed that permutation-invariant
codes are capable of supporting reliable quantum storage, quantum sensing, and
decoherence-free communication [22, 21, 23].

In hindsight, it is clear that permutation-invariant codes also support
recovery of encoded states from deletion errors: since permutations preserve
the states, deletion of arbitrary $t$ positions is not different from deleting
the first $t$ qubits, and thus deletions are equivalent to erasures. However,
making this idea formal requires a rigorous definition of the quantum deletion
channel as well as proving the equivalence. This was accomplished in the works
of Nakayama and Hagiwara [17, 10, 18], who also observed that permutation-
invariant codes are capable of correcting deletion errors and constructed
single-deletion-correcting codes. Subsequently, Shibayama and Hagiwara showed
that Ouyang’s gnu codes can correct $t$ deletions [30]. In particular, the
shortest known code to correct $t$ deletions comes from this family, and it
has length $(t+1)^{2}.$

Recall that correcting deletions has a long history in classical coding
theory. This problem was introduced as far back as 1965 by Levenshtein [14],
and it has been studied both in combinatorial and probabilistic versions.
Despite a number of spectacular advances in recent years, both problems are
still far from solution: for instance, the only case when the optimal codes
are known is correcting a single deletion [33]. We refer the reader to two
recent surveys dealing with constructive and capacity aspects of transmission
over the deletion channel, [9] and [4], published in the special issue devoted
to the scientific legacy of Vladimir Levenshtein.

In quantum coding theory, a deletion can be modeled as a partial trace
operation where the traced-out qubits are unknown. It turns out that the
performance of permutation-invariant codes for correcting errors or deletions
is sometimes amenable to analysis. Focusing on this code family, we study the
error correction (Knill–Laflamme) conditions for general permutation-invariant
codes. Using deletion correction as motivation, we propose a new family of
permutation-invariant codes defined by their parameters $g$, $m$, and
$\delta$. The shortest codes in this family have length $(2t+1)^{2}-2t$ and
can correct all $t$ patterns of qubit errors and $2t$ deletion errors. The
shortest $t$-error-correcting permutation-invariant codes known previously are
due to Ouyang and require $2t$ more physical qubits than the codes that we
propose. Specializing our construction to $t=1,$ we observe that the length of
our code is the same as the Pollatsek–Ruskai’s $((7,2,3))$ permutation-
invariant code [26], although the two codes are different. The authors of [26]
also derived explicit conditions for correcting a single error with
permutation-invariant codes, and we extend this result to $t\geq 1$ errors.

In Sections 2 and 3 we collect the necessary definitions and some basic facts
about quantum deletions. In particular, in Sec. 3 we recall the definition of
deletion operators [31] and prove some of their properties. Sec. 4 contains a
detailed form of the error correcting conditions for permutation-invariant
codes. Our main result (the new code family) is presented in Sec. 5 (checking
the error correcting conditions turns out to be technically involved, and the
proof is moved to Appendix A). In Sec. 6 we find the conditions on the code
parameters for the codes to correct a given number $t\geq 1$ of spontaneous
decay errors. Finally, in Sec. 7 we present a generalization of the
Pollatsek–Ruskai conditions for error correction with their permutation-
invariant codes, and show that it potentially leads to new examples of such
codes.

##  2\. Preliminaries

Throughout this paper, we use the following notation. Let
$\lvert\Psi\rangle=\lvert\psi_{1}\psi_{2},\ldots,\psi_{n}\rangle=\lvert\psi_{1}\rangle\otimes\lvert\psi_{2}\rangle\otimes\ldots\otimes\lvert\psi_{n}\rangle\subset{\mathbb{C}}^{2\otimes
n}$ be a pure state, where ${\mathbb{C}}^{2\otimes n}$ is a shorthand for
$({\mathbb{C}}^{2})^{\otimes n}$, and we assume that
$\langle\psi_{i}\,|\,\mathopen{}\psi_{i}\rangle=1$ for all $i=1,2,\dots,n$. A
general quantum state is identified with its density matrix, i.e., a positive
semidefinite Hermitian matrix of trace 1. The density matrix of a pure state
is simply $\rho=\lvert\psi\rangle\langle\psi\rvert$. For a collection of pure
states
$\lvert\psi_{1}\rangle,\lvert\psi_{2}\rangle,\ldots,\lvert\psi_{n}\rangle$
such that $\Pr(\lvert\psi_{i}\rangle)=p_{i}$ for all $i$ and
$\sum_{i}p_{i}=1,$ the density matrix is defined as
$\rho=\sum_{i}p_{i}\lvert\psi_{i}\rangle\langle\psi_{i}\rvert$. Denote by
$S({\mathbb{C}}^{2\otimes n})$ the set of all density matrices of order
$2^{n}$.

######  Definition 2.1.

Consider an $n\times n$ matrix
$A=\sum_{{\boldsymbol{x}},{\boldsymbol{y}}\in\\{0,1\\}^{n}}a_{{\boldsymbol{x}},{\boldsymbol{y}}}\lvert{\boldsymbol{x}}\rangle\langle{\boldsymbol{y}}\rvert$,
where $a_{{\boldsymbol{x}},{\boldsymbol{y}}}\in{\mathbb{C}}$. For an integer
$i\in\\{1,2,\dots,n\\}$, the partial trace of $A$ is a mapping

$\displaystyle\operatorname{Tr}_{i}:S({\mathbb{C}}^{2\otimes n})$
$\displaystyle\xrightarrow{}S({\mathbb{C}}^{2\otimes(n-1)})$ $\displaystyle A$
$\displaystyle\mapsto\sum_{{\boldsymbol{x}},{\boldsymbol{y}}\in\\{0,1\\}^{n}}a_{{\boldsymbol{x}},{\boldsymbol{y}}}\operatorname{Tr}(\lvert
x_{i}\rangle\langle
y_{i}\rvert)\lvert{\boldsymbol{x}}^{\prime}\rangle\langle{\boldsymbol{y}}^{\prime}\rvert,$

where $\lvert{\boldsymbol{x}}^{\prime}\rangle=\lvert
x_{1},\ldots,x_{i-1},x_{i+1},\ldots,x_{n}\rangle$ and
$\lvert{\boldsymbol{y}}^{\prime}\rangle=\lvert
y_{1},\ldots,y_{i-1},y_{i+1},\ldots,y_{n}\rangle$.

Permutation-invariant quantum states are conveniently described in terms of
Dicke states [6, 11, 16].

######  Definition 2.2.

A Dicke state $\lvert D_{w}^{n}\rangle$ is a linear combination of all qubit
states of length $n$ of “Hamming weight” $w$, i.e.

$\displaystyle\lvert
D_{w}^{n}\rangle=\frac{1}{\sqrt{\binom{n}{w}}}\sum_{\begin{subarray}{c}{\boldsymbol{x}}\in\\{0,1\\}^{n}\\\
|{\boldsymbol{x}}|=w\end{subarray}}\lvert{\boldsymbol{x}}\rangle.$

Sometimes we also use unnormalized Dicke states given by $\lvert
H^{n}_{w}\rangle=\sqrt{\binom{n}{w}}\lvert D_{w}^{n}\rangle$.

Since $\langle D^{n}_{i}\,|\,\mathopen{}D^{n}_{j}\rangle=\delta_{ij}$ by
definition, the Dicke states form an orthonormal basis of
${\mathbb{C}}^{2\otimes n}$.

For spin-$\frac{1}{2}$ particles, a Dicke state $\lvert D_{n}^{w}\rangle$ can
be viewed as a superposition of the tensor product of states of an
$n$-particle system in which $w$ particles are in the spin-up, and $n-w$ are
in the spin-down configuration; for instance,

$\displaystyle\lvert D_{1}^{3}\rangle=\frac{\lvert 001\rangle+\lvert
010\rangle+\lvert
100\rangle}{\sqrt{3}}=\frac{\lvert\downdownarrows\uparrow\rangle+\lvert\downarrow\uparrow\downarrow\rangle+\lvert\uparrow\downdownarrows\rangle}{\sqrt{3}}.$

A quantum code ${\mathscr{C}}$ maps a $2^{k}$-dimensional Hilbert space into a
subspace of the $2^{n}$-dimensional Hilbert space ${\mathbb{C}}^{2\otimes n}$,
i.e., it encodes $k$ logical qubits into $n$ physical qubits. Throughout this
paper, we will be dealing with two-dimensional codes and denote their basis
codewords by $\lvert{\boldsymbol{c}}_{0}\rangle$ and
$\lvert{\boldsymbol{c}}_{1}\rangle.$.

The following definition originates with [26].

######  Definition 2.3.

A permutation-invariant code  is a pair of basis vectors of the form

(1)
$\displaystyle\lvert{\boldsymbol{c}}_{0}\rangle=\sum_{j=0}^{n}\alpha_{j}\lvert
D^{n}_{j}\rangle\quad\text{and}\quad\lvert{\boldsymbol{c}}_{1}\rangle=\sum_{j=0}^{n}\beta_{j}\lvert
D^{n}_{j}\rangle,$

where $\alpha_{j},\beta_{j}\in{\mathbb{C}},j=0,1,\ldots,n$ and
$\sum_{j}\bar{\alpha_{j}}\beta_{j}=0.$

###  2.1. Kraus Operators and the Knill–Laflamme conditions

A quantum channel ${\mathcal{A}}$ is a linear operator acting on density
matrices such that it admits the Kraus decomposition

$\displaystyle\mathcal{A}(\rho)=\sum_{\mathbf{A}\in\mathfrak{K}_{\mathcal{A}}}\mathbf{A}\rho\mathbf{A}^{\dagger},$

where
$\sum_{\mathfrak{K}_{\mathcal{A}}}{\boldsymbol{A}}{\boldsymbol{A}}^{\dagger}={{\boldsymbol{I}}}$
and $\mathfrak{K}_{\mathcal{A}}$ is the Kraus set of the channel. Elements of
this set are called Kraus operators.

######  Example 1.

(Depolarizing Channel). Let
${\boldsymbol{X}},{\boldsymbol{Y}},{\boldsymbol{Z}}$ (bit flip, phase flip,
combined flip) be the set of Pauli errors that act on a state $\rho\in
S({\mathbb{C}}^{2})$ with probability $p/3$ each. Defining
$\mathfrak{K}_{\mathcal{A}}=\\{({{\boldsymbol{I}}}\sqrt{1-p}),({\boldsymbol{X}}\sqrt{p/3}),$
$({\boldsymbol{Y}}\sqrt{p/3}),({\boldsymbol{Z}}\sqrt{p/3})\\}$ to be the Kraus
set of the depolarizing channel, we can write its action on $\rho$ in the form

$\displaystyle{\mathcal{A}}(\rho)=(1-p)\rho+\frac{p}{3}\left({\boldsymbol{X}}\rho{\boldsymbol{X}}+{\boldsymbol{Y}}\rho{\boldsymbol{Y}}+{\boldsymbol{Z}}\rho{\boldsymbol{Z}}\right).$

Observe that
$\sum_{{\boldsymbol{A}}\in\mathfrak{K}_{\mathcal{A}}}{\boldsymbol{A}}{\boldsymbol{A}}^{\dagger}={{\boldsymbol{I}}}$.

The necessary and sufficient conditions for the quantum error correction were
formulated by Knill and Laflamme [12].

######  Theorem 2.1 (Knill–Laflamme conditions).

Let ${\mathscr{C}}$ be a quantum code with an orthonormal basis
$\lvert{\boldsymbol{c}}_{0}\rangle,\lvert{\boldsymbol{c}}_{1}\rangle,\ldots,\lvert{\boldsymbol{c}}_{k-1}\rangle$,
and let ${\mathcal{A}}$ be a quantum channel with Kraus operators
${\boldsymbol{A}}_{i}$. There exists a quantum recovery operator
${\mathcal{R}}$ such that ${\mathcal{R}}({\mathcal{A}}(\rho))=\rho$ for every
density matrix supported on ${\mathscr{C}}$ if and only if for every $a,b$,

(2)
$\displaystyle\langle{\boldsymbol{c}}_{i}\rvert{\boldsymbol{A}}_{a}^{\dagger}{\boldsymbol{A}}_{b}\lvert{\boldsymbol{c}}_{j}\rangle=0\quad\text{for
all $i\neq j$ },$ (3)
$\displaystyle\langle{\boldsymbol{c}}_{i}\rvert{\boldsymbol{A}}_{a}^{\dagger}{\boldsymbol{A}}_{b}\lvert{\boldsymbol{c}}_{i}\rangle=g_{ab}\quad\text{for
all $i=0,1,\ldots,k-1$},$

for some constants $g_{ab}\in{\mathbb{C}}$.

##  3\. Quantum Deletion Channel

In the classical coding theory, a $t$-deletion error is defined as a map from
an $n$-bit string $x$ to the set of its subsequences of length $n-t$.
Following [31], in this section, we define deletions and a deletion channel
for quantum codes. We begin with the following definition.

######  Definition 3.1.

($t$-Deletion channel) Let $t\in\\{1,2,\dots,n\\}$ and let $\rho\in
S({\mathbb{C}}^{2\otimes n})$ be a quantum state. For a set
$E=\\{e_{1},e_{2}\,\ldots,e_{t}\\}\subset\\{1,2,\ldots,n\\}$ with
$e_{1}<e_{2}<\ldots<e_{t}$, define a map $D_{E}:S({\mathbb{C}}^{2\otimes
n})\to S({\mathbb{C}}^{2\otimes(n-t)})$ as

$\displaystyle
D_{E}^{n}(\rho):=\operatorname{Tr}_{e_{1}}\circ\cdots\circ\operatorname{Tr}_{e_{t}}(\rho).$

The action of $D_{E}$ deletes the qubits in locations contained in $E$, and is
called a $t$-deletion error. A $t$-deletion channel
$\operatorname{Del}_{t}^{n}$ is a convex combination of all $t$-deletion
errors, where $t$ is a fixed integer with $|E|=t$, i.e.,

$\displaystyle\operatorname{Del}_{t}^{n}(\rho)=\sum_{E:|E|=t}p(E)D_{E}^{n}(\rho),$

where $p(E)$ is a probability distribution.

Let $n\geq t\geq 1$ be integers. Define the set
$E=\\{e_{1},e_{2},\ldots,e_{t}\\}\subset\\{1,2,\ldots n\\}$ with
$e_{1}<e_{2}<\ldots<e_{t}$. Let $\lvert{\boldsymbol{c}}\rangle=\lvert
c_{1}c_{2}\ldots c_{t}\rangle$ be a pure quantum state with
${\boldsymbol{c}}\in\\{0,1\\}^{t}$. Define the operator
${\boldsymbol{A}}_{E,\langle c\rvert}^{n}=A_{1}\otimes
A_{2}\otimes\ldots\otimes A_{n}$ [31], where

$\displaystyle A_{j}=\begin{cases}\langle c_{i}\rvert\quad j=e_{i}\in E,\\\
{{\boldsymbol{I}}}\quad\quad j\notin E.\end{cases}$

######  Lemma 3.1 ([31], Lemma 3.1).

Let $t\geq 1$, $n\geq t$ be integers. Define the set
$E=\\{e_{1},e_{2},\ldots,e_{t}\\}\subset\\{1,2,\ldots n\\}$ with
$e_{1}<e_{2}<\ldots<e_{t}$. Let $\lvert{\boldsymbol{c}}\rangle=\lvert
c_{1}c_{2}\ldots c_{t}\rangle$ be a pure quantum state with $(c_{1}c_{2}\ldots
c_{t})\in\\{0,1\\}^{t}$. Then,

$\displaystyle{\boldsymbol{A}}_{E,\langle{\boldsymbol{c}}\rvert}^{n}={\boldsymbol{A}}_{e_{1},\langle
c_{1}\rvert}^{n-t+1}{\boldsymbol{A}}_{e_{2},\langle
c_{2}\rvert}^{n-t+2}\ldots{\boldsymbol{A}}_{e_{t-1},\langle
c_{t-1}\rvert}^{n-1}{\boldsymbol{A}}_{e_{t},\langle c_{t}\rvert}^{n}.$

Lemma 3.1 can be easily proved by direct calculations. We are now in a
position to describe the Kraus decomposition of the deletion channel. First,
we cite another auxiliary result.

######  Lemma 3.2 ([31], Lemma 4.3).

Let $\rho\in S\left({\mathbb{C}}^{2\otimes n}\right)$ be a quantum state. The
output state after deleting the qubits on the positions labeled by the set
$E\subset\\{1,2,\ldots,n\\}$ can be expressed as

$\displaystyle
D_{E}^{n}(\rho)=\sum_{{\boldsymbol{c}}\in\\{0,1\\}^{t}}{\boldsymbol{A}}_{E,\langle{\boldsymbol{c}}\rvert}^{n}\rho{\boldsymbol{A}}_{E,\langle{\boldsymbol{c}}\rvert}^{n^{\dagger}}.$

Lemma 3.2 together with Definition 3.1 implies that the Kraus decomposition of
the quantum $t$-deletion channel is given by

$\displaystyle\operatorname{Del}_{t}^{N}(\rho)=\sum_{E,\boldsymbol{c}}p(E){\boldsymbol{A}}_{E,\langle\boldsymbol{c}|}^{n}\rho{\boldsymbol{A}}_{E,\langle\boldsymbol{c}|}^{n}{}^{\dagger},$

where $p(E)$ is a probability distribution.

It will be convenient to distinguish between two types of deletions.

######  Definition 3.2.

(Deletion operators) A $0$-type deletion applied to the $i$-th qubit is the
operator ${\boldsymbol{F}}_{i}:={\boldsymbol{A}}_{i,\langle 0\rvert}^{n}$.
Likewise, a $1$-type deletion is the operator
${\boldsymbol{G}}_{i}:={\boldsymbol{A}}_{i,\langle 1\rvert}^{n}.$ In other
words, given ${\boldsymbol{x}}\in\\{0,1\\}^{n}$ the action of these operators
on the state $\lvert{\boldsymbol{x}}\rangle$ is

$\displaystyle{\boldsymbol{F}}_{i}\lvert{\boldsymbol{x}}\rangle=\langle
0\,|\,\mathopen{}x_{i}\rangle\lvert{\boldsymbol{x}}^{\prime}\rangle\quad\text{and}\quad{\boldsymbol{G}}_{i}\lvert{\boldsymbol{x}}\rangle=\langle
1\,|\,\mathopen{}x_{i}\rangle\lvert{\boldsymbol{x}}^{\prime}\rangle,$

where $\lvert{\boldsymbol{x}}^{\prime}\rangle=\lvert x_{1}\ldots
x_{i-1}x_{i+1}\ldots x_{n}\rangle$.

In the next lemma, we show how these deletion operators transform Dicke
states.

######  Lemma 3.3.

Let $\lvert D_{w}^{n}\rangle$ be a Dicke state and let
$a\in\\{0,1,\dots,n\\}.$ Then for any $i=1,\dots,n$

$\displaystyle({\boldsymbol{F}}_{i})^{a}\lvert
D^{n}_{w}\rangle=\sqrt{\frac{\binom{n-a}{w}}{\binom{n}{w}}}\;\lvert
D^{n-a}_{w}\rangle$ $\displaystyle({\boldsymbol{G}}_{i})^{a}\lvert
D^{n}_{w}\rangle=\sqrt{\frac{\binom{n-a}{w-a}}{\binom{n}{w}}}\;\lvert
D^{n-a}_{w-a}\rangle,$

where by definition $\binom{n}{k}=0$ if $n<k$ or $k<0$.

###### Proof.

Acting by ${\boldsymbol{F}}_{i}$ on the state $\lvert
H^{n}_{w}\rangle=\sum_{{\boldsymbol{x}}:|{\boldsymbol{x}}|=w}\lvert{\boldsymbol{x}}\rangle$
annihilates the terms $\lvert{\boldsymbol{x}}\rangle$ with $x_{i}=1$ and
deletes one zero from the states $\lvert{\boldsymbol{x}}\rangle$ with
$x_{i}=0$. Thus, the only retained states are those with $x_{i}=0$, and

${\boldsymbol{F}}_{i}\lvert H^{n}_{w}\rangle=\lvert H^{n-1}_{w}\rangle.$

Likewise,

${\boldsymbol{G}}_{i}\lvert H^{n}_{w}\rangle=\lvert H^{n-1}_{w-1}\rangle,$

for any $i=1,\ldots,n$. The full claim now follows by induction. ∎

By the nature of permutation-invariant states, the statements we make below in
the paper do not depend on the location of the deleted qubit, and we write
$0$-type and $1$-type deletions simply as ${\boldsymbol{F}},{\boldsymbol{G}}$,
omitting the subscript $i$ from the notation.

Lemmas 3.1, 3.2, and 3.3 imply that the Kraus set of the $t$-deletion channel
for a permutation-invariant code has the form
$\\{{\boldsymbol{G}}^{i}{\boldsymbol{F}}^{t-i}:i\in\\{0,1,\ldots,t\\}\\}.$
Throughout the paper, we will denote the $t$-deletion error set for a
permutation-invariant code as

(4)
$\displaystyle\varepsilon_{t}=\\{{\mathbb{E}}_{0},{\mathbb{E}}_{1},\ldots,{\mathbb{E}}_{t}\\},$

where ${\mathbb{E}}_{i}={\boldsymbol{G}}^{i}{\boldsymbol{F}}^{t-i}$. The
following lemma describes the action of the error operator
${\mathbb{E}}_{a}\in\varepsilon_{t}$ on a permutation-invariant state.

######  Lemma 3.4.

Let ${\mathbb{E}}_{a}$ be an element of the Kraus set of the $t$-deletion
channel $\varepsilon_{t}$ for a permutation-invariant code. Then, for any
permutation-invariant state $\lvert D^{n}_{w}\rangle$,

$\displaystyle{\mathbb{E}}_{a}\lvert
D^{n}_{w}\rangle=\sqrt{\frac{\binom{n-t}{w-a}}{\binom{n}{w}}}\lvert
D^{n-t}_{w-a}\rangle.$

###### Proof.

By Lemma 3.3,

$\displaystyle{\mathbb{E}}_{a}\lvert
D^{n}_{w}\rangle={\boldsymbol{G}}^{a}{\boldsymbol{F}}^{t-a}\lvert
D^{n}_{w}\rangle$
$\displaystyle=\sqrt{\frac{\binom{n-t+a}{w}}{\binom{n}{w}}}{\boldsymbol{G}}^{a}\lvert
D^{n-t+a}_{w}\rangle$
$\displaystyle=\sqrt{\frac{\binom{n-t+a}{w}}{\binom{n}{w}}}\sqrt{\frac{\binom{n-t+a-a}{w-a}}{\binom{n-t+a}{w}}}\lvert
D^{n-t+a-a}_{w-a}\rangle$
$\displaystyle=\sqrt{\frac{\binom{n-t}{w-a}}{\binom{n}{w}}}\lvert
D^{n-t}_{w-a}\rangle.$

∎

We make an important observation: Upon applying a deletion error to a
permutation-invariant state, we obtain a permutation-invariant state (on fewer
qubits). Clearly, this does not hold for Pauli errors: for instance,

${\boldsymbol{X}}_{1}\lvert D^{3}_{1}\rangle=\frac{\lvert 101\rangle+\lvert
110\rangle+\lvert 000\rangle}{\sqrt{3}},$

which is not permutation-invariant. Moreover, generally $X_{i}\lvert
D_{w}^{n}\rangle\neq X_{j}\lvert D_{w}^{n}\rangle$ if $i\neq j$, so the Kraus
set for Pauli errors is much larger than for deletions, complicating the
analysis. A workaround proposed in [26] suggests averaging Pauli errors, but
general constructions look difficult. At the same time, invariance with
respect to permutations plays the defining role for deletions, and it is also
the main property supporting the code construction we propose. We note that
given a deletion-correcting permutation-invariant code, we can argue about its
distance and make claims about its properties with respect to correcting Pauli
errors. Indeed, the following proposition is true.

######  Proposition 3.5.

A permutation-invariant code that corrects $2t$ deletions, also corrects all
combinations of $t$ Pauli errors.

###### Proof.

For a permutation-invariant state, deleting any $2t$ qubits is equivalent to
deleting the first $2t$ qubits in an $n$-qubit state, so deletions are
equivalent to erasures. Of course, a code that corrects $2t$ erasures has the
quantum distance of at least 2$t+1$ (see, e.g., [27]). Thus, correcting
deletions is tied to the code distance, and distance $d=2t+1$ is a sufficient
condition for correcting $t$ qubit errors. ∎

##  4\. Error correction conditions for permutation-invariant codes

Sufficient conditions for any code to correct $t$ deletions were previously
derived in [30]. In this section, we focus on permutation-invariant codes and
derive the necessary and sufficient conditions for such a code to correct
deletions by showing the equivalence between them and the Knill–Laflamme
conditions for the $2t$-deletion channel. By Proposition 3.5, this also
implies that they correct $t$ qubit errors.

######  Theorem 4.1.

Let ${\mathscr{C}}$ be a permutation-invariant quantum error correction code
as given in Definition 2.3, and suppose that the coefficients $\alpha_{j}$ and
$\beta_{j}$, $j=1,\dots,n$ in the codewords (1) are real. Then the code
${\mathscr{C}}$ corrects all $t$-qubit errors if and only if its coefficient
vectors $\boldsymbol{\alpha}=(\alpha_{0},\alpha_{1},\ldots,\alpha_{n})$ and
$\boldsymbol{\beta}=(\beta_{0},\beta_{1},\ldots,\beta_{n})$ satisfy the
following conditions:

$\displaystyle\text{\rm(C1)}\quad\sum_{j=0}^{n}\alpha_{j}\beta_{j}=0;$
$\displaystyle\text{\rm(C2)}\quad\sum_{j=0}^{n}\alpha_{j}^{2}=\sum_{j=0}^{n}\beta_{j}^{2}=1;$
$\displaystyle\text{\rm(C3) \;For all $0\leq a,b\leq 2t$},$
$\displaystyle\hskip
72.26999pt\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\alpha_{j+a}\beta_{j+b}=0;$
$\displaystyle\text{\rm(C4) \;For all $0\leq a,b\leq 2t$},$
$\displaystyle\hskip
72.26999pt\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\left(\alpha_{j+a}\alpha_{j+b}-\beta_{j+a}\beta_{j+b}\right)=0.$

###### Proof.

Since the Dicke states are orthonormal by construction, conditions (C1), (C2)
are required for the codewords
$\lvert{\boldsymbol{c}}_{0}\rangle,\lvert{\boldsymbol{c}}_{1}\rangle$ to form
orthonormal states. We will argue that conditions (C3) and (C4) are equivalent
to the Knill–Laflamme conditions for the $2t$-deletion channel. By Proposition
3.5 this suffices to prove the theorem.

Recall the form of the Kraus set of the $2t$-deletion channel (4). By (1) and
Lemma 3.4, we have

$\displaystyle{\mathbb{E}}_{a}\lvert{\boldsymbol{c}}_{0}\rangle=\sum_{j=0}^{n}\alpha_{j}\sqrt{\frac{\binom{n-2t}{j-a}}{\binom{n}{j}}}\lvert
D^{n-2t}_{j-a}\rangle,$
$\displaystyle{\mathbb{E}}_{a}\lvert{\boldsymbol{c}}_{1}\rangle=\sum_{j=0}^{n}\beta_{j}\sqrt{\frac{\binom{n-2t}{j-a}}{\binom{n}{j}}}\lvert
D^{n-2t}_{j-a}\rangle.$

To show the equivalence of (C3) and (2), we compute

$\displaystyle\langle{\boldsymbol{c}}_{0}\rvert{\mathbb{E}}_{a}^{\dagger}{\mathbb{E}}_{b}\lvert{\boldsymbol{c}}_{1}\rangle$
$\displaystyle=\sum_{j=0}^{n}\sum_{j^{\prime}=0}^{n}\alpha_{j}\beta_{j^{\prime}}\sqrt{\frac{\binom{n-2t}{j-a}\binom{n-2t}{j^{\prime}-b}}{\binom{n}{j}\binom{n}{j^{\prime}}}}\langle
D^{n-2t}_{j-a}\,|\,\mathopen{}D^{n-2t}_{j^{\prime}-b}\rangle$
$\displaystyle=\sum_{j=0}^{n}\sum_{j^{\prime}=0}^{n}\alpha_{j}\beta_{j^{\prime}}\sqrt{\frac{\binom{n-2t}{j-a}\binom{n-2t}{j^{\prime}-b}}{\binom{n}{j}\binom{n}{j^{\prime}}}}\delta_{j-a,j^{\prime}-b}$
$\displaystyle=\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\alpha_{j+a}\beta_{j+b}$

for all $0\leq a,b\leq 2t$. Turning to condition (C4), we find

$\displaystyle\langle{\boldsymbol{c}}_{0}\rvert{\mathbb{E}}_{a}^{\dagger}{\mathbb{E}}_{b}\lvert{\boldsymbol{c}}_{0}\rangle-\langle{\boldsymbol{c}}_{1}\rvert{\mathbb{E}}_{a}^{\dagger}{\mathbb{E}}_{b}\lvert{\boldsymbol{c}}_{1}\rangle$
$\displaystyle=\sum_{j=0}^{n}\sum_{j^{\prime}=0}^{n}\sqrt{\frac{\binom{n-2t}{j-a}\binom{n-2t}{j^{\prime}-b}}{\binom{n}{j}\binom{n}{j^{\prime}}}}\left(\alpha_{j}\alpha_{j^{\prime}}-\beta_{j}\beta_{j^{\prime}}\right)\langle
D^{n-2t}_{j-a}\,|\,\mathopen{}D^{n-2t}_{j^{\prime}-b}\rangle$
$\displaystyle=\sum_{j=0}^{n}\sum_{j^{\prime}=0}^{n}\sqrt{\frac{\binom{n-2t}{j-a}\binom{n-2t}{j^{\prime}-b}}{\binom{n}{j}\binom{n}{j^{\prime}}}}\left(\alpha_{j}\alpha_{j^{\prime}}-\beta_{j}\beta_{j^{\prime}}\right)\delta_{j-a,j^{\prime}-b}$
$\displaystyle=\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\left(\alpha_{j+a}\alpha_{j+b}-\beta_{j+a}\beta_{j+b}\right)$

for all $0\leq a,b\leq 2t$, and thus (C4) is equivalent to (3). Together with
Proposition 3.5 this proves the theorem. ∎

##  5\. A new family of permutation-invariant Codes

In this section, we present a new family of permutation-invariant codes,
defined by the parameters $g,m$, and $\delta$. Here, $g$ is the gap parameter,
$m$ is the occupancy number, and $\delta$ is an auxiliary parameter to adjust
the code length. The code we construct encodes one logical qubit into
$n=2gm+\delta+1$ physical qubits. The following combinatorial identities,
proved in Appendix A, will play a role in the construction.

######  Lemma 5.1.

Let $n,g,m,a,r$ be integers such that $g>0$ and $0\leq a\leq r\leq 2m<n/g$.
Then

(5)
$\displaystyle\sum_{l=0}^{m}(-1)^{l}\frac{\binom{m}{l}}{\binom{n/g-l}{m+1}}\Big{[}\frac{\binom{n-r}{gl-a}}{\binom{n}{gl}}-\frac{\binom{n-r}{gl-r+a}}{\binom{n}{gl}}\Big{]}=0.$

######  Lemma 5.2.

For any real $x$ and integer $m$ such that $x>m>0,$

(6)
$\sum_{l=0}^{m}\frac{\binom{m}{l}}{\binom{2x-l}{m+1}}=\binom{x}{m}^{-1}\frac{(m+1)}{2(x-m)}.$

######  Construction 5.1.

Let $g,m,\delta$ be nonnegative integers. Define a $(g,m,\delta)$ permutation-
invariant code ${\mathcal{Q}}_{g,m,\delta}$ via its logical computational
basis

$\displaystyle\lvert{\boldsymbol{c}}_{0}\rangle=\sum_{\begin{subarray}{c}\text{$l$
{\rm even}}\\\ 0\leq l\leq m\end{subarray}}\gamma b_{l}\lvert
D^{n}_{gl}\rangle+\sum_{\begin{subarray}{c}\text{$l$ {\rm odd}}\\\ 0\leq l\leq
m\end{subarray}}\gamma b_{l}\lvert D^{n}_{n-gl}\rangle,$
$\displaystyle\lvert{\boldsymbol{c}}_{1}\rangle=\sum_{\begin{subarray}{c}\text{$l$
{\rm odd}}\\\ 0\leq l\leq m\end{subarray}}\gamma b_{l}\lvert
D^{n}_{gl}\rangle-\sum_{\begin{subarray}{c}\text{$l$ {\rm even}}\\\ 0\leq
l\leq m\end{subarray}}\gamma b_{l}\lvert D^{n}_{n-gl}\rangle,$

where $n=2gm+\delta+1,$ $b_{l}=\sqrt{{\binom{m}{l}}/{\binom{n/g-l}{m+1}}},$
and $\gamma=\sqrt{\binom{n/(2g)}{m}\frac{n-2gm}{g(m+1)}}$ is the normalizing
factor.

The next theorem establishes the error correction properties of the code
${\mathcal{Q}}_{g,m,\delta}$.

######  Theorem 5.3.

Let $t$ be a nonnegative integer and let $g\geq 2t$, $m\geq t$, and
$\delta\geq 2t$. Then the code ${\mathcal{Q}}_{m,l,\delta}$ encodes one qubit
into $n=2gm+\delta+1$ qubits and corrects any $t$ qubit errors.

###### Proof.

We need to prove that the coefficients
$\boldsymbol{\alpha},\boldsymbol{\beta}$ of the basis states satisfy
conditions (C1)-(C4). Writing these coefficients explicitly, we obtain

$\displaystyle\alpha_{j}=\sum_{\begin{subarray}{c}\text{$l$ even}\\\ 0\leq
l\leq m\end{subarray}}f(l)\delta_{j,gl}+\sum_{\begin{subarray}{c}\text{$l$
odd}\\\ 0\leq l\leq m\end{subarray}}f(l)\delta_{j,n-gl},$
$\displaystyle\beta_{j}=\sum_{\begin{subarray}{c}\text{$l$ odd}\\\ 0\leq l\leq
m\end{subarray}}f(l)\delta_{j,gl}-\sum_{\begin{subarray}{c}\text{$l$ even}\\\
0\leq l\leq m\end{subarray}}f(l)\delta_{j,n-gl},$

where $f(l)=\gamma b_{l}$. Throughout the proof, all the sums on $l$ are taken
over $l=0,1,\dots,m$. We start with

$\alpha_{j}\beta_{j}=\sum_{\text{ $l$ even}}\sum_{\text{
$l^{\prime}$odd}}f(l)f(l^{\prime})\delta_{gl,gl^{\prime}}\delta_{j,gl}-\sum_{\text{
$l$ even}}\sum_{\text{ $l^{\prime}$
even}}f(l)f(l^{\prime})\delta_{gl,n-gl^{\prime}}\delta_{j,gl}\\\ +\sum_{\text{
$l$ odd}}\sum_{\text{ $l^{\prime}$
odd}}f(l)f(l^{\prime})\delta_{n-gl,gl^{\prime}}\delta_{j,n-gl}-\sum_{\text{
$l$ odd}}\sum_{\text{ $l^{\prime}$
even}}f(l)f(l^{\prime})\delta_{n-gl,n-gl^{\prime}}\delta_{j,n-gl},$

where we use the fact $\delta_{jk}\delta_{jl}=\delta_{jl}\delta_{kl}$. The
first sum in this expression is clearly zero since $gl\neq gl^{\prime}$ if $l$
is even and $l^{\prime}$ is odd, and thus $\delta_{gl,gl^{\prime}}=0.$.
Turning to the second sum, now $l$ and $l^{\prime}$ are even. It is easy to
see that $n=2gm+\delta+1\neq g(l+l^{\prime})$ since $l+l^{\prime}\leq 2m,$ and
so $\delta_{gl,n-gl^{\prime}}=0$, and the second sum is zero. The third and
fourth sums are treated as the first and second, respectively, and they are
easily seen to be zero. This shows that condition (C1) holds.

To check condition (C2), write

$\alpha_{j}^{2}=\sum_{\text{$l$ even}}\sum_{\text{ $l^{\prime}$
even}}f(l)f(l^{\prime})\delta_{gl,gl^{\prime}}\delta_{j,gl}+\sum_{\text{ $l$
even}}\sum_{\text{ $l^{\prime}$
odd}}f(l)f(l^{\prime})\delta_{gl,n-gl^{\prime}}\delta_{j,gl}\\\ +\sum_{\text{
$l$ odd}}\sum_{\text{ $l^{\prime}$
even}}f(l)f(l^{\prime})\delta_{n-gl,gl^{\prime}}\delta_{j,n-gl}+\sum_{\text{
$l$ odd}}\sum_{\text{ $l^{\prime}$
odd}}f(l)f(l^{\prime})\delta_{n-gl,n-gl^{\prime}}\delta_{j,n-gl}.$

Notice that the second and third sums are zero since $n=2gm+\delta+1\neq
g(l+l^{\prime})$ for any $l,l^{\prime}\leq m$. The first sum is not 0 only if
$l=l^{\prime}$, and therefore it can be written as $\sum_{\text{ $l$
even}}f(l)^{2}\delta_{j,gl}$. Similarly, the fourth sum can be expressed as
$\sum_{\text{ $l$ odd}}f(l)^{2}\delta_{j,n-gl}$. Hence,

$\displaystyle\sum_{j=0}^{n}\alpha_{j}^{2}$
$\displaystyle=\sum_{j=0}^{n}\Big{(}\sum_{\text{$l$
even}}f(l)^{2}\delta_{j,gl}+\sum_{\text{$l$
odd}}f(l)^{2}\delta_{j,n-gl}\Big{)}=\sum_{l=0}^{m}f(l)^{2}$
$\displaystyle=\gamma^{2}\sum_{l=0}^{m}b_{l}^{2}=1,$

where we used Lemma 5.2. A similar sequence of steps confirms that
$\sum_{j=0}^{n}\beta_{j}^{2}=1,$ and thus condition (C2) is also satisfied.

For condition $(C3)$, let us first evaluate the term

$\displaystyle\begin{multlined}\alpha_{j+a}\beta_{j+b}=\sum_{\text{ $l$
even}}\sum_{\text{ $l^{\prime}$
odd}}f(l)f(l^{\prime})\delta_{gl-a,gl^{\prime}-b}\delta_{j,gl-a}-\sum_{\text{
$l$ even}}\sum_{\text{ $l^{\prime}$
even}}f(l)f(l^{\prime})\delta_{gl-a,n-gl^{\prime}-b}\delta_{j,gl-a}\\\
+\sum_{\text{ $l$ odd}}\sum_{\text{
$l^{\prime}$odd}}f(l)f(l^{\prime})\delta_{n-gl-a,gl^{\prime}-b}\delta_{j,n-gl-a}-\sum_{\text{
$l$ odd}}\sum_{\text{
$l^{\prime}$even}}f(l)f(l^{\prime})\delta_{n-gl-a,n-gl^{\prime}-b}\delta_{j,n-gl^{\prime}-b}.\end{multlined}\alpha_{j+a}\beta_{j+b}=\sum_{\text{
$l$ even}}\sum_{\text{ $l^{\prime}$
odd}}f(l)f(l^{\prime})\delta_{gl-a,gl^{\prime}-b}\delta_{j,gl-a}-\sum_{\text{
$l$ even}}\sum_{\text{ $l^{\prime}$
even}}f(l)f(l^{\prime})\delta_{gl-a,n-gl^{\prime}-b}\delta_{j,gl-a}\\\
+\sum_{\text{ $l$ odd}}\sum_{\text{
$l^{\prime}$odd}}f(l)f(l^{\prime})\delta_{n-gl-a,gl^{\prime}-b}\delta_{j,n-gl-a}-\sum_{\text{
$l$ odd}}\sum_{\text{
$l^{\prime}$even}}f(l)f(l^{\prime})\delta_{n-gl-a,n-gl^{\prime}-b}\delta_{j,n-gl^{\prime}-b}.$

First, observe that the second sum is zero. To see this, recall that
$\delta\geq 2t$, $l+l^{\prime}\leq 2m$, and $b-a\leq 2t$. Therefore,
$g(l+l^{\prime})+b-a\leq 2gm+2t<2gm+\delta+1=n$. Similarly, the third sum is
also zero. For the first sum to be nonzero, it should be that
$g(l-l^{\prime})=a-b.$ If $g>2t$, then $|l-l^{\prime}|\geq 1$ and $|a-b|\leq
2t$, so this condition cannot be fulfilled. The equality $g(l-l^{\prime})=a-b$
is possible only if $g=2t$ and $a-b=\pm 2t$, equivalently $l^{\prime}=l\mp 1$.
By the same argument, the fourth sum is not 0 only if $g=2t$ and $a-b=\pm 2t$,
hence $l^{\prime}=l\pm 1$. Therefore, the first sum can be written as
$\sum_{\text{$l$ even}}f(l)f(l\mp 1)\delta_{j,gl-a}$, while the fourth sum can
be written as $\sum_{\text{$l$ even}}f(l)f(l\mp 1)\delta_{j,n-gl-b}$. Hence,
we have

$\displaystyle\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\alpha_{j+a}\beta_{j+b}$
$\displaystyle=\sum_{\text{$l$ even}}f(l)f(l\mp
1)\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\left(\delta_{j,gl-a}-\delta_{j,n-gl-b}\right)$
$\displaystyle=\sum_{\text{$l$ even}}f(l)f(l\mp
1)\biggl{(}\frac{\binom{n-2t}{gl-a}}{\sqrt{\binom{n}{gl}\binom{n}{gl+b-a}}}-\frac{\binom{n-2t}{n-gl-b}}{\sqrt{\binom{n}{n-gl-b+a}\binom{n}{n-gl}}}\biggr{)}$
$\displaystyle=\sum_{\text{$l$ even}}f(l)f(l\mp
1)\biggl{(}\frac{\binom{n-2t}{gl-a}}{\sqrt{\binom{n}{gl}\binom{n}{gl+b-a}}}-\frac{\binom{n-2t}{gl+b-2t}}{\sqrt{\binom{n}{gl+b-a}\binom{n}{gl}}}\biggr{)}.$

Now, observe that we have two different cases: either $a=0$ and $b=2t$, or
$a=2t$ and $b=0$. For both of them, the difference inside the parentheses is
zero, meaning that we have proved condition (C3).

Finally, consider condition $(C4).$ Let us start with evaluating the term

$\alpha_{j+a}\alpha_{j+b}=\sum_{\text{
$l$even}}\sum_{\text{$l^{\prime}$even}}f(l)f(l^{\prime})\delta_{gl-a,gl^{\prime}-b}\delta_{j,gl-a}+\sum_{\text{$l$even}}\sum_{\text{$l^{\prime}$
odd}}f(l)f(l^{\prime})\delta_{gl-a,n-gl^{\prime}-b}\delta_{j,gl-a}\\\
+\sum_{\text{ $l$ odd}}\sum_{\text{ $l^{\prime}$
odd}}f(l)f(l^{\prime})\delta_{n-gl-a,n-gl^{\prime}-b}\delta_{j,n-gl-a}\\\
+\sum_{\text{ $l$ odd}}\sum_{\text{ $l^{\prime}$
even}}f(l)f(l^{\prime})\delta_{n-gl-a,gl^{\prime}-b}\delta_{j,n-gl-a}.$

First, recall that $\delta\geq 2t,$ $l+l^{\prime}\leq 2m$ and $|b-a|\leq 2t$.
Therefore, the second sum is zero since $g(l+l^{\prime})+b-a\leq
2gm+2t<2gm+\delta+1=n,$ and the fourth sum is zero by a similar argument. For
the first sum to be nonzero, for both $l$ and $l^{\prime}$ even, the equality
$g(l-l^{\prime})=a-b$ should hold. Since $a-b\leq 2t$ and $g\geq 2t$, it can
hold only when $a=b$ and $l=l^{\prime}$. As before, what remains of the sum is
the diagonal, and it can be written as $\sum_{\text{$l$
even}}f(l)^{2}\delta_{j,gl-a}$. For the same reasons, the third sum degrades
to $\sum_{\text{$l$ odd}}f(l)^{2}\delta_{j,n-gl-a}$, which yields

$\displaystyle\alpha_{j+a}\alpha_{j+b}=\sum_{\text{ $l$
even}}f(l)^{2}\delta_{j,gl-a}+\sum_{\text{ $l$
odd}}f(l)^{2}\delta_{j,n-gl-a}.$

By following similar steps, we find that

$\displaystyle\beta_{j+a}\beta_{j+b}=\sum_{\text{ $l$
even}}f(l)^{2}\delta_{j,n-gl-a}+\sum_{\text{ $l$
odd}}f(l)^{2}\delta_{j,gl-a}.$

In summary, we have

$\displaystyle\alpha_{j+a}\alpha_{j+b}-\beta_{j+a}\beta_{j+b}=\sum_{l=0}^{m}(-1)^{l}f(l)^{2}\biggl{(}\delta_{j,gl-a}-\delta_{j,n-gl-a}\biggr{)}.$

Then, recalling that $a=b$, the expression in condition $(C4)$ has the form

$\displaystyle\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\left(\alpha_{j+a}\alpha_{j+b}-\beta_{j+a}\beta_{j+b}\right)$
$\displaystyle=\sum_{l=0}^{m}(-1)^{l}f(l)^{2}\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\binom{n}{j+a}}\left(\delta_{j,gl-a}-\delta_{j,n-gl-a}\right)$
$\displaystyle=\gamma^{2}\sum_{l=0}^{m}(-1)^{l}\frac{\binom{m}{l}}{\binom{n/g-l}{m+1}}\left(\frac{\binom{n-2t}{gl-a}}{\binom{n}{gl}}-\frac{\binom{n-2t}{gl-2t+a}}{\binom{n}{gl}}\right),$

which is zero by Lemma 5.1.

The proof is now complete. ∎

######  Example 2.

The permutation-invariant code ${\mathcal{Q}}_{2,1,2}$ with logical codewords

(8) $\displaystyle\lvert{\boldsymbol{c}}_{0}\rangle=\sqrt{\frac{3}{10}}\lvert
D^{7}_{0}\rangle+\sqrt{\frac{7}{10}}\lvert
D^{7}_{5}\rangle\quad\text{and}\quad\lvert{\boldsymbol{c}}_{1}\rangle=\sqrt{\frac{7}{10}}\lvert
D^{7}_{2}\rangle-\sqrt{\frac{3}{10}}\lvert D^{7}_{7}\rangle$

has the same length as the $7$-qubit permutation-invariant code of [26], and
it can correct a single error.

######  Example 3.

The permutation-invariant code ${\mathcal{Q}}_{4,2,4}$ code with logical
codewords

$\displaystyle\lvert{\boldsymbol{c}}_{0}\rangle=\sqrt{\frac{5}{68}}\lvert
D^{21}_{0}\rangle+\sqrt{\frac{7}{12}}\lvert
D^{21}_{8}\rangle+\sqrt{\frac{35}{102}}\lvert D^{21}_{17}\rangle,$
$\displaystyle\lvert{\boldsymbol{c}}_{1}\rangle=\sqrt{\frac{35}{102}}\lvert
D^{21}_{4}\rangle-\sqrt{\frac{7}{12}}\lvert
D^{21}_{13}\rangle-\sqrt{\frac{5}{68}}\lvert D^{21}_{21}\rangle$

has length 21 and is the shorter than all currently known permutation-
invariant codes that correct double errors.

###  5.1. Deletion Correction Property

We already know that the code ${\mathcal{Q}}_{g,m,\delta}$ corrects deletions.
A precise formulation of this claim is given in the following proposition.

######  Proposition 5.4.

Let $s$ be a nonnegative integer and let $g\geq
s,m\geq\lceil\frac{s}{2}\rceil$, and $\delta\geq s$. Then the code
${\mathcal{Q}}_{g,m,\delta}$ corrects all patterns of $s$ deletions.

This claim follows from the fact that conditions (C3) and (C4) are equivalent
to the Knill–Laflamme conditions for correcting $2t$ deletions when they are
phrased for a permutation-invariant code.

For an odd number of deletions, the shortest code ${\mathcal{Q}}_{g,m,\delta}$
has length $(s+1)^{2}$. This coincides with the length of Ouyang’s gnu codes,
although the code families are different. For any even number of deletions
$>0$, the code ${\mathcal{Q}}_{g,m,\delta},$ where $(g,m,\delta)=(s,\lceil
s/2\rceil,s),$ has length $(s+1)^{2}-s$, which is shorter than the existing
constructions.

In [18], Nakayama and Hagiwara showed that the smallest length of single
quantum deletion-correcting codes is $4$. They also constructed a code that
meets this bound with equality. We note that code ${\mathcal{Q}}_{1,1,1}$
gives another construction of an optimal code correcting one deletion. Its
logical codewords are

$\displaystyle\lvert{\boldsymbol{c}}_{0}\rangle$
$\displaystyle=\sqrt{\frac{1}{3}}\lvert
0000\rangle+\sqrt{\frac{1}{6}}\left(\lvert 1110\rangle+\lvert
1101\rangle+\lvert 1011\rangle+\lvert 0111\rangle\right),$
$\displaystyle\lvert{\boldsymbol{c}}_{1}\rangle$
$\displaystyle=\sqrt{\frac{1}{6}}\left(\lvert 0001\rangle+\lvert
0010\rangle+\lvert 0100\rangle+\lvert
1000\rangle\right)-\sqrt{\frac{1}{3}}\lvert 1111\rangle.$

##  6\. Spontaneous Decay Errors

In this section, we show that the codes constructed in Sec. 5 correct errors
of a different kind, arising from spontaneous photon emission.

###  6.1. Basics of the amplitude damping channel

This channel model arises from an approximation of noisy evolution in many
physical systems. One of them is the process in which an excited electron
decays to its ground state, resulting in the emission of a photon. Say that
the ground state is $\lvert 0\rangle$ and the excited state is $\lvert
1\rangle$, and let the probability of decay be $p$, which is assumed to be
small. Then, the behavior of this noise process on a single qubit system can
be defined by the quantum channel

(9)
$\displaystyle{{\mathcal{E}}}_{p}(\rho)={\boldsymbol{A}}_{0}\rho{\boldsymbol{A}}_{0}^{\dagger}+{\boldsymbol{A}}_{1}\rho{\boldsymbol{A}}_{1}^{\dagger},$

where

$\displaystyle{\boldsymbol{A}}_{0}=\begin{bmatrix}1&0\\\
0&\sqrt{1-p}\end{bmatrix},\quad{\boldsymbol{A}}_{1}=\begin{bmatrix}0&\sqrt{p}\\\
0&0\end{bmatrix}.$

We clearly have ${\boldsymbol{A}}_{0}\lvert 0\rangle=\lvert
0\rangle,{\boldsymbol{A}}_{0}\lvert 1\rangle=\sqrt{1-p}\lvert 1\rangle$ and
${\boldsymbol{A}}_{1}\lvert 0\rangle=0,{\boldsymbol{A}}_{1}\lvert
1\rangle=\sqrt{p}\lvert 0\rangle.$ Because of this, this channel model is
called the amplitude damping channel [5], [34, Sec.4.4]. The action of
${\mathcal{E}}_{p}$ can be extended naturally to $n$-qubit systems by assuming
that spontaneous decay affects independently each of the qubits in the
superposition. We denote the $n$-qubit amplitude damping channel by
${{\mathcal{E}}}_{p}^{\otimes n}.$ The Kraus set of this channel has the form
${{\mathcal{K}}}_{{{\mathcal{E}}}_{p}^{\otimes
n}}=\\{\otimes_{i=1}^{n}{\boldsymbol{K}}_{i}:{\boldsymbol{K}}_{i}\in\\{{\boldsymbol{A}}_{0},{\boldsymbol{A}}_{1}\\}\\}$.
Let us further introduce the set of amplitude damping errors of multiplicity
$t$,

(10)
$\displaystyle\epsilon_{p,t}:=\\{{\boldsymbol{K}}\in{{\mathcal{K}}}_{{{\mathcal{E}}}_{p}^{\otimes
n}}:|\operatorname{supp}({\boldsymbol{K}})|\leq t\\},$

where ${\boldsymbol{K}}:=\otimes_{i=1}^{n}{\boldsymbol{K}}_{i}$ and
$\operatorname{supp}({\boldsymbol{K}}):=\\{i\in\\{1,2,\ldots,n\\}:{\boldsymbol{K}}_{i}={\boldsymbol{A}}_{1}\\},$
calling it a truncated Kraus set of ${{\mathcal{E}}}_{p}^{\otimes n}$ [24].

In quantum coding theory, the problem of error correction is equivalent to
minimizing the worst-case error of a code after the recovery process. In other
words, let ${{\mathcal{E}}}$ be a quantum channel, let ${\mathscr{C}}$ be a
quantum code, and let ${{\mathcal{R}}}$ be the recovery operator that corrects
errors introduced by the channel. Then, the worst-case error is

$\displaystyle
E_{{{\mathcal{E}}},{\mathscr{C}}}({{\mathcal{R}}}):=\max_{\rho\in
S({\mathscr{C}})}\left[1-F(\rho,{{\mathcal{R}}}\circ{{\mathcal{E}}})\right],$

where $S({\mathscr{C}})=\\{\rho\in S({\mathbb{C}}^{q}):\sum_{\lvert
c\rangle\in{{\mathcal{B}}}}\langle c\rvert\rho\lvert c\rangle=1\\}$ (here
${{\mathcal{B}}}$ is an orthonormal basis of ${\mathscr{C}}$ and $q\geq 2$ is
an integer), and $F(\rho,{{\mathcal{R}}}\circ{{\mathcal{E}}})$ is the
entanglement fidelity, defined as

$\displaystyle
F(\rho,{{\mathcal{R}}}\circ{{\mathcal{E}}}):=\sum_{{\boldsymbol{A}}\in{{\mathcal{K}}}_{{{\mathcal{R}}}\circ{{\mathcal{E}}}}}|\operatorname{Tr}({\boldsymbol{A}}\rho)|^{2},$

where ${{\mathcal{K}}}_{{{\mathcal{R}}}\circ{{\mathcal{E}}}}$ is the Kraus set
of the channel ${{\mathcal{R}}}\circ{{\mathcal{E}}}$ [29], [34, p.228]. The
fidelity is a way to measure how close the recovered density matrix
${{\mathcal{R}}}\circ{{\mathcal{E}}}(\rho)$ is to the original matrix $\rho$.

With this, the error correction problem can be stated as the following min-max
problem:

$\displaystyle\inf_{{{\mathcal{R}}}}E_{{{\mathcal{E}}},{\mathscr{C}}}({{\mathcal{R}}})=\inf_{{{\mathcal{R}}}}\max_{\rho\in
S({\mathscr{C}})}\left[1-F(\rho,{{\mathcal{R}}}\circ{{\mathcal{E}}})\right].$

Following [20], we say that the code corrects $t$ amplitude damping errors if
there exist some positive constants $A$ and $p_{0}$ such that

(11) $\displaystyle\inf_{{{\mathcal{R}}}}E_{{{\mathcal{E}}}_{p}^{\otimes
n},{\mathscr{C}}}({{\mathcal{R}}})\leq Ap^{t+1}$

holds for all $p\in[0,p_{0}]$.

In this section, we quantify the error correction properties of the codes
$Q_{g,m,\delta}$. Our main result here is given in the following theorem.

######  Theorem 6.1.

Let $t$ be a nonnegative integer. Let $g\geq t+1$,
$m\geq\lceil\frac{3t}{2}\rceil$, and $\delta\geq t$. Then, the code
${\mathcal{Q}}_{m,l,\delta}$ corrects $t$ amplitude-damping errors.

The general tool for proving error correction in the sense of (11) is given in
the following theorem.

######  Theorem 6.2.

([20], Theorem 10) Let $\epsilon$ be a truncated Kraus set, and
${\boldsymbol{A}},{\boldsymbol{B}}\in\epsilon$. Let ${\mathscr{C}}$ be a code
with an orthonormal basis ${{\mathcal{B}}}$. If
$\eta=\frac{(|\epsilon|-1)|\epsilon|^{2}\Delta}{\lambda_{\min}({\boldsymbol{M}})}$,
then

(12)
$\displaystyle\inf_{{{\mathcal{R}}}}E_{{{\mathcal{E}}},{\mathscr{C}}}({{\mathcal{R}}})\leq
1-\frac{\operatorname{Tr}{\boldsymbol{M}}-|\epsilon|^{2}\Delta}{1+\eta},$

where

(13)
$\displaystyle{\boldsymbol{M}}:=\sum_{{\boldsymbol{A}},{\boldsymbol{B}}\in\epsilon}m_{{\boldsymbol{A}},{\boldsymbol{B}}}\lvert{\boldsymbol{A}}\rangle\langle{\boldsymbol{B}}\rvert,\quad
m_{{\boldsymbol{A}},{\boldsymbol{B}}}:=\frac{1}{|{{\mathcal{B}}}|}\sum_{\lvert
c_{i}\rangle\in{{\mathcal{B}}}}\langle
c_{i}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert c_{i}\rangle,$
(14)
$\displaystyle\Delta:=\max_{{\boldsymbol{A}},{\boldsymbol{B}}}\max_{i}{\boldsymbol{M}}_{{\boldsymbol{A}},{\boldsymbol{B}}}^{ii}+\left(|{{\mathcal{B}}}|-1\right)\max_{{\boldsymbol{A}},{\boldsymbol{B}}}\max_{\begin{subarray}{c}i,j\\\
i\neq
j\end{subarray}}{\boldsymbol{M}}_{{\boldsymbol{A}},{\boldsymbol{B}}}^{ij},$

where

(15)
$\displaystyle{\boldsymbol{M}}_{{\boldsymbol{A}},{\boldsymbol{B}}}:=\sum_{\lvert
c_{i}\rangle,\lvert c_{j}\rangle\in{{\mathcal{B}}}}\left(\langle
c_{i}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert c_{j}\rangle-
m_{{\boldsymbol{A}},{\boldsymbol{B}}}\delta_{\lvert c_{i}\rangle,\lvert
c_{j}\rangle}\right)\lvert c_{i}\rangle\langle c_{j}\rvert,$

and ${\boldsymbol{M}}^{ij}$ denotes the matrix element indexed by $i,j.$

Let ${{\mathcal{E}}}_{p}^{\otimes n}$ be the amplitude damping channel with
decay probability $p$ and let
$\epsilon_{p,t}\subset{{\mathcal{K}}}_{{{\mathcal{E}}}_{p}^{\otimes n}}$ be
the truncated Kraus set as defined in (10). The following lemma provides a
lower bound for the trace of matrix ${\boldsymbol{M}}$ in (13):

######  Lemma 6.3.

([20], Lemma 11) Let $p>0$ be a real number. Then

$\displaystyle\operatorname{Tr}{\boldsymbol{M}}\geq\lambda_{\min}\Big{(}\sum_{{\boldsymbol{A}}\in\epsilon_{p,t}}{\boldsymbol{A}}^{\dagger}{\boldsymbol{A}}\Big{)}\geq
1-\binom{n}{t+1}p^{t+1},$

where $\lambda_{\min}$ is the smallest eigenvalue of ${\boldsymbol{M}}.$

Define $a:=|\operatorname{supp}({\boldsymbol{A}})|$,
$b:=|\operatorname{supp}({\boldsymbol{B}})|$ and
$c:=|\operatorname{supp}({\boldsymbol{A}})\cup\operatorname{supp}({\boldsymbol{B}})|-a$.
The following lemma describes the action of amplitude damping errors on Dicke
states.

######  Lemma 6.4.

([20], Lemma 13) Let ${\boldsymbol{A}},{\boldsymbol{B}}\in\epsilon_{p,t}$.
Then

$\displaystyle\langle
D^{n}_{w}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{w}\rangle=p^{a}(1-p)^{w-a}\frac{\binom{n-c-a}{w-a}}{\binom{n}{w}}\delta_{a,b}.$

We will use this equality in the form

(16) $\displaystyle\langle
D^{n}_{w}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{w}\rangle=\sum_{k=0}^{w}(-1)^{k-a}\frac{\binom{w-a}{k-a}\binom{n-c-a}{w-a}}{\binom{n}{w}}p^{k}\delta_{a,b}.$

Let $\\{\lvert c_{+}\rangle,\lvert c_{-}\rangle\\}$ be the Hadamard basis of
the code ${\mathcal{Q}}_{g,m,\delta}$, namely $\lvert
c_{+}\rangle=\frac{\lvert c_{0}\rangle+\lvert c_{1}\rangle}{\sqrt{2}}$ and
$\lvert c_{-}\rangle=\frac{\lvert c_{0}\rangle-\lvert
c_{1}\rangle}{\sqrt{2}}$. The following lemma provides an upper bound for
$\Delta$ in (14).

######  Lemma 6.5.

Let ${\boldsymbol{A}},{\boldsymbol{B}}\in\epsilon_{p,t}$. Then, for all
$p\in(0,1),$

$\displaystyle\Delta\leq Cp^{2m-t+1},$

where111$[p^{k}](\cdot)$ refers to the coefficient of $p^{k}$ in the expansion
of the expression in the parentheses in powers of $p$.

(17) $\displaystyle C:=\max_{{\boldsymbol{A}},{\boldsymbol{B}}}\sum_{k\geq
2m-t+1}|[p^{k}]\langle
c_{+}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert c_{-}\rangle|.$

###### Proof.

We start with writing $m_{{\boldsymbol{A}},{\boldsymbol{B}}}$ in (13)
explicitly:

$\displaystyle m_{{\boldsymbol{A}},{\boldsymbol{B}}}=\frac{1}{2}\langle
c_{0}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
c_{0}\rangle+\frac{1}{2}\langle
c_{1}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert c_{1}\rangle.$

Observe that $\langle
c_{0}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
c_{1}\rangle=\langle
c_{1}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert c_{0}\rangle=0$
since $g\geq t+1$. Hence, the matrix
${\boldsymbol{M}}_{{\boldsymbol{A}},{\boldsymbol{B}}}$ in (15) can be written
as

$\displaystyle{\boldsymbol{M}}_{{\boldsymbol{A}},{\boldsymbol{B}}}$
$\displaystyle=\frac{\langle
c_{0}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
c_{0}\rangle-\langle
c_{1}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
c_{1}\rangle}{2}\left(\lvert c_{0}\rangle\langle c_{0}\rvert-\lvert
c_{1}\rangle\langle c_{1}\rvert\right)$ $\displaystyle=\langle
c_{+}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
c_{-}\rangle\left(\lvert c_{0}\rangle\langle c_{0}\rvert-\lvert
c_{1}\rangle\langle c_{1}\rvert\right).$

We obtain

(18) $\displaystyle\Delta=\max_{{\boldsymbol{A}},{\boldsymbol{B}}}|\langle
c_{+}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert c_{-}\rangle|.$

The ${\mathcal{Q}}_{g,m,\delta}$ code in Construction 5.1 can be written in
the Hadamard basis as follows:

$\displaystyle\lvert c_{+}\rangle=\sum_{l=0}^{m}\frac{\gamma
b_{l}}{\sqrt{2}}\lvert D^{n}_{gl}\rangle-\sum_{l=0}^{m}\frac{\gamma
b_{l}}{\sqrt{2}}(-1)^{l}\lvert D_{n-gl}^{n}\rangle$ $\displaystyle\lvert
c_{-}\rangle=\sum_{l=0}^{m}\frac{\gamma b_{l}}{\sqrt{2}}(-1)^{l}\lvert
D^{n}_{gl}\rangle+\sum_{l=0}^{m}\frac{\gamma b_{l}}{\sqrt{2}}\lvert
D_{n-gl}^{n}\rangle.$

Let $f(l)=(\gamma b_{l})/\sqrt{2}$. Then, the inner product

$\langle c_{+}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
c_{-}\rangle=\sum_{l=0}^{m}\sum_{l^{\prime}=0}^{m}f(l)f(l^{\prime})(-1)^{l^{\prime}}\langle
D^{n}_{gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{gl^{\prime}}\rangle\\\
+\sum_{l=0}^{m}\sum_{l^{\prime}=0}^{m}f(l)f(l^{\prime})\langle
D^{n}_{gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{n-gl^{\prime}}\rangle-\sum_{l=0}^{m}\sum_{l^{\prime}=0}^{m}f(l)f(l^{\prime})(-1)^{l+l^{\prime}}\langle
D^{n}_{n-gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{gl^{\prime}}\rangle\\\
+\sum_{l=0}^{m}\sum_{l^{\prime}=0}^{m}f(l)f(l^{\prime})(-1)^{l}\langle
D^{n}_{n-gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{n-gl^{\prime}}\rangle.$

Observe that $\langle
D^{n}_{gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{n-gl^{\prime}}\rangle=\langle
D^{n}_{n-gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{gl^{\prime}}\rangle=0$ since the weight of any state can decrease by at
most $t$ upon applying ${\boldsymbol{A}},{\boldsymbol{B}},$ and $n-gl-t\neq
gl^{\prime}$ for any $l,l^{\prime}$. To see this, recall that
$l+l^{\prime}\leq 2m$ and $\delta\geq t$, which yields $g(l+l^{\prime})+t\leq
2gm+t<2gm+\delta+1=n$. Furthermore, the inner products $\langle
D^{n}_{gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{gl^{\prime}}\rangle$ and $\langle
D^{n}_{n-gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{n-gl^{\prime}}\rangle$ are zero unless $l=l^{\prime},$ since $g\geq
t+1.$ Therefore, we obtain

(19) $\displaystyle\langle
c_{+}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
c_{-}\rangle=\sum_{l=0}^{m}f(l)^{2}(-1)^{l}\left(\langle
D^{n}_{gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{gl}\rangle-\langle
D^{n}_{n-gl}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert
D^{n}_{n-gl}\rangle\right).$

By combining (16) with (19) and interchanging the order of summation, we
obtain

$\displaystyle\langle
c_{+}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{B}}\lvert c_{-}\rangle$
$\displaystyle=\sum_{k\geq
0}(-1)^{k-a}p^{k}\sum_{l=0}^{m}(-1)^{l}\frac{f(l)^{2}}{\binom{n}{gl}}\Big{\\{}{\binom{gl-a}{k-a}\binom{n-c-a}{gl-a}}$
(20) $\displaystyle\hskip
21.68121pt-{\binom{n-gl-a}{k-a}\binom{n-c-a}{n-gl-a}}\Big{\\}}+\mathcal{O}(p^{gm+1}).$

Here we considered Kraus operators ${\boldsymbol{A}}$ and ${\boldsymbol{B}}$
such that
$|\operatorname{supp}({\boldsymbol{A}})|=|\operatorname{supp}({\boldsymbol{B}})|$.
Recall that $c,a\leq t,$ which together with Lemma 6.7 below implies that the
inner sum in (20) is zero for all $k\leq 2m-t.$ Now using (18) and (20)
completes the proof. ∎

We will borrow the following lemma from [20] with a small change.

######  Lemma 6.6 ([20], Lemma 15).

Let ${\boldsymbol{A}}\in\epsilon_{p_{1},t}$ and $p_{1}<1/2$ be a real number.
Let

$\displaystyle p_{0}=n^{-t/(2m-2t+1)}\left(\frac{D}{2C}\right)^{1/(2m-2t+1)},$

where $C$ is given by (17) and

$\displaystyle D:=\min_{{\boldsymbol{A}}}\min\\{\langle
c_{0}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{A}}\lvert
c_{0}\rangle,\langle
c_{1}\rvert{\boldsymbol{A}}^{\dagger}{\boldsymbol{A}}\lvert c_{1}\rangle\\}.$

Suppose that $p_{0}\leq p_{1}$. Then, for all $p<p_{0}$,

$\displaystyle\lambda_{\min}({\boldsymbol{M}})\geq\frac{D}{2}p^{t}.$

Proof of Theorem 6.1: By using Theorem 6.2 and Lemmas 6.3, 6.5, and 6.6, we
can bound the worst case error for the amplitude damping channel on $n$ qubit
as follows:

(21) $\displaystyle\inf_{{{\mathcal{R}}}}E_{{{\mathcal{E}}}_{p}^{\otimes
n},{\mathscr{C}}}({{\mathcal{R}}})\leq
1-\frac{1-\binom{n}{t+1}p^{t+1}-|\epsilon_{p,t}|^{2}Cp^{2m-t+1}}{1+\frac{2C|\epsilon_{p,t}|^{2}(|\epsilon_{p,t}|-1)}{D}p^{2m-2t+1}}.$

Note that if $m\geq\lceil\frac{3t}{2}\rceil$ holds, then the upper bound in
(21) converges to zero in the rate of $t+1$ as $p$ goes to zero. This proves
the theorem. ∎

For example, consider the code ${\mathcal{Q}}_{3,3,2}$ with basis states

$\displaystyle\lvert c_{0}\rangle=\frac{1}{8}\left(\lvert
D_{0}^{21}\rangle+\sqrt{21}\lvert D_{6}^{21}\rangle+\sqrt{35}\lvert
D_{12}^{21}\rangle+\sqrt{7}\lvert D_{18}^{21}\rangle\right),$
$\displaystyle\lvert c_{1}\rangle=\frac{1}{8}\left(\sqrt{7}\lvert
D_{3}^{21}\rangle+\sqrt{35}\lvert D_{9}^{21}\rangle-\sqrt{21}\lvert
D_{15}^{21}\rangle-\lvert D_{21}^{21}\rangle\right),$

As shown above, this code is of length 21 and it corrects 2 amplitude damping
errors.

To compare the codes ${\mathcal{Q}}_{g,m,\delta}$ with the existing
constructions of permutation-invariant codes that correct amplitude damping
errors, we note that the shortest code in Ouyang’s gnu family that corrects
$t$ amplitude damping errors has length $(t+1)(3t+1)+t.$ At the same time,
taking $(g,m,\delta)=(t+1,\lceil\frac{3t}{2}\rceil,t)$, we obtain a code
${\mathcal{Q}}_{g,m,\delta}$ of length $(t+1)(1+2\lceil\frac{3t}{2}\rceil)$.
Thus, for an even $t$ our construction requires $t$ fewer physical qubits than
the best permutation-invariant codes known previously. At the same time, for
odd $t$ it needs 1 more physical qubit compared to the gnu codes.

The next lemma was referenced toward the end of the proof of Lemma 6.5.

######  Lemma 6.7.

Let $a,c,k,g,n,m,t$ be nonnegative integers. For all $n>2gm$, $k\leq 2m-t$,
$c\leq a\leq t\leq m$,

(22)
$\displaystyle\sum_{l=0}^{m}(-1)^{l}\frac{\binom{m}{l}}{\binom{n/g-l}{m+1}}\Big{[}\frac{\binom{gl-a}{k-a}\binom{n-(c+a)}{gl-a}}{\binom{n}{gl}}-\frac{\binom{n-gl-a}{k-a}\binom{n-(c+a)}{n-gl-a}}{\binom{n}{gl}}\Big{]}=0.$

###### Proof.

Since
$\binom{n-c-a}{gl-a}\binom{gl-a}{k-a}=\binom{n-c-a}{k-a}\binom{n-c-k}{gl-k}$
and
$\binom{n-c-a}{n-gl-a}\binom{n-gl-a}{k-a}=\binom{n-c-a}{k-a}\binom{n-c-k}{n-gl-k}$,
the left-hand side of (22) can be rewritten as

$\binom{n-c-a}{k-a}\sum_{l=0}^{m}(-1)^{l}\frac{\binom{m}{l}}{\binom{n/g-l}{m+1}\binom{n}{gl}}\Big{[}\binom{n-c-k}{gl-k}-\binom{n-c-k}{gl-c}\Big{]},$

which is zero by Lemma 5.1. ∎

##  7\. Generalization of the Pollatsek–Ruskai Conditions

In [26, Thm. 1] the authors formulated necessary and sufficient conditions for
permutation-invariant codes of a specific form (1) to correct a single error
(and some double errors). In this section we will generalize their conditions
to extend to arbitrary patterns of $t$ errors for all $t\geq 1.$ The
permutation-invariant code ${\mathscr{C}}_{n}$ of [26] has logical codewords

(23)
$\lvert{\boldsymbol{c}}_{0}\rangle=\sum_{l=0}^{(n-1)/2}q_{2l}\sqrt{\binom{n}{2l}}\lvert
D^{n}_{2l}\rangle\quad\text{and}\quad\lvert{\boldsymbol{c}}_{1}\rangle=\sum_{l=0}^{(n-1)/2}q_{n-2l-1}\sqrt{\binom{n}{2l+1}}\lvert
D^{n}_{2l+1}\rangle,$

where the states are not normalized, and where $n$ is assumed to be an odd
integer. The conditions for the code ${\mathscr{C}}_{n}$ to correct $t$ qubit
errors have the following form.

######  Proposition 7.1.

Let $a,b$ be nonnegative integers. For real coefficients
$q_{0},q_{2},\ldots,q_{n-1},$ not all zero, conditions (C3) and (C4) for the
code ${\mathscr{C}}_{n}$ can be equivalently stated as

(D1) For all even $a$ and odd $b$, $\displaystyle{a,b\leq 2t},$
$\displaystyle\sum_{k=0}^{\frac{n-1}{2}-t}\binom{n-2t}{2k}q_{2k+a}q_{n-2k-b}=0;\quad$
(D2) For all even $a$ and $b$, $a\leq b$, $\displaystyle a+b<2t,$
$\displaystyle\sum_{k=0}^{\frac{n-1}{2}-t}\binom{n-2t}{2k}\left(q_{2k+a}q_{2k+b}-q_{2k+2t-a}q_{2k+2t-b}\right)=0;$
(D3) For all odd $a$ and $b$, $a\leq b$, $\displaystyle a+b<2t,$
$\displaystyle\sum_{k=0}^{\frac{n-1}{2}-t}\binom{n-2t}{2k}\left(q_{n-2k-a}q_{n-2k-b}-q_{n-2k-2t+a}q_{n-2k-2t+b}\right)=0.$

###### Proof.

Observe that the coefficient vectors $\boldsymbol{\alpha}$ and
$\boldsymbol{\beta}$ in (23) are

$\displaystyle\alpha_{j}=\sum_{l=0}^{(n-1)/2}q_{j}\sqrt{\binom{n}{j}}\delta_{j,2l},$
$\displaystyle\beta_{j}=\sum_{l=0}^{(n-1)/2}q_{n-j}\sqrt{\binom{n}{j}}\delta_{j,2l+1}.$

We begin with writing the term

$\displaystyle\alpha_{j+a}\beta_{j+b}$
$\displaystyle=\sum_{l=0}^{(n-1)/2}\sum_{l^{\prime}=0}^{(n-1)/2}q_{j+a}q_{n-j-b}\sqrt{\binom{n}{j+a}\binom{n}{j+b}}\delta_{2l-a,2l^{\prime}+1-b}\delta_{j,2l-a}.$

We see that the product $\alpha_{j+a}\beta_{j+b}\neq 0$ only if
$2l^{\prime}=2l+b-a-1$. For this to hold, since both $l$ and $l^{\prime}$ are
integers, the numbers $a$ and $b$ must be of different parity. By symmetry,
the cases (odd,even) and (even,odd) lead to the same expression. Thus, it
suffices to consider only one of them, say that of even $a$ and odd $b$ where
$0\leq a,b\leq 2t$. Condition $(C3)$ yields

$\displaystyle\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\alpha_{j+a}\beta_{j+b}$
$\displaystyle=\sum_{l=0}^{(n-1)/2}\sum_{j=0}^{n}\binom{n-2t}{j}q_{j+a}q_{n-j-b}\delta_{j,2l-a}$
$\displaystyle=\sum_{l=0}^{(n-1)/2}\binom{n-2t}{2l-a}q_{2l}q_{n-2l+a-b}$
$\displaystyle=\sum_{k=0}^{\frac{n-1}{2}-t}\binom{n-2t}{2k}q_{2k+a}q_{n-2k-b}.$

Hence, for the code ${\mathscr{C}}_{n}$, conditions (C3) and (D1) are
equivalent. Now, let us write the terms

$\displaystyle\alpha_{j+a}\alpha_{j+b}$
$\displaystyle=\sum_{l=0}^{(n-1)/2}\sum_{l^{\prime}=0}^{(n-1)/2}q_{j+a}q_{j+b}\sqrt{\binom{n}{j+a}\binom{n}{j+b}}\delta_{2l-a,2l^{\prime}-b}\delta_{j,2l-a}$

and

$\displaystyle\beta_{j+a}\beta_{j+b}$
$\displaystyle=\sum_{l=0}^{(n-1)/2}\sum_{l^{\prime}=0}^{(n-1)/2}q_{n-j-a}q_{n-j-b}\sqrt{\binom{n}{j+a}\binom{n}{j+b}}\delta_{2l+1-a,2l^{\prime}+1-b}\delta_{j,2l+1-a}.$

The products $\alpha_{j+a}\alpha_{j+b}$ and $\beta_{j+a}\beta_{j+b}$ are
nonzero only when $2l=2l^{\prime}+a-b$, implying that $a$ and $b$ have the
same parity. We start with both being even, obtaining

$\displaystyle\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\alpha_{j+a}\alpha_{j+b}$
$\displaystyle=\sum_{l=0}^{(n-1)/2}\sum_{j=0}^{n}\binom{n-2t}{j}q_{j+a}q_{j+b}\delta_{j,2l-a}$
$\displaystyle=\sum_{l=0}^{(n-1)/2}\binom{n-2t}{2l-a}q_{2l}q_{2l-a+b}$
$\displaystyle=\sum_{k=0}^{\frac{n-1}{2}-t}\binom{n-2t}{2k}q_{2k+a}q_{2k+b},$

and

$\displaystyle\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\beta_{j+a}\beta_{j+b}$
$\displaystyle=\sum_{l=0}^{(n-1)/2}\sum_{j=0}^{n}\binom{n-2t}{j}q_{n-j-a}q_{n-j-b}\delta_{j,2l+1-a}$
$\displaystyle=\sum_{l=0}^{(n-1)/2}\binom{n-2t}{2l+1-a}q_{n-2l-1}q_{n-2l-1+a-b}$
$\displaystyle=\sum_{k=0}^{\frac{n-1}{2}-t}\binom{n-2t}{2k}q_{2k+2t-a}q_{2k+2t-b}.$

In the end we obtain

(24)
$\displaystyle\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\left(\alpha_{j+a}\alpha_{j+b}-\beta_{j+a}\beta_{j+b}\right)=\sum_{j=0}^{\frac{n-1}{2}-t}\binom{n-2t}{2k}\left(q_{2k+a}q_{2k+b}-q_{2k+2t-a}q_{2k+2t-b}\right).$

Likewise, for $a$ and $b$ odd, we compute

(25)
$\sum_{j=0}^{n}\frac{\binom{n-2t}{j}}{\sqrt{\binom{n}{j+a}\binom{n}{j+b}}}\left(\alpha_{j+a}\alpha_{j+b}-\beta_{j+a}\beta_{j+b}\right)\\\
=\sum_{k=0}^{\frac{n-1}{2}-t}\binom{n-2t}{2k}\left(q_{n-2k-a}q_{n-2k-b}-q_{n-2k-2t+a}q_{n-2k-2t+b}\right).$

Observe that (24) and (25) are invariant under the exchange $a\leftrightarrow
b$, and they are trivially zero when $a+b=2t$. Furthermore, up to the sign,
they have the same values in the regions $a+b>2t$ and $a+b<2t$. Since
conditions (D2) and (D3) require (24) and (25) to be zero, they can result in
different values only if $a\leq b$ and $a+b<2t$. This shows that conditions
(D2) and (D3) together are equivalent to (C4). The proof is now complete. ∎

For $t=1$, conditions (D1), (D2), and (D3) are equivalent to the conditions
for error correction in [26, Thm. 1]. Here we have extended them for any $t$,
and thus the code ${\mathscr{C}}_{n}$ corrects all $t$ qubit errors if and
only if it has real coefficients that satisfy conditions (D1)-(D3).

We end this section with a remark concerning code construction. Observe that
condition (D1) produces $t(t+1)$ quadratic equations for the coefficients, and
condition (D2) and (D3) together yield $t(t+1)/2$ more. Therefore, to
construct a $t$-error-correcting code that satisfies Proposition 7.1, we need
to solve a system of $3t(t+1)/2$ quadratic equations with respect to $(n+1)/2$
real unknowns, where $n$ is the code length. Generally, such a system is more
likely than not to be incompatible, except for trivial solutions if the length
$n<3t^{2}+3t-1$ since it would be over-determined. For codes of length $n\geq
3t^{2}+3t-1$, there is also no guarantee of a non-trivial solution, and even
attempting to solve the system by computer is a non-trivial task. Along this
path, for $t=1$, Pollatsek and Ruskai [26] showed that there is no code of
length $5$ that satisfies these conditions. The shortest permutation-invariant
code for the single errors they obtained has length 7. For $t=2$, it can be
shown that there is no code of length shorter than $19$. For $n\geq 19$, one
can try to solve a set of $9$ quadratic equations to find an explicit code for
double errors.

As an example, let us examine the case where $t=1$, and $n=7$. By (D1) the
options for $(a,b)$ are $(0,1)$ or $(2,1)$, which yields the following
equations:

$\displaystyle 0$
$\displaystyle=\binom{5}{0}q_{0}q_{6}+\left(\binom{5}{2}+\binom{5}{4}\right)q_{2}q_{4},$
$\displaystyle 0$
$\displaystyle=\left(\binom{5}{0}+\binom{5}{4}\right)q_{2}q_{6}+\binom{5}{2}q_{4}^{2}.$

From (D2) for $(a,b)=(0,0)$ we have

$\displaystyle
0=\binom{5}{0}\left(q_{0}^{2}-q_{2}^{2}\right)+\binom{5}{2}\left(q_{2}^{2}-q_{4}^{2}\right)+\binom{5}{4}\left(q_{4}^{2}-q_{6}^{2}\right).$

As far as (D3) is concerned, there are no pairs $(a,b)$, both odd, such that
$a+b<2t$, so this condition is vacuous and can be ignored. Performing
simplifications, we obtain the following set of equations

$\displaystyle 3q_{2}q_{6}+5q_{4}^{2}=0$ $\displaystyle
q_{0}q_{6}+15q_{2}q_{4}=0$ $\displaystyle
q_{0}^{2}+9q_{2}^{2}-5q_{4}^{2}-5q_{6}^{2}=0.$

Solving this system, we obtain the ((7,2,3)) permutation-invariant code of
[26]. This is to be expected since when $t=1,$ conditions (D1)-D(3) are
equivalent to the conditions in [26, Thm. 1]. At the same time, conditions
(D1)-(D3) are sufficient for the existence of codes that correct any number
$t$ of errors, although their use becomes more difficult as $t$ increases. For
instance, for $t=2$ and $n=19$, conditions (D1)-(D3) give rise to 9 quadratic
equations. Solving them by computer, we determine that there exists a
$((19,2,5))$ permutation-invariant code, and one choice of the coefficients
$q_{2i},i=0,\dots,9$ has the form

$\displaystyle
q_{0}=1,q_{2}=0.0477572,q_{4}=-0.0267249,q_{6}=-0.00506367,q_{8}=0.00332914,q_{10}=0.00527235,$
$\displaystyle
q_{12}=-0.000947223,q_{14}=0.0152707,q_{16}=0.00888631,q_{18}=0.32678.$

These numbers are approximations of the solution, produced by msolve, a C
library for solving systems of polynomial equations [1]. Its output is an
interval for each of the variables, where the solution is actually contained.
These numbers were also verified by Wolfram Mathematica.

##  8\. Concluding remarks

In this paper, we introduced the necessary and sufficient conditions for a
permutation-invariant code to correct arbitrary $t$ errors. We also presented
a family of permutation-invariant codes that can be defined explicitly using
parameters $g,m,\delta$. By adjusting these parameters, one can show that the
proposed codes correct arbitrary $t$ Pauli errors or $t$ amplitude damping
errors. The minimum length of our codes is smaller than in the previous
explicit permutation-invariant code constructions. Since any permutation-
invariant state must necessarily be a ground state of the ferromagnetic
Heisenberg model in the absence of an external magnetic field, the proposed
codes are also suitable for a range of applications discussed in [21, 22, 23].

We conclude with a remark concerning the transversal action of logical gates
on the codewords. Let $G+\tau$ be a universal set of gates, where $G$ is a set
of easily implementable gates (such as those that act transversally on the
physical states), and $\tau$ is a single gate outside of this group. Such
collections of gates are known to support universal computations [19]. The
search for codes that accept transversal action of a group of gates $G$ has
been a frequent research topic in the literature, e.g., [15, 3]. Sometimes
such gate sets are called golden-gates, with a primary example of the form
$2O+T$, where $T$ is the square root of the phase gate and $2O$ is the binary
octahedral group (a.k.a. the Clifford group). The authors of [25] considered a
universal set $G+\tau$ that additionally minimizes the number of $\tau$ gates.
They also defined another golden-gate set of the form $2I+\tau_{60},$ where
$2I$ is the binary icosahedral group and $\tau_{60}$ is another non-Clifford
gate that they defined.

Permutation-invariant codes were linked to transversal gate sets in the recent
paper [13], based on the results of [8]. Among other results, [8] constructed
spin codes as representations of the groups $2O$ and $2I$ that can be mapped
onto the permutation-invariant codes. For instance, [8] constructed a code
spanned by the basis states

(26a) $\displaystyle\lvert
c_{0}\rangle=\sqrt{\frac{3}{10}}\;\Big{|}\frac{7}{2},\frac{7}{2}\Big{\rangle}+\sqrt{\frac{7}{10}}\;\Big{|}\frac{7}{2},-\frac{3}{2}\Big{\rangle},$
(26b) $\displaystyle\lvert
c_{1}\rangle=\sqrt{\frac{7}{10}}\;\Big{|}{\frac{7}{2},\frac{3}{2}}\Big{\rangle}-\sqrt{\frac{3}{10}}\;\Big{|}{\frac{7}{2},-\frac{7}{2}}\Big{\rangle}.$

Following up on this work, the authors of [13] defined a Dicke state mapping
$\mathscr{D}$ that converts a state of a spin-$j$ system into a permutation-
invariant state on $n=2j$ qubits. It can be defined as follows:

(27) $\displaystyle\mathscr{D}:\lvert j,m\rangle\rightarrow\lvert
D^{2j}_{j-m}\rangle.$

This mapping converts the logical gates of a spin code into the logical
transversal gates of a permutation-invariant code. To link this line of work
to our paper, observe that applying $\mathscr{D}$ to the spin code of
(26a)-(26b), we obtain exactly our code $Q_{2,1,2}$ (8). Hence, the
permutation-invariant code admits the 2I group gates transversally [13]. This
observation prompts us to inquire whether other codes in our family admit
transversal logical gates. We leave this question for future study.

##  Appendix A Proofs of combinatorial lemmas from Sec. 5

###### Proof of Lemma 5.1.

First, let us notice that

$\begin{split}\frac{\binom{m}{l}}{\binom{n/g-l}{m+1}}&=\binom{n/g}{l}\binom{n/g-l-m-1}{m-l}\frac{m!(m+1)!\Gamma\left(n/g-2m\right)}{\Gamma\left(n/g+1\right)}\\\
&=(-1)^{m-l}\binom{n/g}{l}\binom{2m-n/g}{m-l}\frac{m!(m+1)!\Gamma\left(n/g-2m\right)}{\Gamma\left(n/g+1\right)}.\end{split}$

Similarly, we obtain

$\displaystyle\frac{\binom{n-r}{gl-a}}{\binom{n}{gl}}=$
$\displaystyle\binom{gl}{a}\binom{n-gl}{r-a}\frac{a!(r-a)!(n-r)!}{n!},$
$\displaystyle\frac{\binom{n-r}{gl-r+a}}{\binom{n}{gl}}=$
$\displaystyle\binom{gl}{r-a}\binom{n-gl}{a}\frac{a!(r-a)!(n-r)!}{n!}.$

Hence, identity (5) is equivalent to the following identity:

(28)
$\displaystyle\sum_{l=0}^{m}\binom{n/g}{l}\binom{2m-n/g}{m-l}\binom{gl}{a}\binom{n-gl}{r-a}=\sum_{l=0}^{m}\binom{n/g}{l}\binom{2m-n/g}{m-l}\binom{gl}{r-a}\binom{n-gl}{a}.$

To prove (28) at once for all $a,r$ satisfying $0\leq a\leq r\leq 2m$, we
first convert it into a power series identity. To do so, we multiply it by
$x^{a}$, sum over $a=0,1,\dots,r$, and note that

$\displaystyle\sum_{a=0}^{r}\binom{gl}{a}\binom{n-gl}{r-a}x^{a}=\left[y^{r}\right]\
\left(1+xy\right)^{gl}\left(1+y\right)^{n-gl}$

and

$\displaystyle\sum_{a=0}^{r}\binom{gl}{r-a}\binom{gl}{a}x^{a}=\left[y^{r}\right]\
\left(1+y\right)^{gl}\left(1+xy\right)^{n-gl},$

where $\left[y^{r}\right]$ denotes the operator of taking the coefficient of
$y^{r}$. It follows that (28) is equivalent to the following power series
having equal coefficients of $y^{r}$ (which are polynomials in $x$) for all
$r\leq 2m$:

$\displaystyle
F(x,y):=\sum_{l=0}^{m}\binom{n/g}{l}\binom{2m-n/g}{m-l}\left(1+xy\right)^{gl}\left(1+y\right)^{n-gl},$
$\displaystyle
G(x,y):=\sum_{l=0}^{m}\binom{n/g}{l}\binom{2m-n/g}{m-l}\left(1+y\right)^{gl}\left(1+xy\right)^{n-gl}.$

In other words, to prove the lemma, we need to show that $F(x,y)\equiv
G(x,y)\pmod{y^{2m+1}}$.

It is easy to see that

$\begin{split}F(x,y)&=[z^{m}]\
(1+z(1+xy)^{g})^{n/g}(1+z(1+y)^{g})^{2m-n/g}(1+y)^{n-mg}\\\ &=[z^{m}]\
\left(\frac{(1+y)^{g}+z(1+xy)^{g}}{1+z}\right)^{n/g}(1+z)^{2m},\end{split}$

and

$\begin{split}G(x,y)&=[z^{m}]\
(1+z(1+y)^{g})^{n/g}(1+z(1+xy)^{g})^{2m-n/g}(1+xy)^{n-mg}\\\ &=[z^{m}]\
\left(\frac{(1+xy)^{g}+z(1+y)^{g}}{1+z}\right)^{n/g}(1+z)^{2m}.\end{split}$

Introducing $A:=(1+y)^{g}$ and $B:=(1+xy)^{g}$ for the sake of simplicity, we
get that

(29) $\displaystyle F(x,y)$ $\displaystyle=\left[z^{m}\right]\
\left(\frac{A+zB}{1+z}\right)^{n/g}(1+z)^{2m},$ $\displaystyle G(x,y)$
$\displaystyle=\left[z^{m}\right]\
\left(\frac{B+zA}{1+z}\right)^{n/g}(1+z)^{2m}.$

Applying the Bürmann–Lagrange inversion formula [7, p.733] to (29), we obtain

$F(x,y)=[w^{m}]\
\left(\frac{A+B}{2}+\frac{A-B}{2}\sqrt{1-4w}\right)^{n/g}\frac{1}{\sqrt{1-4w}}.$

Noticing that $A-B$ is a multiple of $y$, we can expand the last formula
modulo $y^{2m+1}$ as follows:

$\displaystyle
F(x,y)=(-4)^{m}\Big{(}\frac{A+B}{2}\Big{)}^{n/g}\sum_{j=0}^{2m}\binom{n/g}{j}\left(\frac{A-B}{A+B}\right)^{j}\binom{j/2-1/2}{m}+O(y^{2m+1}).$

Note that the expression for $G(x,y)$ can be obtained by exchanging $A$ and
$B$. Observe that the terms with odd $j$ are zero (since
$\binom{j/2-1/2}{m}=0$), while for even $j$, the corresponding terms in
$F(x,y)$ and $G(x,y)$ coincide. This completes the proof of Lemma 5.1. ∎

###### Proof of Lemma 5.2.

Straightforward by Zeilberger’s “creative telescoping”. Let
$F(m,l):=\frac{\binom{m}{l}}{\binom{2x-l}{m+1}}$ and let
$s(m)=\sum_{l}F(m,l)$, where the summation can be extended to all
$l\in\mathbb{Z}.$ We wish to show that $s(m)$ is given by (6). First notice
that

(30) $\displaystyle 2(m+2)F(m,l)-2(x-m-1)F(m+1,l)=G(m,l+1)-G(m,l),$

where

$\displaystyle G(m,l):=F(m,l)\frac{l(m+2)}{m-l+1}.$

To see this, divide both sides of (30) by $F(m,l)$ and use

$\displaystyle\frac{F(m,l+1)}{F(m,l)}=\frac{(m-l)(2x-l)}{(2x-l-m-1)(l+1)},\quad\quad\frac{F(m+1,l)}{F(m,l)}=\frac{(m+2)(m+1)}{(m-l+1)(2x-l-m-1)},$

obtaining the same expression on both sides. Now, sum (30) on $l$ to obtain

$\displaystyle 2(m+2)s(m)-2(x-m-1)s(m+1)=0,$

or

$\displaystyle
s(m+1)=s(m)\frac{m+2}{x-m-1}=s(0)\prod_{j=0}^{m}\frac{m+2-j}{x-m-1+j}=\frac{1}{2x}\prod_{j=0}^{m}\frac{j+2}{x-1-j}.$

Thus,

$\displaystyle
s(m)=\frac{1}{2x}\frac{(m+1)!}{(x-m)(x-1)_{(m-1)}}=\frac{m+1}{2(a-m)}\frac{1}{\frac{x}{m}\binom{x-1}{m-1}},$

which is the same as (6). ∎

## References

  * [1] J. Berthomieu, C. Eder, and M. Safey El Din.  msolve: A library for solving polynomial systems.  In 2021 Int. Sympos. Symb. and Alg. Comput., Saint Petersburg, Russia, 2021.  doi:10.1145/3452143.3465545.
  * [2] S. Blundell.  Magnetism in Condensed Matter.  Oxford University Press, 2001.
  * [3] N. P. Breuckmann and S. Burton.  Fold-transversal Clifford gates for quantum codes.  arXiv:2202.06647.  doi:10.48550/ARXIV.2202.06647.
  * [4] M. Cheraghchi and J. Ribeiro.  An overview of capacity results for synchronization channels.  IEEE Trans. Inf. Theory, 67(6):3207–3232, 2020.
  * [5] I. L. Chuang, D. W. Leung, and Y. Yamamoto.  Bosonic quantum codes for amplitude damping.  Phys. Rev. A, 56:1114–1125, 1997.  doi:10.1103/PhysRevA.56.1114.
  * [6] R. H. Dicke.  Coherence in spontaneous radiation processes.  Phys. Rev., 93:99–110, 1954.  doi:10.1103/PhysRev.93.99.
  * [7] P. Flajolet and R. Sedgewick.  Analytic Combinatorics.  Cambridge University Press, 2009.
  * [8] J. A. Gross.  Designing codes around interactions: The case of a spin.  Phys. Rev. Lett., 127:010504, 2021.  doi:10.1103/PhysRevLett.127.010504.
  * [9] B. Haeupler and A. Shahrasbi.  Synchronization strings and codes for insertions and deletions–A survey.  IEEE Trans. Inf. Theory, 67(6):3190–3206, 2021.
  * [10] M. Hagiwara and A. Nakayama.  A four-qubits code that is a quantum deletion error-correcting code with the optimal length.  In 2020 IEEE International Symposium on Information Theory (ISIT), pages 1870–1874, 2020.  doi:10.1109/ISIT44484.2020.9174339.
  * [11] D. B. Hume, C. W. Chou, T. Rosenband, and D. J. Wineland.  Preparation of Dicke states in an ion chain.  Phys. Rev. A, 80:052302, 2009.  doi:10.1103/PhysRevA.80.052302.
  * [12] E. Knill and R. Laflamme.  A theory of quantum error-correcting codes.  Phys. Rev. A, 55:900–911, 1997.  doi:10.1103/PhysRevA.55.900.
  * [13] E. Kubischta and I. Teixeira.  A family of quantum codes with exotic transversal gates, 2023.  arXiv:2305.07023.
  * [14] V. Levenshtein.  Binary codes capable of correcting deletions, insertions, and reversals.  Soviet Physics Doklady, 10(8):707–710, 1966.
  * [15] J. E. Moussa.  Transversal Clifford gates on folded surface codes.  Phys. Rev. A, 94:042316, 2016.  doi:10.1103/PhysRevA.94.042316.
  * [16] C. S. Mukherjee, S. Maitra, V. Gaurav, and D. Roy.  On actual preparation of Dicke state on a quantum computer, 2020.  arXiv:2007.01681.
  * [17] A. Nakayama and M. Hagiwara.  The first quantum error-correcting code for single deletion errors.  IEICE Communications Express, 9(4):100–104, 2020.
  * [18] A. Nakayama and M. Hagiwara.  Single quantum deletion error-correcting codes.  In 2020 International Symposium on Information Theory and Its Applications (ISITA), pages 329–333, 2020.
  * [19] M. A. Nielsen and I. L. Chuang.  Quantum Computation and Quantum Information.  Cambridge University Press, 2010.  doi:10.1017/CBO9780511976667.
  * [20] Y. Ouyang.  Permutation-invariant quantum codes.  Phys. Rev. A, 90:062317, 2014.  doi:10.1103/PhysRevA.90.062317.
  * [21] Y. Ouyang.  Quantum storage in quantum ferromagnets.  Phys. Rev. B, 103:144417, 2021.  doi:10.1103/PhysRevB.103.144417.
  * [22] Y. Ouyang and G. K. Brennen.  Quantum error correction on symmetric quantum sensors, 2022.  arXiv:2212.06285.
  * [23] Y. Ouyang and R. Chao.  Permutation-invariant constant-excitation quantum codes for amplitude damping.  IEEE Trans. Inf. Theory, 66(5):2921–2933, 2020.  doi:10.1109/TIT.2019.2956142.
  * [24] Y. Ouyang and W. H. Ng.  Truncated quantum channel representations for coupled harmonic oscillators.  Journal of Physics A: Mathematical and Theoretical, 46(20):205301, 2013.  doi:10.1088/1751-8113/46/20/205301.
  * [25] O. Parzanchevski and P. Sarnak.  Super-golden-gates for PU$(2)$.  Advances in Mathematics, 327:869–901, 2018.  doi:https://doi.org/10.1016/j.aim.2017.06.022.
  * [26] H. Pollatsek and M. B. Ruskai.  Permutationally invariant codes for quantum error correction.  Linear Alg. Appl., 392:255–288, 2004.  doi:https://doi.org/10.1016/j.laa.2004.06.014.
  * [27] E. M. Rains.  Quantum weight enumerators.  IEEE Trans. Inf. Theory, 44(4):1388–1394, 1998.  doi:10.1109/18.681316.
  * [28] M. B. Ruskai.  Pauli exchange and quantum error correction, 2000.  ArXiv, quant-ph/0006008.
  * [29] B. Schumacher.  Sending entanglement through noisy quantum channels.  Phys. Rev. A, 54:2614–2628, 1996.  doi:10.1103/PhysRevA.54.2614.
  * [30] T. Shibayama and M. Hagiwara.  Permutation-invariant quantum codes for deletion errors.  In 2021 IEEE International Symposium on Information Theory (ISIT), pages 1493–1498. IEEE, 2021.
  * [31] T. Shibayama and Y. Ouyang.  The equivalence between correctability of deletions and insertions of separable states in quantum codes.  In 2021 IEEE Information Theory Workshop (ITW), pages 1–6, 2021\.  doi:10.1109/ITW48936.2021.9611450.
  * [32] P. W. Shor.  Scheme for reducing decoherence in quantum computer memory.  Phys. Rev. A, 52:R2493–R2496, 1995.  doi:10.1103/PhysRevA.52.R2493.
  * [33] R. Varshamov and G. Tenengolts.  Codes which correct single asymmetric errors.  Automatika i Telemkhanika, 161(3):288–292, 1965.  (in Russian).
  * [34] M. M. Wilde.  Quantum Information Theory.  Cambridge University Press, 2nd edition, 2017.  doi:10.1017/9781316809976.