论文标题
解决量子退火器上的不等式受限的二进制优化问题
Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer
论文作者
论文摘要
我们提出了一种使用量子退火器在不平等约束下解决二进制优化问题的新方法。为了处理不平等约束，我们经常像以前的方法一样使用松弛变量。当我们使用松弛变量时，我们通常进行二进制扩展，这需要大量物理量子。因此，当前量子退火器的问题仅限于小规模。在这项研究中，我们采用了乘数的交替方向方法。这种方法使我们可以使用当前量子退火器中的约束来处理各种类型，而无需松弛变量。为了测试我们的算法的性能，我们使用二次主背问题（QKP）。我们将方法与模拟的退火器以及D-Wave机器的优化和采样模式进行了比较。由于我们的实验，我们发现采样模式显示出最佳的准确性。我们还发现，当我们处理在密集图上定义的各种QKP时，我们方法的计算时间比确切求解器的计算时间更快。
We propose a new method for solving binary optimization problems under inequality constraints using a quantum annealer. To deal with inequality constraints, we often use slack variables, as in previous approaches. When we use slack variables, we usually conduct a binary expansion, which requires numerous physical qubits. Therefore, the problem of the current quantum annealer is limited to a small scale. In this study, we employ the alternating direction method of multipliers. This approach allows us to deal with various types using constraints in the current quantum annealer without slack variables. To test the performance of our algorithm, we use quadratic knapsack problems (QKPs). We compared the accuracy obtained by our method with a simulated annealer and the optimization and sampling mode of a D-Wave machine. As a result of our experiments, we found that the sampling mode shows the best accuracy. We also found that the computational time of our method is faster than that of the exact solver when we tackle various QKPs defined on dense graphs.
