Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.9
URN: urn:nbn:de:0030-drops-111300
URL: https://drops.dagstuhl.de/opus/volltexte/2019/11130/
Apers, Simon
Quantum Walk Sampling by Growing Seed Sets
| pdf-format: |
|
Abstract
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 O~(m^(1/3) delta^(-1/3)), with m the number of edges and delta 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 O~(2^(n/3)), surpassing the Omega(2^(n/2)) barrier set by index erasure.
BibTeX - Entry
@InProceedings{apers:LIPIcs:2019:11130,
author = {Simon Apers},
title = {{Quantum Walk Sampling by Growing Seed Sets}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {9:1--9:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-124-5},
ISSN = {1868-8969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11130},
URN = {urn:nbn:de:0030-drops-111300},
doi = {10.4230/LIPIcs.ESA.2019.9},
annote = {Keywords: Quantum algorithms, Quantum walks, Connectivity, Graph theory}
}
| Keywords: | Quantum algorithms, Quantum walks, Connectivity, Graph theory | |
| Seminar: | 27th Annual European Symposium on Algorithms (ESA 2019) | |
| Issue date: | 2019 | |
| Date of publication: | 06.09.2019 |
