Ising formulation of associative memory models and quantum annealing recall

Abstract

Associative memory models, in theoretical neuro- and computer sciences, can generally store at most a linear number of memories. Recalling memories in these models can be understood as retrieval of the energy minimizing configuration of classical Ising spins, closest in Hamming distance to an imperfect input memory, where the energy landscape is determined by the set of stored memories. We present an Ising formulation for associative memory models and consider the problem of memory recall using quantum annealing. We show that allowing for input-dependent energy landscapes allows storage of up to an exponential number of memories (in terms of the number of neurons). Further, we show how quantum annealing may naturally be used for recall tasks in such input-dependent energy landscapes, although the recall time may increase with the number of stored memories. Theoretically, we obtain the radius of attractor basins $R(N)$ and the capacity $C(N)$ of such a scheme and their tradeoffs. Our calculations establish that for randomly chosen memories the capacity of our model using the Hebbian learning rule as a function of problem size can be expressed as $C(N)=O({e}^{{C}_{1}N})$, ${C}_{1}\ensuremath{\ge}0$, and succeeds on randomly chosen memory sets with a probability of $(1\ensuremath{-}{e}^{\ensuremath{-}{C}_{2}N})$, ${C}_{2}\ensuremath{\ge}0$ with ${C}_{1}+{C}_{2}={(0.5\ensuremath{-}f)}^{2}/(1\ensuremath{-}f)$, where $f=R(N)/N$, $0\ensuremath{\le}f\ensuremath{\le}0.5$, is the radius of attraction in terms of the Hamming distance of an input probe from a stored memory as a fraction of the problem size. We demonstrate the application of this scheme on a programmable quantum annealing device, the D-wave processor.