Student internships

• Quantum HITS.
  
  The HITS algorithm is a web link analysis algorithm proposed by Jon Kleinberg, comparable to Google's PageRank algorithm. It is based on the singular value decomposition of the adjacency matrix of a directed graph. In contrast to Google's PageRank algorithm, there is no known space-efficient implementation of the HITS algorithm. Aim of the project is to develop a space-efficient quantum implementation of the HITS algorithm. Starting point is a recent work (arXiv:2408.12473) showing a quantum space advantage for solving connectivity on directed graphs.
  


• Quantum expansion testing.
  
  In the field of property testing, we wish to determine whether an object has a certain property, or whether it is "far" from having that property. A classic example is "expansion testing", where we want to test whether a graph is an expander, or whether it is far from being an expander -- see "On testing expansion in bounded-degree graphs" by Goldreich and Ron. Aim of this project is to extend these ideas to the quantum setting, where we wish to test whether a given quantum channel is a so-called "quantum expander".
  


• 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 fact no 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).
  


• 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.