EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Self-contained relaxation-based dynamical Ising machines

Mikhail Erementchouk, Aditya Shukla, Pinaki Mazumder

Natural Computing · 2026-12 · 25 (2)

DOI: 10.1007/s11047-026-10082-9 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Natural Computing, online erschienen am 24.07.2026. Verfasst von Mikhail Erementchouk und 2 weiteren Autor:innen. Die Arbeit nennt 51 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: National Science Foundation.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Dynamical Ising machines are based on continuous dynamical systems evolving from a generic initial state to a state strongly related to the ground state of the classical Ising model on a graph. Reaching the ground state is equivalent to finding the maximum (weighted) cut of the graph, which presents the Ising machines as an alternative way to solving and investigating NP-complete problems. Among the dynamical models, relaxation-based models are distinguished by their relations with guarantees of performance achieved in time scaling polynomially with the problem size. However, the terminal states of such machines are essentially non-binary, necessitating special post-processing relying on disparate computing. We show that an Ising machine implementing a special continuous dynamical system (called the $$V_2$$ V 2 model) solves the rounding problem dynamically. We prove that the $$V_2$$ V 2 model, starting from an arbitrary non-binary state, terminates in a state that trivially rounds to a binary state with the cut at least as big as obtained by optimal rounding of the initial state. Besides showing that relaxation-based dynamical Ising machines can be made self-contained, this result presents a non-Boolean realization of solving a non-trivial information processing task on Ising machines. Moreover, we prove that if the initial state of the $$V_2$$ V 2 -machine is a random limited amplitude perturbation of a binary state, the machine progresses to a state with at least as high cut as that of the initial binary state. Since the probability of improving the cut is finite, this shows that the $$V_2$$ V 2 -machine with random agitations converges to a maximum cut state almost surely.

Förderung

  • National Science Foundation

Zitieren

APA

Erementchouk, M., Shukla, A., & Mazumder, P. (2026). Self-contained relaxation-based dynamical Ising machines. Natural Computing, 25(2). https://doi.org/10.1007/s11047-026-10082-9

Vancouver

Erementchouk M, Shukla A, Mazumder P. Self-contained relaxation-based dynamical Ising machines. Natural Computing. 2026;25(2). doi:10.1007/s11047-026-10082-9

BibTeX
@article{Erementchouk2026,
  author = {Erementchouk, Mikhail and Shukla, Aditya and Mazumder, Pinaki},
  title = {Self-contained relaxation-based dynamical Ising machines},
  journal = {Natural Computing},
  year = {2026},
  volume = {25},
  number = {2},
  doi = {10.1007/s11047-026-10082-9}
}
Kostenlos starten →