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$.
Introduction
Many real-world challenges, ranging from drug discovery to circuit design, are fundamentally combinatorial optimization problems: finding the optimal arrangement of discrete variables. A quintessential example is the MAX-CUT problem, which involves partitioning a graph's vertices into two sets to maximize the total weight of the edges between them.
Because MAX-CUT is NP-hard, classical computers struggle as the problem size ($N$) grows. Standard approaches typically require exponential time for exact solutions or rely on heuristics like Simulated Annealing (SA) and mathematical relaxations like the Goemans-Williamson (GW) algorithm. This research investigates whether a specialized physical system—the Coherent Ising Machine (CIM)—can overcome the scaling bottlenecks inherent in these classical methods.
Methods
The researchers utilized a CIM architecture based on a network of Degenerate Optical Parametric Oscillators (DOPO). In this system, short pulses of light circulating in a fiber ring resonator represent "spins" (up or down), determined by the phase of the light.
The Ising Hamiltonian, which mathematically describes the optimization problem, is mapped onto the total loss rate of the optical network. The computation leverages the "minimum loss" principle: the physical system naturally settles into the state requiring the least gain to overcome loss, which corresponds to the optimal solution. To evaluate performance, the authors simulated the quantum noise and nonlinear dynamics of the DOPO pulses using c-number stochastic differential equations (CSDE) on a classical computing cluster.
Key Results and Scaling
The CIM was benchmarked against the G-set (a library of 71 hard MAX-CUT instances) and large Complete Graphs ($K_N$) with up to 20,000 vertices and $10^8$ edges.
- Accuracy: On the G-set, the CIM achieved an average approximation ratio of 0.94148, outperforming the GW algorithm (0.93025) and remaining competitive with SA (0.94692). It found superior solutions to GW in 69 out of 71 instances.
- Speed and Scaling: For complete graphs, the CIM demonstrated near-constant time scaling ($O(1)$). While classical algorithms like GW scale at $O(N^{3.5})$ and SA at $O(N^2)$, the CIM's computation time is primarily limited by the "turn-on delay" of the optical oscillation, which remains relatively flat as $N$ increases.
As shown in the performance comparison, the CIM reaches target energy levels significantly faster than classical counterparts. For a problem with 20,000 vertices, the CIM reached target accuracy in approximately 0.5 milliseconds (estimated physical time), whereas classical algorithms required orders of magnitude more time to achieve comparable results.
Discussion and Future Work
While the simulations demonstrate remarkable potential, physical implementation at the scale of $N = 10^6$ presents hardware challenges, such as the need for 20 GHz pulse repetition frequencies and long fiber loops. Additionally, for massive graphs, the time required to load the problem matrix (I/O) may eventually exceed the actual computation time.
Despite being a heuristic solver that does not guarantee a global optimum for every instance, the CIM consistently provides high-quality approximations with unprecedented speed. Future research will focus on hardware implementation to tackle large-scale combinatorial problems and temporal networks that currently exceed the capabilities of classical CPUs.
Summary updated