Solving the Max-Flow Problem on a Quantum Annealing Computer

This article addresses the question of implementing a maximum flow algorithm on directed graphs in a formulation suitable for a quantum annealing computer. Three distinct approaches are presented. In all three cases, the flow problem is formulated as a quadratic unconstrained binary optimization (QUBO) problem amenable to quantum annealing. The first implementation augments a graph with integral edge capacities into a multigraph with unit-capacity edges and encodes the fundamental objective and constraints of the maximum flow problem using a number of qubits equal to the total capacity of the graph Sigma(i) c(i). The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to O(|E| log C-max), where |E| and C-max denote the number of edges and maximum edge capacity of the graph, respectively. The third implementation adapts the dual minimum cut formulation and encodes the problem instance using |V| qubits, where |V| is the number of vertices in the graph. Scaling factors for penalty terms and coupling matrix construction times are made explicit in this article.