3
$\begingroup$

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?

$\endgroup$

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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