Phase Transition Oscillators Based Ising Machines for Combinatorial Optimization Problem Solvers

Combinatorial optimization problems have immense real-world application including financial portfolio optimization, bio-informatics, drug discovery, cryptography, operations research, resource allocation, satellite-based target tracking, trajectory and route planning. However, many of these problems are classified as non-deterministic polynomial time (NP)-hard or NP-complete, implying that the resources needed to solve the problem grow exponentially as the problem size grows. Many of these issues can be translated into another physics problem: determining the ground state of an Ising model. For a realistic problem size of a few hundred spins, exact algorithms like branch-and-bound can take an inordinate amount of time to reach a guaranteed ground state of the Ising model.

Building Ising Hamiltonian solvers utilizing physical systems called Ising machines is an interesting new area of research that promises to provide results considerably faster than an iterative algorithm operating on a digital computer. Various proposals for building such special purpose Ising machines have recently been made, including superconducting qubits and trapped ions-based quantum computing and quantum annealing digital and mixed-signal complementary metal-oxide-semiconductor (CMOS) annealers and coherent networks of degenerate optical parametric oscillators. The important concept is to depict the Ising Hamiltonian as the system's "energy," allowing it to naturally progress towards the Ising ground state. In this vein of developing special-purpose solvers or accelerators for solving computationally difficult problems, one promising path is to apply the concept of dynamical systems theory, specifically continuous-time dynamical systems (CTDS).. Because of the inherent distributed nature and parallel processing capability, dynamical systems can find the ground state or near-optimum solution with immense speed-up compared to a sequentially working digital computer. In this work, we describe and demonstrate an electronic phase transition nano-oscillator (PTNO) based CTDS that acts as an Ising Hamiltonian solver using a network of injection-locked coupled oscillators. The novel hardware implementation of the oscillator network using ultra-low power and compact one-transistor and one-resistor (1T-1R) PTNOs allows us to harness the intrinsic stochasticity in the phase-transition device VO2, hence traversing complex energy landscapes and escaping local minima to reach an optimum solution.