Quantum algorithms for vertex sparsification

The goal of graph sparsification is to compress large graphs into smaller ones. In vertex sparsification we are given a graph and a set of terminals. We aim to find a graph with the terminals as vertices, that preserves some property of interest. For vertex- flow sparsification we aim to preserve flows. Moitra proved that vertex-flow sparsifiers exist with quality O( log k/ log log k) , where k is the number of terminals. There is a classical algorithm with runtime ˜O(m2) to find such vertex-flow sparsifier, where m is the number of edges of the original graph. In this work we present a new quantum algorithm with runtime ˜O(m11/6n1/6) that finds the same quality vertex-flow sparsifier, where n is the number of vertices of the original graph. This is a small polynomial speedup for dense graphs. The quantum speedup is based on the classical algorithm, but uses various quantum subroutines from the literature.