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.
BT - Quantum Information Processing DA - Jan DO - 10.1007/s11128-020-02939-4 LA - eng N2 -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.
PY - 2021 T2 - Quantum Information Processing TI - Upperbounds on the probability of finding marked connected components using quantum walks UR - https://doi.org/10.1007/s11128-020-02939-4 VL - 20 SN - 1573-1332 ER -