A Four-Qubits Code that is a Quantum Deletion Error-Correcting Code with the Optimal Length

Set $\ket{0},\ket{1}\in\mathbb{C}^{2}$ as

$$\ket{0}:=\left(\begin{array}[]{c}1\\ 0\end{array}\right),\ket{1}:=\left(\begin{array}[]{c}0\\ 1\end{array}\right)$$

respectively. For a binary sequence $\bm{x}=x_{1}x_{2}\dots x_{n}\in\{0,1\}^{n}$, $\ket{\bm{x}}$ denotes

$$\ket{x_{1}}\otimes\ket{x_{2}}\otimes\dots\ket{x_{n}}\in\mathbb{C}^{2\otimes n}.$$

We denote the set of all density matrices of order $N$ by $S(\mathbb{C}^{N})$. An element of $S(\mathbb{C}^{N})$ is called a quantum state in this paper. We also use a complex vector for representing a quantum state if the state is pure.

For an integer $1\leq i\leq n$ and a square matrix

$$A=\sum_{\bm{x},\bm{y}\in\{0,1\}^{n}}a_{\bm{x},\bm{y}}\cdot\ket{x_{1}}\bra{y_{1}}\otimes\cdots\otimes\ket{x_{n}}\bra{y_{n}}$$

with $a_{\bm{x},\bm{y}}\in\mathbb{C}$, define the map $\mathrm{Tr}_{i}:S(\mathbb{C}^{2\otimes n})\rightarrow S(\mathbb{C}^{2\otimes(n-1)})$ as

	$\displaystyle\mathrm{Tr}_{i}(A):=$	$\displaystyle\sum_{\bm{x},\bm{y}\in\{0,1\}^{n}}a_{\bm{x},\bm{y}}\cdot\mathrm{Tr}(\ket{x_{i}}\bra{y_{i}})\cdot\ket{x_{1}}\bra{y_{1}}\otimes$
		$\displaystyle\cdots\otimes\ket{x_{i-1}}\bra{y_{i-1}}\otimes\ket{x_{i+1}}\bra{y_{i+1}}\otimes$
		$\displaystyle\cdots\otimes\ket{x_{n}}\bra{y_{n}}.$

The map $\mathrm{Tr}_{i}$ is called a partial trace.

Recall that in the classical coding theory, a single deletion error is defined as an operator that maps a sequence $x_{1}x_{2}\dots x_{i}\dots x_{n}$ to a short sequence $x_{1}x_{2}\dots x_{i-1}x_{i+1}\dots x_{n}$ for some $i$.

If a quantum state $\rho$ is corresponding to $n$-photons $p_{1},p_{2},\dots,p_{n}$, the state $D_{i}(\rho)$ is corresponding to $n-1$-photons $p_{1},p_{2},\dots,p_{i-1},p_{i+1},\dots,p_{n}$.

Comparing to erasure errors, deletion errors do not tell the position where the information is deleted. Hence to correct deletion errors is more difficult than to correct erasure errors.

Most famous classical error-correcting codes for single deletion errors are “non-linear” codes that are called VT codes [18] discovered by Levenshtein [14]. One of the reasons why “non-linear” codes are preferable for deletion error-correction is unveiled in [1]. It is stated that a code rate of any single deletion error-correcting code cannot exceed $1/2$ if a code is linear. This implies that if a CSS code is constructed from two classical linear deletion error-correcting codes then the code rate of the CSS code is $0$.

In fact, we will show that $Q_{4}$ is a $[4,1]$ single deletion error-correcting code with the encoder $\mathrm{En}_{4}$.

We can characterize this encoding in the following manner. Let $A$ be the set of four bit sequences with Hamming weight $0$ or $4$ and $B$ the set of four bit sequences with Hamming weight $2$, i.e.,

	$\displaystyle A$	$\displaystyle=\{0000,1111\},$
	$\displaystyle B$	$\displaystyle=\{0011,0101,0110,1001,1010,1100\}.$

Then the codeword $|\Phi\rangle$ is

$$\frac{\alpha}{\sqrt{2}}\sum_{a\in A}|a\rangle+\frac{\beta}{\sqrt{6}}\sum_{b\in B}|b\rangle.$$

