Daedalus：一种基于物理原理的混合信号优化引擎，采用动态连续时间注入技术解决3-SAT问题

《IEEE Journal of Solid-State Circuits》：Daedalus: A Physics-Inspired Mixed-Signal Optimization Engine With Dynamic Continuous-Time Injection for Solving 3-SAT Problems

NP完全问题的物理启发式求解方法研究。提出基于混合信号计算的大规模振荡器架构Daedalus，通过连续时间自旋耦合动力学实现3-SAT问题的加速求解，实验表明其能量效率比传统方法提升8.4倍，解决速度提高6倍，在28nm CMOS原型上达到亚微秒级响应。

　　

摘要：

非确定性多项式时间完全（NP完全）组合优化问题（COPs），例如布尔可满足性（SAT），在经典计算架构上难以解决，通常会导致随着问题规模的增加，解决时间和能源消耗呈指数级增长。受自然物理交互的启发，基于物理原理的计算机利用耦合自旋的连续时间（CT）动态、大规模并行性和模拟计算来加速COPs的求解。本文通过引入Daedalus这一基于大规模并行振荡器的直接3-SAT引擎，推动了该领域的发展。Daedalus在混合信号计算框架内运用了基于物理原理的启发式方法，实现了先进的解决时间和能源效率。我们提出了一个包含三体自旋相互作用和非线性自旋耦合的CT动态系统，以实现快速收敛到基态。一个可扩展的基于混合信号的交叉开关反馈系统通过电流求和克服了可扩展性的限制，实现了全互连的3-SAT连接。基于松弛振荡器（RXO）的自旋结合动态CT注入（DaCTI）技术，将解决时间和能源消耗分别提高了和倍，适用于50变量的问题，相比传统的振荡自旋方法有显著提升。通过对20变量和50变量的SATLIB基准测试集中的1000个3-SAT问题进行评估，28纳米CMOS原型分别展示了1.6和31.7微秒的平均解决时间。测量得到的解决能量分别为7.8纳焦和268.9纳焦，且无需任何预处理或后处理。这些结果凸显了Daedalus作为解决NP完全优化问题的可扩展且高效架构的潜力，为大规模基于物理原理的求解器奠定了基础。

引言

组合优化在物流、人工智能、密码学、电子设计自动化（EDA）、医疗保健等多个领域中发挥着关键作用[1]，因此受到了广泛关注。许多组合优化问题（COPs）使用传统计算架构是无法解决的[2]，它们被归类为NP难问题（例如Max-Cut）或非确定性多项式时间完全问题（NP完全问题，例如SAT），这意味着它们不能使用经典算法在多项式时间内得到确定性解决。