Quantum complexity of minimum cut

Understand

The minimum cut problem in an undirected and weighted graph $G$ is to find the minimum total weight of a set of edges whose removal disconnects $G$.

• We completely characterize the quantum query and time complexity of the minimum cut problem in the adjacency matrix model.
• If $G$ has $n$ vertices and edge weights at least $1$ and at most $\tau$, we give a quantum algorithm to solve the minimum cut problem using $\tilde O(n^{3/2}\sqrt{\tau})$ queries and time.
• Moreover, for every integer $1 \le \tau \le n$ we give an example of a graph $G$ with edge weights $1$ and $\tau$ such that solving the minimum cut problem on $G$ requires $\Omega(n^{3/2}\sqrt{\tau})$ many queries to the adjacency matrix of $G$.