Quantum Algorithms for Matching and Network Flows

2005/08/27 by Andris Ambainis, Ambainis, Andris, Robert Spalek +1 · 1 citation
Physics and Astronomy · #FOS: Physical sciences #Quantum Physics (quant-ph) #quant-ph

paper · pdf · doi:10.48550/arxiv.quant-ph/0508205

13 pages, v2: added an Omega(n^2) lower bound for network flows

arxiv created 2005/09/08 · arxiv updated 2009/12/01

Abstract

We present quantum algorithms for the following graph problems: finding a maximal bipartite matching in time O(n sqrtm+n log n), finding a maximal non-bipartite matching in time O(n² (sqrtm/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, sqrtn 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.

Cited by

• Quantum Algorithms for Projection-Free Sparse Convex Optimization

Related

• Time and Query Optimal Quantum Algorithms Based on Decision Trees
• Limitation of Quantum Walk Approach to the Maximum Matching Problem
• A Quantum Approximate Optimization Algorithm
• Applying the Quantum Alternating Operator Ansatz to the Graph Matching Problem
• From Bit-Parallelism to Quantum String Matching for Labelled Graphs