Lower bound on hamming distance bounded error correction using qubits

When using $n$ physical qubits to represent $1$ logical Qubit, In order to correct both $X$ and $Z$ flips (Bit flip and Phase Flip) in any of the physical qubits, we need at least $5$ Qubits. This is equivalent to fixing all errors with at most hamming distance $1$.

Proof

We are using $n$ physical qubits to represent a logical Qubit. Assume we had at most 1 error in the physical qubits. By performing $k$ Measurements on the physical qubits, we are able to at most distinguish at most $2^k$ errors. Since we do not want to destroy our quantum state completely, we are only allowed to make $n-1$ Measurements, leaving one degree of freedom to hold the state of the logical Qubit. Hence we can at most distinguish $2^{n-1}$ states.

There are $2n+1$ states we might be in, given by $\{\begin{array}{rl}n& ,\text{X Flip}\\ n& ,\text{Z Flip}\\ 1& ,\text{No errors}\end{array}$. As such we get the table:

$n$	1	2	3	4	5	6
$2n+1$	3	5	7	9	11	13
$2^{n-1}$	1	2	4	8	16	32

Only for $n\ge 5$ are we able to distinguish enough states so that we can correct all errors with hamming distance 1.

This limit is strict: it has been achieved using Shor’s 5 qubit error correcting code

Distance 2 error correction

Following a reasoning similar to the above, we can have 1 + 2n + \left ( \begin{array} 2n \\ 2 \end{array} \right ) = 1 + 2n + \frac{2n(2n-1)}{2} = 1 + 2n + n(2n-1) = 1+n +2n^2 possible errors, and we are still bound by the $2^{n-1}$ possible states we can distinguish. As such we have

$n$	1	2	3	4	5	6	7	8	9
$1+n+2n^2$	4	11	22	37	56	79	106	137	172
$2^{n-1}$	1	2	4	8	16	32	64	128	256

This shows that we need at least $9$ physical qubits in order to correct all errors with hamming distance $2$ or lower.

General methodology

If we want to be able to correct errors with hamming distance at most $k$, we have ${\sum }_{i=0}^k\left(\begin{array}{c}n\\ i\end{array}\right)$ possible errors to correct. The least number of physical qubits needed is given by the smallest $n\in {\mathbb{Z}}^{+}$ such that $2^{n-1}\ge {\sum }_{i=0}^k\left(\begin{array}{c}n\\ i\end{array}\right)$. This number always exists as the left hand side is exponential, where as the right hand side grows as a polynomial of degree $k$. Since all coefficients of the polynomial are positive, once the equality holds for a given $n$, it also holds for all integers $\ge n$.