2019-09-09
Quantum walk sampling by growing seed sets
Publication
Publication
This work describes a new algorithm for creating a superposition over the edge set of a graph, encoding a quantum sample of the random walk stationary distribution. The algorithm requires a number of quantum walk steps scaling as Õ(m1/3δ−1/3), with m the number of edges and δ the random walk spectral gap. This improves on existing strategies by initially growing a classical seed set in the graph, from which a quantum walk is then run. The algorithm leads to a number of improvements: (i) it provides a new bound on the setup cost of quantum walk search algorithms, (ii) it yields a new algorithm for st-connectivity, and (iii) it allows to create a superposition over the isomorphisms of an n-node graph in time Õ(2n/3), surpassing the Ω(2n/2) barrier set by index erasure.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.4230/LIPIcs.ESA.2019.9 | |
| Leibniz International Proceedings in Informatics (LIPIcs) | |
| Annual European Symposium on Algorithms | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Apers, S. (2019). Quantum walk sampling by growing seed sets. In Annual European Symposium on Algorithms (pp. 9:1–9:12). doi:10.4230/LIPIcs.ESA.2019.9 |
|
