Memristor-based Ising machine for efficient combinatorial optimization

Abstract

Combinatorial optimization problems (COPs) are ubiquitous in science and engineering but pose formidable computational challenges due to their non-deterministic polynomial-time hard (NP-hard) complexity. Conventional digital computers, constrained by the slowing of Moore's Law and the energy-intensive Von Neumann bottleneck associated with data movement, struggle to solve large-scale COPs efficiently. While specialized accelerators like quantum annealers offer potential speedups, they demand extreme cryogenic conditions and have limited connectivity. Other approaches, such as optical systems or oscillator-based systems, still face fundamental efficiency limitations or practical complexities. This thesis explores an alternative path, investigating analog computing paradigms based on memristive devices to realize energy-efficient, high-performance hardware accelerators. Leveraging the unique physical properties of memristor crossbars, all-to-all connectivity, analog programmability, non-volatility, high density, and CMOS compatibility, this work develops and scales memristor-based Ising machines dedicated to efficiently solve COPs.

The core contributions of this thesis include: (1) The development and experimental validation of quantum-inspired parallel annealing (QPA), a novel optimization heuristic tailored for memristor crossbars. QPA exploits hardware parallelism and analog programmability, demonstrating superior performance and scaling compared to traditional serial methods on benchmark COPs. (2) The design and prototyping of a fully analog continuous-time Ising machine (CTIM), where the Ising Hamiltonian is directly mapped onto the continuous physical dynamics of interconnected memristors and amplifiers, enabling optimization via a single transient evolution, enhanced by a continuous-time annealing protocol. (3) The scaling of the CTIM through the fabrication of a 96-spin integrated chip featuring a hardware-efficient annealing mechanism. (4) The introduction of a hybrid multilevel solving framework that combines algorithmic graph coarsening/refinement with the integrated CTIM chip as a fast analog subproblem solver, enabling efficient solving of large-scale problems that exceed physical hardware size.

Collectively, the research in this thesis significantly advances memristor-based optimization hardware. By integrating physics-based computing concepts and proper algorithm-hardware co-design, this work establishes analog memristor systems as a compelling platform for tackling complex optimization challenges.