论文标题
大量邮政问题变体的量子计算
Quantum Computing for a Profusion of Postman Problem Variants
论文作者
论文摘要
在本文中，我们研究了解决中国邮政问题，图形路由优化问题及其在量子退火设备上的许多变体的生存能力。考虑的路由问题变体包括图形类型，定向变化的权重，涉及路由的当事方数量等。我们强调如何将这些问题转换为二次不受限制的二进制优化（QUBO）问题，这是两个等效的自然范式之一，用于量子退火设备。我们还扩展了一种先前发现的算法，用于在封闭的无向图上解决中国邮政问题，以减少问题中使用的约束和变量的数量。根据D-Wave 2000Q和Advantage的实现结果，讨论了最佳退火参数设置和约束权重值。比较了经典，纯量子和杂种算法的结果。
In this paper we study the viability of solving the Chinese Postman Problem, a graph routing optimization problem, and many of its variants on a quantum annealing device. Routing problem variants considered include graph type, directionally varying weights, number of parties involved in routing, among others. We put emphasis on the explanation of how to convert such problems into quadratic unconstrained binary optimization (QUBO) problems, one of two equivalent natural paradigms for quantum annealing devices. We also expand upon a previously discovered algorithm for solving the Chinese Postman Problem on a closed undirected graph to decrease the number of constraints and variables used in the problem. Optimal annealing parameter settings and constraint weight values are discussed based on results from implementation on the D-Wave 2000Q and Advantage. Results from classical, purely quantum, and hybrid algorithms are compared.
