Adaptive Confidence Neural Logic Machines

Quantum annealing offers a promising approach to Boolean satisfiability (SAT); however, existing encodings frequently require large numbers of qubits and produce energy landscapes with narrow spectral gaps, increasing susceptibility to spurious minima. This work introduces Adaptive Confidence Neural Logic Machines (AdaptCNLM), a neural-symbolic framework designed to jointly reduce the representation size of SAT instances and enhance the resulting optimization landscape. AdaptCNLM initially employs neural structural-equivalence encoding (NSEE), a label-free graph neural network that identifies and aggregates structurally equivalent variables while provably preserving satisfying assignments within the induced subcube. Subsequently, dual-confidence scaling is applied, integrating structural and search-derived signals to recover information lost during aggregation and to guide the search toward satisfying assignments. Across five quantum-annealing encodings, NSEE significantly reduces qubit requirements and achieves the highest solve rate with fewer logical qubits. As a complete SAT solver, AdaptCNLM surpasses 16 data-driven and non-data-driven baselines across six SATLIB benchmark families. These findings indicate that learned structural compression, combined with confidence-guided search, enhances both resource efficiency and solving performance in quantum-annealing-based SAT.