Quentin Buzet (Télécom Paris) Can quantum walk search be useful for solving problems in the CONGEST and CONGEST-CLIQUE model?
The k-distinctness problem is a major problem in quantum computing. The best quantum centralized (i.e., non-distributed) algorithms for the k-distinctness problem are based on quantum walk search. In this work, we investigate the complexity of this problem in the distributed setting.
By slightly modifying the algorithm by Le Gall and Magniez (PODC 2018) for network diameter computation in the quantum CONGEST model, we derive a distributed quantum algorithm that efficiently solves a natural distributed version of k-distinctness without using a quantum walk search.
By studying the complexity of a more general problem (k-subset-finding), we obtain a lower bound which suggests that quantum walk search might be a useful technique for solving certain difficult instances of this problem.
Finally, we study what happens in the CONGEST-CLIQUE model and gives a framework to transform a quantum parallel query algorithm into a distributed one in the CONGEST-CLIQUE model.
If time allows, we could discuss a little bit the multiplication of rectangular matrices in the CONGEST-CLIQUE model.