Quantum Software Consortium (QSC)
Day 1 (April 14) @ 13:30 – 15:00
Quantum Speedup for Graph Sparsification, Cut Approximation and Laplacian Solving
Graph sparsification is an important component of a large number of algorithms, ranging from approximation algorithms for cut problems to Laplacian system solvers. 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 optimally in time near-linear in the number of edges of the original graph.
In this work we show that quantum algorithms allow to speed up spectral sparsification, and thereby many of the derived algorithms. To this end we build 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), a 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 the first quantum speedup 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 a similar speedup for Laplacian solving, for approximating effective resistances, cover times and eigenvalues of the Laplacian, and for spectral clustering.
Isogeny graphs in post-quantum cryptography
Public-key cryptography is nowadays an essential part of our daily lives, be it internet banking or credit card transactions. However, ever since the 1990s when Shor developed his quantum factoring algorithm, it has been known that the cryptosystems we use nowadays can be broken using a sufficiently large quantum computer. The search for replacement post-quantum cryptosystems, that is, protocols that will be secure even against adversaries with a quantum computer, has been greatly accelerated by the 2017 NIST competition. One of the proposals, SIKE, uses isogenies of elliptic curves to achieve a practical encryption protocol and subsequently spawned a lot of research in the area. We will formulate the hard problems in isogeny-based cryptography, discuss some of the attacks suggested to solve them and also report on recent experimental work on the underlying assumptions.