Solving the Max-Flow Problem on a Quantum Annealing Computer

Abstract

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 $\sum _i{c_i}$. The second implementation, which encodes flows through edges using a binary representation, reduces the required number of qubits to $\mathcal {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.

Keywords

• Maximum flow problem
• minimum cut problem
• quantum annealing
• quantum computing
• simulated annealing