Energy landscapes of combinatorial optimization in Ising machines

Area of Science:

• Physics
• Computer Science
• Computational Optimization

Background:

• Ising machines (IMs) are specialized processors designed for high-speed, energy-efficient solutions to complex combinatorial optimization problems.
• These systems typically utilize local search heuristics to navigate energy landscapes for optimal solutions.
• Challenges in IM performance are often linked to the inherent complexity of these energy landscapes.

Purpose of the Study:

• To quantify and address major challenges encountered by Ising machines in solving optimization problems.
• To extend energy-landscape visualization tools, specifically disconnectivity graphs, for analyzing problem hardness.
• To investigate the impact of problem embedding on IM performance by examining energy landscape properties.

Main Methods:

• Employed efficient sampling methods to capture energy landscapes of problems with varying structures and hardness.
• Utilized disconnectivity graphs to visualize energetic and entropic barriers affecting IMs.
• Analyzed energy barriers, local minima, and configuration space clustering resulting from locality reduction during problem embedding.
• Sampled disconnectivity graphs for Ising machine energy landscapes, including various Quadratic Unconstrained Binary Optimization (QUBO) mappings and saddle regions.

Main Results:

• Visualized problem energy landscapes, revealing energetic and entropic barriers that pose challenges for Ising machines.
• Identified how embedding combinatorial problems onto Ising hardware, through methods like QUBO mappings, creates energy landscape complexities.
• Demonstrated that specific QUBO energy-landscape properties correlate with subpar performance in quadratic IMs.

Conclusions:

• The geometric properties of QUBO energy landscapes significantly impact the performance of quadratic Ising machines.
• Disconnectivity graphs are effective tools for diagnosing and understanding IM performance limitations.
• Findings suggest avenues for improving Ising machine hardware and problem-embedding strategies for enhanced optimization capabilities.