Mikhail Erementchouk
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Mikhail Erementchouk has a total of 66 co-authors. Here are the top co-authors by number of shared publications:
- Alexander A. Lisyansky
Queens College, CUNY
16 shared publications L. I. Deych
Physics Department Queens College City
15 shared publications- Pinaki Mazumder
Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, USA
14 shared publications - Aditya Shukla
Department of Electrical Engineering and Computer Science, University of Michigan, Ann Arbor, USA
9 shared publications Michael N. Leuenberger
NanoScience Technology Center Department of Physics University of Central Florida 32826 Orlando FL USA
8 shared publicationsPinaki Mazumder
7 shared publications
Latest Publications
- Open Access
- 24 July 2026
- Published by Springer Nature in Natural Computing
- Vol. 25 (2) , 25
Self-contained relaxation-based dynamical Ising machines
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$$ model) solves the rounding problem dynamically. We prove that the $$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$$ -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$$ -machine with random agitations converges to a maximum cut state almost surely.- 24 July 2026
- Published by Springer Nature in Natural Computing
- Vol. 25 (2) , 25
Open AccessSelf-contained relaxation-based dynamical Ising machines
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$$ model) solves the rounding problem dynamically. We prove that the $$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$$ -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$$ -machine with random agitations converges to a maximum cut state almost surely. - Open Access
Relaxation-based dynamical Ising machines for discrete tomography
Dynamical Ising machines are continuous dynamical systems that evolve from a generic initial state to a state strongly related to the ground state of the classical Ising model. We show that such a machine driven by the V${}_2$ dynamical model can solve exactly discrete tomography problems about reconstructing a binary image from the pixel sums along a discrete set of rays. In contrast to usual applications of Ising machines, targeting approximate solutions to optimization problems, the randomly initialized V${}_2$ model converges with high probability ($P_{\mathrm{succ}} \approx 1$) to an image precisely satisfying the tomographic data. For the problems with at most two rays intersecting at each pixel, the V${}_2$ model converges in internal machine time that depends only weakly on the image size. Our consideration is an example of how specific dynamical systems can produce exact solutions to highly non-trivial data processing tasks. Crucially, this solving capability arises from the dynamical features of the V${}_2$ model itself, in particular its equations of motion that enable non-local transitions of the discrete component of the relaxed spin beyond Hamming-neighborhood constraints, rather than from merely recasting the tomography problem in spin form.
Open AccessRelaxation-based dynamical Ising machines for discrete tomography
Dynamical Ising machines are continuous dynamical systems that evolve from a generic initial state to a state strongly related to the ground state of the classical Ising model. We show that such a machine driven by the V${}_2$ dynamical model can solve exactly discrete tomography problems about reconstructing a binary image from the pixel sums along a discrete set of rays. In contrast to usual applications of Ising machines, targeting approximate solutions to optimization problems, the randomly initialized V${}_2$ model converges with high probability ($P_{\mathrm{succ}} \approx 1$) to an image precisely satisfying the tomographic data. For the problems with at most two rays intersecting at each pixel, the V${}_2$ model converges in internal machine time that depends only weakly on the image size. Our consideration is an example of how specific dynamical systems can produce exact solutions to highly non-trivial data processing tasks. Crucially, this solving capability arises from the dynamical features of the V${}_2$ model itself, in particular its equations of motion that enable non-local transitions of the discrete component of the relaxed spin beyond Hamming-neighborhood constraints, rather than from merely recasting the tomography problem in spin form.
- 23 June 2025
- Published by Elsevier in Physica D: Nonlinear Phenomena
- Vol. 481
Non-binary dynamical Ising machines for combinatorial optimization
- 23 June 2025
- Published by Elsevier in Physica D: Nonlinear Phenomena
- Vol. 481
Non-binary dynamical Ising machines for combinatorial optimization
- Open Access
- 18 December 2024
- Published by Springer Nature in Research Square
Self-contained relaxation-based dynamical Ising machines
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 V2 model) solves the rounding problem dynamically. We prove that the V2 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 V2-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 V2-machine with random agitations converges to a maximum cut state almost surely.
- 18 December 2024
- Published by Springer Nature in Research Square
Open AccessSelf-contained relaxation-based dynamical Ising machines
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 V2 model) solves the rounding problem dynamically. We prove that the V2 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 V2-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 V2-machine with random agitations converges to a maximum cut state almost surely.
- Open Access
Non-binary dynamical Ising machines for combinatorial optimization
Dynamical Ising machines achieve accelerated solving of complex combinatorial optimization problems by remapping the convergence to the ground state of the classical spin networks to the evolution of specially constructed continuous dynamical systems. The main adapted principle of constructing such systems is based on requiring that, on the one hand, the system converges to a binary state and, on the other hand, the system's energy in such states mimics the classical Ising Hamiltonian. The emergence of binary-like states is regarded to be an indispensable feature of dynamical Ising machines as it establishes the relation between the machine's continuous terminal state and the inherently discrete solution of a combinatorial optimization problem. This is emphasized by problems where the unknown quantities are represented by spin complexes, for example, the graph coloring problem. In such cases, an imprecise mapping of the continuous states to spin configurations may lead to invalid solutions requiring intensive post-processing. In contrast to such an approach, we show that there exists a class of non-binary dynamical Ising machines without the incongruity between the continuous character of the machine's states and the discreteness of the spin states. We demonstrate this feature by applying such a machine to the problems of finding proper graph coloring, constructing Latin squares, and solving Sudoku puzzles. Thus, we demonstrate that the information characterizing discrete states can be unambiguously presented in essentially continuous dynamical systems. This opens new opportunities in the realization of scalable electronic accelerators of combinatorial optimization.
Open AccessNon-binary dynamical Ising machines for combinatorial optimization
Dynamical Ising machines achieve accelerated solving of complex combinatorial optimization problems by remapping the convergence to the ground state of the classical spin networks to the evolution of specially constructed continuous dynamical systems. The main adapted principle of constructing such systems is based on requiring that, on the one hand, the system converges to a binary state and, on the other hand, the system's energy in such states mimics the classical Ising Hamiltonian. The emergence of binary-like states is regarded to be an indispensable feature of dynamical Ising machines as it establishes the relation between the machine's continuous terminal state and the inherently discrete solution of a combinatorial optimization problem. This is emphasized by problems where the unknown quantities are represented by spin complexes, for example, the graph coloring problem. In such cases, an imprecise mapping of the continuous states to spin configurations may lead to invalid solutions requiring intensive post-processing. In contrast to such an approach, we show that there exists a class of non-binary dynamical Ising machines without the incongruity between the continuous character of the machine's states and the discreteness of the spin states. We demonstrate this feature by applying such a machine to the problems of finding proper graph coloring, constructing Latin squares, and solving Sudoku puzzles. Thus, we demonstrate that the information characterizing discrete states can be unambiguously presented in essentially continuous dynamical systems. This opens new opportunities in the realization of scalable electronic accelerators of combinatorial optimization.
- Open Access
Near-field-assisted capacity of spoof-plasmonic channels
Establishing universal features of spoof-plasmonic systems beyond spectral properties is challenging due to the complexity of the specific physical realizations of spoof-plasmonic channels. We introduce a simple 1D scalar model reproducing the key properties of spoof-plasmonic channels and investigate manifestations of plasmonic-like features when only a few local resonances are present. We show that the channel between the source applied to the interior of the structure and the terminal ends (output ports) effectively comprises two subchannels. The activation of one of the subchannels depends on the spatial variation of the source, and therefore, the contribution of this subchannel in conventional systems is small if the source occupies a subwavelength region. We show that, in spoof-plasmonic structures, the activation of this subchannel can enhance significantly in the frequency region where the spoof-plasmonic effects are prominent. This demonstrates that even a few local scattering resonances may strongly impact the flow of wave-carried information.
Open AccessNear-field-assisted capacity of spoof-plasmonic channels
Establishing universal features of spoof-plasmonic systems beyond spectral properties is challenging due to the complexity of the specific physical realizations of spoof-plasmonic channels. We introduce a simple 1D scalar model reproducing the key properties of spoof-plasmonic channels and investigate manifestations of plasmonic-like features when only a few local resonances are present. We show that the channel between the source applied to the interior of the structure and the terminal ends (output ports) effectively comprises two subchannels. The activation of one of the subchannels depends on the spatial variation of the source, and therefore, the contribution of this subchannel in conventional systems is small if the source occupies a subwavelength region. We show that, in spoof-plasmonic structures, the activation of this subchannel can enhance significantly in the frequency region where the spoof-plasmonic effects are prominent. This demonstrates that even a few local scattering resonances may strongly impact the flow of wave-carried information.
- 9 April 2024
- Published by Springer Nature in Natural Computing
- Vol. 24 (2) , 245-257
Scalable almost-linear dynamical Ising machines
- 9 April 2024
- Published by Springer Nature in Natural Computing
- Vol. 24 (2) , 245-257
Scalable almost-linear dynamical Ising machines
- 19 July 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 72 (10) , 2835-2846
Custom CMOS Ising Machine Based on Relaxed Burer-Monteiro-Zhang Heuristic
Determining the maximum cut of large graphs may require impractically long time, necessitating approximate algorithms and/or specialized computing platforms. A heuristic by Burer, Monteiro and Zhang for max-cut has not only been shown to be advantageous in many respects, but is also applicable to other NP-complete problems. From the perspective of accelerated computing, the heuristic's implementational challenge lies in its gradient-descent dynamics, which could be reduced to several sinusoidal kernel operations applied to each edge of the graph. We had previously established the theoretical underpinnings of a relaxed dynamical heuristic for max-cut similar to the one proposed by Burer et al. but suited for accelerated computing on custom analog CMOS. In this work, we present the first fully custom analog integrated circuit implementing the dynamics of our heuristic on 130-nm CMOS technology. In an era of increasing specificity of computing machines, our algorithm-circuit co-design, originally for max-cut, introduces a versatile approach applicable to a diverse set of practical large-scale NP-complete problems.
- 19 July 2023
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 72 (10) , 2835-2846
Custom CMOS Ising Machine Based on Relaxed Burer-Monteiro-Zhang Heuristic
Determining the maximum cut of large graphs may require impractically long time, necessitating approximate algorithms and/or specialized computing platforms. A heuristic by Burer, Monteiro and Zhang for max-cut has not only been shown to be advantageous in many respects, but is also applicable to other NP-complete problems. From the perspective of accelerated computing, the heuristic's implementational challenge lies in its gradient-descent dynamics, which could be reduced to several sinusoidal kernel operations applied to each edge of the graph. We had previously established the theoretical underpinnings of a relaxed dynamical heuristic for max-cut similar to the one proposed by Burer et al. but suited for accelerated computing on custom analog CMOS. In this work, we present the first fully custom analog integrated circuit implementing the dynamics of our heuristic on 130-nm CMOS technology. In an era of increasing specificity of computing machines, our algorithm-circuit co-design, originally for max-cut, introduces a versatile approach applicable to a diverse set of practical large-scale NP-complete problems.
- Open Access
On computational capabilities of Ising machines based on nonlinear oscillators,
Dynamical Ising machines are actively investigated from the perspective of finding efficient heuristics for NP-hard optimization problems. However, the existing data demonstrate super-polynomial scaling of the running time with the system size, which is incompatible with large NP-hard problems. We show that oscillator networks implementing the Kuramoto model of synchronization are capable of demonstrating polynomial scaling. The dynamics of these networks is related to the semidefinite programming relaxation of the Ising model ground state problem. Consequently, such networks, as we numerically demonstrate, are capable of producing the best possible approximation in polynomial time. To reach such performance, however, the reconstruction of the binary Ising state (rounding) must be specially addressed. We demonstrate that commonly implemented forced collapse to a close-to-Ising state may diminish the computational capabilities up to their complete invalidation. Therefore, consistent treatment of rounding may cardinally improve various operation metrics of already existing and upcoming dynamical Ising machines.
Open AccessOn computational capabilities of Ising machines based on nonlinear oscillators,
Dynamical Ising machines are actively investigated from the perspective of finding efficient heuristics for NP-hard optimization problems. However, the existing data demonstrate super-polynomial scaling of the running time with the system size, which is incompatible with large NP-hard problems. We show that oscillator networks implementing the Kuramoto model of synchronization are capable of demonstrating polynomial scaling. The dynamics of these networks is related to the semidefinite programming relaxation of the Ising model ground state problem. Consequently, such networks, as we numerically demonstrate, are capable of producing the best possible approximation in polynomial time. To reach such performance, however, the reconstruction of the binary Ising state (rounding) must be specially addressed. We demonstrate that commonly implemented forced collapse to a close-to-Ising state may diminish the computational capabilities up to their complete invalidation. Therefore, consistent treatment of rounding may cardinally improve various operation metrics of already existing and upcoming dynamical Ising machines.
- 11 May 2022
- Published by Elsevier in Physica D: Nonlinear Phenomena
- Vol. 437, 133334
On computational capabilities of Ising machines based on nonlinear oscillators
- 11 May 2022
- Published by Elsevier in Physica D: Nonlinear Phenomena
- Vol. 437, 133334
On computational capabilities of Ising machines based on nonlinear oscillators