Edge-of-chaos enhanced quantum-inspired algorithm for combinatorial optimization

Abstract

Nonlinear dynamical systems with continuous variables can be used for solving combinatorial optimization problems with discrete variables. Numerical simulations of them are also useful as heuristic algorithms with a desirable property, namely, parallelizability, which allows us to execute them in a massively parallel manner, leading to ultrafast performance. However, the dynamical-system approaches with continuous variables are usually less accurate than conventional approaches with discrete variables such as simulated annealing. To improve the solution accuracy of a quantum-inspired algorithm called simulated bifurcation (SB), which was found from classical simulation of a quantum nonlinear oscillator network exhibiting quantum bifurcation, here we generalize it by introducing nonlinear control of individual bifurcation parameters and show that the generalized SB (GSB) can achieve surprisingly high performance, namely, almost 100% success probabilities for some large-scale problems. As a result, the time to solution for a 2,000-variable problem is shortened to 10 ms by a GSB-based machine, which is two orders of magnitude shorter than the best known value, 1.3 s, previously obtained by an SB-based machine. To examine the reason for the ultrahigh performance, we investigated chaos in the GSB changing the nonlinear-control strength and found that the dramatic increase of success probabilities happens near the edge of chaos. That is, the GSB can find a solution with high probability by harnessing the edge of chaos. This finding suggests that dynamical-system approaches to combinatorial optimization will be enhanced by harnessing the edge of chaos, opening a broad possibility for physics-inspired approaches to combinatorial optimization.

15 pages, 5 figures, 3 tables

References in corpus (20)

• Ising formulations of many NP problems
• Network of Time-Multiplexed Optical Parametric Oscillators as a Coherent Ising Machine
• A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
• Engineering the quantum states of light in a Kerr-nonlinear resonator by two-photon driving
• Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network: Toward quantum soft computing
• Massively Parallel Probabilistic Computing with Sparse Ising Machines
• Quantum annealing with a network of all-to-all connected, two-photon driven Kerr nonlinear oscillators
• Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity
• Universal quantum computation with a nonlinear oscillator network
• Quantum Computation Based on Quantum Adiabatic Bifurcations of Kerr-Nonlinear Parametric Oscillators
• Annealing by simulating the coherent Ising machine
• Roadmap for Unconventional Computing with Nanotechnology
• Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
• Dissipative quantum bifurcation machine: Quantum heating of coupled nonlinear oscillators
• Order-of-magnitude differences in computational performance of analog Ising machines induced by the choice of nonlinearity
• High-accuracy Ising machine using Kerr-nonlinear parametric oscillators with local four-body interactions
• Evaluating spintronics-compatible implementations of Ising machines
• Simulated bifurcation for higher-order cost functions
• Taming a non-convex landscape with dynamical long-range order: memcomputing Ising benchmarks
• Efficient and Scalable Architecture for Multiple-chip Implementation of Simulated Bifurcation Machines