A coherent Ising machine for MAX-CUT problems : Performance evaluation against semidefinite programming relaxation and simulated annealing

Abstract

Combinatorial optimization problems are computationally hard in general, but they are ubiquitous in our modern life. A coherent Ising machine (CIM) based on a multiple-pulse degenerate optical parametric oscillator (DOPO) is an alternative approach to solve these problems by a specialized physical computing system. To evaluate its potential performance, computational experiments are performed on maximum cut (MAX-CUT) problems against traditional algorithms such as semidefinite programming relaxation of Goemans-Williamson and simulated annealing by Kirkpatrick, et al. The numerical results empirically suggest that the almost constant computation time is required to obtain the reasonably accurate solutions of MAX-CUT problems on a CIM with the number of vertices up to $2\times 10^4$ and the number of edges up to $10^8$.

10 pages, 9 figures; v5: typo in Table 1 (C_best of g22 is 0.9450)

References in corpus (3)

• Network of Time-Multiplexed Optical Parametric Oscillators as a Coherent Ising Machine
• A Coherent Ising Machine Based On Degenerate Optical Parametric Oscillators
• Decoherence induced deformation of the ground state in adiabatic quantum computation

Cited by in corpus (10)

• Large-scale Ising spin network based on degenerate optical parametric oscillators
• Combinatorial Optimization with Physics-Inspired Graph Neural Networks
• Demonstration of nanosecond operation in stochastic magnetic tunnel junctions
• Collective and synchronous dynamics of photonic spiking neurons
• Large-scale Ising Emulation with Four-Body Interaction and All-to-All Connection
• Gaussian Optical Ising Machines
• Evaluating Ising Processing Units with Integer Programming
• Analog Coupled Oscillator Based Weighted Ising Machine
• Uplink MIMO Detection using Ising Machines: A Multi-Stage Ising Approach
• Highly Versatile FPGA-Implemented Cyber Coherent Ising Machine