By this encoding, $\ket{0}$ and $\ket{1}$ are encoded to quantum states which are superpositions of two and six orthonormal states. Hence this encoding is neither an instance of CSS codes nor stabilizer codes.

In this subsection, we prove our code $Q_{4}$ corrects any single deletion errors $D_{1},D_{2},D_{3},$ and $D_{4}$.

Let us set

	$\displaystyle A_{0}$	$\displaystyle:=\{000\},$
	$\displaystyle A_{1}$	$\displaystyle:=\{111\},$
	$\displaystyle B_{0}$	$\displaystyle:=\{011,101,110\},$
	$\displaystyle B_{1}$	$\displaystyle:=\{001,010,100\}.$

Figure 1 shows an example of an encoder for our four qubits code $Q_{4}$. The gate $H$ is the Hadamard matrix, i.e.,

$$H=\left(\begin{array}[]{cc}1/\sqrt{2}&1/\sqrt{2}\\ 1/\sqrt{2}&-1/\sqrt{2}\end{array}\right),$$

and the gate $X$ is the bit-flip matrix, i.e.,

$$X:=\left(\begin{array}[]{cc}0&1\\ 1&0\end{array}\right).$$

The black dot is the control gate for the connected gate. For example, the final gate of Figure 1 is the C-NOT gate with the 3rd qubit as the control qubit and the 1st qubit as the target bit.

The gates $U$ and $V$ are defined as

$$U:=\left(\begin{array}[]{cc}1/\sqrt{3}&-\sqrt{2}/\sqrt{3}\\ \sqrt{2}/\sqrt{3}&1/\sqrt{3}\end{array}\right),V:=\left(\begin{array}[]{cc}1/\sqrt{2}&1/\sqrt{2}\\ -1/\sqrt{2}&1/\sqrt{2}\end{array}\right)$$

respectively.

The input of the circuit is a single qubit $\ket{\phi}\in\mathbb{C}^{2}$. The input position is settled to the left-most position. For the other three positions, initialized three qubits $|000\rangle$ are input.

By the first two depth operations, i.e., the controlled $U$ gate, the controlled $V$ gate and the Hadamard gate, a quantum state $\ket{0000}$ is changed to

$$\frac{1}{\sqrt{2}}\left(\ket{0000}+\ket{0010}\right).$$

and a quantum state $\ket{1000}$ is changed to

$$\frac{1}{\sqrt{6}}\left(\ket{1000}+\ket{1010}+\ket{0100}+\ket{0110}+\ket{1100}+\ket{1110}\right).$$

By the remaining four controlled $X$ gates, i.e. C-NOTs, a quantum state $\ket{x_{1}x_{2}x_{3}0}$ is changed to $\ket{(x_{1}+x_{3})(x_{2}+x_{3})(x_{3})(x_{1}+x_{2}+x_{3})}$, e.g.,

	$\displaystyle\ket{0000}$	$\displaystyle\rightarrow\ket{0000},$
	$\displaystyle\ket{0010}$	$\displaystyle\rightarrow\ket{1111},$
	$\displaystyle\ket{1000}$	$\displaystyle\rightarrow\ket{1001},$
	$\displaystyle\ket{1010}$	$\displaystyle\rightarrow\ket{0110},$
	$\displaystyle\ket{0100}$	$\displaystyle\rightarrow\ket{0101},$
	$\displaystyle\ket{0110}$	$\displaystyle\rightarrow\ket{1010},$
	$\displaystyle\ket{1100}$	$\displaystyle\rightarrow\ket{1100},$
	$\displaystyle\ket{1110}$	$\displaystyle\rightarrow\ket{0011}.$

Hence $(\alpha\ket{0}+\beta\ket{1})\otimes\ket{000}$ is encoded to

$$\alpha\left(\frac{1}{\sqrt{2}}\sum_{\bm{a}\in A}\ket{\bm{a}}\right)+\beta\left(\frac{1}{\sqrt{6}}\sum_{\bm{b}\in B}\ket{\bm{b}}\right).$$

Figure 2 shows a quantum circuit that changes a pure state $\left(\ket{011}+\ket{101}+\ket{110}\right)/\sqrt{3}$ to a pure state $\ket{100}$ and keeps a pure state $\ket{000}$. Hence the circuit changes a pure state $\ket{\Psi_{0}}=\alpha\sum_{\bm{a}\in A_{0}}\ket{\bm{a}}+\frac{\beta}{3}\sum_{\bm{b}\in B_{0}}\ket{\bm{b}}$ to a pure state $\ket{\phi}=\alpha\ket{0}+\beta\ket{1}$.

