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?


2 Answers 2


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.

  • 4
    $\begingroup$ The binary (GF(2)) matrix representation is known as the "check matrix" of the stabilizer code, and is discussed in Nielsen and Chuang in 10.5. Also, it's interesting to note that this problem (finding the distance) is in general NP-hard ieeexplore.ieee.org/document/6320261. You could try heuristics like that paper to maybe get some faster insight. $\endgroup$ Commented Jun 7, 2019 at 19:13

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.


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.