Quantum Neural Network for Solving Complex Combinatorial Optimization Problems

1. Introduction

As 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 ground-state-search 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 Ising-type 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 model

The Hamiltonian of the Ising model is given as follows.

　　H = − Σ_i<jJ_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 spin-spin 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.

Fig. 1. Concept of quantum neural network (QNN).

3. Phase sensitive amplification

An 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 four-wave mixing in an optical fiber [5, 6] or parametric down-conversion 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 round-trip time, we can generate N time-multiplexed DOPOs using a single cavity.

Fig. 2. QNN configuration.

We succeeded in generating more than thousands of DOPOs using a 1-km fiber cavity, paving the way towards achieving a large-scale QNN [5–7]. More recently, we reported the generation of more than 1 million DOPOs using a 10-GHz clock pump and a 20-km fiber cavity [8].

We can implement couplings between time-multiplexed DOPOs by inserting delayed interferometers. In an experiment reported in an earlier paper [6], we implemented nearest-neighbor coupling between DOPOs by placing a 1-bit delayed interferometer in the fiber cavity so that we could realize a one-dimensional 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 low-temperature spins.

4. Measurement-feedback scheme

The above one-dimensional Ising model experiment was important for understanding the physics of a QNN. However, it is difficult to solve real-world 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 all-to-all 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 measurement-feedback 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 spin-spin coupling matrix {J_ij} for a given problem is set in advance. In each DOPO circulation in the cavity, the FPGA calculates s_i = Σ_jJ_ijc_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 measurement-feedback scheme to construct a QNN with 2048 DOPOs [9], with which we succeeded in finding the solutions to maximum cut problems for a 2000-node graph (Fig. 3). In particular, when we applied the QNN to a maximum cut problem of a 2000-node 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).

Fig. 3. Solution searching of a 2000-node graph problem with QNN. (a) Graph problem (random graph with 19,990 edges). The pink dots and white lines respectively show the nodes and edges. (b) Solution obtained with the QNN experimentally. The pink dots are divided into red and blue dots; as a result, we can cut the edges shown by the green lines. Larger dots exhibit nodes with a larger number of edges.

Fig. 4. Ising energy as a function of computation time for a maximum cut problem of a 2000-node complete graph (K2000).

5. Future prospects

Although 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

[1]	M. W. Johnson, M. H. S. Amin, S. Gildert, T. Lanting, F. Hamze, N. Dickson, R. Harris, A. J. Berkley, J. Johansson, P. Bunyk, E. M. Chapple, C. Enderud, J. P. Hilton, K. Karimi, E. Ladizinsky, N. Ladizinsky, T. Oh, I. Perminov, C. Rich, M. C. Thom, E. Tolkacheva, C. J. S. Truncik, S. Uchaikin, J. Wang, B. Wilson, and G. Rose, “Quantum Annealing with Manufactured Spins,” Nature, Vol. 473, pp. 194–198, 2011.
[2]	M. Yamaoka, C. Yoshimura, M. Hayashi, T. Okuyama, H. Aoki, and H. Mizuno, “A 20k-spin Ising Chip to Solve Combinatorial Optimization Problems with CMOS Annealing,” IEEE J. Solid-State Circuits, Vol. 51, No. 1, pp. 303–309, 2015.
[3]	S. Utsunomiya, K. Takata, and Y. Yamamoto, “Mapping of Ising Models onto Injection-locked Laser Systems,” Opt. Express, Vol. 19, No. 19, pp. 18091–18108, 2011.
[4]	T. Umeki, O. Tadanaga, T. Kazama, K. Enbutsu, Y. Miyamoto, and H. Takenouchi, “Advances in Phase Sensitive Amplifiers Based on PPLN Waveguides for Optical Communication,” NTT Technical Review, Vol. 14, No. 1, 2016. https://www.ntt-review.jp/archive/ntttechnical.php?contents=ntr201601fa3.html
[5]	H. Takesue, T. Inagaki, K. Inoue, and Y. Yamamoto, “Coherence Property of >2500-pulse Multiplexed Degenerate OPO,” The 61st JSAP (Japan Society of Applied Physics) Spring Meeting, 17p-PA1-1, Saga­mihara, Kanagawa, Japan, Mar. 2014 (in Japanese).
[6]	H. Takesue, T. Inagaki, T. Umeki, O. Tadanaga, and H. Takenouchi, “Large-scale Time-division Multiplexed OPOs Using PPLN Waveguide,” The 62nd JSAP Spring Meeting, 12a-P6-1, Shonan, Kanagawa, Japan, Mar. 2015 (in Japanese).
[7]	T. Inagaki, K. Inaba, R. Hamerly, K. Inoue, Y. Yamamoto, and H. Takesue, “Large-scale Ising Spin Network Based on Degenerate Optical Parametric Oscillators,” Nat. Photonics, Vol. 10, pp. 415–419, 2016.
[8]	H. Takesue and T. Inagaki, “10 GHz Clock Time-multiplexed Degenerate Optical Parametric Oscillators for a Photonic Ising Spin Network,” Opt. Lett., Vol. 41, No. 18, pp. 4273–4276, 2016.
[9]	T. Inagaki, Y. Haribara, K. Igarashi, T. Sonobe, S. Tamate, T. Honjo, A. Marandi, P. L. McMahon, T. Umeki, K. Enbutsu, O. Tadanaga, H. Takenouchi, K. Aihara, K. Kawarabayashi, K. Inoue, S. Utsunomiya, and H. Takesue, “A Coherent Ising Machine for 2000-node Optimization Problems,” Science, Vol. 354, No. 6312, pp. 603–606, 2016.