Simon Apers

We study an elementary Markov process on graphs based on electric flow sampling (elfs). The elfs process repeatedly samples from an electric flow on a graph. While the sinks of the flow are fixed, the source is updated using the electric flow sample, and the process ends when it hits a sink vertex. We argue that this process naturally connects to many key 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 initial 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.

Abstract Graph sparsification underlies a large number of algorithms for graph cut problems and solving Laplacian systems. In its strongest form, "spectral sparsification" reduces the number of edges to near-linear in the number of nodes, while approximately preserving the cut and spectral structure of the graph. We give a quantum algorithm that outputs a classical description of an $\varepsilon$-spectral sparsifier of a weighted graph with $n$ vertices and $m$ edges. It has time complexity $\widetilde O(\sqrt{mn}/\varepsilon)$ in the adjacency array model and $\widetilde O(n^{3/2}/\varepsilon)$ in the adjacency matrix model. These bounds are tight up to polylogarithmic factors, and improve on the optimal classical complexities $\Omega(m)$ and $\Omega(n^2)$, respectively. Using classical algorithms on the obtained sparsifier yields immediate quantum speedups for approximately solving Laplacian systems and for approximating a range of graph cut problems in essentially the same complexity. As a significantly more involved application we show how to speed up the quantum query complexity for computing exactly the edge connectivity of simple graphs. We show upper bounds on the query complexity of $\widetilde O(\sqrt{mn})$ and $\widetilde O(n^{3/2})$ in the adjacency matrix and adjacency array models, respectively. The upper bound for the adjacency matrix model is tight up to logarithmic factors, while for the adjacency array model the best quantum query lower bound we know is $\Omega(n)$.

The complexity of matrix multiplication is a central topic in computer science. While the focus has traditionally been on exact algorithms, a long line of literature also considers randomized algorithms, which return an approximate solution in faster time. In this work, we adopt a unifying perspective that frames these randomized algorithms in terms of mean estimation. Using it, we first give refined analyses of classical algorithms based on random walks by Cohen-Lewis (`99), and based on sketching by Sarlós (`06) and Drineas-Kannan-Mahoney (`06). We then propose an improvement on Cohen-Lewis that yields a single classical algorithm that is faster than all the other approaches, if we assume no use of (exact) fast matrix multiplication as a subroutine. Second, we demonstrate a quantum speedup on top of these algorithms by using the recent quantum multivariate mean estimation algorithm by Cornelissen-Hamoudi-Jerbi (`22).