美杜莎：一种带有建立与破坏反馈机制的可扩展量子启发k-SAT求解器

《IEEE Journal of Solid-State Circuits》：Medusa: A Scalable Quantum-Inspired k-SAT Solver With Make and Break Feedback

　　摘要：布尔可满足性问题（SAT 或 k-SAT，k≥3）是一个二进制组合优化问题（COP），传统经典计算难以在多项式时间内解决。量子系统和量子启发系统被宣称可以解决这些及类似的非确定性多项式时间（NP）问题。本工作介绍了 Medusa，这是一种量子启发式的 k-SAT 求解器，能够处理多达 200 个变量和 1016 个条款的问题。该求解器采用模拟和混合信号电路实现，得益于大规模并行性、连续时间操作和卓越的能效，并以业界领先的性能和能效推进了量子启发式模拟计算领域的发展。这一性能是通过引入三项关键架构改进实现的：双重 Make 和 Break 反馈、分布式逻辑反馈网络以及多宏操作。与单一反馈机制相比，双重反馈机制将 50 变量 3-SAT 问题的平均求解时间（TTS）改善了 30 倍。反馈网络中的分布式逻辑实现了具有任意阶相互作用的自旋全互连，从而实现 k-SAT 操作并支持求解器的可扩展性，这一特性通过多宏操作得到进一步增强。采用 28 nm 工艺实现的 Medusa，在流行的 SATLIB uf50-218 基准测试中实现了 4.92 微秒的 TTS，平均求解能耗（ETS）为 19.1 纳焦。对于 uf200-860 基准测试，该求解器实现了 30.9 毫秒的平均 TTS，在同等规模问题上优于量子退火。