Performance Comparison between Coherent Ising Machines and Quantum Annealer

Hiroki Takesue, Takahiro Inagaki, Kensuke Inaba,
and Toshimori Honjo

Abstract

NTT has been developing a coherent Ising machine (CIM), which efficiently finds solutions to ground-state-search problems of the Ising model using a network of optical parametric oscillators. We introduce our recent experiment that compared the computational performance of CIMs (the one developed by NTT and another developed by Stanford University) with a quantum annealer, which solves the Ising-model problems using superconducting devices.

Keywords: coherent Ising machine, quantum annealing, LASOLV

1. Introduction

A combinatorial optimization problem is to find the best combination of choices among a set of many choices and is generally considered a problem that cannot be efficiently solved with modern digital computers. It is known that any combinatorial optimization problem can be efficiently converted to a ground-state-search problem of the Ising model, which is a theoretical model describing the behavior of interacting spins. A recent trend is to solve such Ising model problems through experiments using physical systems that mimic the Ising spins, which are now called Ising machines. A pioneer of such Ising machines is the quantum annealer (QA) based on superconducting qubits as artificial spins. The Canadian company D-Wave Systems has developed QAs with as many as thousands of qubits [1]. A coherent Ising machine (CIM) is another Ising machine that uses degenerate optical parametric oscillators (DOPO) as spins [2, 3]. NTT has been developing a computation system based on the concept of a CIM called LASOLV^TM [4]. In this article, we describe the experimental performance comparison between CIMs and a D-Wave QA undertaken by NTT, National Aeronautics and Space Administration (NASA), and Stanford University [5].

2. Coherent Ising machine

A DOPO is an optical oscillator that can be implemented by placing a phase sensitive-amplifier (PSA) in an optical cavity. A PSA is an optical amplifier based on optical parametric amplification and efficiently amplifies the 0 and π phase components relative to the pump phase [6]. As a result, a DOPO takes only the 0 or π phase above the oscillation threshold; thus, the discrete phase states can be used to represent the Ising spin states. The CIM developed by NTT generates thousands of time-multiplexed DOPO pulses by turning on and off the PSA placed in a 1-km optical fiber with a 1-GHz frequency (Fig. 1). The interaction between the DOPO pulses are implemented using a method called measurement-feedback. With this method, some of the pulse energies of N DOPO pulses are split using a beam splitter for each circulation in the cavity, and the amplitudes (with signs) of all N DOPO pulses are measured. The measurement results are input into a digital circuit for matrix computation, where the spin-spin interaction matrix (an N × N matrix) for a given Ising problem is installed in advance. The digital circuit multiplies the matrix and set of N measurement results to obtain the feedback signal for each pulse in the next circulation in the cavity. We then use the feedback signal to modulate an optical pulse, and the pulse is injected into the corresponding DOPO pulse inside the cavity through another beam splitter to complete measurement-feedback. By repeating this procedure typically during 100 to 1000 circulations in the cavity while increasing the pump amplitude from zero, the combination of the DOPO phases evolves into a phase that most stabilizes the whole system, which in many cases corresponds to the ground state of the given Ising problem. In 2016, we reported on a 2000-node CIM on the basis of measurement-feedback and demonstrated that the CIM could deliver a fine solution to a 2000-node optimization problem ~50 times faster than simulated annealing implemented on a modern digital computer [2].

Fig. 1. Coherent Ising machine based on measurement-feedback.

3. Performance comparison with D-Wave QA

A quantum annealing algorithm starts with an initial state where all the spins are set at the superposition of spin up and down by applying transverse magnetic fields. Spin-spin interactions for a given Ising problem are then gradually implemented while decreasing the transverse field. With the help of quantum fluctuations, the whole system reaches ground states with high probability [7]. The D-Wave QA has been used in several proof-of-concept experiments such as optimization of traffic flow [8]. We report on an experiment of comparing the probabilities to obtain the exact solutions to the common Ising model problems obtained with the CIM developed by NTT and that developed by Stanford University and the 2000-spin D-Wave QA owned by NASA [5].

