Quantum Computing from Graphs
- URL: http://arxiv.org/abs/2501.17959v1
- Date: Wed, 29 Jan 2025 19:47:39 GMT
- Title: Quantum Computing from Graphs
- Authors: Andrey Boris Khesin,
- 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.
We also use graphs to extend the quantum Gilbert-Varshamov bound to a three-way distance-rate-weight trade-off.
- Score: 0.0
- License:
- Abstract: While stabilizer tableaus have proven exceptionally useful as a descriptive tool for additive quantum codes, they offer little guidance for concrete constructions or coding algorithm analysis. We introduce a representation of stabilizer codes as graphs with certain structures. Specifically, the graphs take a semi-bipartite form where input nodes map to output nodes, such that output nodes may connect to each other but input nodes may not. Intuitively, the graph's input-output edges represent information propagation of the encoder, while output-output edges represent the code's entanglement. We prove that this graph representation is in bijection with tableaus and give an efficient compilation algorithm that transforms tableaus into graphs. We show that this map is efficiently invertible, which gives a universal recipe for code construction by finding graphs with 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. We construct several constant-size codes and several infinite code families. We also use graphs to extend the quantum Gilbert-Varshamov bound to 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 encoding circuits whose depths scale with the degree and for implementing certain logical diagonal and Clifford gates with reduced depth. Finally, we find an efficient decoding algorithm for certain classes of graphs. These results give evidence that graphs are useful for the study of quantum computing and its implementations.
Related papers
- Universal graph representation of stabilizer codes [1.6385815610837167]
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.
arXiv Detail & Related papers (2024-11-07T18:58:58Z) - InstructG2I: Synthesizing Images from Multimodal Attributed Graphs [50.852150521561676]
We propose a graph context-conditioned diffusion model called InstructG2I.
InstructG2I first exploits the graph structure and multimodal information to conduct informative neighbor sampling.
A Graph-QFormer encoder adaptively encodes the graph nodes into an auxiliary set of graph prompts to guide the denoising process.
arXiv Detail & Related papers (2024-10-09T17:56:15Z) - Boson subtraction as an alternative to fusion gates for generating graph
states [0.0]
We propose an alternative approach to generate graph states based on the graph picture of linear quantum networks (LQG picture)
These subtraction schemes correspond to efficient heralded optical setups with single-photon sources and more flexible measurement elements than fusion gates.
arXiv Detail & Related papers (2023-06-27T02:14:17Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
We introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes.
The efficient computation is enabled by a kernerlized Gumbel-Softmax operator.
Experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs.
arXiv Detail & Related papers (2023-06-14T09:21:15Z) - Graphon Pooling for Reducing Dimensionality of Signals and Convolutional
Operators on Graphs [131.53471236405628]
We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space.
We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals.
We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
arXiv Detail & Related papers (2022-12-15T22:11:34Z) - 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) - Auto-Encoding Twin-Bottleneck Hashing [141.5378966676885]
This paper proposes an efficient and adaptive code-driven graph.
It is updated by decoding in the context of an auto-encoder.
Experiments on benchmarked datasets clearly show the superiority of our framework over the state-of-the-art hashing methods.
arXiv Detail & Related papers (2020-02-27T05:58:12Z) - 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.