Ising formulation of associative memory models and quantum annealing recall

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\left(N\right)$ and the capacity $C\left(N\right)$ 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\left(N\right)=O\left(e^{C_{1}N}\right)$, $C_1\ge 0$, and succeeds on randomly chosen memory sets with a probability of $(1-e^{-C_{2}N})$, $C_2\ge 0$ with $C_1+C_2={(0.5-f)}^2/(1-f)$, where $f=R\left(N\right)/N$, $0\le f\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.

Figure 1

Chimera graph showing the connectivity of qubits on the DW2 processor chip at Burnaby, BC that we use. Not all qubits are usable in the graph; there are missing qubits, which are rejected at the calibration stage. There are 64 $K_{4,4}$-connected blocks of qubits laid out as a matrix of $8\times 8$ blocks. Each block has 2 columns (vertical) and 4 rows (horizontal). Fully connected problems such as Hopfield networks have to be embedded onto the native graph structure keeping in mind the missing qubits.

Figure 2

Variation of the energies of the fundamental memories (blue) and the probe memory (red) under the Hamiltonian ${\widehat{H}}_{\text{AM}}$ with the probe vector $\chi$ as in (18). The dotted vertical line (green) represents the highest ($h=0.75$) allowed field strength for successful recall of $\chi$. Applying fields above this maximum value overbiases the Hamiltonian such that $\chi$ itself becomes the lowest energy state. A vertical slice at any fixed value of $h$ is the spectrum of the problem Hamiltonian ${\widehat{H}}_P={\widehat{H}}_{\text{AM}}$ for the $p$-fundamental memories plus the input probe memory.

Figure 3

Probability of correct recall using quantum annealing with respect to the applied field strength $h>0$. This probability is high ($\simeq 1$) for the particular set of $p=3$ memories and the input vector (18) for almost the entire region with $h<0.75$. For small values of $h$ ($\le 0.15$), the thermal noise degrades the annealing recall success significantly.

Figure 4

Temporal evolution of the classical control functions $A\left(s\right)$ and $B\left(s\right)$ in the time-dependent annealing Hamiltonian $H\left(s\right)$ in Eq. (4) where $s=t/T_{\text{anneal}}$ is the normalized annealing time.

Figure 5

Frequency, expressed as a percentage, of being returned by DW2 for the three fundamental memories (17) with zero applied field $h=0$. The total sum of percentages for the three memories is 16, with the remainder of returned states being other energy minima outside the set of stored fundamental memories.