Permutation-Invariant Quantum Codes for Deletion Errors

Quantum error-correcting codes are one of the essential factors for the development of quantum computers, which were first introduced by Shor in 1995 [22]. Since then, many codes have been constructed, e.g., CSS codes[2], stabilizer codes[4], surface codes[3], etc.

Recently, in 2019, Leahy et al. provided a way to turn quantum insertion-deletion errors into errors that can be handled by conventional methods under the specific assumption [10]. Since then, quantum deletion error-correction have attracted a lot of attention from researchers. In quantum information theory, quantum deletion error-correction is a problem of determining the quantum state in the entire quantum system from a quantum state in a partial system. Therefore it is related to various topics, e.g., quantum erasure error-correcting codes [5], quantum secret sharing [7], purification of quantum state [8], quantum cloud computing [1], etc.

The first quantum deletion codes under the general scenario was constructed in 2020 [11]. Since then, several quantum deletion codes have been constructed so far [6, 12, 21]. However, research on quantum deletion codes is not yet sufficiently advanced. All the quantum deletion codes that have already been found can correct only single-deletion errors. In other words, quantum error-correcting codes that can correct two or more deletion errors have not been found to date. Furthermore, in classical coding theory, the construction of codes that can correct both substitution and deletion errors has attracted much attention [23, 24]; however, no such codes have yet been found in quantum coding theory.

In this paper, we consider permutation-invariant quantum codes, which are invariant under any permutation of the underlying particles. Permutation-invariant quantum codes have been constructed using a variety of techniques[20, 19, 14, 17, 15, 13]. Recently, permutation-invariant quantum codes have been explored for applications such as for quantum storage[16] and robust quantum metrology[18]. These are expected to be applied to physically realistic scenarios[25].

This paper is organized as follows. In Section 2, some notations and definitions are introduced. In Section 3, the deletion error-correcting codes as quantum codes are defined and the main theorem is stated, and in Section 4, we give the proof of the main theorem. In Section 5, we present two families of our codes. The first gives quantum codes that can correct any number of deletion errors, and the code can also correct multiple qubit errors. The second gives quantum codes that can correct single-deletion errors that have been found so far; these are also included in our codes. In Section 6, we consider a generalization of our codes. Finally, this paper is summarized in Section 7.

Throughout this paper, we fix the following notation. Let $N\geq 2$ be an integer and $[N]\coloneqq\{1,2,\dots,N\}$. For a square matrix $M$ over the complex field $\mathbb{C}$, we denote by ${\rm Tr}(M)$ the sum of the diagonal elements of $M$. Set $|0\rangle,|1\rangle\in\mathbb{C}^{2}$ as $|0\rangle\coloneqq(1,0)^{\top}$, $|1\rangle\coloneqq(0,1)^{\top}$, and $|\bm{x}\rangle\coloneqq|x_{1}\rangle\otimes|x_{2}\rangle\otimes\dots\otimes|x_{N}\rangle\in\mathbb{C}^{2\otimes N}$ for a bit sequence $\bm{x}=x_{1}x_{2}\cdots x_{N}\in\{0,1\}^{N}$. Here $\otimes$ is the tensor product operation and $\top$ is the transpose operation. Let $\langle\bm{x}|\coloneqq|\bm{x}\rangle^{\dagger}$ denote the conjugate transpose of $|\bm{x}\rangle$. We define the Hamming weight ${\rm wt}(\bm{x})$ of $\bm{x}$ by ${\rm wt}(\bm{x})\coloneqq\#\{p\in[N]\mid x_{p}\neq 0\}$.

A positive semi-definite Hermitian matrix of trace $1$ is called a density matrix. We denote by $S(\mathbb{C}^{2\otimes N})$ the set of all density matrices of order $2^{N}$. An element of $S(\mathbb{C}^{2\otimes N})$ is called a quantum state. We also use a complex vector $|\psi\rangle\in\mathbb{C}^{2\otimes N}$ for representing a pure quantum state $|\psi\rangle\langle\psi|\in S(\mathbb{C}^{2\otimes N})$.

Let $M=\sum_{\bm{x},\bm{y}\in\{0,1\}^{N}}m_{\bm{x},\bm{y}}|x_{1}\rangle\langle y_{1}|\otimes\cdots\otimes|x_{N}\rangle\langle y_{N}|$ be a square matrix with $m_{\bm{x},\bm{y}}\in\mathbb{C}$. For an integer $p\in[N]$, define a map ${\rm Tr}_{p}:S(\mathbb{C}^{2\otimes N})\rightarrow S(\mathbb{C}^{2\otimes(N-1)})$ as

The map ${\rm Tr}_{p}$ is called a partial trace.

Recall that in classical coding theory, for an integer $1\leq t<N$, a $t$-deletion error is defined as a map from a bit sequence of length $N$ to its subsequence of length $N-t$. We define a $t$-deletion error in the terms of quantum coding theory.

In this paper, an integer $1\leq t<N$ is fixed and denotes a number of deletions, and a set $P\subset[N]$ denotes the deletion position satisfying $|P|=t$.

Note that a $t$-deletion error-correcting code is an $s$-deletion error-correcting code for any positive integer $s\leq t$.

The following Definition 3.3 is the conditions for constructing our codes. Note that for binomial coefficients, if $w<0$ or $N<w$, we define $\binom{N}{w}\coloneqq 0$.

The following Theorem 3.4 is the main theorem of this paper and describes a new construction method for quantum deletion error-correcting codes.

