Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer.
Solving Inequality-Constrained Binary Optimization Problems on Quantum Annealer.
复制标题
解决量子退火器上的不等式约束二元优化问题。
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Masayuki Ohzeki
中科院分区：
文献类型：
--
作者：
Kouki Yonaga;Masamichi J. Miyama;Masayuki Ohzeki
我们提出了一个新的方法来解决二元优化问题的不等式约束下使用量子退火。为了处理不等式约束，我们经常使用松弛变量，就像以前的方法一样。当我们使用松弛变量时，我们通常进行二进制扩展，这需要大量的物理量子位。因此，当前量子退火机的问题仅限于小规模。在这项研究中，我们采用交替方向法的乘数。这种方法使我们能够处理各种类型的使用限制在当前的量子退火没有松弛变量。为了测试我们的算法的性能，我们使用二次背包问题（QKPs）。我们比较了我们的方法与模拟退火和D波机的优化和采样模式所获得的精度。作为我们的实验结果，我们发现，采样模式显示出最好的准确性。我们还发现，我们的方法的计算时间是快于精确求解器，当我们处理各种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.
影响因子：
4.6
作者：
Ikeda, Kazuki;Nakamura, Yuma;Humble, Travis S.
通讯作者：
Humble, Travis S.