On the Probability of Finding Marked Connected Components Using Quantum Walks
Tóm tắt
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.
Tài liệu tham khảo
L. K. Grover, “A fast quantum mechanical algorithm for database search,” in Proceedings of the 28th ACM Symposium on the Theory of Computing, 1996, pp. 212–219.
M. Szegedy, “Quantum speed-up of Markov chain based algorithms,” in Proceedings of the 45th Symposium on Foundations of Computer Science, 2004, pp. 32–41.
F. Magniez, A. Nayak, P. C. Richter, and M. Santha, “On the hitting times of quantum versus randomwalks,” Algorithmica 63, 91–116 (2012).
H. Krovi, F. Magniez, M. Ozols, and J. Roland, “Quantum walks can find a marked element on any graph,” Algorithmica 74, 851–907 (2016).
P. Hoyer and M. Komeili, “Efficient quantum walk on the grid with multiple marked elements,” in Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science STACS’2017, Leibniz Int. Proc. Inform. 66, 42:1–42:14 (2017).
N. Nahimovs and A. Rivosh, “Exceptional configurations of quantum walks with Grover’s coin,” in Proceedings of the 10th International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science, MEMICS 2015 (2016), pp. 79–92.
Y. Aharonov, L. Davidovich and N. Zagury, “Quantum random walks,” Phys. Rev. A 48, 1687–1690 (1993).
N. Nahimovs and R. A. M. Santos, “Adjacent vertices can be hard to find by quantum walks,” in Theory and Practice of Computer Science, Proceedings 43rd International Conference SOFSEM 2017, 2017, pp. 256–267.
A. Ambainis and A. Rivosh, “Quantum walks with multiple or moving marked locations,” in Proceedings of International Conference on Theory and Practice of Computer Science SOFSEM, 2008, pp. 485–496.
T. G. Wong and R. A. M. Santos, “Exceptional quantum walk search on the cycle,” Quantum Inform. Process. 16 (6), 154 (2017).
K. Prūsis, J. Vihrovs, and T. G. Wong, “Stationary states in quantum walk search,” Phys. Rev. A 94, 032334 (2016).