Okada Shuntaro, Ohzeki Masayuki, Terabe Masayoshi, Taguchi Shinichiro
Electronics R & I Division, DENSO Corporation, Tokyo, 103-6015, Japan.
Graduate School of Information Sciences, Tohoku University, Sendai, 980-8579, Japan.
Sci Rep. 2019 Feb 14;9(1):2098. doi: 10.1038/s41598-018-38388-4.
Quantum annealing is a heuristic algorithm that solves combinatorial optimization problems, and D-Wave Systems Inc. has developed hardware implementation of this algorithm. However, in general, we cannot embed all the logical variables of a large-scale problem, since the number of available qubits is limited. In order to handle a large problem, qbsolv has been proposed as a method for partitioning the original large problem into subproblems that are embeddable in the D-Wave quantum annealer, and it then iteratively optimizes the subproblems using the quantum annealer. Multiple logical variables in the subproblem are simultaneously updated in this iterative solver, and using this approach we expect to obtain better solutions than can be obtained by conventional local search algorithms. Although embedding of large subproblems is essential for improving the accuracy of solutions in this scheme, the size of the subproblems are small in qbsolv since the subproblems are basically embedded by using an embedding of a complete graph even for sparse problem graphs. This means that the resource of the D-Wave quantum annealer is not exploited efficiently. In this paper, we propose a fast algorithm for embedding larger subproblems, and we show that better solutions are obtained efficiently by embedding larger subproblems.
量子退火是一种解决组合优化问题的启发式算法，D-Wave系统公司已经开发了该算法的硬件实现。然而，一般来说，由于可用量子比特的数量有限，我们无法嵌入大规模问题的所有逻辑变量。为了处理大型问题，已提出qbsolv作为一种将原始大型问题划分为可嵌入D-Wave量子退火器的子问题的方法，然后使用量子退火器对这些子问题进行迭代优化。在这个迭代求解器中，子问题中的多个逻辑变量会同时更新，并且通过这种方法，我们期望获得比传统局部搜索算法更好的解决方案。尽管在该方案中嵌入大型子问题对于提高解决方案的准确性至关重要，但在qbsolv中，子问题的规模较小，因为即使对于稀疏问题图，子问题基本上也是通过使用完全图的嵌入来进行嵌入的。这意味着D-Wave量子退火器的资源没有得到有效利用。在本文中，我们提出了一种用于嵌入更大子问题的快速算法，并表明通过嵌入更大的子问题可以有效地获得更好的解决方案。
