Periodicity of Grover walks on bipartite regular graphs with at most five distinct eigenvalues

• URL: http://arxiv.org/abs/2111.15074v2
• Date: Mon, 28 Feb 2022 06:26:24 GMT
• Title: Periodicity of Grover walks on bipartite regular graphs with at most five distinct eigenvalues
• Authors: Sho Kubota
• Abstract summary: We determine connected bipartite regular graphs with four distinct adjacency eigenvalues that induce periodic Grover walks. We also show that there are only three kinds of the second largest eigenvalues of bipartite regular periodic graphs with five distinct eigenvalues.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We determine connected bipartite regular graphs with four distinct adjacency eigenvalues that induce periodic Grover walks, and show that it is only $C_6$. We also show that there are only three kinds of the second largest eigenvalues of bipartite regular periodic graphs with five distinct eigenvalues. Using walk-regularity, we enumerate feasible spectra for such graphs.

Related papers

• 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)
• Improving Expressive Power of Spectral Graph Neural Networks with Eigenvalue Correction [55.57072563835959]
  spectral graph neural networks are characterized by filters. We propose an eigenvalue correction strategy that can free filters from the constraints of repeated eigenvalue inputs.
  arXiv  Detail & Related papers  (2024-01-28T08:12:00Z)
• Discrete-time quantum walks on Cayley graphs of Dihedral groups using generalized Grover coins [0.0]
  We study discrete-time quantum walks on Cayley graphs corresponding to Dihedral groups. We show that the walks are periodic only for coins that are permutation or negative of a permutation matrix.
  arXiv  Detail & Related papers  (2023-09-26T18:53:35Z)
• One-step Bipartite Graph Cut: A Normalized Formulation and Its Application to Scalable Subspace Clustering [56.81492360414741]
  We show how to enforce a one-step normalized cut for bipartite graphs, especially with linear-time complexity. In this paper, we first characterize a novel one-step bipartite graph cut criterion with normalized constraints, and theoretically prove its equivalence to a trace problem. We extend this cut criterion to a scalable subspace clustering approach, where adaptive anchor learning, bipartite graph learning, and one-step normalized bipartite graph partitioning are simultaneously modeled.
  arXiv  Detail & Related papers  (2023-05-12T11:27:20Z)
• Unitary interaction geometries in few-body systems [0.0]
  We consider few-body systems in which only a certain subset of the particle-particle interactions is resonant. Few-body systems whose unitary graph is connected will collapse unless a repulsive 3-body interaction is included. We show that this conjecture is correct for the 4-body case as well as for a few 5-body configurations.
  arXiv  Detail & Related papers  (2023-03-02T14:39:52Z)
• Periodicity of bipartite walk on biregular graphs with conditional spectra [0.0]
  We study a class of discrete quantum walks, known as bipartite walks. Any discrete quantum walk is given by the powers of a unitary matrix $U$ indexed by arcs or edges of the underlying graph. We apply periodicity results of bipartite walks to get a characterization of periodicity of Grover's walk on regular graphs.
  arXiv  Detail & Related papers  (2022-11-04T21:02:30Z)
• Sign and Basis Invariant Networks for Spectral Graph Representation Learning [75.18802152811539]
  We introduce SignNet and BasisNet -- new neural architectures that are invariant to all requisite symmetries and hence process collections of eigenspaces in a principled manner. Our networks are theoretically strong for graph representation learning -- they can approximate any spectral graph convolution. Experiments show the strength of our networks for learning spectral graph filters and learning graph positional encodings.
  arXiv  Detail & Related papers  (2022-02-25T23:11:59Z)
• Spectral embedding and the latent geometry of multipartite networks [67.56499794542228]
  Many networks are multipartite, meaning their nodes can be divided into partitions and nodes of the same partition are never connected. This paper demonstrates that the node representations obtained via spectral embedding live near partition-specific low-dimensional subspaces of a higher-dimensional ambient space. We propose a follow-on step after spectral embedding, to recover node representations in their intrinsic rather than ambient dimension.
  arXiv  Detail & Related papers  (2022-02-08T15:52:03Z)
• Odd-periodic Grover walk [0.0]
  We investigate the relationship between the quantum walk and the underlying graph, focusing on the characterization of graphs exhibiting a periodic Grover walk. It is expected that graphs exhibiting a periodic Grover walk with odd period correspond to cycles with odd length. We address that problem and are able to perfectly characterize the class of graphs exhibiting an odd-periodic Grover walk by using a method.
  arXiv  Detail & Related papers  (2021-06-12T08:02:25Z)
• A new type of spectral mapping theorem for quantum walks with a moving shift on graphs [0.2578242050187029]
  The spectral mapping theorem for quantum walks can only be applied for walks employing a shift operator whose square is the identity. We acquire a new spectral mapping theorem for the Grover walk with a shift operator whose cube is the identity on finite graphs.
  arXiv  Detail & Related papers  (2021-03-09T05:45:25Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure. The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2020-09-30T04:59:10Z)

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.