A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs

Abstract

An $s-t$ minimum cut in a graph corresponds to a minimum weight subset of edges whose removal disconnects vertices $s$ and $t$. Finding such a cut is a classic problem that is dual to that of finding a maximum flow from $s$ to $t$. In this work we describe a quantum algorithm for the minimum $s-t$ cut problem on undirected graphs. For an undirected graph with $n$ vertices, $m$ edges, and integral edge weights bounded by $W$, the algorithm computes with high probability the weight of a minimum $s-t$ cut after $\tilde{O}(\sqrt{m}{n}^{5/6}{W}^{1/3})$ queries to the adjacency list of $G$. For simple graphs this bound is always $\tilde{O}(n^{11/6})$, even in the dense case when $m=\Omega (n^2)$. In contrast, a randomized algorithm must make $\Omega (m)$ queries to the adjacency list of a simple graph $G$ even to decide whether $s$ and $t$ are connected.

The proof of the upper bound on the time complexity in the first arXiv version contained a fatal flaw. In this version we remove the claim about time complexity and prove the result only for query complexity