Dobrynin Dmitrii, Renaudineau Adrien, Hizzani Mohammad, Strukov Dmitri, Mohseni Masoud, Strachan John Paul
Peter Grünberg Institut (PGI-14), <a href="https://ror.org/02nv7yv05">Forschungszentrum Jülich</a> GmbH, Jülich, Germany.
<a href="https://ror.org/04xfq0f34">RWTH Aachen University</a>, Aachen, Germany.
Phys Rev E. 2024 Oct;110(4-2):045308. doi: 10.1103/PhysRevE.110.045308.
Physics-based Ising machines (IM) have been developed as dedicated processors for solving hard combinatorial optimization problems with higher speed and better energy efficiency. Generally, such systems employ local search heuristics to traverse energy landscapes in searching for optimal solutions. Here, we quantify and address some of the major challenges met by IMs by extending energy-landscape geometry visualization tools known as disconnectivity graphs. Using efficient sampling methods, we visually capture landscapes of problems having diverse structure and hardness manifesting as energetic and entropic barriers for IMs. We investigate energy barriers, local minima, and configuration space clustering effects caused by locality reduction methods when embedding combinatorial problems to the Ising hardware. To this end, we sample disconnectivity graphs of PUBO energy landscapes and their different QUBO mappings accounting for both local minima and saddle regions. We demonstrate that QUBO energy-landscape properties lead to the subpar performance for quadratic IMs and suggest directions for their improvement.
基于物理的伊辛机（IM）已被开发为专用处理器，用于以更高的速度和更好的能源效率解决硬组合优化问题。一般来说，此类系统采用局部搜索启发式方法来遍历能量景观以寻找最优解。在此，我们通过扩展被称为不连通性图的能量景观几何可视化工具，对IM遇到的一些主要挑战进行量化并加以解决。使用高效采样方法，我们直观地捕捉具有不同结构和难度的问题的景观，这些问题表现为IM的能量和熵障碍。我们研究了在将组合问题嵌入伊辛硬件时，由局部性降低方法导致的能量障碍、局部极小值和配置空间聚类效应。为此，我们对PUBO能量景观及其不同的QUBO映射的不连通性图进行采样，同时考虑局部极小值和鞍点区域。我们证明，QUBO能量景观特性导致二次IM的性能欠佳，并提出了改进方向。
