Quantum walk sampling by growing seed sets
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.
|, , ,|
|Leibniz International Proceedings in Informatics|
|Annual European Symposium on Algorithms|
|Organisation||Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands|
Apers, S.M.G. (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