用逻辑函数简化自旋相互作用，大幅提升多状态伊辛问题求解效率
Efficient Optimization Accelerator Framework for Multistate Ising Problems
- 将自旋交互建模为广义布尔逻辑，大幅压缩搜索空间
- 在图着色任务中达到顶尖算法精度，性能比现有伊辛机快万倍
- 适用于需要高并发、低功耗的优化场景，如芯片布局与调度
伊辛机是新兴的硬件架构，能高效求解NP难组合优化问题。通常组合问题需转化为无约束二次二值优化（QUBO）形式，但此转换常使解空间复杂化，尤其对多状态问题性能下降明显。本文提出将自旋相互作用建模为广义布尔逻辑函数，显著减少探索空间。在图着色问题上，使用概率伊辛求解器验证了该方法的有效性，其准确率与当前最优启发式及机器学习算法相当，且显著优于现有基于QUBO的伊辛机（包括概率伊辛与模拟分歧机）。同时，基于该方法设计了1024神经元全连接的概率伊辛加速器，部署于FPGA，相比基于GPU的Tabucol启发式算法实现约10000倍性能提升，且物理神经元数量减少1.5至4倍。本工作在多状态优化问题中确立了更高的效率、可扩展性与解质量。
原文摘要 · Abstract (English)
Ising Machines are emerging hardware architectures that efficiently solve NP-Hard combinatorial optimization problems. Generally, combinatorial problems are transformed into quadratic unconstrained binary optimization (QUBO) form, but this transformation often complicates the solution landscape, degrading performance, especially for multi-state problems. To address this challenge, we model spin interactions as generalized boolean logic function to significantly reduce the exploration space. We demonstrate the effectiveness of our approach on graph coloring problem using probabilistic Ising solvers, achieving similar accuracy compared to state-of-the-art heuristics and machine learning algorithms. It also shows significant improvement over state-of-the-art QUBO-based Ising solvers, including probabilistic Ising and simulated bifurcation machines. We also design 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA with the proposed approach that shows ~10000x performance acceleration compared to GPU-based Tabucol heuristics and reducing physical neurons by 1.5-4x over baseline Ising frameworks. Thus, this work establishes superior efficiency, scalability and solution quality for multi-state optimization problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。