QUANTUM SPEEDUP FOR GRAPH SPARSIFICATION, CUT APPROXIMATION, AND LAPLACIAN SOLVING

Graph sparsification underlies a large number of algorithms, ranging from approximation algorithms for cut problems to solvers for linear systems in the graph Laplacian. 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. In this work we demonstrate a polynomial quantum speedup for spectral sparsification and many of its applications. In particular, we give a quantum algorithm that, given a weighted graph with n nodes and m edges, outputs a classical description of an \epsilon -spectral sparsifier in sublinear time Owidetilde \(\surd mn/\epsilon ). This contrasts with the optimal classical complexity Owidetilde \(m). We also prove that our quantum algorithm is optimal up to polylog-factors. The algorithm builds on a string of existing results on sparsification, graph spanners, quantum algorithms for shortest paths, and efficient constructions for k-wise independent random strings. Our algorithm implies a quantum speedup for solving Laplacian systems and for approximating a range of cut problems such as min cut and sparsest cut.