Universal graph representation of stabilizer codes

• URL: http://arxiv.org/abs/2411.14448v3
• Date: Mon, 10 Feb 2025 17:15:22 GMT
• Title: Universal graph representation of stabilizer codes
• Authors: Andrey Boris Khesin, Jonathan Z. Lu, Peter W. Shor,
• Abstract summary: We introduce a representation of stabilizer codes as graphs with certain structures. The graph representation gives insight into both code construction and algorithms. Key code properties such as distance, weight, and encoding circuit depth are all controlled by the graph degree.
• Score: 1.6385815610837167
• License:
• Abstract: 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 small scales. We construct as examples constant-size codes, e.g. a $[[54, 6, 5]]$ code and families of $[[n, \Theta(\frac{n}{\log n}), \Theta(\log n)]]$ and $[[n, \Omega(n^{3/5}), \Theta(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. 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.

Related papers

• Quantum Computing from Graphs [0.0]
  We introduce a representation of stabilizer codes as graphs with certain structures. The graph representation gives insight into both code construction and algorithms. We also use graphs to extend the quantum Gilbert-Varshamov bound to a three-way distance-rate-weight trade-off.
  arXiv  Detail & Related papers  (2025-01-29T19:47:39Z)
• Cayley Graph Propagation [0.0]
  We show that truncation is detrimental to the expansion properties of Cayley graph structures. Instead, we propose CGP, a method to propagate information over a complete Cayley graph structure.
  arXiv  Detail & Related papers  (2024-10-04T13:32:34Z)
• A Graph is Worth $K$ Words: Euclideanizing Graph using Pure Transformer [47.25114679486907]
  We introduce GraphsGPT, featuring a Graph2Seq encoder that transforms Non-Euclidean graphs into learnable Graph Words. A GraphGPT decoder reconstructs the original graph from Graph Words to ensure information equivalence.
  arXiv  Detail & Related papers  (2024-02-04T12:29:40Z)
• Efficient Signed Graph Sampling via Balancing & Gershgorin Disc Perfect Alignment [51.74913666829224]
  We show that for datasets with strong inherent anti-correlations, a suitable graph contains both positive and negative edge weights. We propose a linear-time signed graph sampling method centered on the concept of balanced signed graphs. Experimental results show that our signed graph sampling method outperformed existing fast sampling schemes noticeably on various datasets.
  arXiv  Detail & Related papers  (2022-08-18T09:19:01Z)
• A Near-Optimal Best-of-Both-Worlds Algorithm for Online Learning with Feedback Graphs [21.563733343861713]
  We consider online learning with feedback graphs, a sequential decision-making framework where the learner's feedback is determined by a directed graph over the action set. We present a computationally efficient algorithm for learning in this framework that simultaneously achieves near-optimal regret bounds in both and adversarial environments.
  arXiv  Detail & Related papers  (2022-06-01T15:14:32Z)
• Partition and Code: learning how to compress graphs [50.29024357495154]
  "Partition and Code" framework entails three steps: first, a partitioning algorithm decomposes the graph into elementary structures, then these are mapped to the elements of a small dictionary on which we learn a probability distribution, and finally, an entropy encoder translates the representation into bits. Our algorithms are quantitatively evaluated on diverse real-world networks obtaining significant performance improvements with respect to different families of non-parametric and parametric graph compressor.
  arXiv  Detail & Related papers  (2021-07-05T11:41:16Z)
• Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
  Graphon is a nonparametric model that generates graphs with arbitrary sizes and can be induced from graphs easily. We propose a novel framework called textitgraphon autoencoder to build an interpretable and scalable graph generative model. A linear graphon factorization model works as a decoder, leveraging the latent representations to reconstruct the induced graphons.
  arXiv  Detail & Related papers  (2021-05-29T08:11:40Z)
• Random Graph Matching with Improved Noise Robustness [2.294014185517203]
  We propose a new algorithm for graph matching under probabilistic models. Our algorithm recovers the underlying matching with high probability when $alpha le 1 / (log log n)C$. This improves the condition $alpha le 1 / (log n)C$ achieved in previous work.
  arXiv  Detail & Related papers  (2021-01-28T02:39:27Z)
• Learning Graphons via Structured Gromov-Wasserstein Barycenters [143.42601038462965]
  We propose a novel and principled method to learn a nonparametric graph model called graphon. The proposed approach overcomes drawbacks of prior state-of-the-art methods, and outperforms them on both synthetic and real-world data.
  arXiv  Detail & Related papers  (2020-12-10T13:04:29Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.