# Quantum Error Correcting Codes and Graphs

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?

• – D.W.
Aug 14 '20 at 8:54

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.