How to show that the three-qubit repetition code only corrects up to 1-bit flip errors?

From Nielsen and Chuang, the error correction criteria is $$P E_i^{\dagger} E_j P=\alpha_{i j} P$$ $$P$$ is the projector onto the correct codespace, $$E_{j}$$ are error operations and $$\alpha_{i j}$$ is a Hermitian matrix. Using this, how do I show that, the three-qubit repetition code can only correct up to 1-bit flip error?

Furthermore, what are the relevant Kraus operators for an error channel with both single and double-bit flips?

Let's refer to the theorem from Nielson and Chuang,

This theorem says that if you are given a set of errors $$\{E_i\}$$, and if it satisfies condition 10.16 then it is a correctable set of errors. If the set does not satisfy the conditions, then the set is not correctable set of errors.

Critical here is that if a set is not correctable, it does not mean that every error in the set is not correctable. Its possible that subset of errors in the set are correctable.

So, what we can do is for any given code, look at different possible sets of errors, and check if the code corrects the set or not.

The repetition code

Let's now see how this applies to the repetition code. The projector as you know is $$P = (|000\rangle \langle 000| + |111\rangle \langle 111|)/2.$$ In anticipation of what is to follow, lets compute the following.

\begin{align} PIP &= P, \\ PX_lP &= 0, \\ PX_lX_mP &= 0, \quad (l \ne m), \\ PX_1X_2X_3P &= |111\rangle \langle 000| + |000\rangle \langle 111| \not\propto P. \end{align}

We will consider the following three sets of errors.

1. $$\{I, X_1, X_2, X_3\}$$
2. $$\{I, X_1X_2, X_1X_3, X_2X_3\}$$
3. $$\{I, X_1, X_2, X_3, X_1X_2, X_1X_3, X_2X_3\}$$

Set 1

It is easy to compute in this case that $$\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix}$$ In this case condition 10.16 is satisfied. Which is why we can say that set of single-qubit bit flips are correctable by the repetition code.

Set 2

Again, we can easily find that $$\alpha = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{pmatrix},$$ Therefore, the condition 10.16 is satisfied, and this set is a correctable set of errors. So, similar to this question/answer, we discover that if we are guaranteed that either we get no error or only two-qubit bit flips, then the repetition code works to correct all errors.

Set 3

This is where the problem is. If we set $$E_i = X_l$$ and $$E_j = X_mX_n$$ with $$l \ne m \ne n$$, then $$E_i^\dagger E_j = X_1X_2X_3$$. In this case, we find that $$PE_i^\dagger E_jP \not \propto P$$. So, condition 10.16 is not satisfied for every pair $$E_i, E_j$$. Therefore, set 3 does not constitute a correctable set of errors.

In other words, if our noise channel has single-qubit and two-qubit bit flips affecting the qubits, then the repetition code fails to correct all errors. In particular, $$P(X_l)(X_mX_n)P\not \propto P$$ tells us exactly what we can infer otherwise. That the repetition code cannot tell if a single-qubit occurred, or the complementary two-qubit error occured.

It is left as an exercise to the reader to figure out what happens if we add three-qubit errors to the mix.

Following this presentation, we have the following 5 qubit error-protecting circuit for the original 1 qubit:

Step 1:

$$(\alpha|0\rangle + \beta|1\rangle)|0000\rangle$$ $$=\alpha|00000\rangle + \beta|10000\rangle$$

Step 2,3:

$$\alpha|00000\rangle + \beta|11100\rangle$$

Step 4:

Suppose there exist some error-producing probabilities for each of qubit 1, 2, 3 such that

$$\boxed{|0\rangle_{q1} \rightarrow a|0\rangle + b|1\rangle \\|0\rangle_{q2} \rightarrow c|0\rangle + d|1\rangle \\ |0\rangle_{q3} \rightarrow e|0\rangle + f|1\rangle \\|1\rangle_{q1} \rightarrow g|0\rangle + h|1\rangle \\|1\rangle_{q2} \rightarrow i|0\rangle + j|1\rangle \\|1\rangle_{q3} \rightarrow k|0\rangle + l|1\rangle}$$

