Simulating Frustrated Spin Systems with Memory Dynamics

A variety of frustrated lattices have been proposed as models of physical systems and benchmarks for quantum annealers by virtue of their low-temperature complexity. Standard computational methods for their simulation are inefficient due to the presence of a low-temperature spin-glass phase. For Glauber-type algorithms, the spin-flip dynamics are not sufficiently correlated to address the aging of the lattice; for cluster algorithms, the percolation probability is generally above the critical threshold at low temperature. We provide a novel approach, based on the memcomputing architecture, to study these frustrated lattices. This approach features a continuous relaxation of spins, and a correlated memory capable of learning the frustration of the system. This gives rise to long-range dynamics similar to classical cluster updates, without ever employing any algorithmic step. We propose a theoretical model for studying the long-range memory, and a numerical method for its simulation. The simulation results in a polynomial-scaling of the relaxation time on the tiling lattice with respect to the system size (while other methods scale exponentially). Finally, we discuss possible extensions to the simulation of quantum systems and general graph structures.