In this paper, we report new results on a novel Ising machine technology for solving combinatorial optimization problems using networks of coupled self-sustaining oscillators. Specifically, we present several working hardware prototypes using CMOS electronic oscillators, built on bread-boards/perfboards and PCBs, implementing Ising machines consisting of up to 240 spins with programmable couplings. We also report that, just by simulating the differential equations of such Ising machines of larger sizes, good solutions can be achieved easily on benchmark optimization problems, demonstrating the effectiveness of oscillator-based Ising machines.
more »
« less
This content will become publicly available on December 1, 2023
An Ising machine based on networks of subharmonic electrical resonators
Abstract Combinatorial optimization problems are difficult to solve with conventional algorithms. Here we explore networks of nonlinear electronic oscillators evolving dynamically towards the solution to such problems. We show that when driven into subharmonic response, such oscillator networks can minimize the Ising Hamiltonian on non-trivial antiferromagnetically-coupled 3-regular graphs. In this context, the spin-up and spin-down states of the Ising machine are represented by the oscillators’ response at the even or odd driving cycles. Our experimental setting of driven nonlinear oscillators coupled via a programmable switch matrix leads to a unique energy minimizer when one exists, and probes frustration where appropriate. Theoretical modeling of the electronic oscillators and their couplings allows us to accurately reproduce the qualitative features of the experimental results and extends the results to larger graphs. This suggests the promise of this setup as a prototypical one for exploring the capabilities of such an unconventional computing platform.
more »
« less
- NSF-PAR ID:
- 10443184
- Date Published:
- Journal Name:
- Communications Physics
- Volume:
- 5
- Issue:
- 1
- ISSN:
- 2399-3650
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
Modern computers require an exponential increase in resources when solving computationally hard problems, motivating the need for an alternative computing platform to solve such problems in an energy‐efficient manner. Vertex coloring, a nondeterministic polynomial time (NP‐hard) combinatorial optimization problem, is one such problem. Herein, an experimental demonstration of using cardiac cell‐based bio‐oscillator network coupling dynamics to solve a vertex coloring problem in various scales of graphs using a simple cell patterning method to construct scalable and controlled cardiac cell networks is presented. Although there are limitations to using these cardiac cells as oscillators, such as their low frequency compared to complementary metal–oxide–semiconductor (CMOS) oscillators, that result in longer processing times, the accuracy in large graph instances, the significantly less amount of energy consumption, and the ease of fabrication and potential to extend this system to massively parallel 3D structures make the bio‐oscillators a promising new platform for collective computing applications.
-
more » « less
Conventional computing architectures have no known efficient algorithms for combinatorial optimization tasks such as the Ising problem, which requires finding the ground state spin configuration of an arbitrary Ising graph. Physical Ising machines have recently been developed as an alternative to conventional exact and heuristic solvers; however, these machines typically suffer from decreased ground state convergence probability or universality for high edge-density graphs or arbitrary graph weights, respectively. We experimentally demonstrate a proof-of-principle integrated nanophotonic recurrent Ising sampler (INPRIS), using a hybrid scheme combining electronics and silicon-on-insulator photonics, that is capable of converging to the ground state of various four-spin graphs with high probability. The INPRIS results indicate that noise may be used as a resource to speed up the ground state search and to explore larger regions of the phase space, thus allowing one to probe noise-dependent physical observables. Since the recurrent photonic transformation that our machine imparts is a fixed function of the graph problem and therefore compatible with optoelectronic architectures that support GHz clock rates (such as passive or non-volatile photonic circuits that do not require reprogramming at each iteration), this work suggests the potential for future systems that could achieve orders-of-magnitude speedups in exploring the solution space of combinatorially hard problems.
-
more » « less
Abstract Coupled electronic oscillators have recently been explored as a compact, integrated circuit- and room temperature operation-compatible hardware platform to design Ising machines. However, such implementations presently require the injection of an externally generated second-harmonic signal to impose the phase bipartition among the oscillators. In this work, we experimentally demonstrate a new electronic autaptic oscillator (EAO) that uses engineered feedback to eliminate the need for the generation and injection of the external second harmonic signal to minimize the Ising Hamiltonian. Unlike conventional relaxation oscillators that typically decay with a single time constant, the feedback in the EAO is engineered to generate two decay time constants which effectively helps generate the second harmonic signal internally. Using this oscillator design, we show experimentally, that a system of capacitively coupled EAOs exhibits the desired bipartition in the oscillator phases without the need for any external second harmonic injection, and subsequently, demonstrate its application in solving the computationally hard Maximum Cut (MaxCut) problem. Our work not only establishes a new oscillator design aligned to the needs of the oscillator Ising machine but also advances the efforts to creating application specific analog computing platforms.
-
Abstract The modeling of nonlinear dynamical systems subject to strong and evolving nonsmooth nonlinearities is typically approached via integer-order differential equations. In this study, we present the possible application of variable-order (VO) fractional operators to a class of nonlinear lumped parameter models that have great practical relevance in mechanics and dynamics. Fractional operators are intrinsically multiscale operators that can act on both space- and time-dependent variables. Contrarily to their integer-order counterpart, fractional operators can have either fixed or VO. In the latter case, the order can be function of either independent or state variables. We show that when using VO equations to describe the response of dynamical systems, the order can evolve as a function of the response itself; therefore, allowing a natural and seamless transition between widely dissimilar dynamics. Such an intriguing characteristic allows defining governing equations for dynamical systems that are evolutionary in nature. Within this context, we present a physics-driven strategy to define VO operators capable of capturing complex and evolutionary phenomena. Specific examples include hysteresis in discrete oscillators and contact problems. Despite using simplified models to illustrate the applications of VO operators, we show numerical evidence of their unique modeling capabilities as well as their connection to more complex dynamical systems.more » « less
