论文标题
可扩展的几乎线性动力学机器
Scalable almost-linear dynamical Ising machines
论文作者
论文摘要
过去的十年中，通过用连续动力学变量代表的旋转将伊辛·哈密顿量最大程度地降至最小化的伊辛·哈密顿量来最大程度地降至靶向硬组合优化问题。但是，这些机器在较大尺度上的功能尚待充分探索。我们研究了基于几乎线性耦合模拟自旋网络的ISING机器。我们表明，此类网络利用了类似于ISING模型的半决赛正放松的计算资源。我们估计几乎是线性机器的预期性能，并在一组{0,1}加权图上进行基准测试。我们表明，所研究的机器的运行时间是多项式尺度（与连接图中的边数线性线性缩放）。作为机器物理实现的一个例子，我们提出了一个兼容CMOS的实现，其中包括一系列顶点，可以有效地将连续的旋转存储在带电的电容器上，并通过模拟电流进行外部传达。
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.