Then, $$\alpha(a|0\rangle + b|1\rangle)(c|0\rangle + d|1\rangle)(a|e\rangle + f|1\rangle)|00\rangle + \beta|((g|0\rangle + h|1\rangle)(i|0\rangle + j|1\rangle)(ak|0\rangle + l|1\rangle)00\rangle$$

$$=\alpha ace|00000\rangle + \alpha acf|00100\rangle + \alpha ade|01000\rangle + \alpha adf|01100\rangle + \alpha bce|10000\rangle + \alpha bcf|10100\rangle + \alpha bde|11000\rangle + \alpha bdf|11100\rangle + \beta gik|00000\rangle + \beta gil|00100\rangle + \beta gjk|01000\rangle + \beta gjl|01100\rangle + \beta hik|10000\rangle + \beta hil|10100\rangle + \beta hjk|11000\rangle + \beta hjl|11100\rangle$$

Step 5, 6, 7, 8:

$$\alpha ace|00000\rangle + \alpha acf|00101\rangle + \alpha ade|01011\rangle + \alpha adf|01110\rangle + \alpha bce|10010\rangle + \alpha bcf|10111\rangle + \alpha bde|11001\rangle + \alpha bdf|11100\rangle + \beta gik|00000\rangle + \beta gil|00101\rangle + \beta gjk|01011\rangle + \beta gjl|01110\rangle + \beta hik|10010\rangle + \beta hil|10111\rangle + \beta hjk|11001\rangle + \beta hjl|11100\rangle$$

$$=\alpha ace|000\rangle|00\rangle + \alpha acf|001\rangle|01\rangle + \alpha ade|010\rangle|11\rangle + \alpha adf|011\rangle|10\rangle + \alpha bce|100\rangle|10\rangle + \alpha bcf|101\rangle|11\rangle + \alpha bde|110\rangle|01\rangle + \alpha bdf|111\rangle|00\rangle + \beta gik|000\rangle|00\rangle + \beta gil|001\rangle|01\rangle + \beta gjk|010\rangle|11\rangle + \beta gjl|011\rangle|10\rangle + \beta hik|100\rangle|10\rangle + \beta hil|101\rangle|11\rangle + \beta hjk|110\rangle|01\rangle + \beta hjl|111\rangle|00\rangle$$

$$=\color{red}{[\alpha ace|000\rangle + \alpha bdf|111\rangle + \beta gik|000\rangle + \beta hjl|111\rangle]}|00\rangle + \color{red}{[\alpha acf|001\rangle + \alpha bde|110\rangle + \beta gil|001\rangle + \beta hjk|110\rangle]}|01\rangle + \color{red}{[\alpha adf|011\rangle + \alpha bce|100\rangle + \beta gjl|011\rangle + \beta hik|100\rangle]}|10\rangle + \color{red}{[\alpha ade|010\rangle + \alpha bcf|101\rangle + \beta gjk|010\rangle + \beta hil|101\rangle]}|11\rangle$$

Suppose a small $$5\%$$ independent probability of error exist for each qubit.

$$a = \sqrt{0.95}, b = \sqrt{0.05}$$ $$c = \sqrt{0.95}, d = \sqrt{0.05}$$ $$e = \sqrt{0.95}, f = \sqrt{0.05}$$ $$g = \sqrt{0.05}, h = \sqrt{0.95}$$ $$i = \sqrt{0.05}, j = \sqrt{0.95}$$ $$k = \sqrt{0.05}, l = \sqrt{0.95}$$

Then

$$=\color{red}{[ 0.93\alpha|000\rangle + 0.01\alpha|111\rangle + 0.01\beta|000\rangle + 0.93\beta|111\rangle]}|00\rangle + \color{red}{[ 0.21\alpha|001\rangle + 0.05\alpha|110\rangle + 0.05\beta|001\rangle + 0.21\beta|110\rangle]}|01\rangle + \color{red}{[ 0.05\alpha|011\rangle + 0.21\alpha|100\rangle + 0.21\beta|011\rangle + 0.05\beta|100\rangle]}|10\rangle + \color{red}{[ 0.21\alpha|010\rangle + 0.05\alpha|101\rangle + 0.05\beta|010\rangle + 0.21\beta|101\rangle]}|11\rangle$$

Now we measure the $$4^{th}$$ and $$5^{th}$$ parity bits to collapse the above into exactly one branch.

$$|00\rangle \rightarrow \color{red}{[ 0.93\alpha|000\rangle + 0.01\alpha|111\rangle + 0.01\beta|000\rangle + 0.93\beta|111\rangle]}$$

This branch contains mostly error free results with a very small chance of 3 simultaneous errors. $$\alpha, \beta$$ survive uncollapsed and may be amplified/post-processed as needed.

$$|01\rangle \rightarrow \color{red}{[ 0.21\alpha|001\rangle + 0.05\alpha|110\rangle + 0.05\beta|001\rangle + 0.21\beta|110\rangle]}$$

This branch contains mostly single error results with a very small chance of 2 simultaneous errors. $$\alpha, \beta$$ survive uncollapsed and may be amplified/post-processed as needed.

$$|10\rangle \rightarrow \color{red}{[ 0.05\alpha|011\rangle + 0.21\alpha|100\rangle + 0.21\beta|011\rangle + 0.05\beta|100\rangle]}$$

This branch contains mostly single error results with a very small chance of 2 simultaneous errors. $$\alpha, \beta$$ survive uncollapsed and may be amplified/post-processed as needed.

$$|11\rangle \rightarrow \color{red}{[ 0.21\alpha|010\rangle + 0.05\alpha|101\rangle + 0.05\beta|010\rangle + 0.21\beta|101\rangle]}$$

This branch also contains mostly single error results (middle qubit being the error) with a very small chance of 2 simultaneous errors. $$\alpha, \beta$$ survive uncollapsed and may be amplified/post-processed as needed.

Therefore, collapsing parity bits $$q_4, q_5$$ results in $$> 95\%$$ of the errors being single qubit errors. $$\alpha, \beta$$ survive uncollapsed and may be amplified/post-processed as needed.

Consider

$$(\alpha |0\rangle + \beta |1\rangle)$$

where

$$|0\rangle \rightarrow a|0\rangle + b|1\rangle$$ $$|1\rangle \rightarrow c|0\rangle + d|1\rangle$$

Then

$$(\alpha |0\rangle + \beta |1\rangle)\rightarrow (\alpha (a|0\rangle + b|1\rangle) + \beta( c|0\rangle + d|1\rangle)$$ $$= \alpha a|0\rangle + \alpha b|1\rangle + \beta c|0\rangle + \beta d|1\rangle$$

Suppose $$a=1, b=0, c=0, d=-1$$, then

$$\alpha |0\rangle - \beta |1\rangle$$

constitutes a phase-flip error.

Suppose $$a=0, b=1, c=1, d=0$$, then

$$\beta |0\rangle + \alpha |1\rangle$$

constitutes a bit-flip error.

Suppose $$a=0, b=-1, c=1, d=0$$, then

$$\beta |0\rangle - \alpha |1\rangle$$

constitutes a bit-flip + phase-flip error.

Maximizing protection, we attempt the following 7 qubit error-protecting circuit for the original 1 qubit:

Step 1:

$$(\alpha|0\rangle + \beta|1\rangle)|000000\rangle$$ $$=\alpha|0000000\rangle + \beta|1000000\rangle$$

Step 2,3:

$$\alpha|0000000\rangle + \beta|1110000\rangle$$

Step 4:

$$\alpha(a|0\rangle + b|1\rangle)(c|0\rangle + d|1\rangle)(a|e\rangle + f|1\rangle)|0000\rangle + \beta|((g|0\rangle + h|1\rangle)(i|0\rangle + j|1\rangle)(ak|0\rangle + l|1\rangle|0000\rangle$$

$$=\alpha ace|0000000\rangle + \alpha acf|0010000\rangle + \alpha ade|0100000\rangle + \alpha adf|0110000\rangle + \alpha bce|1000000\rangle + \alpha bcf|1010000\rangle + \alpha bde|1100000\rangle + \alpha bdf|11100\rangle + \beta gik|00000\rangle + \beta gil|0010000\rangle + \beta gjk|0100000\rangle + \beta gjl|0110000\rangle + \beta hik|1000000\rangle + \beta hil|1010000\rangle + \beta hjk|1100000\rangle + \beta hjl|1110000\rangle$$

Step 5, 6, 7, 8,9,10,11,12,13:

$$\alpha ace|0000000\rangle + \alpha acf|0010111\rangle + \alpha ade|0101101\rangle + \alpha adf|0111010\rangle + \alpha bce|1001011\rangle + \alpha bcf|1011100\rangle + \alpha bde|1100110\rangle + \alpha bdf|1110001\rangle + \beta gik|0000000\rangle + \beta gil|0010111\rangle + \beta gjk|0101101\rangle + \beta gjl|0111010\rangle + \beta hik|1001011\rangle + \beta hil|1011101\rangle + \beta hjk|1100110\rangle + \beta hjl|1110001\rangle$$

$$\color{red}{(\alpha ace|000\rangle + \beta gik|000\rangle)}|0000\rangle + \color{red}{(\alpha acf|001 + \beta gil|001\rangle)}|0111\rangle + \color{red}{(\alpha ade|010\rangle + \beta gjk|010\rangle)}|1101\rangle + \color{red}{(\alpha adf|011\rangle + \beta gjl|011\rangle)}|1010\rangle + \color{red}{(\alpha bce|100\rangle + \beta hik|100\rangle)}|1011\rangle + \color{red}{(\alpha bcf|101\rangle + \beta hil|101\rangle)}|1100\rangle + \color{red}{(\alpha bde|110\rangle + \beta hjk|110\rangle)}|0110\rangle + \color{red}{(\alpha bdf|111\rangle + \beta hjl|111\rangle)}|0001\rangle$$

Now we measure the $$q_4, q_5, q_6, q_7$$ parity bits to collapse the 8 possibilities above into exactly one branch.

$$|0000\rangle \rightarrow \color{red}{0.93\alpha|000\rangle + 0.01\beta |000\rangle}$$

$$|0111\rangle \rightarrow \color{red}{0.21\alpha |001 + 0.21\beta|001\rangle}$$

$$...$$

Thus, $$\alpha, \beta$$ survive uncollapsed, but over-protection causes the states to no longer be distinguishable by observation.