Universal graph representation of stabilizer codes

• URL: http://arxiv.org/abs/2411.14448v2
• Date: Thu, 19 Dec 2024 03:07:48 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 $[[n, k]]$ stabilizer codes as semi-bipartite graphs.<n>We argue that graphs provide a flexible platform for building codes particularly at smaller (non-asymptotic) scales.<n>Key code properties such as distance, weight, and encoding circuit depth, are all controlled by the graph degree.
• Score: 1.6385815610837167
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We introduce a representation of $[[n, k]]$ stabilizer codes as semi-bipartite graphs 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 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 a family of roughly $[[n, \frac{n}{\log n}, \log n]]$ codes. We also leverage graphs in a probabilistic analysis to extend the quantum Gilbert-Varshamov bound into a three-way distance-rate-weight tradeoff. 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 non-constant but reduced depth. Finally, we construct a simple efficient decoding algorithm and prove a performance guarantee for a certain class of graphs, including the roughly $[[n, \frac{n}{\log n}, \log n]]$ code. 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)
• Implementation of Continuous-Time Quantum Walk on Sparse Graph [0.0]
  Continuous-time quantum walks (CTQWs) play a crucial role in quantum computing. How to efficiently implement CTQWs is a challenging issue. In this paper, we study implementation of CTQWs on sparse graphs.
  arXiv  Detail & Related papers  (2024-08-20T05:20:55Z)
• 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)
• Learning quantum graph states with product measurements [22.463154358632472]
  We consider the problem of learning $N$ identical copies of an unknown $n$-qubit quantum graph state with product measurements. We detail an explicit algorithm that uses product measurements on multiple identical copies of such graph states to learn them.
  arXiv  Detail & Related papers  (2022-05-13T02:55:21Z)
• 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)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• 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)
• Proximity Preserving Binary Code using Signed Graph-Cut [27.098042566421963]
  We introduce a binary embedding framework, called Proximity Preserving Code (PPC), which learns similarity and dissimilarity between data points to create a compact and affinity-preserving binary code. We show that the proposed approximation is superior to the commonly used spectral methods with respect to both accuracy and complexity.
  arXiv  Detail & Related papers  (2020-02-05T13:58:41Z)
• Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving [1.0660480034605238]
  "spectral sparsification" reduces number of edges to near-linear in number of nodes. We show a quantum speedup for spectral sparsification and many of its applications. Our algorithm implies a quantum speedup for solving Laplacian systems.
  arXiv  Detail & Related papers  (2019-11-17T17:29:40Z)

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.