Quantum Walk Sampling by Growing Seed Sets - Archive ouverte HAL Access content directly
Conference Papers Year :

Quantum Walk Sampling by Growing Seed Sets

(1, 2)
1
2

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 $\tO(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 $\widetilde{O}(2^{n/3})$, surpassing the $\Omega(2^{n/2})$ barrier set by index erasure.

Dates and versions

hal-02436629 , version 1 (13-01-2020)

Identifiers

Cite

Simon Apers. Quantum Walk Sampling by Growing Seed Sets. ESA 2019 - 27th Annual European Symposium on Algorithms, Sep 2019, Munich/Garching, Germany. ⟨10.4230/LIPIcs.ESA.2019.9⟩. ⟨hal-02436629⟩

Collections

INRIA INRIA2
32 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More