Simulated bifurcation for higher-order cost functions

Abstract

High-performance Ising machines for solving combinatorial optimization problems have been developed with digital processors implementing heuristic algorithms such as simulated bifurcation (SB). Although Ising machines have been designed for second-order cost functions, there are practical problems expressed naturally by higher-order cost functions. In this work, we extend SB to such higher-order cost functions. By solving a problem having third-order cost functions, we show that the higher-order SB can outperform not only the second-order SB with additional spin variables, but also simulated annealing applied directly to the third-order cost functions. This result suggests that the higher-order SB can be practically useful.

arXiv comment4 pages, 2 figures, 1 table

References in corpus (14)

• Ising formulations of many NP problems
• Quantum Annealing in the Transverse Ising Model
• Network of Time-Multiplexed Optical Parametric Oscillators as a Coherent Ising Machine
• Physics-Inspired Optimization for Quadratic Unconstrained Problems Using a Digital Annealer
• Bifurcation-based adiabatic quantum computation with a nonlinear oscillator network: Toward quantum soft computing
• Quantum annealing with a network of all-to-all connected, two-photon driven Kerr nonlinear oscillators
• Optimized simulated annealing for Ising spin glasses
• Quantum Computation Based on Quantum Adiabatic Bifurcations of Kerr-Nonlinear Parametric Oscillators
• Benchmark of quantum-inspired heuristic solvers for quadratic unconstrained binary optimization
• 3-Regular 3-XORSAT Planted Solutions Benchmark of Classical and Quantum Heuristic Optimizers
• High-accuracy Ising machine using Kerr-nonlinear parametric oscillators with local four-body interactions
• Simulated bifurcation assisted by thermal fluctuation
• Equation Planting: A Tool for Benchmarking Ising Machines
• How we are leading a 3-XORSAT challenge: from the energy landscape to the algorithm and its efficient implementation on GPUs

Cited by in corpus (11)

• All-to-all reconfigurability with sparse and higher-order Ising machines
• Real-time Trading System based on Selections of Potentially Profitable, Uncorrelated, and Balanced Stocks by NP-hard Combinatorial Optimization
• Correlation-diversified portfolio construction by finding maximum independent set in large-scale market graph
• Pairs-trading System using Quantum-inspired Combinatorial Optimization Accelerator for Optimal Path Search in Market Graphs
• Annealing for prediction of grand canonical crystal structures: Efficient implementation of n-body atomic interactions
• General Oscillator-Based Ising Machine Models with Phase-Amplitude Dynamics and Polynomial Interactions
• Edge-of-chaos enhanced quantum-inspired algorithm for combinatorial optimization
• Enhancing In-vehicle Multiple Object Tracking Systems with Embeddable Ising Machines
• Tensor networks for $p$-spin models
• Machine Learning-assisted High-speed Combinatorial Optimization with Ising Machines for Dynamically Changing Problems
• Recent quantum runtime (dis)advantages