Search algorithm on strongly regular graph by lackadaisical quantum walk

Fangjie Peng, Meng Li, Xiaoming SunJournal of Physics A Mathematical and Theoretical 2024 · DOI

Abstract

Abstract Quantum walk is a widely used method in designing quantum algorithms. In this article, we consider the lackadaisical discrete-time quantum walk (DTQW) on strongly regular graphs (SRG). When there is a single marked vertex in a SRG, we prove that lackadaisical DTQW can find the marked vertex with asymptotic success probability 1, with a quadratic speedup compared to classical random walk. This paper deals with any parameter family of SRG and argues that, by adding self-loops with proper weights, the asymptotic success probability can reach 1. The running time and asymptotic success probability matches the result of continuous-time quantum walk, and improves the result of DTQW.
BibTeX
@article{peng2024search,
  author = {Fangjie Peng and Meng Li and Xiaoming Sun},
  title = {{Search algorithm on strongly regular graph by lackadaisical quantum walk}},
  journal = {Journal of Physics A Mathematical and Theoretical},
  year = {2024},
  doi = {10.1088/1751-8121/ad3055},
}

Loading related content...

Figure