Order-of-magnitude differences in computational performance of analog Ising machines induced by the choice of nonlinearity

Abstract

Ising machines based on nonlinear analog systems are a promising method to accelerate computation of NP-hard optimization problems. Yet, their analog nature is also causing amplitude inhomogeneity which can deteriorate the ability to find optimal solutions. Here, we investigate how the system's nonlinear transfer function can mitigate amplitude inhomogeneity and improve computational performance. By simulating Ising machines with polynomial, periodic, sigmoid and clipped transfer functions and benchmarking them with MaxCut optimization problems, we find the choice of transfer function to have a significant influence on the calculation time and solution quality. For periodic, sigmoid and clipped transfer functions, we report order-of-magnitude improvements in the time-to-solution compared to conventional polynomial models, which we link to the suppression of amplitude inhomogeneity induced by saturation of the transfer function. This provides insights into the suitability of systems for building Ising machines and presents an efficient way for overcoming performance limitations.

References in corpus (19)

• Ising formulations of many NP problems
• Digitized adiabatic quantum computing with a superconducting circuit
• A mathematical framework for critical transitions: bifurcations, fast-slow systems and stochastic dynamics
• A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
• Large-scale photonic Ising machine by spatial light modulation
• Reprogrammable Electro-Optic Nonlinear Activation Functions for Optical Neural Networks
• Realizing the $XY$ Hamiltonian in polariton simulators
• Large-scale Ising spin network based on degenerate optical parametric oscillators
• Digital quantum simulation of spin models with circuit quantum electrodynamics
• Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity
• Heuristic Recurrent Algorithms for Photonic Ising Machines
• Nanophotonic spin-glass for realization of a coherent Ising machine
• Annealing by simulating the coherent Ising machine
• Noise-enhanced spatial-photonic Ising machine
• High-accuracy Ising machine using Kerr-nonlinear parametric oscillators with local four-body interactions
• A Quantum Model for Coherent Ising Machine: Stochastic Differential Equations with Replicator Dynamics
• Controlled Online Optimization Learning (COOL): Finding the ground state of spin Hamiltonians with reinforcement learning
• Scaling advantage of nonrelaxational dynamics for high-performance combinatorial optimization
• Complexity continuum within Ising formulation of NP problems

Cited by in corpus (11)

• Combinatorial optimization solving by coherent Ising machines based on spiking neural networks
• Using continuation methods to analyse the difficulty of problems solved by Ising machines
• Analogue Spin Simulators: How to keep the Amplitude Homogeneous
• Edge-of-chaos enhanced quantum-inspired algorithm for combinatorial optimization
• Non-binary dynamical Ising machines for combinatorial optimization
• Requirements on bit resolution in optical Ising machine implementations
• Enhancing In-vehicle Multiple Object Tracking Systems with Embeddable Ising Machines
• Noise-injected analog Ising machines enable ultrafast statistical sampling and machine learning
• Minor embedding with Stuart-Landau oscillator networks
• Machine Learning-assisted High-speed Combinatorial Optimization with Ising Machines for Dynamically Changing Problems
• Limitations in Parallel Ising Machine Networks: Theory and Practice