The principles and applications of coherent Ising computing

doi:10.12267/j.issn.2096-5931.2024.07.010

Abstract

Abstract:

With the rapid development of artificial intelligence, many industries require massive computational power as technical support. Low-energy optical computing and quantum computing have emerged as the most promising solution for high-speed and large-scale data processing in the future. The optical parametric oscillations pulses are used as the computational bits in coherent Ising computing. A coherent Ising machine based on optical parametric oscillation can search for spin configurations at the ground state of the Ising model, thereby improving the computational speed and accuracy in solving combinatorial optimization problems. The improved coherent Ising machine can overcome the limitations of local minima, and its test results on large-scale combinatorial optimization problems have surpassed some classical algorithms, providing a new direction for solving various combinatorial optimization problems.

Key words: coherent Ising machine, optical parametric oscillator, combinatorial optimization problem

CLC Number:

FAN Chenrui, YUAN Wei, MA Yin, YANG Daquan, WEN Kai, WANG Chuan. The principles and applications of coherent Ising computing[J]. Information and Communications Technology and Policy, 2024, 50(7): 76-84.

Add to citation manager EndNote|Ris|BibTeX

URL:

http://ictp.caict.ac.cn/EN/10.12267/j.issn.2096-5931.2024.07.010

http://ictp.caict.ac.cn/EN/Y2024/V50/I7/76

Figures/Tables 4

COP类型	数字划分	图划分	着色问题
哈密顿量	$H = A ∑ i = 1 N n i s i 2$	$H = A ∑ n = 1 N s i 2 + B ∑ (u v ∈ E) 1 - s u s v 2$	$H = A ∑ v 1 - ∑ i = 1 n x v, i 2 + A ∑ (u v) ∈ E ∑ i = 1 n x u, i x v, i$

COP类型	数字划分	图划分	着色问题
哈密顿量	$H = A ∑ i = 1 N n i s i 2$	$H = A ∑ n = 1 N s i 2 + B ∑ (u v ∈ E) 1 - s u s v 2$	$H = A ∑ v 1 - ∑ i = 1 n x v, i 2 + A ∑ (u v) ∈ E ∑ i = 1 n x u, i x v, i$

References 38