We denote the number of spins for a given problem, average number of couplings per spin, and coupling density as N_p, d, and D (= d/N_p), respectively. The success probabilities for the problems with D = 50% as a function of N_p are shown in Fig. 2(a). While the success probability of the CIMs did not decrease significantly with the problem size, that for the D-Wave QA decreased rapidly as we increased N_p and ended up at 0.001% with N_p = 50. Figure 2(b) shows the relationship between the success probabilities and d. When solving sparse problems with d = 3, the D-Wave QA slightly outperformed the CIMs. However, the performance of the D-Wave QA degraded rapidly when N_p increased. The success probabilities for d = 3 and D = 50% were comparable, indicating that success probability does not depend on D.

Fig. 2. Success probabilities of CIMs and D-Wave QA in solving Ising problems. (a) Dense problems (50% coupling density), (b) problems with various coupling densities.

The performance difference between the CIMs and D-Wave QA probably originates from the difference in the implementation of the spin-spin couplings. The superconducting qubits of the D-Wave QA are physically connected in a graph structure called a Chimera graph, where each qubit has only six connections. Therefore, a given Ising problem needs to be converted to a problem on the Chimera graph structure before being input into the D-Wave QA, which often increases the number of required spins, especially when solving dense problems. On the other hand, all-to-all coupling among DOPO pulses is possible in the CIMs because of the use of measurement-feedback; thus, Ising problems with any coupling density can be input without any conversion.

In our experiment, we used two methods for converting Ising problems into the Chimera graph structure. One is the native clique embedding method, which embeds a problem into the Chimera graph in accordance with a pre-determined algorithm. The other is a heuristic method that undertakes optimization to minimize the required number of qubits in advance for each problem. The success probabilities of the D-Wave QA on the basis of these two embedding methods and that for the CIMs for 50-node Ising problems are shown in Fig. 3. The use of the heuristic method could decrease the effective problem size run on the D-Wave QA, improving success probabilities compared with native clique embedding. Nevertheless, the success probabilities of the D-Wave QA did not reach that of the CIMs when d was 5 or larger, and the difference increased as d or D increased. This suggests that the manner of implementing the Ising model problems onto a physical system significantly affects the computational performance of Ising machines based on such systems.

Fig. 3. Success probability dependence on coupling densities for 50-spin problems.

4. Summary

We described the performance comparison between CIMs and the D-Wave QA (as of 2019). We expect that both will evolve and improve in performance. Important future work regarding these computers is to clarify if such new computers based on physical systems can have an advantage over modern digital computers and if such an advantage can lead to applications that benefit society.

References

