The EQSI Seminar will take place on Monday, May 19, 17:00 CET with a talk "Elfs, trees and quantum walks" by Simon Apers.
Join us on Zoom:
Link: https://zoom.us/j/95523872350?pwd=elYrVHNvRnJNN1EyVnY2bU9aNGN1QT09
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).
To foster the exchange of information, EQSI will organise a monthly series of online talks on quantum software. The talks will alternate between higher-level overview talks by distinguished scientists (EQSI Colloquium) and presentations of specific recent results (EQSI Seminar). Typically, the talks will take place in the 3rd week of the month, starting at 5pm CET, so that audiences from both Europe and North America are able to watch the talks live.
Recordings of the EQSI Colloquium talks will be available on the EQSI Youtube channel
Talk schedule:
Tuesday, March 21, 2023 5pm CET (EQSI Colloquium): Ashley Montanaro (Phasecraft and University of Bristol), Near-term quantum algorithms for optimization (Watch on Youtube).
Monday, April 17, 2023, 5pm CET (EQSI Seminar): Freek Witteveen (University of Copenhagen), The minimal canonical form of a tensor network
Tuesday, May 16, 2023, 5pm CET (EQSI Colloquium): Andrew Childs (University of Maryland), Quantum divide and conquer
Monday, June 19, 2023, 5pm CET (EQSI Seminar): Simon Apers (CNRS), Elfs, trees and quantum walks