Spintronics-compatible approach to solving maximum satisfiability problems with probabilistic computing, invertible logic and parallel tempering

Abstract

The search of hardware-compatible strategies for solving NP-hard combinatorial optimization problems (COPs) is an important challenge of today s computing research because of their wide range of applications in real world optimization problems. Here, we introduce an unconventional scalable approach to face maximum satisfiability problems (Max-SAT) which combines probabilistic computing with p-bits, parallel tempering, and the concept of invertible logic gates. We theoretically show the spintronic implementation of this approach based on a coupled set of Landau-Lifshitz-Gilbert equations, showing a potential path for energy efficient and very fast (p-bits exhibiting ns time scale switching) architecture for the solution of COPs. The algorithm is benchmarked with hard Max-SAT instances from the 2016 Max-SAT competition (e.g., HG-4SAT-V150-C1350-1.cnf which can be described with 2851 p-bits), including weighted Max-SAT and Max-Cut problems.

arXiv comment7 Figures, 20 pages

References in corpus (15)

• Ising formulations of many NP problems
• Parallel Tempering: Theory, Applications, and New Perspectives
• Quantum Annealing: A New Method for Minimizing Multidimensional Functions
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Stochastic p-bits for Invertible Logic
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Demonstration of nanosecond operation in stochastic magnetic tunnel junctions
• Low Barrier Nanomagnets as p-bits for Spin Logic
• Polynomial-time solution of prime factorization and NP-hard problems with digital memcomputing machines
• Micromagnetic understanding of stochastic resonance driven by spin-transfertorque
• Spin-orbit torque based physical unclonable function
• Hardware Design for Autonomous Bayesian Networks
• Analog Coupled Oscillator Based Weighted Ising Machine
• Memcomputing for Accelerated Optimization
• A high-performance analog Max-SAT solver and its application to Ramsey numbers

Cited by in corpus (14)

• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
• Efficient Probabilistic Computing with Stochastic Perovskite Nickelates
• Evaluating spintronics-compatible implementations of Ising machines
• Integrated probabilistic computer using voltage-controlled magnetic tunnel junctions as its entropy source
• Enhanced Convergence in p-bit Based Simulated Annealing with Partial Deactivation for Large-Scale Combinatorial Optimization Problems
• Physics-inspired Ising Computing with Ring Oscillator Activated p-bits
• Voltage-insensitive stochastic magnetic tunnel junctions with double free layers
• Pushing the Boundary of Quantum Advantage in Hard Combinatorial Optimization with Probabilistic Computers
• GPU-accelerated simulated annealing based on p-bits with real-world device-variability modeling
• The First Hardware Demonstration of a Universal Programmable RRAM-based Probabilistic Computer for Molecular Docking
• In-plane dominant anisotropy stochastic magnetic tunnel junction for probabilistic computing: A Fokker-Planck study
• Metrics for spin-based computing
• Ground-State Probabilistic Logic with the Simplest Binary Energy Landscape for Probabilistic Computing