Quantum Software Consortium (QSC)
Day 1 (April 6) @ 11:00–12:30
Simon Apers (CWI Amsterdam, ULB Brussels)
Quantum algorithms for graph sparsification, cut approximation and Laplacian solving
Graph sparsification is a key tool in modern combinatorial optimization. It reduces the number of edges of a graph to near-linear in the number of nodes, while approximately preserving quantities of interest such as the cut or spectral structure of the graph. This is an important routine in efficient algorithms for approximating the minimum and maximum cut in a graph, or for solving a linear system in the graph Laplacian.
In this talk I will formally introduce graph sparsification, and I will show how quantum computers can speed up this key technique. This leads to faster quantum algorithms for the aforementioned problems of cut approximation and solving a Laplacian system.
Jana Sotáková (QuSoft, University of Amsterdam)
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 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 discuss how the underlying algebraic structure of isogeny problems opens up exciting possibilities to analyze these isogeny graphs.
Michael Walter (University of Amsterdam)
Tensors, invariants, and optimization
Given a vector in a representation, can it be distinguished from zero by an invariant polynomial? This classical question in invariant theory connects to a diverse set of problems in mathematics and computer science. In quantum information, it captures the quantum marginal problem and recent notions of tensor ranks. We will see that the general question can be usefully thought of as an optimization problem over non-commutative groups and discuss a rigorous algorithm for solving it.
