Abstract
We study an elementary Markov process on graphs based on electric flow sampling (elfs). This process naturally connects to many quantities of interest -- e.g., we describe a random walk coupling which implies that the elfs process has the same arrival distribution as a random walk. We also analyze the electric hitting time, which is the expected time before the process hits a sink vertex. As our main technical contribution, we show that the electric hitting time on trees is logarithmic in the graph size and weights.
The motivation behind the elfs process is that quantum walks can sample from electric flows, and they can hence implement this process very naturally. This yields a quantum walk algorithm for sampling from the random walk arrival distribution, which has widespread applications. It complements the existing line of quantum walk search algorithms which only return an element from the sink, but yield no insight in the distribution of the returned element. By our bound on the electric hitting time on trees, the quantum walk algorithm on trees requires quadratically fewer steps than the random walk hitting time, up to polylog factors.
Joint work with Stephen Piddock (arXiv:2211.16379).
Join us on Zoom:
Link: https://zoom.us/j/95523872350?pwd=elYrVHNvRnJNN1EyVnY2bU9aNGN1QT09
About EQSI
European Quantum Software Institute (EQSI) is an initiative for quantum software research and education in Europe.
The initiative unites 6 leading research institutions to conduct joint research projects and educational and outreach activities, in collaboration with providers of quantum computing infrastructure and industry partners interested in developing quantum algorithms.
EQSI activities include annual workshops and monthly online seminars.
Subscribe to the EQSI mailing list to receive the announcements of the EQSI Colloquium, as well as other news and events from EQSI: https://mlists.ist.utl.pt/mailman/listinfo/groups.pqi.eqsi-info