Email this article On the Probability of Finding Marked Connected Components Using Quantum Walks
- Authors: Khadiev K.1,2, Nahimovs N.1, Santos R.A.1
-
Affiliations:
- Center for Quantum Computer Science, Faculty of Computing
- Institute of Computational Mathematics and Information Technologies
- Issue: Vol 39, No 7 (2018)
- Pages: 1016-1023
- Section: Article
- URL: https://bakhtiniada.ru/1995-0802/article/view/202871
- DOI: https://doi.org/10.1134/S1995080218070144
- ID: 202871
Cite item
Open Access
Access granted
Subscription Access
Abstract
Finding a marked vertex in a graph can be a complicated task when using quantum walks. Recent results show that for two or more adjacent marked vertices search by quantum walk with Grover’s coin may have no speed-up over classical exhaustive search. In this paper, we analyze the probability of finding a marked vertex for a set of connected components of marked vertices. We prove two upper bounds on the probability of finding a marked vertex and sketch further research directions.
About the authors
K. Khadiev
Center for Quantum Computer Science, Faculty of Computing; Institute of Computational Mathematics and Information Technologies
Author for correspondence.
Email: kamilhadi@gmail.com
Latvia, Raina bulv. 19, Riga, LV-1586; ul. Kremlevskaya 35, Kazan, Tatarstan, 420008
N. Nahimovs
Center for Quantum Computer Science, Faculty of Computing
Email: kamilhadi@gmail.com
Latvia, Raina bulv. 19, Riga, LV-1586
R. A. M. Santos
Center for Quantum Computer Science, Faculty of Computing
Email: kamilhadi@gmail.com
Latvia, Raina bulv. 19, Riga, LV-1586
Supplementary files
