# 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.^{1}

Recently, several approaches to simulating the Ising model have been demonstrated using artificial spin networks, such as superconducting quantum bits (qubits)^{2} and CMOS devices.^{3} 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.^{4} 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.^{7} We experimentally confirmed that our CIM can find solutions for NP-hard maximum cut problems of a 2000-node complete graph.^{4}

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.

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 *i*th 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 *i*th signal DOPO for the next step as , where *J*_{ij} is the coupling coefficient between the *i*th and *j*th 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 *i*th 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.^{4} 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.

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).*

*Front. Phys.*2, p. 5, 2014.

*Nature*473, p. 194-198, 2011.

*IEEE J. Solid-State Circuits*51, p. 303-309, 2015.

*Science*354, p. 603-606, 2016.

*Nat. Photon.*8, p. 937-942, 2014.

*Nat. Photon.*10, p. 415-419, 2016.

*arXiv:1501.07030v5 [quant-ph]*, 2016.