Periodicity of bipartite walk on biregular graphs with conditional spectra

• URL: http://arxiv.org/abs/2211.02752v3
• Date: Wed, 14 Dec 2022 19:16:05 GMT
• Title: Periodicity of bipartite walk on biregular graphs with conditional spectra
• Authors: Qiuting Chen
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper we study a class of discrete quantum walks, known as bipartite walks. These include the well-known Grover's walks. Any discrete quantum walk is given by the powers of a unitary matrix $U$ indexed by arcs or edges of the underlying graph. The walk is periodic if $U^k=I$ for some positive integer $k$. Kubota has given a characterization of periodicity of Grover's walk when the walk is defined on a regular bipartite graph with at most five eigenvalues. We extend Kubota's results--if a biregular graph $G$ has eigenvalues whose squares are algebraic integers with degree at most two, we characterize periodicity of the bipartite walk over $G$ in terms of its spectrum. We apply periodicity results of bipartite walks to get a characterization of periodicity of Grover's walk on regular graphs.

Related papers

• 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)
• 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)
• A high-fidelity quantum state transfer algorithm on the complete bipartite graph [15.305667582809924]
  Current quantum state transfer algorithms on the complete bipartite graph suffer from low fidelity in some cases. We propose a two-stage quantum state transfer algorithm on the complete bipartite graph.
  arXiv  Detail & Related papers  (2023-02-23T11:20:12Z)
• Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
  We study Grover's search algorithm focusing on continuous-time quantum walk on graphs. Instead of finding specific graph topologies convenient for the related quantum walk, we fix the graph topology and vary the underlying graph endowed Laplacians.
  arXiv  Detail & Related papers  (2022-07-04T19:33:06Z)
• Hamiltonians of Bipartite Walks [0.0]
  We introduce a discrete quantum walk model called bipartite walks. For the transition matrix of a quantum walk, there is a Hamiltonian associated with it. Via the Hamiltonians, phenomena of bipartite walks lead to phenomena of continuous walks.
  arXiv  Detail & Related papers  (2022-07-04T18:50:32Z)
• Fractional disclination charge and discrete shift in the Hofstadter butterfly [15.3862808585761]
  We numerically compute the discrete shift $mathscrS$ for the square lattice Hofstadter model of free fermions. We show that bands with the same Chern number may have different values of $mathscrS$, although odd and even Chern number bands always have half-integer and integer values of $mathscrS$ respectively.
  arXiv  Detail & Related papers  (2022-04-11T18:00:01Z)
• Periodicity of Grover walks on bipartite regular graphs with at most five distinct eigenvalues [0.0]
  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.
  arXiv  Detail & Related papers  (2021-11-30T02:31:50Z)
• 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 Thorough View of Exact Inference in Graphs from the Degree-4 Sum-of-Squares Hierarchy [37.34153902687548]
  We tackle the problem of exactly recovering an unknown ground-truth binary labeling of the nodes from a single corrupted observation of each edge. We apply a hierarchy of relaxations known as the sum-of-squares hierarchy, to the problem. We show that the solution of the dual of the relaxed problem is related to finding edge weights of the Johnson and Kneser graphs.
  arXiv  Detail & Related papers  (2021-02-16T08:36:19Z)
• Continuous-time quantum walks in the presence of a quadratic perturbation [55.41644538483948]
  We address the properties of continuous-time quantum walks with Hamiltonians of the form $mathcalH= L + lambda L2$. We consider cycle, complete, and star graphs because paradigmatic models with low/high connectivity and/or symmetry.
  arXiv  Detail & Related papers  (2020-05-13T14:53:36Z)
• Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk [0.0]
  The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph. It can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph. We present a number of numerical simulations supporting this hypothesis.
  arXiv  Detail & Related papers  (2020-02-26T00:10:38Z)

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.