An Equivalent QUBO Model to the Minimum Multi-Way Cut Problem

Abstract

Motivated by an application in Computer Vision, we present an e cient QUBO solution for the minimum multi-way cut problem. For an edge-weighted input graph G = (V;E) and a set of terminals T = ft1; t2; : : : ; tkg V we want to nd a subset of edges Ec of minimum total cost such that G0 = G n Ec separates T. QUBO rep- resentations are useful for solving problems on an adiabatic quantum computer like those produced by D-Wave Systems. Our reduction from the multi-way cut problem requires only O(kjV j) binary variables/qubits. The main result of this paper is a proof of correctness of this model. Furthermore, our reduction is small enough to be able to empirically test it with an existing D-Wave hybrid quantum-classical solver, which is illustrated at the end of this paper.