Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving

Add to your list(s) Download to your calendar using vCal

• Simon Apers, INRIA and CWI
• Friday 08 November 2019, 12:00-13:00
• MR15, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact Johannes Bausch.

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. The breakthrough work by Benczúr and Karger (STOC’96) and Spielman and Teng (STOC’04) showed that sparsification can be done in time near-linear in the number of edges of the original graph, which is optimal.

In this work we show that quantum algorithms allow to polynomially speed up spectral sparsification, and thereby many of the derived algorithms. The algorithm builds on a string of existing results, most notably sparsification algorithms by Spielman and Srivastava (STOC’08) and Koutis and Xu (TOPC’16), a spanner construction by Thorup and Zwick (STOC’01), the single-source shortest-paths quantum algorithm by Dürr et al. (ICALP’04) and an efficient k-wise independent hash construction by Christiani, Pagh and Thorup (STOC’15). Combining our sparsification algorithm with existing classical algorithms yields quantum speedups for approximating the max cut, min cut, min st-cut, sparsest cut and balanced separator of a graph. Combining our algorithm with a classical Laplacian solver, we demonstrate speedups for Laplacian solving, for approximating effective resistances, cover times, eigenvalues and eigenvectors of the Laplacian, and for spectral clustering.

This is joint work with Ronald de Wolf.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR15, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.