Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2002.11227 · Quantum Information Processing

Search on vertex-transitive graphs by lackadaisical quantum walk

Mason L. Rhodes, Thomas G. Wong

Published Sep 1, 2020• 23 citations
arXivHTMLPDF
DOI
10.1007/s11128-020-02841-z

Related papers

Lackadaisical discrete-time quantum walk on Johnson graph

Fangjie Peng, Meng Li, Xiaoming Sun

Physica A Statistical Mechanics and its Applications•Jan 2, 2024•4 citations

Lackadaisical Quantum Walk in the Hypercube to Search for Multiple Marked Vertices

Luciano S. de Souza, Jonathan H. A. de Carvalho, Tiago A. E. Ferreira

arXiv:2108.09399•Lecture notes in computer science•Jan 1, 2021•4 citations

Analysis of lackadaisical quantum walks

Peter Høyer, Zhan Yu

The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each vertex in the graph. We analytically prove that lackadaisical quantum walks can find a unique marked vertex on any regular locally arc-transitive graph with constant success probability quadratically faster than the hitting time. This result proves several speculations and numerical findings in previous work, including the conjectures that the lackadaisical quantum walk finds a unique marked vertex with constant success probability on the torus, cycle, Johnson graphs, and other classes of vertex-transitive graphs. Our proof establishes and uses a relationship between lackadaisical quantum walks and quantum interpolated walks for any regular locally arc-transitive graph.

arXiv:2002.11234•Quantum Information and Computation•Nov 1, 2020•15 citations

Graph partition and simple random walk/quantum walk search on graph

Ide Yusuke

電気学会研究会資料•Jan 1, 2018•0 citations

Quantum Walks on Finite Graphs

Renato Portugal

Springer eBooks•Jan 1, 2013•0 citations

Search by lackadaisical quantum walk with symmetry breaking

Jacob Rapoza, Thomas G. Wong

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.

arXiv:2108.13856•Physical Review A•Dec 22, 2021•5 citations
The lackadaisical quantum walk is a quantum analogue of the lazy random walk obtained by adding a self-loop to each vertex in the graph. We analytically prove that lackadaisical quantum walks can find a unique marked vertex on any regular locally arc-transitive graph with constant success probability quadratically faster than the hitting time. This result proves several speculations and numerical findings in previous work, including the conjectures that the lackadaisical quantum walk finds a unique marked vertex with constant success probability on the torus, cycle, Johnson graphs, and other classes of vertex-transitive graphs. Our proof establishes and uses a relationship between lackadaisical quantum walks and quantum interpolated walks for any regular locally arc-transitive graph.
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.