Solving complex optimization problems with a coherent Ising machine

As the various systems in our society grow larger and more complex, their analysis and optimization grow increasingly important. Many such tasks are classified as combinatorial optimization problems, which can be mapped onto the ground-state-search problems of the Ising model.¹

Recently, several approaches to simulating the Ising model have been demonstrated using artificial spin networks, such as superconducting quantum bits (qubits)² and CMOS devices.³ These physical Ising machines have suffered from a limited number of spin-spin couplings, however, because of the use of solid-state devices as artificial spins.

We have realized a coherent Ising machine (i.e., an artificial spin network based on quantum electronics technologies, CIM) that is instead based on photonics.⁴ To achieve this, we used time-multiplexed degenerate optical parametric oscillators (DOPOs)^{5, 6} as artificial spins, and realized all-to-all coupling between 2048 DOPOs using a measurement-feedback scheme.⁷ We experimentally confirmed that our CIM can find solutions for NP-hard maximum cut problems of a 2000-node complete graph.⁴

The setup of our CIM is illustrated in Figure 1. A periodically poled lithium niobate (PPLN) waveguide module is placed in a fiber ring cavity, which includes a 1km fiber delay line, an optical bandpass filter, optical couplers, and a fiber stretcher for cavity-phase stabilization. When we inject pump pulses with a wavelength of λ_p into the PPLN waveguide, pulsed spontaneous emission noise begins circulating in the cavity. If we limit the wavelength component to 2λ_p using the optical bandpass filter, parametric amplification occurs only at signal-idler degeneracy, i.e., where only lights with 0 or π phase components (relative to the pump phase) are efficiently amplified. As a result, the oscillations occur with 0 or π phase and can thus be used as stable artificial spins realized with light.

Figure 1. The setup of our coherent Ising machine (CIM). The optical bandpass filter and fiber stretcher in the cavity are not shown for conciseness. FPGA: Field-programmable gate array. OPO: Optical parametric oscillator. PPLN: Periodically poled lithium niobate.

By launching 0.77μm pump pulses at a clock frequency of 1GHz to the phase-sensitive amplifier, we can generate ∼5000 time-multiplexed DOPOs at a wavelength of 1.54μm. Among all of the DOPOs, we use 2048 as the ‘signal’ pulses for the Ising model computation, and periodically turn the pump pulses for the signal DOPOs on and off to repeat the computation. While the signal DOPO amplitudes are growing, 10% of the DOPO light is extracted from the cavity using a 9:1 optical coupler, and the cosine components of the ith signal DOPO amplitude—{c_i} ( i∊{0, 1, …, 2047})—are measured using a balanced homodyne detector (BHD). The measurement result {c_i} is launched into a field-programmable gate array (FPGA) module, into which a matrix that corresponds to the spin-spin interaction terms of a given Ising problem have been installed in advance.

The FPGA then calculates the coupling signal for the ith signal DOPO for the next step as , where J_ij is the coupling coefficient between the ith and jth spins. A coupling pulse with the same wavelength as the DOPO pulses is then modulated using the coupling signal σ_i and is launched into the ith signal DOPO circulating in the cavity. In this way, we can couple any pair-signal DOPOs among the 2048, which amounts to more than two million combinations in the case of undirected coupling (i.e., J_ij=J_ji). We repeat this procedure until the signal DOPOs reach the oscillation threshold. The signal DOPOs change their phases during this process so that the DOPO network starts to oscillate in the phase configuration that minimizes the total loss. This is analogous to a multi-mode laser's tendency to oscillate at the mode with the lowest loss if we pump it sufficiently slowly.

Using our CIM, we solved maximum-cut problems of 2000-node undirected graphs. An example of the solutions experimentally obtained for a random graph with 2000 nodes and 19,990 edges is shown in Figure 2. We succeeded in cutting 13,313 of 19,990 edges in less than 5ms, which is the period for turning the signal DOPOs on and off.⁴ This confirmed that the CIM can find good solutions to large-scale optimization problems. To evaluate the computation time of the CIM, we also ran a maximum cut problem for a 2000-node complete graph on the CIM. The obtained Ising energy as a function of the cut value is shown in Figure 3. The Ising energy obtained with the CIM reached the reference energy level obtained with an algorithm with certified accuracy (GW-SDP) in only 70μs. In contrast, simulated annealing run on a CPU (Intel Xeon X5650) took 3.4ms to reach the same energy. This result implies that the CIM might outperform conventional computers when solving dense graph problems.

Figure 2. (a) The graph problem that we used to test our CIM (a random graph with 19,990 edges). Pink dots and white lines show the nodes and edges, respectively. (b) Solution experimentally obtained with the CIM. Green lines show the cut edges.

Figure 3. Ising energy as a function of computation time for a maximum cut problem of a 2000-node complete graph. The blue and red curves show the energies obtained with the CIM and simulated annealing (SA) run on a CPU. The dotted line denotes the reference energy obtained with the GW-SDP algorithm.

In summary, we have realized a CIM based on optical technology that can achieve all-to-all coupling between 2048 spins. Furthermore, we have experimentally confirmed that the CIM can deliver solutions to NP-hard maximum cut problems for 2000-node graphs. In our future work, we plan to increase the number of spins by at least 10 times so that we can further widen the advantages of this scheme over conventional computers.

This research was conducted in collaboration with the Japan Science and Technology Agency, National Institute of Informatics, Osaka University, University of Tokyo, and Stanford University. The research was funded by the Impulsing Paradigm Change through the Disruptive Technologies (ImPACT) Program of the Council of Science, Technology and Innovation (Cabinet Office, Government of Japan).