We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrt{ m+n} log n), finding a maximal non-bipartite matching in time O(n^2 (sqrt{ m/n} + log n) log n), and finding a maximal flow in an integer network in time O(min(n^{ 7/6} sqrt m * U^{ 1/3}, sqrt{ n U} m) log n), where n is the number of vertices, m is the number of edges, and U <= n^{ 1/4} is an upper bound on the capacity of an edge.
Categories: quant-ph