# For any given parameters, does there always exist a quantum code which saturates the Quantum Hamming Bound?

We know that the Quantum Hamming Bound is as follows:

$$\sum_{j=0}^t 3^j {n\choose j} \leq 2^{n-k}$$

where

• $$n$$ is the number of physical qubits,
• $$k$$ is the number of logical qubits,
• $$t$$ is the maximum weight for which all errors are correctable.

For any given $$t$$ and $$k$$, should there always exist of code with $$n$$ physical qubits which saturates this bound? How can we go about trying to prove/disprove this in a more formal manner?

TL;DR: No. There exist $$t$$ and $$k$$ for which the Quantum Hamming Bound (QHB) cannot be saturated by any block size $$n$$.

## Constraint on block size $$n$$

Consider the simplest case of $$t=1$$ in which the QHB takes the form $$\sum_{j=0}^t3^j {n\choose j}=1+3n\leqslant 2^{n-k}\tag1$$ or equivalently $$k\leqslant n-\log_2(1+3n).\tag2$$ The inequality can only be saturated by integer values of $$k$$ and $$n$$ if $$\log_2(1+3n)$$ is an integer. This happens if and only if the binary representation of $$n$$ takes the form$$^1$$ $$10101\dots 101\tag3$$ i.e. if and only if $$n\in F$$ where $$F:=\{1,5,21,85,\dots\}$$ is the set of sums of consecutive powers of four beginning with $$4^0=1$$.

Thus, we have a necessary condition for a code $$[\![n,k,3]\!]$$ to saturate QHB: it must be the case that $$n\in F$$.

## Constraint on number $$k$$ of encoded qubits

Define $$f(x):=x-\log_2(1+3x)$$ and let $$f[F]$$ denote the image of $$F$$ under $$f$$. We can strengthen the above necessary condition for a code $$[\![n,k,3]\!]$$ to saturate QHB as follows: it must be the case that $$n\in F$$ and $$k=f(n)$$. In particular, it must be the case that $$k\in f[F]$$.

By calculus, $$f$$ is strictly increasing on positive integers$$^2$$. Moreover, evaluating $$f$$ on the first few elements of $$F$$, we find $$f(1)=-1, f(5)=1, f(21)=15, f(85)=77.\tag4$$ Clearly, there are gaps, so $$\mathbb{Z}_+\setminus f[F]$$ is non-empty.

## Conclusion

For $$t=1$$ and any $$k\in\mathbb{Z}_+\setminus f[F]$$ there exists no $$n$$ saturating the Quantum Hamming Bound.

$$^1$$ Fun exercise.
$$^2$$ The derivative of $$f(x)$$ has a single root at $$x_*=\frac{3-\ln2}{3\ln2}\approx1.1$$ and is positive for $$x>x_*$$, so $$f(x)$$ is strictly increasing for $$x>x_*$$. However, $$f(1)=-1<2-\log_27=f(2)$$, so $$f(x)$$ is in fact strictly increasing on all positive integers.

Why not take the special case of $$t=1,k=2$$ (because we know $$t=1,k=1$$ has a solution). You are looking for an integer value of $$n$$ such that $$1+3n=2^{n-2}.$$ I claim there is not such solution. One way to see this is to define $$f(n)=1+3n-2^{n-2}$$. We can work out a few values

n 3 4 5 6 7
f(n) 8 9 8 3 -10

So, no solution $$f(n)=0$$ for those values of $$n$$. But for $$n>4$$, $$f(n)$$ is a decreasing function ($$\frac{df}{dn}=3-2^{n-2}\log2$$), so it only becomes more negative for larger values of $$n$$, so there cannot be a solution.