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

SHAHROKH HEIDARI; MICHAEL J. DINNEEN; PATRICE DELMAS

首页> 外文期刊>International journal of unconventional computing >An Equivalent QUBO Model to the Minimum Multi-Way Cut Problem

【24h】

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

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

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相关主题

摘要

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 G = (V, E) and a set of terminals T = {t_1, t_2,...,} ? V we want to find a subset of edges E_c of minimum total cost such that G' = GE_c separates T. 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 O(kV) 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.

著录项

来源
《International journal of unconventional computing》 |2023年第1期|93-113|共21页
作者
SHAHROKH HEIDARI; MICHAEL J. DINNEEN; PATRICE DELMAS;
展开▼
作者单位

School of Computer Science, The University of Auckland, New Zealand, Intelligent Vision Systems Lab, The University of Auckland, New Zealand;

School of Computer Science, The University of Auckland, New Zealand;

Intelligent Vision Systems Lab, The University of Auckland, New Zealand;

展开▼
收录信息
原文格式 PDF
正文语种英语
中图分类计算技术、计算机技术;
关键词
Multi-way cut; quantum annealing; D-Wave; QUBO; computer vision; image restoration;

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

摘要

著录项

相关主题

期刊订阅