Combinatorial optimization solving by coherent Ising machines based on spiking neural networks

Bo Lu1, Yong-Pan Gao2, Kai Wen3, and Chuan Wang1

1School of Artificial Intelligence, Beijing Normal University, Beijing 100875, China
2School of Electronics Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China
3Beijing QBoson Quantum Technology Co., Ltd., Beijing 100015, China

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Spiking neural network is a kind of neuromorphic computing that is believed to improve the level of intelligence and provide advantages for quantum computing. In this work, we address this issue by designing an optical spiking neural network and find that it can be used to accelerate the speed of computation, especially on combinatorial optimization problems. Here the spiking neural network is constructed by the antisymmetrically coupled degenerate optical parametric oscillator pulses and dissipative pulses. A nonlinear transfer function is chosen to mitigate amplitude inhomogeneities and destabilize the resulting local minima according to the dynamical behavior of spiking neurons. It is numerically shown that the spiking neural network-coherent Ising machines have excellent performance on combinatorial optimization problems, which is expected to offer new applications for neural computing and optical computing.

► BibTeX data

► References

[1] Douglas B Kitchen, Hélène Decornez, John R Furr, and Jürgen Bajorath. ``Docking and scoring in virtual screening for drug discovery: methods and applications''. Nature reviews Drug discovery 3, 935–949 (2004).
https:/​/​doi.org/​10.1038/​nrd1549

[2] Amparo Soler-Dominguez, Angel A Juan, and Renatas Kizys. ``A survey on financial applications of metaheuristics''. ACM Computing Surveys (CSUR) 50, 1–23 (2017). url: doi.org/​10.1145/​3054133.
https:/​/​doi.org/​10.1145/​3054133

[3] Francisco Barahona, Martin Grötschel, Michael Jünger, and Gerhard Reinelt. ``An application of combinatorial optimization to statistical physics and circuit layout design''. Operations Research 36, 493–513 (1988). arXiv:https:/​/​doi.org/​10.1287/​opre.36.3.493.
https:/​/​doi.org/​10.1287/​opre.36.3.493
arXiv:https://doi.org/10.1287/opre.36.3.493

[4] Sanjeev Arora and Boaz Barak. ``Computational complexity: a modern approach'' (2009).

[5] Tadashi Kadowaki and Hidetoshi Nishimori. ``Quantum annealing in the transverse ising model''. Physical Review E 58, 5355 (1998). url: doi.org/​10.1103/​PhysRevE.58.5355.
https:/​/​doi.org/​10.1103/​PhysRevE.58.5355

[6] Arnab Das and Bikas K Chakrabarti. ``Colloquium: Quantum annealing and analog quantum computation''. Reviews of Modern Physics 80, 1061 (2008). url: doi.org/​10.1103/​RevModPhys.80.1061.
https:/​/​doi.org/​10.1103/​RevModPhys.80.1061

[7] Zhe Wang, Alireza Marandi, Kai Wen, Robert L Byer, and Yoshihisa Yamamoto. ``Coherent ising machine based on degenerate optical parametric oscillators''. Physical Review A 88, 063853 (2013). url: doi.org/​10.1103/​PhysRevA.88.063853.
https:/​/​doi.org/​10.1103/​PhysRevA.88.063853

[8] Brian Sutton, Kerem Yunus Camsari, Behtash Behin-Aein, and Supriyo Datta. ``Intrinsic optimization using stochastic nanomagnets''. Scientific reports 7, 1–9 (2017). url: doi.org/​10.1038/​srep44370.
https:/​/​doi.org/​10.1038/​srep44370

[9] Michael Saccone, Francesco Caravelli, Kevin Hofhuis, Sergii Parchenko, Yorick A Birkhölzer, Scott Dhuey, Armin Kleibert, Sebastiaan Van Dijken, Cristiano Nisoli, and Alan Farhan. ``Direct observation of a dynamical glass transition in a nanomagnetic artificial hopfield network''. Nature Physics 18, 517–521 (2022).
https:/​/​doi.org/​10.1038/​s41567-022-01538-7

[10] Ryan Hamerly, Takahiro Inagaki, Peter L McMahon, Davide Venturelli, Alireza Marandi, Tatsuhiro Onodera, Edwin Ng, Carsten Langrock, Kensuke Inaba, Toshimori Honjo, et al. ``Experimental investigation of performance differences between coherent ising machines and a quantum annealer''. Science advances 5, eaau0823 (2019).
https:/​/​doi.org/​10.1126/​sciadv.aau0823

[11] Alireza Marandi, Zhe Wang, Kenta Takata, Robert L Byer, and Yoshihisa Yamamoto. ``Network of time-multiplexed optical parametric oscillators as a coherent ising machine''. Nature Photonics 8, 937–942 (2014). url: doi.org/​10.1038/​nphoton.2014.249.
https:/​/​doi.org/​10.1038/​nphoton.2014.249

