Résumé
A minimum cut in a graph is a set of edges that disconnects the graph and has minimum total weight. Finding such a minimum cut is a canonical problem in combinatorial optimization that has been studied since at least the 1960s, and which is still an active topic of research. In recent work we characterized the quantum complexity of the minimum cut problem, showing a quantum speedup in the query and time complexity of finding a minimum cut with respect to classical algorithms. The corresponding quantum algorithm builds on a recent quantum speedup for graph sparsification by Apers and de Wolf (FOCS '20) and on recent advances in classical algorithms for minimum cut by Kawarabayashi and Thorup (STOC '15) and Rubinstein et al. (ITCS '18). As a key tool we propose a classical algorithm for finding the partitioning of a weighted graph induced by the set of near-minimum cuts.
This is based on joint works with Troy Lee and Pawel Gawrychowski.
