2018/04/04 by Amit Saha, Ritajit Majumdar, Saha, Amit +7 · 1 citation
Computer Science · #FOS: Physical sciences #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph) #Quantum-Dot Cellular Automata
paper · pdf · doi:10.48550/arxiv.1804.01446
openalex publication_date 2018/04/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Nature of quantum walk in presence of multiple marked state has been studied by Nahimovs and Rivosh \cite10.1007/978-3-662-49192-831. They have shown that if the marked states are arranged in a √(k) × √(k) cluster in a √(N) × √(N) grid, then to find a single marked state among the multiple ones, quantum walk requires Ω(√(N) - √(k)) time. In this paper, we show that using lackadaisical quantum walk with the weight of the self-loop as \frac4N(k + \lfloor(√(k))/(2)\rfloor), where k is odd, the probability of finding a marked state increases by ∼ 0.2. Furthermore, we show that instead of applying the quantum walk O(k) times to find all the marked states, classical search in the vicinity of the marked state found after the first implementation of the quantum walk can find all the marked states in O(√(k)) time on average.