More Like this

1. Efficient optimization with higher-order ising machines

   https://doi.org/10.1038/s41467-023-41214-9  

   Bybee, Connor; Kleyko, Denis; Nikonov, Dmitri E.; Khosrowshahi, Amir; Olshausen, Bruno A.; Sommer, Friedrich T. (December 2023, Nature Communications)

   Abstract A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Booleank-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines. 

   more » « less
2. Stochastic logic in biased coupled photonic probabilistic bits

   https://doi.org/10.1038/s42005-025-01953-1  

   Horodynski, Michael; Roques-Carmes, Charles; Salamin, Yannick; Choi, Seou; Sloan, Jamison; Luo, Di; Soljačić, Marin (January 2025, Communications Physics)

   Abstract Optical computing often employs tailor-made hardware to implement specific algorithms, trading generality for improved performance in key aspects like speed and power efficiency. An important computing approach that is still missing its corresponding optical hardware is probabilistic computing, used e.g. for solving difficult combinatorial optimization problems. In this study, we propose an experimentally viable photonic approach to solve arbitrary probabilistic computing problems. Our method relies on the insight that coherent Ising machines composed of coupled and biased optical parametric oscillators can emulate stochastic logic. We demonstrate the feasibility of our approach by using numerical simulations equivalent to the full density matrix formulation of coupled optical parametric oscillators. 

   more » « less
3. A note on analyzing the stability of oscillator Ising machines

   https://doi.org/10.1049/ell2.13054  

   Bashar, Mohammad_Khairul; Lin, Zongli; Shukla, Nikhil (December 2023, Electronics Letters)

   Abstract The rich non‐linear dynamics of the coupled oscillators (under second harmonic injection) can be leveraged to solve computationally hard problems in combinatorial optimization such as finding the ground state of the Ising Hamiltonian. While prior work on the stability of the so‐called Oscillator Ising Machines (OIMs) has used the linearization method, in this letter, the authors present a complementary method to analyze stability using the second‐order derivative test of the energy/cost function. The authors establish the equivalence between the two methods, thus augmenting the tool kit for the design and implementation of OIMs. 

   more » « less
4. Stability of oscillator Ising machines: Not all solutions are created equal

   https://doi.org/10.1063/5.0157107  

   Bashar, Mohammad Khairul; Lin, Zongli; Shukla, Nikhil (October 2023, Journal of Applied Physics)

   Nonlinear dynamical systems such as coupled oscillators are being actively investigated as Ising machines for solving computationally hard problems in combinatorial optimization. Prior works have established the equivalence between the global minima of the cost function describing the coupled oscillator system and the ground state of the Ising Hamiltonian. However, the properties of the oscillator Ising machine (OIM) from a nonlinear control viewpoint, such as the stability of the OIM solutions, remain unexplored. Therefore, in this work, using nonlinear control-theoretic analysis, we (i) identify the conditions required to ensure the functionality of the coupled oscillators as an Ising machine, (ii) show that all globally optimal phase configurations may not always be stable, resulting in some configurations being more favored over others and, thus, creating a biased OIM, and (iii) elucidate the impact of the stability of locally optimal phase configurations on the quality of the solution computed by the system. Our work, fostered through the unique convergence between nonlinear control theory and analog systems for computing, provides a new toolbox for the design and implementation of dynamical system-based computing platforms. 

   more » « less
5. Augmenting an electronic Ising machine to effectively solve boolean satisfiability

   https://doi.org/10.1038/s41598-023-49966-6  

   Sharma, Anshujit; Burns, Matthew; Hahn, Andrew; Huang, Michael (December 2023, Scientific Reports)

   Abstract With the slowdown of improvement in conventional von Neumann systems, increasing attention is paid to novel paradigms such as Ising machines. They have very different approach to solving combinatorial optimization problems. Ising machines have shown great potential in solving binary optimization problems like MaxCut. In this paper, we present an analysis of these systems in boolean satisfiability (SAT) problems. We demonstrate that, in the case of 3-SAT, a basic architecture fails to produce meaningful acceleration, largely due to the relentless progress made in conventional SAT solvers. Nevertheless, careful analysis attributes part of the failure to the lack of two important components: cubic interactions and efficient randomization heuristics. To overcome these limitations, we add proper architectural support for cubic interaction on a state-of-the-art Ising machine. More importantly, we propose a novel semantic-aware annealing schedule that makes the search-space navigation much more efficient than existing annealing heuristics. Using numerical simulations, we show that such an “Augmented” Ising Machine for SAT is projected to outperform state-of-the-art software-based, GPU-based and conventional hardware SAT solvers by orders of magnitude. 

   more » « less