01050nas a2200169   4500000000100000008004100001260000800042100001400050700002200064700002500086700001800111245009400129856004700223490000700270520058900277022001400866       2021                            d  cJan1 aAdam Glos1 aNikolajs Nahimovs1 aKonstantin Balakirev1 aKamil Khadiev00aUpperbounds on the probability of finding marked connected components using quantum walks  uhttps://doi.org/10.1007/s11128-020-02939-40 v203 a<p>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.</p>
  a1573-1332