Universal Graph Representation of Stabilizer Codes

While stabilizer tableaus have proven useful as a descriptive tool for additive quantum codes, they otherwise offer little guidance for concrete constructions or algorithm analysis. We introduce a representation of stabilizer codes as graphs with certain structures, and prove via the ZX calculus that this representation is related to stabilizer tableaus by an efficiently computable bijection. This gives a new universal recipe for code construction by way of finding graphs with nice properties. The graph representation gives insight into both code construction and algorithms. We construct as examples families of <a:math xmlns:a="http://www.w3.org/1998/Math/MathML" display="inline"> <a:mtext>⟦</a:mtext> <a:mi>n</a:mi> <a:mo>,</a:mo> <a:mspace width="0.25em"/> <a:mi mathvariant="normal">Θ</a:mi> <a:mo stretchy="false">(</a:mo> <a:mfrac> <a:mi>n</a:mi> <a:mrow> <a:mi>log</a:mi> <a:mo></a:mo> <a:mi>n</a:mi> </a:mrow> </a:mfrac> <a:mo stretchy="false">)</a:mo> <a:mo>,</a:mo> <a:mspace width="0.25em"/> <a:mi mathvariant="normal">Θ</a:mi> <a:mo stretchy="false">(</a:mo> <a:mi>log</a:mi> <a:mo></a:mo> <a:mi>n</a:mi> <a:mo stretchy="false">)</a:mo> <a:mtext>⟧</a:mtext> </a:math> and <k:math xmlns:k="http://www.w3.org/1998/Math/MathML" display="inline"> <k:mtext>⟦</k:mtext> <k:mi>n</k:mi> <k:mo>,</k:mo> <k:mspace width="0.25em"/> <k:mi mathvariant="normal">Ω</k:mi> <k:mo stretchy="false">(</k:mo> <k:msup> <k:mi>n</k:mi> <k:mrow> <k:mn>4</k:mn> <k:mo>/</k:mo> <k:mn>5</k:mn> </k:mrow> </k:msup> <k:mo stretchy="false">)</k:mo> <k:mo>,</k:mo> <k:mspace width="0.25em"/> <k:mi mathvariant="normal">Θ</k:mi> <k:mo stretchy="false">(</k:mo> <k:msup> <k:mi>n</k:mi> <k:mrow> <k:mn>1</k:mn> <k:mo>/</k:mo> <k:mn>5</k:mn> </k:mrow> </k:msup> <k:mo stretchy="false">)</k:mo> <k:mtext>⟧</k:mtext> </k:math> codes. We use graphs in a probabilistic analysis to extend the quantum Gilbert-Varshamov bound into a three-way distance-rate-weight trade-off. Moreover, code properties such as distance and encoding circuit depth are bounded by simple functions of the graph degree. We prove that key coding algorithms—distance approximation, minimum-weight generator selection, and decoding—are unified as instances of one optimization game on a graph. By studying this game, we construct an efficient greedy decoder and prove that it corrects all recoverable errors for all graphs with cycle lengths no shorter than 13 (reducible to 5 with mild extra constraints); these include the above two families. Our results suggest that graphs are generically useful for the study of stabilizer codes.