Efficient optimization accelerator framework for multi-state spin Ising problems.

Area of Science:

• Computational physics and computer engineering.
• Development of novel algorithms for optimization problems.

Background:

• Ising Machines are hardware designed for combinatorial optimization.
• Current methods often transform problems into Quadratic Unconstrained Binary Optimization (QUBO) form, which can complicate solutions.
• This complexity particularly affects multi-state problems, degrading performance.

Purpose of the Study:

• To develop a novel approach for Ising Machines that reduces the solution exploration space.
• To improve the efficiency and accuracy of solving multi-state optimization problems.
• To demonstrate the effectiveness of the proposed method on the graph coloring problem.

Main Methods:

• Modeling spin interactions as generalized boolean logic functions.
• Utilizing probabilistic Ising solvers to test the approach.
• Implementing a 1024-neuron all-to-all connected probabilistic Ising accelerator on FPGA.

Main Results:

• Achieved accuracy comparable to state-of-the-art heuristics and machine learning algorithms for graph coloring.
• Demonstrated significant performance improvement over existing QUBO-based Ising solvers.
• The FPGA accelerator showed ~10000x performance acceleration compared to GPU-based heuristics.
• Reduced physical neuron requirements by 1.5-4x compared to baseline Ising frameworks.

Conclusions:

• The proposed generalized boolean logic modeling offers superior efficiency and scalability for multi-state optimization problems.
• This method enhances solution quality and reduces hardware requirements.
• Establishes a new benchmark for performance in Ising Machine applications.