Strongly regular and strongly walk-regular graphs that admit perfect state transfer

• URL: http://arxiv.org/abs/2506.02530v1
• Date: Tue, 03 Jun 2025 07:10:06 GMT
• Title: Strongly regular and strongly walk-regular graphs that admit perfect state transfer
• Authors: Sho Kubota, Hiroto Sekido, Harunobu Yata, Kiyoto Yoshino,
• Abstract summary: We study perfect state transfer in Grover walks on two important classes of graphs: strongly regular graphs and strongly walk-regular graphs.<n>We first give a complete classification of strongly regular graphs that admit perfect state transfer. The only such graphs are the complete bipartite graph $K_2,2 and the complete graph $K_2,2,2.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We study perfect state transfer in Grover walks on two important classes of graphs: strongly regular graphs and strongly walk-regular graphs. The latter class is a generalization of the former. We first give a complete classification of strongly regular graphs that admit perfect state transfer. The only such graphs are the complete bipartite graph $K_{2,2}$ and the complete tripartite graph $K_{2,2,2}$. We then show that, if a genuine strongly walk-regular graph admits perfect state transfer, then its spectrum must be of the form $\{[k]^1, [\frac{k}{2}]^{\alpha}, [0]^{\beta}, [-\frac{k}{2}]^{\gamma}\}$, and we enumerate all feasible spectra of this form up to $k=20$ with the help of a computer. These results are obtained using techniques from algebraic number theory and spectral graph theory, particularly through the analysis of eigenvalues and eigenprojections of a normalized adjacency matrix. While the setting is in quantum walks, the core discussion is developed entirely within the framework of spectral graph theory.

Related papers

• Real state transfer on edge perturbed graphs with generalized clusters [0.0]
  We study the existence of real state transfer in edge-perturbed graphs containing generalized clusters.<n>A central observation is that the evolution of certain quantum states depends solely on the local structure of the underlying graph.
  arXiv  Detail & Related papers  (2025-05-12T18:26:59Z)
• Pulsation of quantum walk on Johnson graph [0.0]
  We propose a phenomenon of discrete-time quantum walks on graphs called the pulsation. The pulsation means that the state periodically transfers between $G_1$ and $G_2$ with the initial state of the uniform superposition. The proof is based on Kato's theory in finite-dimensional vector spaces.
  arXiv  Detail & Related papers  (2024-11-03T07:32:19Z)
• A generalization of quantum pair state transfer [0.0]
  An $s$-pair state in a graph is a quantum state of the form $mathbfe_u+smathbfe_v$. We develop the theory of perfect $s$-pair state transfer in continuous quantum walks.
  arXiv  Detail & Related papers  (2024-04-25T14:45:49Z)
• CKGConv: General Graph Convolution with Continuous Kernels [24.58050212186722]
  We propose a novel and general graph convolution framework by parameterizing the kernels as continuous functions of pseudo-coordinates derived via graph positional encoding. We name this Continuous Kernel Graph Convolution (CKGConv) We show that CKGConv-based Networks outperform existing graph convolutional networks and perform comparably to the best graph transformers across a variety of graph datasets.
  arXiv  Detail & Related papers  (2024-04-21T10:26:13Z)
• Generating Graphs via Spectral Diffusion [48.70458395826864]
  We present GGSD, a novel graph generative model based on 1) the spectral decomposition of the graph Laplacian matrix and 2) a diffusion process.<n>An extensive set of experiments on both synthetic and real-world graphs demonstrates the strengths of our model against state-of-the-art alternatives.
  arXiv  Detail & Related papers  (2024-02-29T09:26:46Z)
• 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)
• Graph Distillation with Eigenbasis Matching [43.59076214528843]
  We propose Graph Distillation with Eigenbasis Matching (GDEM) to replace the real large graph. GDEM aligns the eigenbasis and node features of real and synthetic graphs. It directly replicates the spectrum of the real graph and thus prevents the influence of GNNs.
  arXiv  Detail & Related papers  (2023-10-13T15:48:12Z)
• From Cluster Assumption to Graph Convolution: Graph-based Semi-Supervised Learning Revisited [51.24526202984846]
  Graph-based semi-supervised learning (GSSL) has long been a hot research topic.<n> graph convolutional networks (GCNs) have become the predominant techniques for their promising performance.<n>We propose three simple but powerful graph convolution methods.
  arXiv  Detail & Related papers  (2023-09-24T10:10:21Z)
• Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs [48.79929516665371]
  Graphs with homophily-prone edges tend to connect nodes with the same class. Heterophily-prone edges tend to build relationships between nodes with different classes. Existing GNNs only take the original graph during training.
  arXiv  Detail & Related papers  (2023-06-13T08:06:10Z)
• 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)
• G-Mixup: Graph Data Augmentation for Graph Classification [55.63157775049443]
  Mixup has shown superiority in improving the generalization and robustness of neural networks by interpolating features and labels between two random samples. We propose $mathcalG$-Mixup to augment graphs for graph classification by interpolating the generator (i.e., graphon) of different classes of graphs. Experiments show that $mathcalG$-Mixup substantially improves the generalization and robustness of GNNs.
  arXiv  Detail & Related papers  (2022-02-15T04:09:44Z)
• AnchorGAE: General Data Clustering via $O(n)$ Bipartite Graph Convolution [79.44066256794187]
  We show how to convert a non-graph dataset into a graph by introducing the generative graph model, which is used to build graph convolution networks (GCNs) A bipartite graph constructed by anchors is updated dynamically to exploit the high-level information behind data. We theoretically prove that the simple update will lead to degeneration and a specific strategy is accordingly designed.
  arXiv  Detail & Related papers  (2021-11-12T07:08:13Z)
• Application of graph theory in quantum computer science [0.0]
  We demonstrate that the continuous-time quantum walk models remain powerful for nontrivial graph structures. The quantum spatial search defined through CTQW has been proven to work well on various undirected graphs. In the scope of this aspect we analyze, whether quantum speed-up is observed for complicated graph structures as well.
  arXiv  Detail & Related papers  (2021-09-27T12:07:25Z)
• Perfect State Transfer in Weighted Cubelike Graphs [0.0]
  A continuous-time quantum random walk describes the motion of a quantum mechanical particle on a graph. We generalize the PST or periodicity of cubelike graphs to that of weighted cubelike graphs.
  arXiv  Detail & Related papers  (2021-09-26T13:44:44Z)
• 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)

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.