Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

Quadratic Unconstrained Binary Optimization (QUBO) problems concern the minimization of quadratic polynomials in n{0,1}n{0,1}-valued variables. These problems are NP-complete, but prior work has identified a sequence of polynomial-time computable lower bounds on the minimum value, denoted by C2,C3,C4,…C2,C3,C4,…. It is known that C2C2 can be computed by solving a maximum flow problem, whereas the only previously known algorithms for computing Ck(k>2) require solving a linear program. In this paper we prove that C3C3 can be computed by solving a maximum multicommodity flow problem in a graph constructed from the quadratic function. In addition to providing a lower bound on the minimum value of the quadratic function on {0,1}n{0,1}n, this multicommodity flow problem also provides some information about the coordinates of the point where this minimum is achieved. By looking at the edges that are never saturated in any maximum multicommodity flow, we can identify relational persistencies: pairs of variables that must have the same or different values in any minimizing assignment. We furthermore show that all of these persistencies can be detected by solving single-commodity flow problems in the same network.