Search by Lackadaisical Quantum Walk with Symmetry Breaking

• URL: http://arxiv.org/abs/2108.13856v3
• Date: Mon, 29 Nov 2021 15:08:46 GMT
• Title: Search by Lackadaisical Quantum Walk with Symmetry Breaking
• Authors: Jacob Rapoza, Thomas G. Wong
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The lackadaisical quantum walk is a lazy version of a discrete-time, coined quantum walk, where each vertex has a weighted self-loop that permits the walker to stay put. They have been used to speed up spatial search on a variety of graphs, including periodic lattices, strongly regular graphs, Johnson graphs, and the hypercube. In these prior works, the weights of the self-loops preserved the symmetries of the graphs. In this paper, we show that the self-loops can break all the symmetries of vertex-transitive graphs while providing the same computational speedups. Only the weight of the self-loop at the marked vertex matters, and the remaining self-loop weights can be chosen randomly, as long as they are small compared to the degree of the graph.

Related papers

• Global Phase Helps in Quantum Search: Yet Another Look at the Welded Tree Problem [55.80819771134007]
  In this paper, we give a short proof of the optimal linear hitting time for a welded tree problem by a discrete-time quantum walk. The same technique can be applied to other 1-dimensional hierarchical graphs.
  arXiv  Detail & Related papers  (2024-04-30T11:45:49Z)
• Exponential speedups for quantum walks in random hierarchical graphs [8.984888893275713]
  We show how to generalize the use of quantum walks to a class of hierarchical graphs. The hitting times of quantum walks on these graphs are related to the localization properties of zero modes in certain disordered tight binding Hamiltonians.
  arXiv  Detail & Related papers  (2023-07-27T17:59:58Z)
• 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)
• The Exact Class of Graph Functions Generated by Graph Neural Networks [43.25172578943894]
  Graph Neural Network (GNN) whose output is identical to the graph function? In this paper, we fully answer this question and characterize the class of graph problems that can be represented by GNNs. We show that this condition can be efficiently verified by checking quadratically many constraints.
  arXiv  Detail & Related papers  (2022-02-17T18:54:27Z)
• 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)
• 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)
• On Applying the Lackadaisical Quantum Walk Algorithm to Search for Multiple Solutions on Grids [63.75363908696257]
  The lackadaisical quantum walk is an algorithm developed to search graph structures whose vertices have a self-loop of weight $l$. This paper addresses several issues related to applying the lackadaisical quantum walk to search for multiple solutions on grids successfully.
  arXiv  Detail & Related papers  (2021-06-11T09:43:09Z)
• 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)
• 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)
• 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.