Why can't there be an error detecting code with fewer than 4 qubits?

Question

Essentially this boils down to: Is it possible to encode a single logical qubit in three physical qubits so that the resulting code has distance two?

In other words, does a $[\![3,1,2]\!]$ code exist?

Comments:

• No $[\![3,1,2]\!]$ stabilizer code exists. A simple argument is given for example below equation $(14)$ in this paper. In general it shows that no $[\![2n+1,2n-1,2]\!]$ stabilizer code exists.

• No $[\![3,1,3]\!]$, $[\![3,2,2]\!]$, or $[\![2,1,2]\!]$ code exists; this follows from the quantum singleton bound $$ n-k\geq 2(d-1). $$

• There is a well known $[\![4,2,2]\!]$ stabilizer code with stabilizer $ XXXX,ZZZZ $. This is the smallest known quantum code with $ d \geq 2 $.

This question is similar to Why can't there be an error correcting code with fewer than 5 qubits? but for $ d=2 $ instead of $ d=3 $.

Answer 1

No, there is no $[\![3,1,2]\!]$ code.

Background

As in classical error correction, existence of quantum codes can often be ruled out using a range of inequalities that codes must satisfy. Indeed, the question already makes use of the singleton bound to rule out existence of similar codes. Below, I will use equations and inequalities in theorem $10$ on page $7$ in Quantum shadow enumerators. The paper derives the quantum analogue of the shadow of a classical binary code and uses it to extend the results in Quantum MacWilliams Identities which in turn derives quantum versions of MacWilliams identities relating the weight distribution of a code $C$ and its dual $C^\perp$.

No $[\![3,1,2]\!]$ code exists

Theorem $10$ lists a few equations and ineqalities that relate weights$^1$ $A_i$ and $B_i$ and shadow weights$^2$ $S_i$ for $i=0,\dots,n$ to each other and to the parameters of the code $[\![n,k,d]\!]=(\!(n,K=2^k,d)\!)$. If the code exists, then the relations are satisfied. Suppose then that there is a code $[\![3,1,2]\!]=(\!(3,2,2)\!)$. We will use equations and inequalities in theorem $10$ to derive a contradiction. It is sufficient to compute $A_0,\dots,A_3$, $B_0$, $B_1$ and $S_0$ since at this point we will obtain a contradiction with one of the inequalities - namely, $S_0\ge 0$ - proving that no $[\![3,1,2]\!]$ code exists.

First, we compute Krawtchouk polynomials $P_i(x):=P_i(x,n=3)$

$$ \begin{align} P_0(x)&=1\\ P_1(x)&=9-4x. \end{align}\tag1 $$

We won't need $P_2(x)$ and $P_3(x)$. Next, we use the polynomials to write down equations for $B_0$, $B_1$ and $S_0$ in terms of $A_i$

$$ \begin{align} 8B_0 &= A_0+A_1+A_2+A_3\\ 8B_1 &= 9A_0+5A_1+A_2-3A_3\\ 8S_0 &= A_0-A_1+A_2-A_3. \end{align}\tag2 $$

Now, by the first relation in theorem $10$, we have $A_0=K^2=4$ and by the fourth one $2B_0=A_0$ and $2B_1=A_1$. Substituting into $(2)$, we obtain

$$ \begin{align} A_1+A_2+A_3&=12\\ A_1+A_2-3A_3&=-36 \end{align}\tag3 $$

so $A_1+A_2=0$ and $A_3=12$. However, from the second relation in theorem $10$, we know that $A_1\ge 0$ and $A_2\ge 0$, so $A_1=A_2=0$. But then $S_0=-1$ and we arrive at a contradiction with the last relation in theorem $10$, namely $S_0\ge 0$. Therefore, no code $[\![3,1,2]\!]$ exists.

---

^{$^1$ For definition of $A_i$ and $B_i$ see discussion on page $2$ in Quantum shadow enumerators.
$^2$ For definition of $S_i$ see theorem $4$ on page $4$ in Quantum shadow enumerators and preceding discussion.}

Answer 2

This answer provides an elementary version of the proof that there is no $[\![3,1,2]\!]$ code. The proof is based on the arguments in Quantum shadow enumerators and Quantum MacWilliams Identities, but uses only basic linear algebra and quantum error correction conditions (see e.g. section $7.3.3$ in these notes).

Quantum error correction conditions

