A comfortable graph structure for Grover walk

• URL: http://arxiv.org/abs/2201.01926v3
• Date: Fri, 23 Jun 2023 07:32:48 GMT
• Title: A comfortable graph structure for Grover walk
• Authors: Yusuke Higuchi, Mohamed Sabri and Etsuo Segawa
• Abstract summary: We consider a Grover walk model on a finite internal graph, which is connected with a finite number of semi-infinite length paths. We give some characterization upon the scattering of the stationary state on the surface of the internal graph. We introduce a comfortability function of a graph for the quantum walk, which shows how many walkers can stay in the interior.
• Score: 0.0
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We consider a Grover walk model on a finite internal graph, which is connected with a finite number of semi-infinite length paths and receives the alternative inflows along these paths at each time step. After the long time scale, we know that the behavior of such a Grover walk should be stable, that is, this model has a stationary state. In this paper our objectives are to give some characterization upon the scattering of the stationary state on the surface of the internal graph and upon the energy of this state in the interior. For the scattering, we concretely give a scattering matrix, whose form is changed depending on whether the internal graph is bipartite or not. On the other hand, we introduce a comfortability function of a graph for the quantum walk, which shows how many quantum walkers can stay in the interior, and we succeed in showing the comfortability of the walker in terms of combinatorial properties of the internal graph.

Related papers

• Limits, approximation and size transferability for GNNs on sparse graphs via graphops [44.02161831977037]
  We take a perspective of taking limits of operators derived from graphs, such as the aggregation operation that makes up GNNs. Our results hold for dense and sparse graphs, and various notions of graph limits.
  arXiv  Detail & Related papers  (2023-06-07T15:04:58Z)
• Circuit equation of Grover walk [0.0]
  We consider the Grover walk on the infinite graph in which an internal finite subgraph receives the inflow from the outside with some frequency. We characterize the scattering on the surface of the internal graph and the energy penetrating inside it. For the complete graph as the internal graph, we illustrate the relationship of the scattering and the internal energy to the frequency and the number of tails.
  arXiv  Detail & Related papers  (2022-11-02T07:07:30Z)
• A convergence time of Grover walk on regular graph to stationary state [0.0]
  We consider a quantum walk model on a finite graph which has an interaction with the outside. We show that larger degree of the regular graph makes the convergence speed of this quantum walk model slower.
  arXiv  Detail & Related papers  (2022-10-16T02:57:33Z)
• 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)
• Understanding convolution on graphs via energies [23.18124653469668]
  Graph Networks (GNNs) typically operate by message-passing, where the state of a node is updated based on the information received from its neighbours. Most message-passing models act as graph convolutions, where features are mixed by a shared, linear transformation before being propagated over the edges. On node-classification tasks, graph convolutions have been shown to suffer from two limitations: poor performance on heterophilic graphs, and over-smoothing.
  arXiv  Detail & Related papers  (2022-06-22T11:45:36Z)
• Key graph properties affecting transport efficiency of flip-flop Grover percolated quantum walks [0.0]
  We study quantum walks with the flip-flop shift operator and the Grover coin. We show how the position of the source and sink together with the graph geometry and its modifications affect transport. This gives us a deep insight into processes where elongation or addition of dead-end subgraphs may surprisingly result in enhanced transport.
  arXiv  Detail & Related papers  (2022-02-19T11:55:21Z)
• Gradient flows on graphons: existence, convergence, continuity equations [27.562307342062354]
  Wasserstein gradient flows on probability measures have found a host of applications in various optimization problems. We show that the Euclidean gradient flow of a suitable function of the edge-weights converges to a novel continuum limit given by a curve on the space of graphons.
  arXiv  Detail & Related papers  (2021-11-18T00:36:28Z)
• Quantum walks on regular graphs with realizations in a system of anyons [0.0]
  We build interacting Fock spaces from association schemes and set up quantum walks on regular graphs. In the dual perspective interacting Fock spaces gather a new meaning in terms of anyon systems.
  arXiv  Detail & Related papers  (2021-09-22T18:01:20Z)
• 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)
• Space-Time Correspondence as a Contrastive Random Walk [47.40711876423659]
  We cast correspondence as prediction of links in a space-time graph constructed from video. We learn a representation in which pairwise similarity defines transition probability of a random walk. We demonstrate that a technique we call edge dropout, as well as self-supervised adaptation at test-time, further improve transfer for object-centric correspondence.
  arXiv  Detail & Related papers  (2020-06-25T17:56:05Z)
• 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)

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.