Universal Graph Representation of Stabilizer Codes - Andrey Boris Khesin скачать в хорошем качестве

Universal Graph Representation of Stabilizer Codes - Andrey Boris Khesin

arXiv: https://arxiv.org/pdf/2411.14448 Abstract: While stabilizer tableaus have proven exceptionally useful as a descriptive tool for additive quantum codes, they otherwise offer little guidance for concrete constructions or coding algorithm analysis. We introduce a representation of [[n, k]] stabilizer codes as graphs with certain structures. Specifically, the graphs take a semi-bipartite form wherein k “input” nodes map to n “output” nodes, such that output nodes may connect to each other but input nodes may not. We prove by passage through the ZX Calculus that this graph representation is in bijection with tableaus and give an efficient compilation algorithm that transforms tableaus into graphs. We then show that this map is efficiently invertible, which gives a new universal recipe for code construction by way of finding graphs with sufficiently nice properties. The graph representation gives insight into both code construction and algorithms. To the former, we argue that graphs provide a flexible platform for building codes particularly at smaller (non-asymptotic) scales. We construct as examples constant-size codes, e.g. a [[54, 6, 5]] code and families of [[n, Θ( n/log n), Θ(log n)]] and [[n, Ω(n^{3/5}), Θ(n^{1/5})]] codes. We also leverage graphs in a probabilistic analysis to extend the quantum Gilbert-Varshamov bound into a three-way distance-rate-weight trade-off. To the latter, we show that key coding algorithms—distance approximation, weight reduction, and decoding—are unified as instances of a single optimization game on a graph. Moreover, key code properties such as distance, weight, and encoding circuit depth, are all controlled by the graph degree. We give efficient algorithms for producing simple encoding circuits whose depths scale as twice the degree and for implementing logical diagonal and certain Clifford gates with reduced depth. Finally, we construct a simple efficient decoding algorithm and prove a performance guarantee for a certain class of graphs, including the above two families. This class contains all graphs of girth at least 9, building a bridge between stabilizer codes and extremal graph theory. These results give evidence that graphs are generically useful for the study of stabilizer codes and their practical implementations. Joint-Work With: Jonathan Z. Lu and Peter W. Shor Presented at the ZX-calculus seminar on the 10th of March 2025.