

Feature Articles: A New Era in Quantum Information Processing Technologies Quantum Neural Network for Solving Complex Combinatorial Optimization ProblemsAbstractOptimization of various social systems, including communication, traffic, and social networking systems, requires the solving of complex combinatorial optimization problems. In this article, we describe the recent progress achieved in developing a quantum neural network, a computer that finds solutions to combinatorial optimization problems using a network of degenerate optical parametric oscillators. Keywords: Ising model, combinatorial optimization problem, optical parametric oscillator 1. IntroductionAs various systems in our society grow larger and more complex, it becomes increasingly important to analyze and optimize such systems. These complex problems are classified as combinatorial optimization problems, which cannot be solved efficiently with conventional digital computers. It is known that such problems can be converted to groundstatesearch problems of the Ising model, which is a theoretical model proposed by E. Ising that describes a group of interacting spins. Several institutions recently reported artificial spin networks that were applied to simulate the Ising model in order to solve combinatorial optimization problems [1, 2]. Our team has been studying such an Isingtype computer called a quantum neural network (QNN) [3]. In a QNN, Ising spins are represented by degenerate optical parametric oscillators (DOPOs), which are coupled with mutual injections of DOPO light. In this article, we describe the basic working principle of a QNN and report the recent experimental progress made in this area at NTT. 2. Ising modelThe Hamiltonian of the Ising model is given as follows. H = − Σ_{i<}_{j}J_{ij}σ_{i}σ_{j}. (1) Here, σ_{i} and J_{ij} respectively represent the ith spin state and the coupling coefficient between the ith and jth spins. The ground state of the Ising model corresponds to a set of spins {σ_{i}} that minimize Eq. (1) for a given matrix {J_{ij}}. A QNN, also known as a coherent Ising machine, is a network of artificial spins based on quantum optical oscillators that simulates the Ising model [3]. In our QNN, a spin state is represented by a DOPO, and the spinspin interaction coefficient J_{ij} is implemented by adjusting the length and transmittance of an optical path between the ith and jth DOPO (Fig. 1). Since the networked DOPO tends to oscillate with a phase configuration that minimizes the total energy, we can obtain the ground state of a given Ising model by simply reading the phases of the DOPOs that are above the threshold.
3. Phase sensitive amplificationAn important physical phenomenon for generating a DOPO is a nonlinear optical effect called phase sensitive amplification [4]. When we input a pump light (angular frequency ω_{p}) and a signal light ω_{s} to a medium with the second or third order optical nonlinearity, we can generate an idler light with an angular frequency ω_{i} = ω_{p} − ω_{s} (second order case) and an initial phase −θ, where θ represents the initial phase difference between the pump and the signal. In particular, when the signal and idler frequencies degenerate (ω_{s} = ω_{i}), the amplification coefficient of the signal amplitude is proportional to cosθ, which means that the light is efficiently amplified when its initial phase difference from the pump is either 0 or π. To achieve such a phase sensitive amplifier (PSA), we can utilize fourwave mixing in an optical fiber [5, 6] or parametric downconversion in a periodically poled lithium niobate waveguide [4, 7]. If we pump a PSA placed in an optical cavity, the 0 or πphase component of the spontaneous emission noise is most efficiently amplified by the PSA, which eventually leads to an optical parametric oscillation with either one of the binary phase states (Fig. 2). In addition, if we use a pulsed pump whose temporal interval is set at 1/N of the cavity roundtrip time, we can generate N timemultiplexed DOPOs using a single cavity.
We succeeded in generating more than thousands of DOPOs using a 1km fiber cavity, paving the way towards achieving a largescale QNN [5–7]. More recently, we reported the generation of more than 1 million DOPOs using a 10GHz clock pump and a 20km fiber cavity [8]. We can implement couplings between timemultiplexed DOPOs by inserting delayed interferometers. In an experiment reported in an earlier paper [6], we implemented nearestneighbor coupling between DOPOs by placing a 1bit delayed interferometer in the fiber cavity so that we could realize a onedimensional Ising model. With the optically coupled DOPOs, we successfully observed that the DOPOs showed ferro and antiferromagnetic behavior when we changed the phase difference between the two arms of the interferometer, suggesting that the DOPOs well simulated the characteristics of lowtemperature spins. 4. Measurementfeedback schemeThe above onedimensional Ising model experiment was important for understanding the physics of a QNN. However, it is difficult to solve realworld combinatorial optimization problems that are usually represented by large and complex spin networks using an optically coupled DOPO network. For example, in order to achieve alltoall connection between 2000 DOPOs, we need as many as 1999 interferometers placed in the cavity, which is very hard to do experimentally. We employed the measurementfeedback scheme shown in Fig. 2 in order to achieve flexible couplings among thousands of DOPOs. In this scheme, we measure the amplitudes of all N DOPOs {c_{i}} while the DOPOs are circulating in the cavity and while controlling the evolution of their amplitudes. The measurement results are fed to a field programmable gate array (FPGA), where the spinspin coupling matrix {J_{ij}} for a given problem is set in advance. In each DOPO circulation in the cavity, the FPGA calculates s_{i} = Σ_{j}J_{ij}c_{j}, the feedback signal for the ith DOPO in the next round trip. The feedback signal s_{i} is used to modulate a light pulse whose frequency is exactly the same as that of the DOPOs, and the pulse is launched to the ith DOPO. As a result, any pair among N DOPOs can be coupled with this scheme. The number of such combinations is N(N−1)/2 when the problem is given by a directed graph. We used the measurementfeedback scheme to construct a QNN with 2048 DOPOs [9], with which we succeeded in finding the solutions to maximum cut problems for a 2000node graph (Fig. 3). In particular, when we applied the QNN to a maximum cut problem of a 2000node complete graph, we obtained a solution that corresponds to a reference Ising energy in less than 100 µs, which is approximately 50 times shorter than the computation time obtained with simulated annealing run on a CPU (central processing unit) (Fig. 4).
5. Future prospectsAlthough QNN research is still in a very early stage, our experimental results suggest that the QNN may outperform conventional digital computers for certain types of problems. We are currently planning to increase the number of DOPOs of our QNN to further widen the performance advantage over digital computers. We also plan to search for applications of QNN by collaborating with researchers from various fields such as statistical physics, mathematics, and computer science. References
