Universal graph representation of stabilizer codes
arXiv:2411.14448 · doi:10.1103/1gjs-2rhx
Abstract
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 and 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.
This paper subsumes arXiv:2301.02356. v4: added about 20 new figures
References in corpus (32)
- Supplementary information for "Quantum supremacy using a programmable superconducting processor"
- Surface codes: Towards practical large-scale quantum computation
- Quantum Simulation
- Improved Simulation of Stabilizer Circuits
- Predicting Many Properties of a Quantum System from Very Few Measurements
- Extending the computational reach of a noisy superconducting quantum processor
- Holographic quantum error-correcting codes: Toy models for the bulk/boundary correspondence
- Boson sampling with 20 input photons in 60-mode interferometers at state spaces
- High-threshold and low-overhead fault-tolerant quantum memory
- Deterministic generation of a two-dimensional cluster state
- Quantum error-correcting codes associated with graphs
- Repeated Quantum Error Detection in a Surface Code
- Quantum Low-Density Parity-Check Codes
- Quantum LDPC codes with positive rate and minimum distance proportional to n^{1/2}
- Implementation of the Five Qubit Error Correction Benchmark
- Graph-theoretic Simplification of Quantum Circuits with the ZX-calculus
- Superdense coding of quantum states
- Reducing T-count with the ZX-calculus
- Balanced Product Quantum Codes
- Fault-tolerant quantum computation with few qubits
- The ZX-calculus is complete for stabilizer quantum mechanics
- The ZX calculus is a language for surface code lattice surgery
- Equivalence Checking of Quantum Circuits with the ZX-Calculus
- Constructing quantum circuits with global gates
- Constructions and performance of hyperbolic and semi-hyperbolic Floquet codes
- Graphical Structures for Design and Verification of Quantum Error Correction
- Graph Concatenation for Quantum Codes
- Quantum double aspects of surface code models
- Complete Flow-Preserving Rewrite Rules for MBQC Patterns with Pauli Measurements
- On the Hardness of the Minimum Distance Problem of Quantum Codes
- AKLT-states as ZX-diagrams: diagrammatic reasoning for quantum states
- Engineering holography with stabilizer graph codes