A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
Preprint
Abstract
An $s{\operatorname{-}}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{\operatorname{-}}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{\operatorname{-}}t$ cut after $\widetilde O(\sqrt{m} n^{5/6} W^{1/3})$ queries to the adjacency list of $G$. For simple graphs this bound is always $\widetilde 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.
Keywords
All Related Versions
This publication has 6 references indexed in Scilit:
- Approximate Undirected Maximum Flows in O(mpolylog(n)) Time2015
- Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov ArgumentsSIAM Journal on Computing, 2008
- Lower Bounds for Local Search by Quantum ArgumentsSIAM Journal on Computing, 2006
- Quantum Lower Bounds by Quantum ArgumentsJournal of Computer and System Sciences, 2002
- Beyond the flow decomposition barrierJournal of the ACM, 1998
- Maximal Flow Through a NetworkCanadian Journal of Mathematics, 1956