<p>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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$V_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>V</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> model) solves the rounding problem dynamically. We prove that the <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$V_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>V</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$V_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>V</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>-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 <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$V_2$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>V</mi> <mn>2</mn> </msub> </math></EquationSource> </InlineEquation>-machine with random agitations converges to a maximum cut state almost surely.</p>

Self-contained relaxation-based dynamical Ising machines

期刊论文
出版模式：

开放获取
发表日期：

2026年7月24日

查看全文

Mikhail Erementchouk,
Aditya Shukla,
Pinaki Mazumder

摘要

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.