Quadratic speedup for finding marked vertices by quantum walks
| Authors |
|
|---|---|
| Publication date | 2020 |
| Host editors |
|
| Book title | STOC '20 |
| Book subtitle | proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing : June 22-26, 2020, Chicago, IL, USA |
| ISBN (electronic) |
|
| Event | 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 |
| Pages (from-to) | 412-424 |
| Number of pages | 13 |
| Publisher | New York, NY: Association for Computing Machinery |
| Organisations |
|
| Abstract |
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. |
| Document type | Conference contribution |
| Language | English |
| Published at | https://doi.org/10.1145/3357713.3384252 |
| Other links | https://www.scopus.com/pages/publications/85086756521 |
| Permalink to this page | |
