- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Impacts of graph structure on the computational properties of oscillator Ising machines

Yi Cheng, Nikhil Shukla, and Zongli Lin*

  • Charles L. Brown Department of Electrical and Computer Engineering, University of Virginia, Charlottesville, Virginia 22904, USA

  • *Contact author: zl5y@virginia.edu
PDF

Phys. Rev. E 111, 044211 – Published 15 April, 2025

DOI: https://doi.org/10.1103/PhysRevE.111.044211

Abstract

Many combinatorial optimization problems (COPs) can be mapped to Ising Hamiltonians. Oscillator Ising machines (OIMs) are built to minimize the Ising Hamiltonians, thereby indirectly solving the COPs. Specifically, the dynamics of an OIM evolve in the direction of decreasing value of the Ising Hamiltonian, and its state converges to a steady state, known as an asymptotically stable equilibrium point. Such an equilibrium point represents a candidate solution of the underlying COP. Although OIMs show great potential in solving COPs, they, like many heuristic algorithms, are prone to getting stuck in local minima. Even for trivial problems, e.g., unfrustrated Ising Hamiltonians, an OIM may get trapped in local minima if its parameters and its initial condition are not properly selected. In this work, we examine the impacts of the graph structure underlying an OIM on the computational properties of the OIM. In particular, we identify graph structures of OIMs for which the parameters of the OIMs can be properly designed such that only the equilibrium points representing global minima are asymptotically stable and all other equilibrium points are unstable. Thus, an OIM with such a graph structure, possibly with a small perturbation, can converge to the globally optimal solutions from any initial condition.

View figure in article

Physics Subject Headings (PhySH)

Article Text