Let $\mathcal{E}=\{P_0\otimes P_1\otimes P_2\,|\,P_0,P_1,P_2\in\{I,X,Y,Z\}\}$ denote the set of Pauli errors on three qubits. For $E\in\mathcal{E}$, define $\mathrm{wt}_x(E)$ as the number of qubits on which $E$ acts as $X$ and similarly for $\mathrm{wt}_y(E)$ and $\mathrm{wt}_z(E)$. Define $E$'s weight by $\mathrm{wt}(E)=\mathrm{wt}_x(E)+\mathrm{wt}_y(E)+\mathrm{wt}_z(E)$. Then $\mathcal{E}=\mathcal{E}_0\cup\mathcal{E}_1\cup\mathcal{E}_2\cup\mathcal{E}_3$ where $\mathcal{E}_k$ is the subset of $\mathcal{E}$ consisting or errors of weight $k$.

Suppose $\mathcal{C}=\mathrm{span}(|0_L\rangle, |1_L\rangle)\subset\mathbb{C}^{2^3}$ is a two-dimensional subspace of the Hilbert space of three qubits. For $E\in\mathcal{E}$, define the $2\times 2$ matrix $C_E$ by $(C_E)_{ij}=\langle i_L|E|j_L\rangle$ where $i,j=0,1$. The quantum error correction conditions (see e.g. equation $(7.36)$ and surrounding discussion in the above cited lecture notes) state that $\mathcal{C}$ is a $[\![3,1,2]\!]$ code if and only if for every single-qubit Pauli error $E\in\mathcal{E}_1$ we have $C_E=c_EI$ for some $c_E\in\mathbb{R}$. Equivalently, $\mathcal{C}$ is a $[\![3,1,2]\!]$ code if and only if for every $E\in\mathcal{E}_1$ $$ \left\|C_E-\frac12 I\,\mathrm{tr}(C_E)\right\|^2_F=0\tag1 $$ where $\|A\|_F^2=\sum_{ij}|a_{ij}|^2$ denotes the Frobenius norm of matrix $A$. We will show that there is no such code by proving a positive lower bound $$ \sum_{E\in\mathcal{E}_1}\left\|C_E-\frac12 I\,\mathrm{tr}(C_E)\right\|^2_F > 0.\tag2 $$

Weights

Let $P$ denote the projector onto the code subspace $\mathcal{C}$ and define $$ \begin{align} A_k &= \sum_{E\in\mathcal{E}_k}\mathrm{tr}(EP)^2\tag3 \\ B_k &= \sum_{E\in\mathcal{E}_k}\mathrm{tr}(EPEP).\tag4 \end{align} $$ Since $\mathcal{C}$ is two-dimensional, we see immediately that $A_0=4$ and $B_0=2$.

Quantum error correction conditions in terms of weights

Substituting $P=|0_L\rangle\langle 0_L|+|1_L\rangle\langle 1_L|$ into the formulas for $A_1$ and $B_1$, we have $$ A_1 = \sum_{E\in\mathcal{E}_1}\left(\sum_i\langle i_L|E|i_L\rangle\right)^2 = \sum_{E\in\mathcal{E}_1}\mathrm{tr}^2(C_E)= \sum_{E\in\mathcal{E}_1}|\mathrm{tr}(C_E)|^2\tag5 $$ and $$ B_1 = \sum_{E\in\mathcal{E}_1}\sum_{ij}|\langle i_L|E|j_L\rangle|^2 = \sum_{E\in\mathcal{E}_1}\|C_E\|_F^2.\tag6 $$ For any $2\times 2$ matrix $M=\begin{bmatrix}a&b\\c&d\end{bmatrix}$, we have $$ \begin{align} \left\|M-\frac12 I\,\mathrm{tr}(M)\right\|^2_F &= \left|a-\frac{a+d}{2}\right|^2 + |b|^2 + |c|^2 + \left|c-\frac{a+d}{2}\right|^2\\ &= \frac12|a-d|^2 + |b|^2 + |c|^2\\ &= |a|^2+|b|^2 + |c|^2 + |d|^2 - \frac12|a+d|^2\\ &= \|M\|_F^2 - \frac12|\mathrm{tr}(M)|^2 \end{align}\tag7 $$ where we used parallelogram law $|x-y|^2+|x+y|^2=2|x|^2+2|y|^2$. Setting $M:=C_E$, using $(5)$ and $(6)$ and summing over $\mathcal{E}_1$, we obatin $$ \sum_{E\in\mathcal{E}_1}\left\|C_E-\frac12 I\,\mathrm{tr}(C_E)\right\|^2_F = B_1 - \frac12 A_1.\tag8 $$ Thus, $\mathcal{C}$ is a distance-$2$ code if and only if $B_1-\frac12 A_1=0$.

