Quantum Algorithms for Max Flow Networks

• Group Members: Bradley Albright and Archana Mohandas

Network flow matching remains one of the most studied subjects in computer science for its application to so many different real world problems. Network Flow is the problem of finding how much flow we can push from a start node to an end node with the constraint of limited capacities along connecting edges. This algorithm can be used in specific matching problems such as for scheduling, segmentation, and circulation of goods. It’s versatility is shown in the fact that it is not only able to be used both for minimization and maximization because of the strong duality between maximum flow and the min-cut theorem described below.

Over the years classical algorithms have made improvements to the max flow solve time, however, we now look to quantum computing to take the next step towards faster max flow algorithms. In many classical algorithms our data structures are oftentimes our limiting factor. Quantum algorithms seek to break this boundary by making use of Grover’s search to speed up our ability to find the specifics we need. We researched algorithms that make use of Quantum theory and Grover’s search to speed up the process of max flow search.

One of the first algorithms proposed as a solution to this problem is the Ford-Fulkerson algorithm. This method finds an augmented path (path from start to end node based on current edge capacity), computes the bottleneck capacity (edge capacity that limits the flow through the path), and augments each edge as well as the total flow. Typically, either breadth-first search or depth-first search is used to find the augmented paths, which takes O(n) where n is the set of edges in the graph. The total time taken for Ford-Fulkerson using this method is O(n*U) where U is the maximum flow (brilliant.org).

In the example above basic paths from the start node to the end node are found. Then if there is a nonzero flow over an augmenting path in the residual graph then it is possible to increase flow over the graph. By phrasing this problem as an LP we are also able to show that when we have found a minimum cut along our graph we also have found the maximum flow of the graph.

Definitions:

• Cut: A set of edges that completely separate the start node from the end node

We assign layers l:V to N to its vertices such that l(a) = 0 and l(y) = 1 + min_(x:(x,y) in E) l(x). This new graph design creates a directed tree graph that determines the layers based on the exploration of BFS

Quantum alg for BFS:

1. Set l(a) = 0 and l(x) = inf for x != a. Create a one-entry queue W = {a}
2. While W != empty set
3. Take the first vertex x from W
4. Find by Grover’s search all its neighbors y with l(y) = inf, set l(y) := l(x)+1, and append y into W
5. remove x from W

The quantized version of this algorithm implements Grover’s search to improve the time complexity of this classical problem. Given a connected directed graph G = (V,E) a layered graph is created such that the vertices are ordered in layers with edges only connecting layers i to i+1:

Grover’s search finds all the neighbors of each vertex v in the layered graph and computes the “layer number” for all vertices. This reduces the time spent searching for augmented paths from the source to the sink. The time spent in Grover’s searches leading to an augmenting path in v is at most O((Uavdv)), where avis the number of augmenting paths going through v, dvis the length of the list of neighbors of v, ev, iis the number of outgoing edges from v, and U is the maximum capacity at every edge:

Using Grover’s search to find augmented paths reduces the typical total runtime of the algorithm from O(nmlog(U)) to O(n^(13/6)U(1/3))log(n)).

Here are some points of review about Grover’s Algorithm:

• Superior database search when compared to classical algorithms
• Uses an oracle that adds a negative phase to solution states
• Uses problems property that it is often times difficult to find a solution but easy to verify a solution
• Begins with a uniform superposition
• Use the oracle to negate the probability of the winner
• Reflect all amplitudes around the average amplitude
• In the case of multiple solutions sqrt(N/M) rotations will suffice

Below is an example of the general Grover search algorithm that uses the oracle as well as the rotation about the mean operator to search a database. In the max flow algorithm this would be initialized such that the neighboring edges of a node are inputs. Then the oracle will find such edges that have infinite weight.

We show an example of a qiskit circuit of a grover problem oracle below:

This quantum improvement hints of bigger improvements to other classical algorithms. With the use of quantum computers we can find solutions faster and more efficiently to many other problems that we have found in computer science. This is just one of the ways that quantum computers can provide a speedup to searches and algorithms. This research could be continued by having a full implementation in a simulated environment like Qiskit or in hardware.

Sources:

Ambainis, A., & Spalek, R. (2005, September 5). Quantum Algorithms for Matching and Network Flows [PDF].

Ford-Fulkerson Algorithm. (n.d.). Retrieved January 29, 2021, from https://brilliant.org/wiki/ford-fulkerson-algorithm/

Grover’s Algorithm (n.d.) Retrieved January 29, 2021, from https://en.wikipedia.org/wiki/Grover%27s_algorithm

Maximum Flow Problem (n.d.) Retrieved January 29, 2021, from https://en.wikipedia.org/wiki/Maximum_flow_problem

Team, T. (2021, January 26). Grover’s Algorithm. Retrieved January 29, 2021, from https://qiskit.org/textbook/ch-algorithms/grover.html