  The past decade has seen the emergence of Ising machines targeting hard
combinatorial optimization problems by minimizing the Ising Hamiltonian with
spins represented by continuous dynamical variables. However, capabilities of
these machines at larger scales are yet to be fully explored. We investigate an
Ising machine based on a network of almost-linearly coupled analog spins. We
show that such networks leverage the computational resource similar to that of
the semidefinite positive relaxation of the Ising model. We estimate the
expected performance of the almost-linear machine and benchmark it on a set of
{0,1}-weighted graphs. We show that the running time of the investigated
machine scales polynomially (linearly with the number of edges in the
connectivity graph). As an example of the physical realization of the machine,
we present a CMOS-compatible implementation comprising an array of vertices
efficiently storing the continuous spins on charged capacitors and
communicating externally via analog current.
