论文标题
构建动态系统以建模高阶iSing旋转相互作用及其在解决组合优化问题中的应用
Constructing Dynamical Systems to Model Higher Order Ising Spin Interactions and their Application in Solving Combinatorial Optimization Problems
论文作者
论文摘要
Ising模型为许多计算硬组合优化问题（COP）提供了自然映射。因此，最近提出了最大程度地减少Ising Hamiltonian的动态系统启发的计算模型和硬件平台，并作为解决COPS的潜在候选人，并承诺具有重大的绩效益处。但是，ISING模型，因此，相应的基于系统的计算模型主要考虑节点之间的二次相互作用。考虑到Ising旋转之间高阶相互作用的计算模型仍然在很大程度上没有探索。因此，在这项工作中，我们建议基于动态系统的计算模型考虑ISING旋转之间的高阶（> 2）相互作用，随后，这使我们能够提出计算模型直接求解许多需要高阶相互作用的COP（HyperGraphs上的COP）。具体而言，我们通过开发动态系统来计算布尔nae-k-sat的解决方案（k大于3）问题，并求解了超图的最大k-cut，从而证明了我们的方法。我们的工作促进了物理启发的“工具箱”来解决警察的潜力。
The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, the Ising model, and consequently, the corresponding dynamical system-based computational models primarily consider quadratic interactions among the nodes. Computational models considering higher order interactions among Ising spins remain largely unexplored. Therefore, in this work, we propose dynamical-system-based computational models to consider higher order (>2) interactions among the Ising spins, which subsequently, enables us to propose computational models to directly solve many COPs that entail such higher order interactions (COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K is greater than 3) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired 'toolbox' for solving COPs.
