01063nas a2200181   4500000000100000000000100001008004100002260000800043100001400051700002200065700002500087700001800112245009400130856004700224490000700271520058900278022001400867       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