Heidari, SDinneen, MJDelmas, P2023-01-242023-01-242022CDMTCS Research Reports CDMTCS-565 (2022)1178-3540https://hdl.handle.net/2292/62559Motivated 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.Items in ResearchSpace are protected by copyright, with all rights reserved, unless otherwise indicated. Previously published items are made available in accordance with the copyright policy of the publisher.https://researchspace.auckland.ac.nz/docs/uoa-docs/rights.htmTechnical ReportFields of ResearchCopyright: The author(s)http://purl.org/eprint/accessRights/OpenAccess