Enviar artigo por via de e-mail On the Probability of Finding Marked Connected Components Using Quantum Walks
- Autores: Khadiev K.1,2, Nahimovs N.1, Santos R.1
-
Afiliações:
- Center for Quantum Computer Science, Faculty of Computing
- Institute of Computational Mathematics and Information Technologies
- Edição: Volume 39, Nº 7 (2018)
- Páginas: 1016-1023
- Seção: Article
- URL: https://journals.rcsi.science/1995-0802/article/view/202871
- DOI: https://doi.org/10.1134/S1995080218070144
- ID: 202871
Citar
Acesso aberto
Acesso está concedido
Somente assinantes
Resumo
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.
Palavras-chave
Sobre autores
K. Khadiev
Center for Quantum Computer Science, Faculty of Computing; Institute of Computational Mathematics and Information Technologies
Autor responsável pela correspondência
Email: kamilhadi@gmail.com
Letônia, 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
Letônia, Raina bulv. 19, Riga, LV-1586
R. Santos
Center for Quantum Computer Science, Faculty of Computing
Email: kamilhadi@gmail.com
Letônia, Raina bulv. 19, Riga, LV-1586