Remember that the step 1 of the decoding algorithm changes a single deleted quantum state $D_{i}(\rho)$ to $\ket{\Psi_{0}}$. Hence the circuit is available as a decoding circuit after step 1.

Let us provide another quantum circuit that is depicted as Figure 3. The quantum circuit consists of two parts. The first part has six C-NOT and the last part is the same as the circuit defined by Figure 2. The first part changes a quantum pure state $\ket{x_{1}x_{2}x_{3}}$ to $\ket{x_{1}x_{2}x_{3}0}$ if the Hamming weight of $x_{1}x_{2}x_{3}$ is even and to $\ket{(x_{1}+1)(x_{2}+1)(x_{3}+1)1}$ if the weight is odd. This implies that the first part changes a single deleted quantum state $D_{i}(\rho)$ to

$$\ket{\Psi_{0}}\bra{\Psi_{0}}\otimes\left(\begin{array}[]{cc}1/2&0\\ 0&1/2\end{array}\right).$$

Since the last part is the same as the circuit corresponding to Figure 2, the state is changed to

$$\ket{\phi}\bra{\phi}\otimes\ket{0}\bra{0}\otimes\ket{0}\bra{0}\otimes\left(\begin{array}[]{cc}1/2&0\\ 0&1/2\end{array}\right).$$

In other words, the state at the first position of output is a pure state $\ket{\phi}$.

We generalize our $[4,1]$ single deletion error-correcting code $Q_{4}$ to a $[2^{k+2}-4,k]$ single quantum deletion error-correcting code for any positive integer $k$.

Let $l$ be a positive integer. For $0\leq i\leq l-1$, let us define

$$\mathcal{A}_{i}:=\{\bm{x}\in\{0,1\}^{4(l-1)}\mid\mathrm{wt}(\bm{x})=2i\text{ or }4(l-1)-2i\}$$

and

$$\mathrm{En}_{4(l-1)}\left(\ket{\phi_{l}}\right):=\sum_{0\leq i\leq l-1}c_{i}\left(\sum_{\bm{x}\in\mathcal{A}_{i}}\ket{\bm{x}}\right),$$

where $\ket{\phi_{l}}:=\sum_{0\leq i\leq l-1}c_{i}\ket{i}$ is a quantum pure state of level $l$, i.e. $\ket{\phi_{l}}\in\mathbb{C}^{l}$, and $\ket{0},\ket{1},\dots,\ket{l-1}$ is the standard orthonormal basis of $\mathbb{C}^{l}$.

We claim that the image of $\mathrm{En}_{4(l-1)}$ is a single quantum deletion error-correcting code for any $l\geq 2$. A decoding algorithm $\mathrm{De}_{4(l-1)}$ can be defined similar to $\mathrm{De}_{4}$. Due to the limit of page numbers, we only explain how to define its measurement $\{\mathcal{P}_{0},\mathcal{P}_{1}\}$.

$\mathcal{P}_{0}$ (resp. $\mathcal{P}_{1}$) is the projection from $\mathbb{C}^{2\otimes 4(l-1)}$ to the linear space $\mathcal{V}_{0}$ (resp. $\mathcal{V}_{1}$) spanned by

	$\displaystyle\{\ket{\bm{x}}\mid$	$\displaystyle\;\bm{x}\in\{0,1\}^{4(l-1)-1},$
		$\displaystyle\text{ the Hamming weight of $\bm{x}$ is even (resp. odd) }\}.$

The outcome is $i\in\{0,1\}$ if the quantum state in $S(\mathbb{C}^{2\otimes 4(l-1)})$ is changed into a state in $S(\mathcal{V}_{i})$.

For the case $l=2^{k}$, we obtain a $[2^{k+2}-4,k]$ single quantum deletion error-correcting code.

Our code word has symmetry for position permutations. In other words, any permutation for four qubits does not change the codeword. Additionally, any received word after any single deletion has also symmetry for position permutation.

This means that even if we permute the three input to the quantum circuits corresponding to Figure 2, we can obtain the original quantum information $\ket{\phi}$ at the left most position of output.