Daedalus: A Physics-Inspired Mixed-Signal Optimization Engine With Dynamic Continuous-Time Injection for Solving 3-SAT Problems

Abstract

Nondeterministic polynomial-time complete (NP- complete) combinatorial optimization problems (COPs), such as Boolean satisfiability (SAT), are intractable on classical com- puting architectures, often resulting in exponential scaling of solution time and energy as the problem size increases. Inspired by natural physical interactions, physics-inspired computers harness the continuous-time (CT) dynamics of coupled spins, massive parallelism, and analog computation to accelerate solving COPs. This work advances the field by introducing Daedalus, a massively parallel oscillator-based direct 3-SAT engine that leverages physics-inspired heuristics within a mixed-signal com- pute fabric and achieves state-of-the-art solution time and energy efficiency. We present a CT dynamical system with three-body spin interactions and non-linear spin coupling to enable rapid convergence to ground states. A scalable mixed-signal crossbar- based feedback system employs current summation to overcome scalability limits and enable all-to-all 3-SAT connectivity. Relax- ation oscillator (RXO)-based spins with dynamic CT injection (DaCTI) improve solution time and energy by 6 × and 8.4×, respectively, for 50-variable problems, compared to conventional oscillating spins. Evaluated with 1000 3-SAT problems from both the 20- and 50-variable SATLIB benchmark, the 28-nm CMOS prototype demonstrates a mean solution time of 1.6 and 31.7 µs, respectively. The measured solution energy is 7.8 and 268.9 nJ, without req