Student internships

• Quantum algorithms and dynamic data structures.
  
  Dynamic data structures play a key role in the fastest algorithms for problems in optimization, statistics and string processing. At their core, these data structures maintain a clever sketch of data that continually undergoes changes (e.g., when edges are added or removed in a graph). As quantum algorithms are known to provide speedups over many data processing tasks, it is anticipated that quantum algorithms can also improve over the best dynamic data structures. A recent example is a faster quantum algorithm for zero-sum games (arXiv:2301.03763). The purpose of this internship is to study the relevants concepts in quantum computing and dynamic data structures, and to try and combine these to obtain faster quantum data structures for dynamic data. Joint supervision with Frédéric Magniez.
  


• Quantum algorithms for graph spanners and sparsifiers.
  
  A graph spanner is a sparse subgraph that approximately preserves shortest-path distances. In a recent work, a quantum algorithm for constructing graph spanners was described. This was used to obtain faster quantum algorithms for a wide range of graph problems such as graph sparsification, computing the minimum cut, and solving Laplacian systems. The aim of this project is to find a faster quantum algorithm for constructing a spanner of an *unweighted* graph. This would lead to faster algorithms for all of the aforementioned problems as well.
  


• Quantum algorithm for tree edit distance.
  
  While we know quantum speedups for many problems in optimization, the problem of computing the "edit distance" between two strings has always evaded a quantum speedup. Recent work in quantum fine-grained complexity suggests that in no fact quantum speedup is possible for this problem (link). A closely related and apparently more motivated problem is that of "tree edit distance", where the goal is to compute the edit distance between two tree graphs instead of two strings. This problem is closely related to computing the max-plus product, for which we do know a quantum speedup. The aim of this project is to study quantum algorithms for tree edit distance, potentially by building on dynamic programming techniques (link, link).
  


• OR-query complexity of graph matching.
  
  Query complexity studies the number of "queries" or "probes" that one has to make to an object to learn something about it. In a recent work (arXiv:2208.02526), it was shown that the OR-query complexity of bipartite matching is almost-linear. They used this to bound the quantum query complexity of bipartite matching. In this project we aim to bound the OR-query complexity of general matching by working the other way around. There is a quantum query algorithm for general matching (arXiv:2010.02324), and we will try to use this to bound the OR-query complexity of general matching.
  


• Quantum s-t connectivity.
  
  Given access to a graph and a pair of vertices s and t, the problem of s-t connectivity is to decide whether there exists a path from s to t in the graph. This problem is well studied in the classical literature, with an interesting landscape of tradeoffs between the time and space complexity of the problem. In some recent works (arXiv:2212.00094, arXiv:1904.11446) we have started to study the quantum complexity and time-space tradeoff of s-t connectivity. The algorithms are based on quantum walks. Despite some progress, we are far from having a full understanding of the quantum space-time tradeoff, and the goal of this project is to find new quantum (walk) algorithms showing improved tradeoffs.