IJUC Homeย โขย Issue Contents
An Equivalent QUBO Model to the Minimum Multi-Way Cut Problem
Shahrokh Heidari, Michael J. Dinneen and Patrice Delmas
Motivated by an application in Computer Vision, we present an efficient QUBO solution for the minimum multi-way cut problem. For an edge-weighted input graph ๐บ = (๐, ๐ธ) and a set of terminals ๐ = {๐ก1, ๐ก2, . . . , ๐ก๐} โ ๐ we want to find a subset of edges ๐ธ๐ย of minimum total cost such that ๐บโ = ๐บ \ ๐ธ๐ separates ๐. QUBO representations 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 ๐(๐|๐|) 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.
Keywords: Multi-way cut, quantum annealing, D-Wave, QUBO, computer vision, image restoration