Abstract
In this paper, we propose a quantum computing oriented benchmark for combinatorial optimization. This benchmark, coined as QOPTLib, is composed of 40 instances equally distributed over four well-known problems: Traveling Salesman Problem, Vehicle Routing Problem, one-dimensional Bin Packing Problem and the Maximum Cut Problem. The sizes of the instances in QOPTLib not only correspond to computationally addressable sizes, but also to the maximum length approachable with non-zero likelihood of getting a good result. In this regard, it is important to highlight that hybrid approaches are also taken into consideration. Thus, this benchmark constitutes the first effort to provide users a general-purpose dataset. Also in this paper, we introduce a first full solving of QOPTLib using two solvers based on quantum annealing. Our main intention with this is to establish a preliminary baseline, hoping to inspire other researchers to beat these outcomes with newly proposed quantum-based algorithms.
Abstract (translated)
在本文中,我们提出了一个面向量子计算的组合优化基准。这个基准被称为QOPTLib,由40个实例组成,均匀分布于四个著名问题:旅行商问题、车辆路由问题、一维 Bin Packing 问题和最大剪枝问题。QOPTLib中的实例大小不仅对应于计算可处理的大小,而且对应于非零可能性获得良好结果的最大长度。在这方面,需要强调的是,也考虑了混合方法。因此,这个基准构成了为用户提供通用数据集的第一步努力。此外,本文我们还介绍了使用量子退火方法解决QOPTLib的第一个完整解决方案。我们主要希望建立一个初步基准,希望激励其他研究人员通过新提出的基于量子的算法超越这些结果。
URL
https://arxiv.org/abs/2404.15852