The Foliage Partition: An Easy-to-Compute LC-Invariant for Graph States
- URL: http://arxiv.org/abs/2305.07645v1
- Date: Fri, 12 May 2023 17:55:45 GMT
- Title: The Foliage Partition: An Easy-to-Compute LC-Invariant for Graph States
- Authors: Adam Burchardt, Frederik Hahn
- Abstract summary: This paper introduces the foliage partition, an easy-to-compute LC-invariant for graph states.
Inspired by the foliage of a graph, our invariant has a natural graphical representation in terms of leaves, axils, and twins.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces the foliage partition, an easy-to-compute LC-invariant
for graph states, of computational complexity $\mathcal{O}(n^3)$ in the number
of qubits. Inspired by the foliage of a graph, our invariant has a natural
graphical representation in terms of leaves, axils, and twins. It captures
both, the connection structure of a graph and the $2$-body marginal properties
of the associated graph state. We relate the foliage partition to the size of
LC-orbits and use it to bound the number of LC-automorphisms of graphs. We also
show the invariance of the foliage partition when generalized to weighted
graphs and qudit graph states.
Related papers
- Distinguishing Graph States by the Properties of Their Marginals [0.0]
We introduce a family of easy-to-compute LU-invariants based on the marginal structure of the graphs.
We show that these invariants can uniquely identify all LU-orbits and entanglement classes of every graph state of 8 qubits or less.
We also discuss examples of entanglement classes with more nodes, where their marginal structure does not allow us to tell them apart.
arXiv Detail & Related papers (2024-06-14T12:03:10Z) - Graph Generation via Spectral Diffusion [51.60814773299899]
We present GRASP, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.
Specifically, we propose to use a denoising model to sample eigenvectors and eigenvalues from which we can reconstruct the graph Laplacian and adjacency matrix.
Our permutation invariant model can also handle node features by concatenating them to the eigenvectors of each node.
arXiv Detail & Related papers (2024-02-29T09:26:46Z) - Cross-View Graph Consistency Learning for Invariant Graph
Representations [16.007232280413806]
We propose a cross-view graph consistency learning (CGCL) method that learns invariant graph representations for link prediction.
This paper empirically and experimentally demonstrates the effectiveness of the proposed CGCL method.
arXiv Detail & Related papers (2023-11-20T14:58:47Z) - Structure-free Graph Condensation: From Large-scale Graphs to Condensed
Graph-free Data [91.27527985415007]
Existing graph condensation methods rely on the joint optimization of nodes and structures in the condensed graph.
We advocate a new Structure-Free Graph Condensation paradigm, named SFGC, to distill a large-scale graph into a small-scale graph node set.
arXiv Detail & Related papers (2023-06-05T07:53:52Z) - 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) - A Graph Convolution for Signed Directed Graphs [0.0]
Graph convolutions for signed directed graphs have not been delivered much yet.
We propose a novel complex Hermitian adjacency matrix that encodes graph information via complex numbers.
To the best of our knowledge, it is the first spectral convolution for graphs with signs.
arXiv Detail & Related papers (2022-08-23T01:58:35Z) - Dirichlet Graph Variational Autoencoder [65.94744123832338]
We present Dirichlet Graph Variational Autoencoder (DGVAE) with graph cluster memberships as latent factors.
Motivated by the low pass characteristics in balanced graph cut, we propose a new variant of GNN named Heatts to encode the input graph into cluster memberships.
arXiv Detail & Related papers (2020-10-09T07:35:26Z) - Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted
Z-graded graphs [62.997667081978825]
We identify conditions which allow one to lift one dimensional solutions to solutions on graphs.
We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
arXiv Detail & Related papers (2020-08-11T17:58:13Z) - Wasserstein-based Graph Alignment [56.84964475441094]
We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph.
We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
arXiv Detail & Related papers (2020-03-12T22:31:59Z) - The Power of Graph Convolutional Networks to Distinguish Random Graph
Models: Short Version [27.544219236164764]
Graph convolutional networks (GCNs) are a widely used method for graph representation learning.
We investigate the power of GCNs to distinguish between different random graph models on the basis of the embeddings of their sample graphs.
arXiv Detail & Related papers (2020-02-13T17:58:42Z)
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.