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.