论文标题
破坏量子退火器在解决限制下的优化问题中的限制
Breaking limitation of quantum annealer in solving optimization problems under constraints
论文作者
论文摘要
量子退火是使用虚拟量子波动的优化问题的通用求解器。量子退火研究领域最开创性的进展是其硬件实施，即使用人工旋转的所谓量子退火器。但是，人工旋转之间的连通性在称为嵌合体图的特殊网络上稀疏且有限。已经提出了几种嵌入技术，但是逻辑旋转的数量（代表要解决的优化问题）已大大减少。特别是，一个包括完全甚至部分连接的旋转在内的优化问题在嵌合图上遭受了可嵌入的尺寸低。在本研究中，我们提出了一种替代方法，可以通过一种名为Hubbard-Stratonovich Transformation或其变体的统计力学中的知名方法在嵌合体图上解决大规模优化问题。所提出的方法可用于处理完全连接的ISING模型，而无需嵌入嵌合体图，并导致优化问题的非平凡结果。我们通过许多涉及解决线性方程的分区问题和日本京都城市的交通流量优化问题测试了提出的方法。
Quantum annealing is a generic solver for optimization problems that uses fictitious quantum fluctuation. The most groundbreaking progress in the research field of quantum annealing is its hardware implementation, i.e., the so-called quantum annealer, using artificial spins. However, the connectivity between the artificial spins is sparse and limited on a special network known as the chimera graph. Several embedding techniques have been proposed, but the number of logical spins, which represents the optimization problems to be solved, is drastically reduced. In particular, an optimization problem including fully or even partly connected spins suffers from low embeddable size on the chimera graph. In the present study, we propose an alternative approach to solve a large-scale optimization problem on the chimera graph via a well-known method in statistical mechanics called the Hubbard-Stratonovich transformation or its variants. The proposed method can be used to deal with a fully connected Ising model without embedding on the chimera graph and leads to nontrivial results of the optimization problem. We tested the proposed method with a number of partition problems involving solving linear equations and the traffic flow optimization problem in Sendai and Kyoto cities in Japan.
