Ising Machines: Theory and Practice

Naomi Sagan and Jaijeet Roychowdhury

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2023-138
May 12, 2023

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-138.pdf

Ising machines have generated much excitement in recent years due to their promise for solving the Ising problem, a graph-based hard combinatorial optimization problem. In particular, Oscillator-based Ising Machines (OIMs), which consist of resistively-coupled nonlinear oscillators, are a promising on-chip iteration of Ising Machines. The system dynamics, represented as differential equations in oscillator phase, admit a Lyapunov function, i.e., a function with a non-positive time derivative. This Lyapunov function, at stable equilibria, matches the Ising Hamiltonian, the discrete cost function of the Ising problem. However, there are both practical barriers to large-scale on-chip implementation and many unanswered fundamental theoretical questions.

First, achieving physical all-to-all connectivity in integrated circuit (IC) implementations of large, densely-connected Ising machines remains a key challenge. We present a novel approach, DaS, that uses low-rank decomposition to achieve effectively-dense Ising connectivity using only sparsely interconnected hardware. The innovation consists of two components. First, we use the SVD to find a low-rank approximation of the Ising coupling matrix while maintaining very high accuracy. This decomposition requires substantially fewer nonzeros to represent the dense Ising coupling matrix. Second, we develop a method to translate the low-rank decomposition to a hardware implementation that uses only sparse resistive interconnections. We validate DaS on the MU-MIMO detection problem, important in modern telecommunications. Our results indicate that as problem sizes scale, DaS can achieve dense Ising coupling using only 5%-20% of the resistors needed for brute-force dense connections (which would be physically infeasible in ICs). we also show the impact of this sparsification on achieved minimization using simulated annealing, a widely-used Ising solver. We achieve nearly 90% sparsity without degrading solution quality at all, even with loose thresholds on the approximation error of the sparsification process.

Second, it is not well-understood why OIMs perform well on certain problems and don’t get stuck in local minima. In particular, parameter cycling, i.e., gradually increasing the value of a particular OIM parameter over during the solution process, can help the system reach global minima. Past work on Ising machines indicates that traversal of bifurcations, or points where the number of solutions to a system changes, is essential to their Hamiltonian minimization properties. We explore bifurcations for OIMs with two or three oscillators, both analytically and using numerical methods. In addition, we draw connections between the landscape of the Lyapunov function and the potential of OIMs to find global Ising Hamiltonian minima, using a combination of theoretical analysis, numerical simulation, and Monte Carlo methods.

Advisor: Jaijeet Roychowdhury


BibTeX citation:

@mastersthesis{Sagan:EECS-2023-138,
    Author = {Sagan, Naomi and Roychowdhury, Jaijeet},
    Title = {Ising Machines: Theory and Practice},
    School = {EECS Department, University of California, Berkeley},
    Year = {2023},
    Month = {May},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-138.html},
    Number = {UCB/EECS-2023-138},
    Abstract = {Ising machines have generated much excitement in recent years due to their promise for solving the Ising problem, a graph-based hard combinatorial optimization problem. In particular, Oscillator-based Ising Machines (OIMs), which consist of resistively-coupled nonlinear oscillators, are a promising on-chip iteration of Ising Machines. The system dynamics, represented as differential equations in oscillator phase, admit a Lyapunov function, i.e., a function with a non-positive time derivative. This Lyapunov function, at stable equilibria, matches the Ising Hamiltonian, the discrete cost function of the Ising problem. However, there are both practical barriers to large-scale on-chip implementation and many unanswered fundamental theoretical questions.

First, achieving physical all-to-all connectivity in integrated circuit (IC) implementations of large, densely-connected Ising machines remains a key challenge. We present a novel approach, DaS, that uses low-rank decomposition to achieve effectively-dense Ising connectivity using only sparsely interconnected hardware. The innovation consists of two components. First, we use the SVD to find a low-rank approximation of the Ising coupling matrix while maintaining very high accuracy. This decomposition requires substantially fewer nonzeros to represent the dense Ising coupling matrix. Second, we develop a method to translate the low-rank decomposition to a hardware implementation that uses only sparse resistive interconnections. We validate DaS on the MU-MIMO detection problem, important in modern telecommunications. Our results indicate that as problem sizes scale, DaS can achieve dense Ising coupling using only 5%-20% of the resistors needed for brute-force dense connections (which would be physically infeasible in ICs). we also show the impact of this sparsification on achieved minimization using simulated annealing, a widely-used Ising solver. We achieve nearly 90% sparsity without degrading solution quality at all, even with loose thresholds on the approximation error of the sparsification process.

Second, it is not well-understood why OIMs perform well on certain problems and don’t get stuck in local minima. In particular, parameter cycling, i.e., gradually increasing the value of a particular OIM parameter over during the solution process, can help the system reach global minima. Past work on Ising machines indicates that traversal of bifurcations, or points where the number of solutions to a system changes, is essential to their Hamiltonian minimization properties. We explore bifurcations for OIMs with two or three oscillators, both analytically and using numerical methods. In addition, we draw connections between the landscape of the Lyapunov function and the potential of OIMs to find global Ising Hamiltonian minima, using a combination of theoretical analysis, numerical simulation, and Monte Carlo methods.}
}

EndNote citation:

%0 Thesis
%A Sagan, Naomi
%A Roychowdhury, Jaijeet
%T Ising Machines: Theory and Practice
%I EECS Department, University of California, Berkeley
%D 2023
%8 May 12
%@ UCB/EECS-2023-138
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2023/EECS-2023-138.html
%F Sagan:EECS-2023-138