Medusa: A Scalable Quantum-Inspired k -SAT Solver With Make and Break Feedback
IEEE Journal of Solid-State Circuits · 2026-11 · 61 (11) · 6076-6090
DOI: 10.1109/jssc.2026.3726445 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Journal of Solid-State Circuits, 2026-11. Verfasst von Luke D. Wormald und 7 weiteren Autor:innen. Die Arbeit nennt 50 Literaturangaben. Gefördert von: U.S. Defense Advanced Research Projects Agency (DARPA) under the Quantum-Inspired Classical Computing (QuICC) Program..
Abstract (Originalsprache)
Boolean satisfiability (SAT or $k$ -SAT, $k \ge 3$ ) is a binary combinatorial optimization problem (COP) that is challenging for traditional classical computing to address in polynomial time. Quantum and quantum-inspired systems have been touted to tackle these and similar nondeterministic polynomial-time (NP) problems. This work describes Medusa, a quantum-inspired $k$ -SAT solver capable of addressing problems of up to 200 variables and 1016 clauses. Implemented using analog and mixed-signal circuits, the solver benefits heavily from massive parallelism, continuous-time operation, and excellent energy efficiency, and advances the field of quantum-inspired, analog computing with best-in-class performance and energy efficiency. This performance is achieved with the introduction of three key architectural advancements: dual Make and Break feedback, a distributed logic feedback network, and multi-macro operation. The dual feedback mechanism improves the mean time to solution (TTS) for 50-variable 3-SAT problems by $30\times $ when compared with a single feedback mechanism. The distributed logic in the feedback network implements all-to-all spin connectivity with arbitrary order interactions, enabling $k$ -SAT operation and supporting the scalability of the solver, which is further enhanced by multi-macro operation. Medusa, implemented in a 28 nm process, achieves a $4.92~\mu $ s TTS for the popular SATLIB uf50-218 benchmark with a mean energy to solution (ETS) of 19.1 nJ. For the uf200-860 benchmark the solver achieves a 30.9 ms mean TTS, outperforming quantum annealing for problems of the same size.
Förderung
- U.S. Defense Advanced Research Projects Agency (DARPA) under the Quantum-Inspired Classical Computing (QuICC) Program.
Zitieren
APA
Wormald, L. D., Hsu, Y., Dikopoulos, E., Tang, W., Datsko, B., Hammoud, A., Zhang, Z., & Flynn, M. P. (2026). Medusa: A Scalable Quantum-Inspired k -SAT Solver With Make and Break Feedback. IEEE Journal of Solid-State Circuits, 61(11), 6076-6090. https://doi.org/10.1109/jssc.2026.3726445
Vancouver
Wormald LD, Hsu Y, Dikopoulos E, Tang W, Datsko B, Hammoud A, et al. Medusa: A Scalable Quantum-Inspired k -SAT Solver With Make and Break Feedback. IEEE Journal of Solid-State Circuits. 2026;61(11):6076-6090. doi:10.1109/jssc.2026.3726445
BibTeX
@article{Wormald2026,
author = {Wormald, Luke D. and Hsu, Ying-Tuan and Dikopoulos, Evangelos and Tang, Wei and Datsko, Benjamin and Hammoud, Ali and Zhang, Zhengya and Flynn, Michael P.},
title = {Medusa: A Scalable Quantum-Inspired k -SAT Solver With Make and Break Feedback},
journal = {IEEE Journal of Solid-State Circuits},
year = {2026},
volume = {61},
number = {11},
pages = {6076--6090},
doi = {10.1109/jssc.2026.3726445}
}
EUVIMED