Analog Approach to Constraint Satisfaction Enabled by Spin Orbit Torque Magnetic Tunnel Junctions

Area of Science:

• Computational complexity theory
• Materials science
• Hardware-based computing

Background:

• Boolean satisfiability (k-SAT) is a fundamental NP-complete problem, representing a significant challenge in computer science.
• Existing solvers often struggle with the computational demands of large-scale k-SAT instances.
• Constraint satisfaction problems are critical in various fields, including artificial intelligence and operations research.

Purpose of the Study:

• To develop and demonstrate a proof-of-concept hardware-based analog solver for k-SAT problems.
• To leverage the unique physics of Magnetic Tunnel Junctions (MTJs) for solving satisfiability problems.
• To evaluate the performance of an MTJ-based system on hard 3-SAT instances.

Main Methods:

• Utilizing Magnetic Tunnel Junctions (MTJs) as the core component for the analog SAT solver.
• Implementing device-level modifications to MTJs to emulate analog SAT solver dynamics.
• Testing the MTJ-based system's ability to solve Boolean satisfiability problems in the presence of thermal noise.

Main Results:

• The MTJ-based system successfully solves Boolean satisfiability problems.
• The hardware solver achieves an 85% success rate on hard 3-SAT problems.
• The solver operates within a polynomial time complexity concerning the number of variables (for <50 variables).

Conclusions:

• Magnetic Tunnel Junctions offer a viable physical platform for building analog hardware SAT solvers.
• The proposed MTJ-based approach provides an efficient solution for a significant fraction of hard 3-SAT problems.
• This work paves the way for novel hardware acceleration of computationally intensive satisfiability problems.