$B_0$ in terms of $A_k$: basis expansion

It will be helpful to express $B_0$ and $B_1$ in terms of $A_k$. Pauli strings form an orthogonal basis, so $$ P=\frac18\sum_{E\in\mathcal{E}}\mathrm{tr}(EP)E.\tag9 $$ Multiplying both sides by $P$ and taking the trace, we have $$ \mathrm{tr}(P)=\frac18\sum_{E\in\mathcal{E}}\mathrm{tr}^2(EP)\tag{10} $$ where we recognize $B_0$ on the left hand side and one eighth of $A_0+A_1+A_2+A_3$ on the right $$ 8B_0=A_0+A_1+A_2+A_3.\tag{11} $$ However, $8B_0=16=4A_0$, so we can rewrite $(11)$ as $$ 0=-3A_0+A_1+A_2+A_3.\tag{12} $$

$B_1$ in terms of $A_k$: counting anticommuting Pauli strings

In order to express $B_1$ in terms of $A_k$, we substitute $(9)$ into the definition of $B_1$ $$ \begin{align} B_1&=\sum_{E\in\mathcal{E}_1}\mathrm{tr}(EPEP)\\ &= \frac{1}{64}\sum_{F,G\in\mathcal{E}}\sum_{E\in\mathcal{E}_1}\mathrm{tr}(FP)\mathrm{tr}(GP)\mathrm{tr}(EFEG)\\ &= \frac{1}{64}\sum_{F\in\mathcal{E}}\sum_{E\in\mathcal{E}_1}\mathrm{tr}^2(FP)\mathrm{tr}(EFEF)\\ &= \frac{1}{64}\sum_{k=0}^3 \left(\sum_{F\in\mathcal{E}_k}\mathrm{tr}^2(FP)\sum_{E\in\mathcal{E}_1}\mathrm{tr}(EFEF)\right).\tag{13} \end{align} $$ Now, we note that $\mathrm{tr}(EFEF)=\pm 8$ depending on whether $E$ and $F$ commute or anticommute. In particular, if $F\in\mathcal{E}_0$ then $\sum_{E\in\mathcal{E}_1}\mathrm{tr}(EFEF)=9\cdot 8$ since all nine elements of $\mathcal{E}_1$ commute with identity. Similarly, if $F\in\mathcal{E}_1$ then seven elements of $\mathcal{E}_1$ commute with $F$ and two anticommute, so $\sum_{E\in\mathcal{E}_1}\mathrm{tr}(EFEF)=5\cdot 8$. Continuing, we have $$ \begin{align} F\in\mathcal{E}_0\implies\sum_{E\in\mathcal{E}_1}\mathrm{tr}(EFEF)&=(9 - 0)\cdot 8 = 9 \cdot 8\\ F\in\mathcal{E}_1\implies\sum_{E\in\mathcal{E}_1}\mathrm{tr}(EFEF)&=(7 - 2)\cdot 8 = 5 \cdot 8\\ F\in\mathcal{E}_2\implies\sum_{E\in\mathcal{E}_1}\mathrm{tr}(EFEF)&=(5 - 4)\cdot 8 = 1 \cdot 8\\ F\in\mathcal{E}_3\implies\sum_{E\in\mathcal{E}_1}\mathrm{tr}(EFEF)&=(3 - 6)\cdot 8 = -3 \cdot 8.\tag{14} \end{align} $$ Substituting these results into $(13)$ and recognizing that $\sum_{F\in\mathcal{E}_k}\mathrm{tr}^2(FP)=A_k$, we obtain $$ 8B_1 = 9A_0 + 5A_1 + A_2 - 3A_3.\tag{15} $$

Shadow

