论文标题
使用基准优化问题对量子退火器和混合求解器的实验分析
Experimental analysis of quantum annealers and hybrid solvers using benchmark optimization problems
论文作者
论文摘要
本文研究了D-Wave的量子系统上的Hamiltonian周期问题（HCP）和旅行推销员问题（TSP）。最初，由于大多数图书馆在邻接矩阵方面呈现其基准实例的动机，我们为HCP和TSP Hamiltonians开发了一种新颖的矩阵公式，这可以使基准实例在量子平台中无缝且自动整合。我们广泛的实验测试使我们得出了一些有趣的结论。 D-Wave的{\ tt Advantage \ _System4.1}在量子利用和解决方案的质量方面都比{\ tt Advantage \ _System1.1}更有效。最后，我们通过实验确定D-Wave的混合求解器始终为问题提供有效的解决方案，而不会违反QUBO约束，即使对于任意的大问题，$ 120美元的节点订单。在求解TSP实例时，量子退火器产生的解决方案通常是无效的，因为它们违反了图的拓扑。为了解决此用途，我们主张使用\ emph {min-max归一化}对TSP Hamiltonian的系数。最后，我们对表达HCP和TSP汉密尔顿人所需的确切限制数量进行了彻底的数学分析。该分析是定量解释的，为什么几乎总是运行不完整的图形实例需要比完整实例更多的Qubit。事实证明，不完整的图需要比完整的图表更多的二次约束，这一事实已被一系列实验所证实。
This paper studies the Hamiltonian Cycle Problem (HCP) and the Traveling Salesman Problem (TSP) on D-Wave's quantum systems. Initially, motivated by the fact that most libraries present their benchmark instances in terms of adjacency matrices, we develop a novel matrix formulation for the HCP and TSP Hamiltonians, which enables the seamless and automatic integration of benchmark instances in quantum platforms. our extensive experimental tests have led us to some interesting conclusions. D-Wave's {\tt Advantage\_system4.1} is more efficient than {\tt Advantage\_system1.1} both in terms of qubit utilization and quality of solutions. Finally, we experimentally establish that D-Wave's Hybrid solvers always provide a valid solution to a problem, without violating the QUBO constraints, even for arbitrarily big problems, of the order of $120$ nodes. When solving TSP instances, the solutions produced by the quantum annealer are often invalid, in the sense that they violate the topology of the graph. To address this use we advocate the use of \emph{min-max normalization} for the coefficients of the TSP Hamiltonian. Finally, we present a thorough mathematical analysis on the precise number of constraints required to express the HCP and TSP Hamiltonians. This analysis, explains quantitatively why, almost always, running incomplete graph instances requires more qubits than complete instances. It turns out that incomplete graph require more quadratic constraints than complete graphs, a fact that has been corroborated by a series of experiments.
