Electric Flow Sampling and Quantum Walks on Trees

Watch a conference talk from TQC 2023 exploring an innovative elementary Markov process called electric flow sampling (elfs) and its connections to quantum walks. Learn how this process, which repeatedly samples from electric flows on graphs with fixed sinks but updated sources, relates to random walks and exhibits the same arrival distribution. Discover the analysis of electric hitting time, particularly on trees where it demonstrates logarithmic behavior relative to graph size and weights. Understand how quantum walks can naturally implement this process by sampling from electric flows, leading to a quantum walk algorithm that samples from random walk arrival distributions - a significant advancement over existing quantum walk search algorithms that only return sink elements. Follow along as the speaker demonstrates how this quantum walk algorithm achieves quadratically faster performance than random walk hitting time on trees, with only polylogarithmic overhead factors.