We need one more ingredient before we can prove $(2)$. Define $$ S_0=\mathrm{tr}(PY^{\otimes 3}\overline{P}Y^{\otimes 3})\tag{16} $$ and note that $S_0$ is the Hilbert-Schmidt inner product of two positive operators $P$ and $Y^{\otimes 3}\overline{P}Y^{\otimes 3}$. Therefore, $S_0\ge 0$. Moreover, by expanding $Y^{\otimes 3}\overline{P}Y^{\otimes 3}$ in the operator basis $\mathcal{E}$, we have $$ \begin{align} Y^{\otimes 3}\overline{P}Y^{\otimes 3}&=\frac18\sum_{E\in\mathcal{E}}\mathrm{tr}(EY^{\otimes 3}\overline{P}Y^{\otimes 3})E\\ &=\frac18\sum_{E\in\mathcal{E}}(-1)^{\mathrm{wt}_x(E)+\mathrm{wt}_z(E)}\mathrm{tr}(Y^{\otimes 3}E\overline{P}Y^{\otimes 3})E\\ &=\frac18\sum_{E\in\mathcal{E}}(-1)^{\mathrm{wt}_x(E)+\mathrm{wt}_z(E)}\mathrm{tr}(E\overline{P})E\\ &=\frac18\sum_{E\in\mathcal{E}}(-1)^{\mathrm{wt}_x(E)+\mathrm{wt}_z(E)}\mathrm{tr}(\overline{E}P)E\\ &=\frac18\sum_{E\in\mathcal{E}}(-1)^{\mathrm{wt}_x(E)+\mathrm{wt}_y(E)+\mathrm{wt}_z(E)}\mathrm{tr}(EP)E\\ &=\frac18\sum_{E\in\mathcal{E}}(-1)^{\mathrm{wt}(E)}\mathrm{tr}(EP)E\\ \end{align}\tag{17} $$ which after multiplication by $P$, taking the trace and substituting from the definition of $A_k$ becomes $$ 8S_0=A_0-A_1+A_2-A_3.\tag{18} $$

Positive lower bound

To derive the promised positive lower bound, begin by subtracting $4A_1$ from both sides of $(15)$ $$ 8B_1-4A_1 = 9A_0 + A_1 + A_2 - 3A_3\tag{19} $$ and add $(12)$ to obtain $$ \begin{align} 8B_1-4A_1 &= 6A_0 + 2A_1 + 2A_2 - 2A_3\\ 4B_1-2A_1 &= 3A_0 + A_1 + A_2 - A_3. \end{align}\tag{20} $$ However, $\mathrm{tr}(EP)$ is real, so $A_1\ge 0$ and using $(18)$ we get $$ 4B_1-2A_1 \ge 3A_0 - A_1 + A_2 - A_3 = 2A_0 + 8S_0\tag{21}. $$ But $S_0\ge 0$ and we have $$ \begin{align} 4B_1-2A_1 \ge 2A_0=8.\tag{22} \end{align} $$ Finally, using $(8)$, we obtain $$ \sum_{E\in\mathcal{E}_1}\left\|C_E-\frac12 I\,\mathrm{tr}(C_E)\right\|^2_F = B_1-\frac12 A_1 \ge 2 > 0\tag{23} $$ which demonstrates that quantum error correction conditions for a code of distance two cannot be satisfied by a two-dimensional subspace $\mathcal{C}$ of the three-qubit Hilbert space $\mathbb{C}^{2^3}$. Therefore, no $[\![3,1,2]\!]$ code exists.$\square$

Answer 3

Here's a proof using the Shadow inequalities, analogous to what @Adam Zalcman described using the Shadow for qubit systems:

A $[\![3,1,2]\!]$ is a quantum maximum distance separable code (QMDS). QMDS codes can be purified to a $[\![4,0,3]\!]$ or absolutely maximally entangled state $\varrho$ on four qubits (Prop 7 in [1]). Such state has all 2-body marginals maximally mixed.

Now compute

$S_0 = \operatorname{tr}[(\varrho_{1234} \otimes \varrho_{1'2'3'4'}) (A_{11'} \otimes A_{22'} \otimes A_{33'} \otimes A_{44'})]$

where $A = \operatorname{I} - \operatorname{swap}$ is (proportional to) the projector onto the anti-symmetric subspace.

Being a trace inner product of two positive elements, $S_0$ must be non-negative. However, expanding $S_0$ by making use of the swap trick, $\operatorname{tr}(A \otimes B) = \operatorname{tr}(AB)$ gives

$S_0 = \operatorname{tr}(\varrho^2) - 4\operatorname{tr}(\varrho_{1}^2) + 3\operatorname{tr}(\varrho_{12}^2) - 4\operatorname{tr}(\varrho_{123}^2) + \operatorname{tr}(\varrho^2) = 1 - 4/2 + 6/4 - 4/2 + 1 = -1/2$

where I wrote the purity of only one marginal representative, because all $k$ body marginals have the same purity for given k.

Thus $S_0$ is negative, leading to a contradiction. Consequentially a $[\![3,1,2]\!]$ does not exist.

This is also described here [2], and the general Shadow-like inequalities were derived in [3] and corresponding matrix inequalities in [4].

[1] https://arxiv.org/abs/1907.07733
[2] https://arxiv.org/abs/1708.06298
[3] https://arxiv.org/abs/quant-ph/9704042
[4] https://arxiv.org/abs/2002.12887