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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.