[12] Takahiro Inagaki, Kensuke Inaba, Ryan Hamerly, Kyo Inoue, Yoshihisa Yamamoto, and Hiroki Takesue. ``Large-scale ising spin network based on degenerate optical parametric oscillators''. Nature Photonics 10, 415–419 (2016).
https:/​/​doi.org/​10.1038/​nphoton.2016.68

[13] Peter L McMahon, Alireza Marandi, Yoshitaka Haribara, Ryan Hamerly, Carsten Langrock, Shuhei Tamate, Takahiro Inagaki, Hiroki Takesue, Shoko Utsunomiya, Kazuyuki Aihara, et al. ``A fully programmable 100-spin coherent ising machine with all-to-all connections''. Science 354, 614–617 (2016).
https:/​/​doi.org/​10.1126/​science.aah5178

[14] Takahiro Inagaki, Yoshitaka Haribara, Koji Igarashi, Tomohiro Sonobe, Shuhei Tamate, Toshimori Honjo, Alireza Marandi, Peter L McMahon, Takeshi Umeki, Koji Enbutsu, et al. ``A coherent ising machine for 2000-node optimization problems''. Science 354, 603–606 (2016). url: doi.org/​10.1126/​science.aah4243.
https:/​/​doi.org/​10.1126/​science.aah4243

[15] Toshimori Honjo, Tomohiro Sonobe, Kensuke Inaba, Takahiro Inagaki, Takuya Ikuta, Yasuhiro Yamada, Takushi Kazama, Koji Enbutsu, Takeshi Umeki, Ryoichi Kasahara, et al. ``100,000-spin coherent ising machine''. Science advances 7, eabh0952 (2021).
https:/​/​doi.org/​10.1126/​sciadv.abh0952

[16] Fabian, Bhm, Guy, Verschaffelt, Van, der, and Sande. ``A poor man's coherent ising machine based on opto-electronic feedback systems for solving optimization problems.''. Nature communications 10, 3538–3538 (2019). url: doi.org/​10.1038/​s41467-019-11484-3.
https:/​/​doi.org/​10.1038/​s41467-019-11484-3

[17] Qizhuang Cen, Tengfei Hao, Hao Ding, Shanhong Guan, Zhiqiang Qin, Kun Xu, Yitang Dai, and Ming Li. ``Microwave photonic ising machine'' (2020). arXiv:2011.00064.
arXiv:2011.00064

[18] D Pierangeli, G Marcucci, and C Conti. ``Large-scale photonic ising machine by spatial light modulation''. Physical Review Letters 122, 213902 (2019). url: doi.org/​10.1103/​PhysRevLett.122.213902.
https:/​/​doi.org/​10.1103/​PhysRevLett.122.213902

[19] Yisheng Fang, Junyi Huang, and Zhichao Ruan. ``Experimental observation of phase transitions in spatial photonic ising machine''. Physical Review Letters 127, 043902 (2021).
https:/​/​doi.org/​10.1103/​PhysRevLett.127.043902

[20] Wenchen Sun, Wenjia Zhang, Yuanyuan Liu, Qingwen Liu, and Zuyuan He. ``Quadrature photonic spatial ising machine''. Optics Letters 47, 1498–1501 (2022).
https:/​/​doi.org/​10.1364/​OL.446789

[21] Yoshitomo Okawachi, Mengjie Yu, Jae K Jang, Xingchen Ji, Yun Zhao, Bok Young Kim, Michal Lipson, and Alexander L Gaeta. ``Demonstration of chip-based coupled degenerate optical parametric oscillators for realizing a nanophotonic spin-glass''. Nature communications 11, 1–7 (2020).
https:/​/​doi.org/​10.1038/​s41467-020-17919-6

[22] Timothée Leleu, Yoshihisa Yamamoto, Shoko Utsunomiya, and Kazuyuki Aihara. ``Combinatorial optimization using dynamical phase transitions in driven-dissipative systems''. Phys. Rev. E 95, 022118 (2017).
https:/​/​doi.org/​10.1103/​physreve.95.022118

[23] Fabian Böhm, Thomas Van Vaerenbergh, Guy Verschaffelt, and Guy Van der Sande. ``Order-of-magnitude differences in computational performance of analog ising machines induced by the choice of nonlinearity''. Communications Physics 4, 1–11 (2021).
https:/​/​doi.org/​10.1038/​s42005-021-00655-8

[24] Sam Reifenstein, Satoshi Kako, Farad Khoyratee, Timothee Leleu, and Yoshihisa Yamamoto. ``Coherent ising machines with optical error correction circuits''. Advanced Quantum Technologies 4, 2100077 (2021).
https:/​/​doi.org/​10.1002/​qute.202100077

[25] Timothée Leleu, Yoshihisa Yamamoto, Peter L. McMahon, and Kazuyuki Aihara. ``Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity''. Phys. Rev. Lett. 122, 040607 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.122.040607

[26] Satoshi Kako, Timothée Leleu, Yoshitaka Inui, Farad Khoyratee, Sam Reifenstein, and Yoshihisa Yamamoto. ``Coherent ising machines with error correction feedback''. Advanced Quantum Technologies 3, 2000045 (2020).
https:/​/​doi.org/​10.1002/​qute.202000045

