On the Probability of Finding Marked Connected Components Using Quantum Walks
- Авторы: Khadiev K.1,2, Nahimovs N.1, Santos R.1
-
Учреждения:
- Center for Quantum Computer Science, Faculty of Computing
- Institute of Computational Mathematics and Information Technologies
- Выпуск: Том 39, № 7 (2018)
- Страницы: 1016-1023
- Раздел: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202871
- DOI: https://doi.org/10.1134/S1995080218070144
- ID: 202871
Цитировать
Аннотация
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.
Ключевые слова
Об авторах
K. Khadiev
Center for Quantum Computer Science, Faculty of Computing; Institute of Computational Mathematics and Information Technologies
Автор, ответственный за переписку.
Email: kamilhadi@gmail.com
Латвия, 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
Латвия, Raina bulv. 19, Riga, LV-1586
R. Santos
Center for Quantum Computer Science, Faculty of Computing
Email: kamilhadi@gmail.com
Латвия, Raina bulv. 19, Riga, LV-1586