We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Upperbounds on the probability of finding marked connected components using quantum walks.
- Authors
Glos, Adam; Nahimovs, Nikolajs; Balakirev, Konstantin; Khadiev, Kamil
- Abstract
Quantum walk search may exhibit phenomena beyond the intuition from a conventional random walk theory. One of such examples is exceptional configuration phenomenon—it appears that it may be much harder to find any of two or more marked vertices, that if only one of them is marked. In this paper, we analyze the probability of finding any of marked vertices in such scenarios and prove upperbounds for various sets of marked vertices. We apply the upperbounds to large collection of graphs and show that the quantum search may be slow even when taking real-world networks.
- Publication
Quantum Information Processing, 2021, Vol 20, Issue 1, p1
- ISSN
1570-0755
- Publication type
Article
- DOI
10.1007/s11128-020-02939-4