Here, the notations $Q_{A,B}^{f}$, ${\rm Enc}_{A,B}^{f}$, and ${\rm Dec}_{A,B}^{f}$ above are defined in the next section.

In this section, we shall give the proof of Theorem 3.4. The proofs of Lemmas in this section are given in later appendices.

The map ${\rm Enc}_{A,B}^{f}$ can be written as a form ${\rm enc}\circ{\rm pad}^{N,K}$ with some unitary transformation ${\rm enc}$, thus it satisfies the condition of Definition 3.2. Note that for the vector $|\Psi\rangle$ defined by Equation (1),

holds by the condition (D1). Therefore, $|\Psi\rangle$ is a quantum state.

A quantum state is permutation-invariant if the state is invariant under position permutations. A quantum code is permutation-invariant if any state of the code is permutation-invariant. The term permutation-invariant is also called as PI. The code $Q_{A,B}^{f}$ is a PI code. The following Lemma 4.2 describes the state after a deletion error for a PI state.

Note that Equation (1) is obtained in Equation (2) by setting

Equation (3) in our codes can be expressed in good form by the following Lemma 4.3. The conditions (D2) and (D3) can be considered as an adaptation of the Knill and Laflamme conditions[9] to PI codes for deletion errors.

A set $\mathbb{P}\coloneqq\{P_{k}\}$ of projection matrices of order $2^{N}$ is called a projective measurement if and only if $\sum_{k}P_{k}=\mathbb{I}$, where $k$ is an index and $\mathbb{I}$ is the identity matrix of order $2^{N}$. If the quantum state immediately before the measurement is $\rho\in S(\mathbb{C}^{2\otimes N})$ then the probability that outcome $k$ occurs is given by ${\rm Tr}(P_{k}\rho)$, and the quantum state $\rho^{\prime}$ after the measurement is $\rho^{\prime}\coloneqq\frac{P_{k}\rho P_{k}}{{\rm Tr}(P_{k}\rho)}$.

If non-empty sets $A,B\subset\{0,1\}^{N}$ satisfy the condition (D3), the set $\mathbb{P}_{A,B}$ is clearly a projective measurement. The following Lemma 4.5 shows the results of the projective measurement $\mathbb{P}_{A,B}$ under the state after a deletion error in our code $Q_{A,B}^{f}$.

We now describe the proof of the main theorem.

By Theorem 3.4, we can construct a permutation-invariant quantum code for deletion errors from finding two non-empty sets $A,B\subset\{0,1,\dots,N\}$ with $A\cap B=\varnothing$ and a map $f:A\cup B\rightarrow\mathbb{C}$ that satisfy the three conditions (D1), (D2), and (D3). we give two families of our codes in this section.

In this section, we discuss constructions of $[N,K]$ $t$-deletion error-correcting codes for any positive integer $K$. Let $L$ be a positive integer and $A_{0},A_{1},\dots,$ $A_{L-1}\subset\{0,1,\dots,N\}$ be mutually disjoint non-empty sets and $f:\bigcup_{i=0}^{L-1}A_{i}\rightarrow\mathbb{C}$ be a map which satisfy the following three conditions:

• (D1)*

  For any integer $i\in\{0,1,\dots,L-1\}$,

  $\displaystyle\sum_{w\in A_{i}}|f(w)|^{2}{\binom{N}{w}}=1.$

• (D2)*

  For any integers $0\leq k\leq t$ and $i,j\in\{0,1,\dots,L-1\}$,

  $\displaystyle\sum_{w\in A_{i}}|f(w)|^{2}{\binom{N-t}{w-k}}=\sum_{w\in A_{j}}|f(w)|^{2}{\binom{N-t}{w-k}}\neq 0.$

• (D3)*

  For any integers $w_{1},w_{2}\in\bigcup_{i=0}^{L-1}A_{i}$,

  $\displaystyle w_{1}\neq w_{2}~{}\Longrightarrow~{}|w_{1}-w_{2}|>t.$

Let us define an encoder as a linear map ${\rm Enc}_{\{A_{i}\}}^{f}:\mathbb{C}^{L}\rightarrow\mathbb{C}^{2\otimes N}$. For a quantum state $|\psi\rangle=\sum_{i=0}^{L-1}\textstyle\alpha_{i}|i\rangle\in\mathbb{C}^{L}$, where $|0\rangle,|1\rangle,\dots,|L-1\rangle$ is the standard orthogonal basis of $\mathbb{C}^{L}$, ${\rm Enc}_{\{A_{i}\}}^{f}$ maps the state $|\psi\rangle$ to the following state $|\Psi\rangle$,

Note that this encoder is an extension of Definition 4.1. We claim that the image of ${\rm Enc}_{\{A_{i}\}}^{f}$ is a $t$-deletion error-correcting code for an integer $1\leq t<N$. We can use the same method as in Section 4 for the proof. For the case $L=2^{K}$, we obtain a $[N,K]$ $t$-deletion error-correcting code.

Although we do not discuss it in detail here, we can construct $[N,K]$ single-deletion error-correcting codes with any integer $K\geq 1$ by extending Theorem 5.4. But no example of $[N,K]$ $t$-deletion error-correcting codes with $K\geq 2$ and $t\geq 2$ has been found to date.

This paper gave a construction of permutation-invariant quantum codes for deletion errors. In particular, the codes given in Theorem 5.2 contain the first example of quantum codes that can correct two or more deletion errors and the first example of codes that can correct both multiple-qubit errors and multiple-deletion errors.

The research has been partly executed in response to support by KAKENHI 18H01435.