Search algorithm on strongly regular graph by lackadaisical quantum walk
Lists
Only you see this
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...