References (34)

  1. A. Lucas, Ising formulations of many NP problems, Front. Phys. 2, 5 (2014).
  2. I. Ernst, Contribution to the theory of ferromagnetism, Z. Phys. A: Hadrons Nucl. 31, 253 (1925).
  3. D. Sherrington and S. Kirkpatrick, Solvable model of a spin-glass, Phys. Rev. Lett. 35, 1792 (1975).
  4. M. Mézard, G. Parisi, and M. A. Virasoro, Spin Glass Theory and Beyond: An Introduction to the Replica Method and Its Applications (World Scientific Publishing Company, Singapore, 1987), Vol. 9
  5. J. Si, S. Yang, Y. Cen, J. Chen, Y. Huang, Z. Yao, D.-J. Kim, K. Cai, J. Yoo, X. Fong, and H. Yang, Energy-efficient superparamagnetic Ising machine and its application to traveling salesman problems, Nat. Commun. 15, 3457 (2024).
  6. M. K. Bashar, Z. Lin, and N. Shukla, Oscillator-inspired dynamical systems to solve Boolean satisfiability, IEEE J. Explor. Solid-State Comput. Devices Circuits 9, 12 (2023).
  7. J. J. Hopfield, Neural networks and physical systems with emergent collective computational abilities, Proc. Natl. Acad. Sci. USA 79, 2554 (1982).
  8. A. C. Coolen, R. Kühn, and P. Sollich, Theory of Neural Information Processing Systems (Oxford University Press, Oxford, UK, 2005).
  9. C. Marullo and E. Agliari, Boltzmann machines as generalized Hopfield networks: A review of recent results and outlooks, Entropy 23, 34 (2020).
  10. P. Picco, Artificial neural networks. A review from physical and mathematical points of view, in Annales de l'IHP Physique Théorique (Gauthier-Villar Publisher, Paris, France, 1996), Vol. 64, pp. 289–307.
  11. E. Agliari, A. Barra, and F. Camboni, Criticality in diluted ferromagnets, J. Stat. Mech.: Theory Exp. (2008) P10003.
  12. E. Agliari, R. Burioni, and P. Sgrignoli, A two-populations Ising model on diluted random graphs, J. Stat. Mech.: Theory Exp. (2010) P07021.
  13. H. Takesue, T. Inagaki, K. Inaba, T. Ikuta, and T. Honjo, Large-scale coherent Ising machine, J. Phys. Soc. Jpn. 88, 061014 (2019).
  14. Q. Cen, H. Ding, T. Hao, S. Guan, Z. Qin, J. Lyu, W. Li, N. Zhu, K. Xu, Y. Dai, and M. Li, Large-scale coherent Ising machine based on optoelectronic parametric oscillator, Light Sci. Appl. 11, 333 (2022).
  15. Y. Yamamoto, K. Aihara, T. Leleu, K. Kawarabayashi, S. Kako, M. Fejer, K. Inoue, and H. Takesue, Coherent Ising machines-optical neural networks operating at the quantum limit, npj Quantum Inf. 3, 49 (2017).
  16. J. Vaidya, R. S. Kanthi, and N. Shukla, Creating electronic oscillator-based Ising machines without external injection locking, Sci. Rep. 12, 981 (2022).
  17. J. Chou, S. Bramhavar, S. Ghosh, and W. Herzog, Analog coupled oscillator based weighted Ising machine, Sci. Rep. 9, 14786 (2019).
  18. O. Maher, M. Jiménez, C. Delacour, N. Harnack, J. Núñez, M. J. Avedillo, B. Linares-Barranco, A. Todri-Sanial, G. Indiveri, and S. Karg, A CMOS-compatible oscillation-based VO2 Ising machine solver, Nat. Commun. 15, 3334 (2024).
  19. X. Chen, D. Yang, G. Hwang, Y. Dong, B. Cui, D. Wang, H. Chen, N. Lin, W. Zhang, H. Li, R. Shao, P. Lin, H. Hong, Y. Yao, L. Sun, Z. Wang, and H. Yang, Oscillatory neural network-based Ising machine using 2D memristors, ACS Nano 18, 10758 (2024).
  20. R. Iimura, S. Kitamura, and T. Kawahara, Annealing processing architecture of 28-nm CMOS chip for Ising model with 512 fully connected spins, IEEE Trans. Circuits Syst. I Regul. Pap. 68, 5061 (2021).
  21. Y. Su, J. Mu, H. Kim, and B. Kim, A scalable CMOS Ising computer featuring sparse and reconfigurable spin interconnects for solving combinatorial optimization problems, IEEE J. Solid-State Circuits 57, 858 (2022).
  22. D. Jiang, X. Wang, Z. Huang, Y. Yang, and E. Yao, A network-on-chip-based annealing processing architecture for large-scale fully connected Ising model, IEEE Trans. Circuits Syst. I Regul. Pap. 70, 2868 (2023).
  23. Y. Su, T. T.-H. Kim, and B. Kim, A reconfigurable CMOS Ising machine with three-body spin interactions for solving Boolean satisfiability with direct mapping, IEEE Solid-State Circuits Lett. 6, 221 (2023).
  24. E. Elmitwalli, Z. Ignjatovic, and S. Kose, Utilizing multi-body interactions in a CMOS-based Ising machine for LDPC decoding, IEEE Trans. Circuits Syst. I Regul. Pap. 71, 40 (2024).
  25. A. Mallick, M. K. Bashar, Z. Lin, and N. Shukla, Computational models based on synchronized oscillators for solving combinatorial optimization problems, Phys. Rev. Appl. 17, 064064 (2022).
  26. M. K. Bashar, Z. Lin, and N. Shukla, Stability of oscillator Ising machines: Not all solutions are created equal, J. Appl. Phys. 134, 144901 (2023).
  27. T. Wang, L. Wu, P. Nobel, and J. Roychowdhury, Solving combinatorial optimisation problems using oscillator based Ising machines, Nat. Comput. 20, 287 (2021).
  28. Y. Cheng, M. Khairul Bashar, N. Shukla, and Z. Lin, A control theoretic analysis of oscillator Ising machines, Chaos: Interdisc. J. Nonlin. Sci. 34, 073103 (2024).
  29. J. L. Gross, J. Yellen, and M. Anderson, Graph Theory and Its Applications (Chapman and Hall/CRC, London, UK, 2018).
  30. A. S. Asratian, T. M. J. Denley, and R. Häggkvist, Bipartite Graphs and Their Applications, Cambridge Tracts in Mathematics (Cambridge University Press, Cambridge, UK, 1998).
  31. E. Lobe, L. Schürmann, and T. Stollenwerk, Embedding of complete graphs in broken chimera graphs, Quantum Info. Proc. 20, 234 (2021).
  32. S. Okada, M. Ohzeki, M. Terabe, and S. Taguchi, Improving solutions by embedding larger subproblems in a D-wave quantum annealer, Sci. Rep. 9, 2098 (2019).
  33. C. Berge, The Theory of Graphs and Its Applications (Wiley, New York, NY, 1963).
  34. R.-C. Li, Relative perturbation theory: I. Eigenvalue and singular value variations, SIAM J. Matrix Anal. Appl. 19, 956 (1998).

Outline

Information

Phys. Rev. E 111, 044211– Published 15 April, 2025
  • Received 24 October 2024
  • Accepted 25 March 2025
Article part of CHORUS
Crossmark - Check for updates button

©2025 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation