标题： 通过在D-Wave量子退火器中嵌入更大的子问题来改进解决方案 显示英文标题

标题： Improving solutions by embedding larger subproblems in a D-Wave quantum annealer

摘要： 量子退火是一种启发式算法，用于解决组合优化问题，D-Wave Systems Inc. 已开发了该算法的硬件实现。 然而，通常情况下，我们无法嵌入大规模问题的所有逻辑变量，因为可用的量子位数量是有限的。 为了处理大规模问题，提出了 qbsolv 作为一种方法，将原始的大问题划分为可以在 D-Wave 量子退火器中嵌入的子问题，并使用量子退火器迭代优化这些子问题。 在这个迭代求解器中，子问题中的多个逻辑变量会同时更新，使用这种方法，我们期望获得比传统局部搜索算法更好的解决方案。 尽管在该方案中，大型子问题的嵌入对于提高解决方案的准确性至关重要，但 qbsolv 中的子问题规模较小，因为子问题基本上是通过使用完全图的嵌入来实现的，即使对于稀疏的问题图也是如此。 这意味着 D-Wave 量子退火器的资源没有被高效利用。 在本文中，我们提出了一种快速嵌入更大子问题的算法，并表明通过嵌入更大的子问题可以高效地获得更好的解决方案。 显示英文摘要

摘要： 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.