6533b86cfe1ef96bd12c8c4f
RESEARCH PRODUCT
Upperbounds on the probability of finding marked connected components using quantum walks
Nikolajs NahimovsAdam GlosAdam GlosKonstantin BalakirevKamil Khadievsubject
FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)FOS: Physical sciences01 natural sciencesUpper and lower bounds010305 fluids & plasmasTheoretical Computer Science0103 physical sciencesFOS: MathematicsMathematics - CombinatoricsQuantum walkElectrical and Electronic Engineering010306 general physicsQuantum computerMathematicsDiscrete mathematicsConnected componentQuantum PhysicsStatistical and Nonlinear PhysicsRandom walkQuantum searchElectronic Optical and Magnetic MaterialsModeling and SimulationSignal ProcessingCombinatorics (math.CO)Quantum Physics (quant-ph)Stationary stateComputer Science - Discrete Mathematicsdescription
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 upper bounds for various sets of marked vertices. We apply the upper bounds to large collection of graphs and show that the quantum search may be slow even when taking real-world networks.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2019-03-04 |