2020-06-08
Quadratic speedup for finding marked vertices by quantum walks
Publication
Publication
Presented at the
52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 (June 2020), Chicago, Illinois, USA
A quantum walk algorithm can detect the presence of a marked vertex on a graph quadratically faster than the corresponding random walk algorithm (Szegedy, FOCS 2004). However, quantum algorithms that actually find a marked element quadratically faster than a classical random walk were only known for the special case when the marked set consists of just a single vertex, or in the case of some specific graphs. We present a new quantum algorithm for finding a marked vertex in any graph, with any set of marked vertices, that is (up to a log factor) quadratically faster than the corresponding classical random walk, resolving a question that had been open for 15 years.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.1145/3357713.3384252 | |
| Quantum algorithms and applications , Quantum Computation with Bounded Space , WISE Women In Science Excel , Progress in quantum computing:Algorithms, communication, and applications | |
| 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 | |
| , | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Ambainis, A., Gilyén, A., Jeffery, S., & Kokainis, M. (2020). Quadratic speedup for finding marked vertices by quantum walks. In Proceedings of the Annual ACM SIGACT Symposium on Theory of Computing (pp. 412–424). doi:10.1145/3357713.3384252 |
|
