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 ∑ici. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to O(|E|logCmax), where |E| and Cmax 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.
For more about this transaction see link below.