Troy Lee

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)$.

Abstract Let $G$ be an $n$-vertex graph with $m$ edges. When asked a subset $S$ of vertices, a cut query on $G$ returns the number of edges of $G$ that have exactly one endpoint in $S$. We show that there is a bounded-error quantum algorithm that determines all connected components of $G$ after making $O(\log(n)^6)$ many cut queries. In contrast, it follows from results in communication complexity that any randomized algorithm even just to decide whether the graph is connected or not must make at least $\Omega(n/\log(n))$ many cut queries. We further show that with $O(\log(n)^8)$ many cut queries a quantum algorithm can with high probability output a spanning forest for $G$. En route to proving these results, we design quantum algorithms for learning a graph using cut queries. We show that a quantum algorithm can learn a graph with maximum degree $d$ after $O(d \log(n)^2)$ many cut queries, and can learn a general graph with $O(\sqrt{m} \log(n)^{3/2})$ many cut queries. These two upper bounds are tight up to the poly-logarithmic factors, and compare to $\Omega(dn)$ and $\Omega(m/\log(n))$ lower bounds on the number of cut queries needed by a randomized algorithm for the same problems, respectively. The key ingredients in our results are the Bernstein-Vazirani algorithm, approximate counting with ``OR queries'', and learning sparse vectors from inner products as in compressed sensing.