Quantum Searching on Markov Chains - The Complete Graph |
| Min-Ho Leea, Nark Nyul Choia, Gregor Tannerb
aSchool of Liberal Arts and Teacher Training, Kumoh National Institute of Technology, 61, Daehak-ro, 39177 Gumi-si, Gyeongbuk, Republic of Korea bSchool of Mathematical Sciences, University of Nottingham, University Park, Nottingham NG7 2RD, United Kindom |
| Full Text PDF |
| We will give an introduction into the quantum search algorithms on the Markov chains introduced by Szegedy and recent modifications based on partially absorbing Markov chains due to Krovi et al. Algorithmica 74, 851 (2016) It has been shown that a quantum search can find a set of marked vertices quadratically faster (in units of the hitting time) for any reversible Markov chain. The proofs are based on certain properties of the stationary state of the partially absorbing walk and rely on quantum phase estimation techniques. We will offer an alternative view of the underlying mechanism of the quantum search based on spectral properties of the quantum walk operator. By considering the complete graph as an example, we identify the relevant two-level quantum subspace leading to a Grover-like rotation in the underlying vector space. |
DOI:10.12693/APhysPolA.140.538 topics: quantum search, quantum walk, absorbing Markov chain, complete graph |