  We describe a hybrid analog-digital computing approach to solve important
combinatorial optimization problems that leverages memristors (two-terminal
nonvolatile memories). While previous memristor accelerators have had to
minimize analog noise effects, we show that our optimization solver harnesses
such noise as a computing resource. Here we describe a memristor-Hopfield
Neural Network (mem-HNN) with massively parallel operations performed in a
dense crossbar array. We provide experimental demonstrations solving NP-hard
max-cut problems directly in analog crossbar arrays, and supplement this with
experimentally-grounded simulations to explore scalability with problem size,
providing the success probabilities, time and energy to solution, and
interactions with intrinsic analog noise. Compared to fully digital approaches,
and present-day quantum and optical accelerators, we forecast the mem-HNN to
have over four orders of magnitude higher solution throughput per power
consumption. This suggests substantially improved performance and scalability
compared to current quantum annealing approaches, while operating at room
temperature and taking advantage of existing CMOS technology augmented with
emerging analog non-volatile memristors.
