According to (Macchiavello, Palma, Zeilinger, 2001; pg82) a lower bound of the encoding Hilbert space of a non degenerate code is given by the quantum version of the Hamming bound: $$2^k \sum_{i=0}^t 3^i \begin{pmatrix} n \\ i\end{pmatrix}\le 2^n$$ where we are looking at a $[n,k,2t+1]$ code. Does such a bound exist for a degenerate code? and why is it different (if it indeed is)?


1 Answer 1


This bound works by counting the number of orthogonal states that must be available. If you're encoding into $n$ qubits, you can't require more than $2^n$ orthogonal states, because that's all that's available. This is the right hand side of the bound.

If you wish to encode $k$ logical qubits in a distance $2t+1$ code, then each of the $2^k$ basis states of those logical qubits must encode to something different. Moreover, you need to be able to correct for up to $t$ errors of type $X$, $Y$ or $Z$. If we require each of these to map to a different orthogonal state, then there are $3n$ possible 1-qubit errors, $3^2\binom{n}{2}$ 2-qubit errors (choice of one of 3 Paulis for each error, and a pair of locations for them to happen at), and so on. So, this gives the stated bound, known as the Quantum Hamming bound (also Gilbert-Varshamov). However, an essential feature of the derivation is the assumption that each error is mapped onto a different orthogonal state.

The very definition of a degenerate code is that multiple errors can be mapped onto the same state. As a trivial example, consider the effect of a single-qubit $Z$ error on any one of the qubits of the GHZ state $$ \frac{1}{\sqrt{2}}(|0\rangle^{\otimes n}+|1\rangle^{\otimes n}). $$ No matter where that error happens, the resultant state is the same, but that's fine: I don't need to be able to identify which of the $n$ qubits the error happened on to fix it. Once I know the error has happened, I can apply a $Z$ gate on any of the qubits that I choose in order to fix it. (I don't claim that this example enables you to detect that error.) So, the Quantum Hamming bound does not apply to degenerate codes. Indeed, there are known examples where the bound is beaten, e.g. D. P. DiVincenzo, P. W. Shor, and J. A. Smolin, Phys. Rev. A 57, 830 (1998) (free version), although there are surprisingly few.

The only replacement that I know of is the Quantum Singleton Bound, $n-k\geq 4t$. The Quantum Hamming bound, in practice, appears to give very good estimates of what can be achieved, but is not absolute when it comes to degenerate codes.


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.