Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk

• URL: http://arxiv.org/abs/2002.11227v2
• Date: Thu, 20 Aug 2020 16:29:00 GMT
• Title: Search on Vertex-Transitive Graphs by Lackadaisical Quantum Walk
• Authors: Mason L. Rhodes, Thomas G. Wong
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The lackadaisical quantum walk is a discrete-time, coined quantum walk on a graph with a weighted self-loop at each vertex. It uses a generalized Grover coin and the flip-flop shift, which makes it equivalent to Szegedy's quantum Markov chain. It has been shown that a lackadaisical quantum walk can improve spatial search on the complete graph, discrete torus, cycle, and regular complete bipartite graph. In this paper, we observe that these are all vertex-transitive graphs, and when there is a unique marked vertex, the optimal weight of the self-loop equals the degree of the loopless graph divided by the total number of vertices. We propose that this holds for all vertex-transitive graphs with a unique marked vertex. We present a number of numerical simulations supporting this hypothesis, including search on periodic cubic lattices of arbitrary dimension, strongly regular graphs, Johnson graphs, and the hypercube.

Related papers

• Unifying quantum spatial search, state transfer and uniform sampling on graphs: simple and exact [2.871419116565751]
  This article presents a novel and succinct algorithmic framework via alternating quantum walks. It unifies quantum spatial search, state transfer and uniform sampling on a large class of graphs. The approach is easy to use since it has a succinct formalism that depends only on the depth of the Laplacian eigenvalue set of the graph.
  arXiv  Detail & Related papers  (2024-07-01T06:09:19Z)
• Universal approach to deterministic spatial search via alternating quantum walks [2.940962519388297]
  We propose a novel approach for designing deterministic quantum search algorithms on a variety of graphs via alternating quantum walks. Our approach is universal because it does not require an instance-specific analysis for different graphs.
  arXiv  Detail & Related papers  (2023-07-30T05:14:19Z)
• 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)
• 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)
• Search by Lackadaisical Quantum Walk with Symmetry Breaking [0.0]
  The lackadaisical quantum walk is a lazy version of a discrete-time, coined quantum walk. They have been used to speed up spatial search on a variety of graphs.
  arXiv  Detail & Related papers  (2021-08-31T14:08:40Z)
• Equivalent Laplacian and Adjacency Quantum Walks on Irregular Graphs [0.0]
  The continuous-time quantum walk is a particle evolving by Schr"odinger's equation in discrete space. In some physical systems, however, the Hamiltonian is proportional to the adjacency matrix instead.
  arXiv  Detail & Related papers  (2021-07-12T16:59:06Z)
• Spectral clustering under degree heterogeneity: a case for the random walk Laplacian [83.79286663107845]
  This paper shows that graph spectral embedding using the random walk Laplacian produces vector representations which are completely corrected for node degree. In the special case of a degree-corrected block model, the embedding concentrates about K distinct points, representing communities.
  arXiv  Detail & Related papers  (2021-05-03T16:36:27Z)
• Mining Large Quasi-cliques with Quality Guarantees from Vertex Neighborhoods [44.007522460918565]
  Mining dense subgraphs is an important primitive across a spectrum of graph-mining tasks. We show that mining cliques and quasi-cliques of non-trivial sizes from real-world graphs is often not a difficult problem.
  arXiv  Detail & Related papers  (2020-08-18T15:50:25Z)
• 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)
• 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)
• Analysis of Lackadaisical Quantum Walks [0.0]
  The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each. We analytically prove that lackadaisical quantum walks can find a unique marked. vertebrae on any regular locally arc-transitive graph with constant success probability. quadratically faster than the hitting time.
  arXiv  Detail & Related papers  (2020-02-26T00:40:25Z)

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.