[1]	GOODMAN J W, LEONBERGER F J, KUNG S Y, et al. Optical interconnections for VLSI systems[J]. Proceedings of the IEEE, 1984, 72(7): 850-866.
[2]	GOODMAN J W, DIAS A R, WOODY L M. Fully parallel, high-speed incoherent optical method for performing discrete Fourier transforms[J]. Optics Letters, 1978, 2(1): 1-3. pmid: 19680386
[3]	BUSE K, ADIBI A, PSALTIS D. Non-volatile holographic storage in doubly doped lithium niobate crystals[J]. Nature, 1998, 393(6686): 665-668.
[4]	PAPADIMITRIOU C H, STEIGLITZ K. Combinatorial optimization: algorithms and complexity[M]. New York: Courier Corporation, 1998.
[5]	越民义, 李荣珩. 组合优化导论(第2版)[M]. 北京: 科学出版社, 2014.
[6]	HOPFIELD J J. Neural networks and physical systems with emergent collective computational abilities[J]. Proceedings of the National Academy of Sciences of the United States of America-Biological Sciences, 1982, 79(8): 2554-2558.
[7]	AMIT D J, GUTFREUND H. Spin-glass models of neural networks[J]. Physical Review A, 1985, 32(2):1007-1018. pmid: 9896156
[8]	AGLIARI E, BARRA A, ANTONI A D, et al. Parallel retrieval of correlated patterns: from hopfield networks to boltzmann machines[J]. Neural Networks, 2013, 38: 52-63. doi: 10.1016/j.neunet.2012.11.010 pmid: 23246601
[9]	SOURLAS N. Spin-glass models as error-correcting codes[J]. Nature, 1989, 339(6227):693-695.
[10]	ANDREW L. Ising formulations of many NP problems[J]. arXiv Preprint, arXiv:1302.5843, 2014. DOI:10.3389/fphy.2014.00005.
[11]	PARIHAR A, SHUKLA N, JERRY M, et al. Vertex coloring of graphs via phase dynamics of coupled oscillatory networks[J]. Scientific Reports, 2017, 7(1): 1-11.
[12]	INUI Y, GUNATHILAKA M D S H, KAKO S, et al. Control of amplitude homogeneity in coherent Ising machines with artificial zeeman terms[J]. Communications Physics, 2022, 5(1): 154-161.
[13]	LELEU T, YAMAMOTO Y, UTSUNOMIYA S, et al. Combinatorial optimization using dynamical phase transitions in driven-dissipative systems[J]. Physical Review E, 2017, 95(2): 022118. DOI:10.1103/PhysRevE.95.022118.
[14]	LU B, GAO Y P, WEN K, et al. Combinatorial optimization solving by coherent Ising machines based on spiking neural networks[J]. arXiv Preprint, arXiv:2208. 07502, 2023. DOI:10.48550/arXiv.2208.07502.
[15]	LELEU T, YAMAMOTO Y, MCMAHON P L, et al. Destabilization of local minima in analog spin systems by correction of amplitude heterogeneity[J]. Physical Review Letters, 2019, 122(4): 040607.
[16]	BÖHM F, VAERENBERGH T V, VERSCHAFFELT G, et al. Order-of-magnitude differences in computational performance of analog Ising machines induced by the choice of nonlinearity[J]. Communications Physics, 2021, 4(1): 149.
[17]	WANG Z, MARANDI A, WEN K, et al. Coherent Ising machine based on degenerate optical parametric oscillators[J]. Physical Review A, 2013, 88(6): 063853.
[18]	MARANDI A, WANG Z, TAKATA K, et al. Network of time-multiplexed optical parametric oscillators as a coherent Ising machine[J]. Nature Photonics, 2014, 8(12): 937-942.
[19]	TAKATA K, MARANDI A, HAMERLY R, et al. A 16-bit coherent Ising machine for one-dimensional ring and cubic graph problems[J]. Scientific Reports, 2016, 6(1): 34089.
[20]	MCMAHON P L, MARANDI A, HARIBARA Y, et al. A fully programmable 100-spin coherent Ising machine with all-to-all connections[J]. Science, 2016, 354(6312): 614-617. pmid: 27811274
[21]	INAGAKI T, HARIBARA Y, IGARASHI K, et al. A coherent Ising machine for 2000-node optimization problems[J]. Science, 2016, 354(6312): 603-606. pmid: 27811271
[22]	HONJO T, SONOBE T, INABA K, et al. 100 000-spin coherent Ising machine[J]. Science Advances, 2021, 7(40): eabh0952.
[23]	HAMERLY R, INAGAKI T, MCMAHON P L, et al. Experimental investigation of performance differences between coherent Ising machines and a quantum annealer[J]. Science Advances, 2019, 5(5): eaau0823.
[24]	HASEGAWA M, ITO H, TAKESUE H, et al. Optimization by neural networks in the coherent Ising machine and its application to wireless communication systems[J]. IEICE Transactions on Communications, 2021, 104(3): 210-216.
[25]	KURASAWA K, HASHIMOTO K, LI A, et al. A high-speed channel assignment algorithm for dense IEEE 802.11 systems via coherent Ising machine[J]. IEEE Wireless Communications Letters, 2021, 10(8): 1682-1686.
[26]	HUANG Y. Quantum computing for MIMO beam selection problem: model and optical experimental solution[C]. 2023 IEEE Global Communications Conference, 2023:5463-5468.
[27]	OTSUKA T, LI A, TAKESUE H, et al. High-speed resource allocation algorithm using a coherent Ising machine for noma systems[J]. IEEE Transactions on Vehicular Technology, 2023, 73(1):707.
[28]	BÖHM F, INAGAKI T, INABA K, et al. Understanding dynamics of coherent ising machines through simulation of large-scale 2D Ising models[J]. Nature Communications, 2018, 9(1): 5020.
[29]	TAKESUE H, YAMADA Y, INABA K, et al. Observing a phase transition in a coherent Ising machine[J]. Physical Review Applied, 2023, 19(3): L031001.
[30]	NG E, ONODERA T, KAKO S, et al. Efficient sampling of ground and low-energy Ising spin configurations with a coherent Ising machine[J]. Physical Review Research, 2022, 4(1): 013009.
[31]	MIZUNO Y, KOMATSUZAKI T. Finding optimal pathways in chemical reaction networks using Ising machines[J]. Physical Review Research, 2024, 6(1): 013115.
[32]	TERAYAMA K, SUMITA M, TAMURA R, et al. Black-box optimization for automated discovery[J]. Accounts of Chemical Research, 2021, 54(6): 1334-1346.
[33]	MAO Z, MATSUDA Y, TAMURA R, et al. Chemical design with GPU-based Ising machines[J]. Digital Discovery, 2023, 2(4):1098-1103.
[34]	GENIN S N, RYABINKIN I G, IZMAYLOV A F. Quantum chemistry on quantum annealers[J]. arXiv Preprint, arXiv:1901.04715, 2019. DOI:10.48550/arXiv.1901.04715.
[35]	ZHA J Y, SU J Q. Encoding molecular docking for quantum computers[J]. Journal of Chemical Theory and Computation, 2023, 19(24): 9018-9024. doi: 10.1021/acs.jctc.3c00943 pmid: 38090816
[36]	ROOS, KELLY R. An Ising spin state explanation for financial asset allocation[J]. Physica a Statistical Mechanics & Its Applications, 2016, 445(1):112-116.
[37]	CIVIDINO D, WESTPHAL R, SORNETTE D. Multiasset financial bubbles in an agent-based model with noise traders’ herding described by an n-vector Ising model[J]. Physical Review Research, 2023, 5(1):013009.
[38]	TATSUMURA K, HIDAKA R, NAKAYAMA J, et al. Real-time trading system based on selections of potentially profitable, uncorrelated, and balanced stocks by np-hard combinatorial optimization[J]. IEEE Access, 2023,11:120023.