Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving

Graph sparsification underlies a large number of algorithms, ranging from algorithms for cut problems to solvers for linear systems in the Laplacian. In its strongest form, "spectral sparsification" reduces the of edges to near-linear in the number of nodes, while approximately the cut and spectral structure of the graph. In this work we a polynomial quantum speedup for spectral sparsification and many its applications. In particular, we give a quantum algorithm that, given a graph with n nodes and m edges, outputs a classical description of \ε-spectral sparsifier in sublinear timẽ(\√mn/\ε). This contrasts with the optimal classical ̃(m). We also prove that our quantum algorithm is optimal to polylog-factors. The algorithm builds on a string of existing results on, graph spanners, quantum algorithms for shortest paths, and constructions for k-wise independent random strings. Our algorithm a quantum speedup for solving Laplacian systems and for approximating a of cut problems such as min cut and sparsest cut.