[27] Timothée Leleu, Farad Khoyratee, Timothée Levi, Ryan Hamerly, Takashi Kohno, and Kazuyuki Aihara. ``Scaling advantage of chaotic amplitude control for high-performance combinatorial optimization''. Communications Physics 4, 1–10 (2021).
https:/​/​doi.org/​10.1038/​s42005-021-00768-0

[28] Marcello Calvanese Strinati and Claudio Conti. ``Multidimensional hyperspin machine''. Nature Communications 13, 7248 (2022).
https:/​/​doi.org/​10.1038/​s41467-022-34847-9

[29] Takahiro Inagaki, Kensuke Inaba, Timothée Leleu, Toshimori Honjo, Takuya Ikuta, Koji Enbutsu, Takeshi Umeki, Ryoichi Kasahara, Kazuyuki Aihara, and Hiroki Takesue. ``Collective and synchronous dynamics of photonic spiking neurons''. Nature communications 12, 1–8 (2021).
https:/​/​doi.org/​10.1038/​s41467-021-22576-4

[30] Bo Lu, Chen-Rui Fan, Lu Liu, Kai Wen, and Chuan Wang. ``Speed-up coherent ising machine with a spiking neural network''. Optics Express 31, 3676–3684 (2023).
https:/​/​doi.org/​10.1364/​OE.479903

[31] Wolfgang Maass. ``Networks of spiking neurons: the third generation of neural network models''. Neural networks 10, 1659–1671 (1997).
https:/​/​doi.org/​10.1016/​S0893-6080(97)00011-7

[32] Romain Brette, Michelle Rudolph, Ted Carnevale, Michael Hines, David Beeman, James M Bower, Markus Diesmann, Abigail Morrison, Philip H Goodman, Frederick C Harris, et al. ``Simulation of networks of spiking neurons: a review of tools and strategies''. Journal of computational neuroscience 23, 349–398 (2007).
https:/​/​doi.org/​10.1007/​s10827-007-0038-6

[33] Eugene M Izhikevich. ``Simple model of spiking neurons''. IEEE Transactions on neural networks 14, 1569–1572 (2003).
https:/​/​doi.org/​10.1109/​TNN.2003.820440

[34] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. ``Human-level control through deep reinforcement learning''. Nature 518, 529–533 (2015).
https:/​/​doi.org/​10.1038/​nature14236

[35] Qiang Yu, Kay Chen Tan, and Huajin Tang. ``Pattern recognition computation in a spiking neural network with temporal encoding and learning''. In The 2012 International Joint Conference on Neural Networks (IJCNN). Pages 1–7. IEEE (2012).
https:/​/​doi.org/​10.1109/​IJCNN.2012.6252427

[36] Roger Rodriguez and Henry C Tuckwell. ``Statistical properties of stochastic nonlinear dynamical models of single spiking neurons and neural networks''. Physical Review E 54, 5585 (1996).
https:/​/​doi.org/​10.1103/​physreve.54.5585

[37] Omri Harish and David Hansel. ``Asynchronous rate chaos in spiking neuronal circuits''. PLoS computational biology 11, e1004266 (2015).
https:/​/​doi.org/​10.1371/​journal.pcbi.1004266

[38] Fabian Böhm, Takahiro Inagaki, Kensuke Inaba, Toshimori Honjo, Koji Enbutsu, Takeshi Umeki, Ryoichi Kasahara, and Hiroki Takesue. ``Understanding dynamics of coherent ising machines through simulation of large-scale 2d ising models''. Nature communications 9, 1–9 (2018).
https:/​/​doi.org/​10.1038/​s41467-018-07328-1

[39] Fuda Ma and Jin-Kao Hao. ``A multiple search operator heuristic for the max-k-cut problem''. Annals of Operations Research 248, 365–403 (2017).
https:/​/​doi.org/​10.1007/​s10479-016-2234-0

Cited by

[1] Lu Liu, Xing-Yu Wu, Chu-Yao Xu, Lu-Fan Zhang, and Chuan Wang, "The deterministic pattern matching based on the parameterized quantum circuit", EPJ Quantum Technology 11 1, 3 (2024).

[2] Bo Lu, Lu Liu, Jun-Yang Song, Kai Wen, and Chuan Wang, "Recent progress on coherent computation based on quantum squeezing", Association of Asia Pacific Physical Societies Bulletin 33 1, 7 (2023).

[3] Bo Lu, Chen-Rui Fan, Lu Liu, Kai Wen, and Chuan Wang, "Speed-up coherent Ising machine with a spiking neural network", Optics Express 31 3, 3676 (2023).

The above citations are from Crossref's cited-by service (last updated successfully 2024-05-24 21:08:00) and SAO/NASA ADS (last updated successfully 2024-05-24 21:08:01). The list may be incomplete as not all publishers provide suitable and complete citation data.