Quantum Error Correcting Codes and Graphs

Question

Couple of weeks ago I asked this question on theory CS but I didn't get an answer. So trying it here.

I was reading combinatorial approach towards quantum correction. A lot of work in this is on finding diagonal distance of a graph. Let me add definition of diagonal distance so that this remains self-contained.

Given a labeling $L$ (a map where each vertex is is assigned 1 or 0) we define two operations on this:

1. $X(v,L)$: you flip labeling of vertex v that is if it was zero make it 1 if it was 1 make it 0.

2. $Z(v,L)$: you flip labeling of every neighbor of vertex v

Then diagonal distance is defined as length of minimal non-trivial sequence of operation so that $L$ is taken back to itself.

How is this exactly related to the quantum error correction property?

Answer 1

The distance of an error correcting code is the smallest number of single-qubit rotations that you have to apply to map one logical codeword into an orthogonal one. If I express it in terms of the stabilizers of the code, it's the smallest tensor product of single-qubit unitaries (usually Paulis) that commutes with all the generators.

Let's see how this connects to a graph state description. Usually a graph state has stabilizers defined as $X$ on a vertex, and $Z$ on all the neighbouring vertices. So, imagine that I store as a 0 or 1 on a give vertex whether the current tensor product of Pauli errors commutes with that stabilizer or not. If I apply an $X$ on that vertex, or a $Z$ on any of the neighbouring vertices, it flips whether the tensor product commutes or anti-commutes, so I simply flip the 0/1 value on the vertex. When all stabilizers commute, we've implemented a logical error or something that is a product of the stabilizers. So long as you eliminate the possibility that it is a product of stabilizers (probably what is meant by 'non-trivial'), you've found a logical error. Then you're just after the shortest such sequence.