11
$\begingroup$

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 $.

$\endgroup$

2 Answers 2

7
+50
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ Nice! The shadow enumerators paper, below theorem 10, mentions the bounds in the GF(4) paper arxiv.org/abs/quant-ph/9608006. The GF(4) paper has a table, made from the same type of inequalities used in your answer, with bounds on maximum distance given $ n $ and $ k $ (the table was originally meant for additive codes, but it turns out the bounds are valid for all codes, except where they are marked by $ \beta $ in which case the bound is +1 for the non-additive case). In particular, the table states that every $ [[3,1,d]] $ code is $ d=1 $, confirming what you have worked out above. $\endgroup$ Aug 5, 2022 at 12:59
  • $\begingroup$ @IanGershonTeixeira It bugged me a bit that this proof wasn't standalone, especially since there appear to be some errors in the arxiv version of one of the papers, so I "extracted" the core argument and wrote it out in elementary terms (where "elementary" means "using linear algebra and quantum error correction conditions"). See the other answer I just posted. Perhaps this is of some use (for example, it might serve as a light introduction to weight and shadow enumerators). $\endgroup$ Aug 14, 2022 at 23:01
  • $\begingroup$ For an arbitrary $ [[n,k,d]] $ code is it always the case that the $ A_i $ are integers? $\endgroup$ Feb 12, 2023 at 15:05
3
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.