[1]	D-Wave Systems, www.dwavesys.com
[2]	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.
[3]	P. McMachon, A. Marandi1, Y. Haribara, R. Hamerly, C. Langrock, S. Tamate, T. Inagaki, H. Takesue, S. Utsunomiya, K. Aihara, R. L. Byer, M. M. Fejer, H. Mabuchi, and Y. Yamamoto, “A Fully Programmable 100-spin Coherent Ising Machine with All-to-all Connections,” Science, Vol. 354, No. 6312, pp. 614–617, 2016.
[4]	J. Arai, S. Yagi, H. Uchiyama, K. Tomita, K. Miyahara, T. Tomoe, and K. Horikawa, “LASOLV^TM Computing System: Hybrid Platform for Efficient Combinatorial Optimization,” NTT Technical Review, Vol. 18, No. 1, pp. 35–40, 2020. https://ntt-review.jp/archive/ntttechnical.php?contents=ntr202001fa5.html
[5]	R. Hamerly, T. Inagaki, P. L. McMahon, D. Venturelli, A. Marandi, T. Onodera, E. Ng, C. Langrock, K. Inaba, T. Honjo, K. Enbutsu, T. Umeki, R. Kasahara, S. Utsunomiya, S. Kako, K. Kawarabayashi, R. L. Byer, M. M. Fejer, H. Mabuchi, D. Englund, E. Rieffel, H. Takesue, and Y. Yamamoto, “Experimental Investigation of Performance Differences between Coherent Ising Machines and a Quantum Annealer,” Sci. Adv., Vol. 5, No. 5, eaau0823, 2019.
[6]	T. Umeki, T. Kazama, T. Kobayashi, K. Enbutsu, R. Kasahara, and Y. Miyamoto, “Low-noise Amplification and Nonlinearity Mitigation Based on Parametric Repeater Technology,” NTT Technical Review, Vol. 17, No. 5, pp. 20–26, 2019. https://ntt-review.jp/archive/ntttechnical.php?contents=ntr201905fa3.html
[7]	T. Kadowaki and H. Nishimori, “Quantum Annealing in the Transverse Ising Model,” Phys. Rev. E, Vol. 58, No. 5, 5355, 1998.
[8]	F. Neukart, G. Compostella, C. Seidel, D. von Dollen, S. Yarkoni, and B. Parney, “Traffic Flow Optimization Using a Quantum Annealer,” Frontiers in ICT, Vol. 4, 29, 2017.

	Hiroki Takesue Senior Distinguished Scientist, Group Leader, Quantum Optical State Control Research Group, Quantum Science and Technology Laboratory, NTT Basic Research Laboratories. He received a B.E., M.E., and Ph.D. in engineering science from Osaka University in 1994, 1996, and 2002. In 1996, he joined NTT Basic Research Laboratories, where he was engaged in research on lightwave frequency synthesis, optical access networks using wavelength division multiplexing, and quantum optics. He is currently pursuing research on communication and computation using quantum optics technologies. He is the recipient of several awards, including the ITU-T Kaleidoscope Conference 2nd Best Paper Award in 2008 and The Commendation for Science and Technology by the Minister of Education, Culture, Sports, Science and Technology of Japan (The Young Scientists’ Prize) in 2010. He was a visiting scholar at Stanford University, California, USA, from 2004 to 2005, and a guest researcher at the National Institute of Standards and Technology (NIST), Colorado, USA, in 2014. He is a guest professor in the Graduate School of Engineering Science, Osaka University, and a member of the Institute of Electrical and Electronics Engineers (IEEE) and the Japan Society of Applied Physics (JSAP).
	Takahiro Inagaki Distinguished Scientist, Quantum Optical State Control Research Group, Quantum Science and Technology Laboratory, NTT Basic Research Laboratories. He received a B.E., M.E., and Ph.D. in engineering science from Tohoku University, Miyagi, in 2007, 2009, and 2012. While at Tohoku University, he conducted research on quantum state transfer between photon polarization and an electron spin in a semiconductor. He joined the Quantum Optical State Control Research Group in NTT Basic Research Laboratories in 2012. He is currently researching quantum communication based on entanglement and a coherent Ising machine for combinatorial optimization problems. He is a member of the Physical Society of Japan (PSJ) and JSAP.
	Kensuke Inaba Senior Research Scientist, Quantum Optical State Control Research Group, Quantum Science and Technology Laboratory, NTT Basic Research Laboratories. He received a B.E., M.E., and Dr.Eng. from the Department of Applied Physics, Osaka University, in 2003, 2005, and 2007. He joined NTT Basic Research Laboratories in 2008. Since 2004, he has been studying quantum many-body physics in correlated electron systems in condensed matter. His current interests are correlated cold atoms and photons and their application to quantum simulation and computation.
	Toshimori Honjo Senior Research Scientist, Supervisor, Quantum Optical State Control Research Group, Quantum Science and Technology Laboratory, NTT Basic Research Laboratories. He received a B.S. and M.S. in information science from Tokyo Institute of Technology in 1996 and 1998, and a Ph.D. in engineering from Osaka University in 2007. In 1998, he joined NTT Software Laboratories, where he conducted research on secure communication systems. Since 2003, he has been researching quantum optics and quantum cryptography at NTT Basic Research Laboratories. His current research interests include physical computer systems and quantum communication. In 2009, he was a visiting researcher at the University of Vienna, Austria. He is a member of the Information Processing Society of Japan (IPSJ).

↑ TOP