How to calculate the distance of stabilizer code?

Question

How to calculate the distance of the stabilizer code [[n,k,d]]? It's better if you can make a 3-qubit example. And what's the relationship between d and Pauli group?

Answer 1

There are various ways that you might go about computing the distance. I'll give a fairly general strategy here, although I'm sure here are imprvements that can be made.

Your starting point is a set of stabilizers $\{K_n\}$ on $N$ qubits, satisfying $K_n^2=I$ and $[K_n,K_m]=0$. Generically, you want to consider the full set of $4^N$ possible tensor products of Pauli operators $\{I,X,Y,Z\}$ across all $N$ sites. Go through each of these in turn. If it does not commute with each and every $K_n$, discard it. If it can be written as a product of some subset of the $K_n$, discard it. From the set that you have left, find the term with the smallest weight (i.e. the number of terms that are not $I$). That's the distance.

For example, consider the stabilizers $$ K_1=Z\otimes Z\otimes Z,\qquad K_2=X\otimes X\otimes I $$ I'm not writing out all 64 possible terms here, but stare at it for a minute. You'll realise that $I\otimes I\otimes Z$ commutes with both and cannot be written as a product of the two, so the distance is 1. The problem is that $N=3$ is a bit too simple an example to be able to show you too much.

A brief comment on how I would do the maths: I'd set up a computer to do it, using binary matrices. I'd describe each stabilizer generator by a row of $2N$ elements. The first $N$ are a binary string showing where the $Z$s are, and the second $N$ are a binary string showing where the $X$s are. Commutation is a simple linear algebra check, and similarly, we can check for the containment of stabilizers in a term by using an inner product. All calculations are performd modulo 2.

Answer 2

Sorry to bring this back from the dead, but someone recently linked to this question.

The algorithms the poster is looking for are based on trellises or the Brouver-Zimmerman algorithm. See the papers by me for the former and by Grassl and Greg White's dissertation for the latter. Pryadko also recently released a probabilistic algorithm to do this.

The fact that it's NP-hard in general doesn't mean we can't do it. It simply means we shouldn't expect to do it quickly as $n, k \to \infty$. The NP-ness often causes people to immediately give up on computing something.