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
Keywords Connectivity, Graph theory, Quantum algorithms, Quantum walks
Persistent URL
Conference Annual European Symposium on Algorithms
Apers, S. (2019). Quantum walk sampling by growing seed sets. In Leibniz International Proceedings in Informatics. doi:10.4230/LIPIcs.ESA.2019.9