Exponential capacity of associative memories under quantum annealing recall

Abstract

Associative memory models, in theoretical neuro- and computer sciences, can generally store a sublinear number of memories. We show that using quantum annealing for recall tasks endows associative memory models with exponential storage capacities. 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 a model using the Hebbian learning rule with recall via quantum annealing is exponential in the size of the problem, $C(N)=\mathcal{O}(e^{C_{1}N}),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=(.5-f{)}^2/(1-f)$, where, $f=R(N)/N,0\le f\le .5$ is the radius of attraction in terms of 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 Dwave processor.

9 pages, 4 figures. Comments welcome

References in corpus (8)

• An introduction to quantum machine learning
• Mathematical Foundation of Quantum Annealing
• Quantum annealing correction for random Ising problems
• Temperature scaling law for quantum annealing optimizers
• Unraveling Quantum Annealers using Classical Hardness
• Experimental quantum annealing: case study involving the graph isomorphism problem
• Quantum pattern recognition with liquid-state nuclear magnetic resonance
• Adiabatic Quantum Optimization for Associative Memory Recall

Cited by in corpus (5)

• Adiabatic Quantum Computing
• Machine learning \& artificial intelligence in the quantum domain
• Particle Track Classification Using Quantum Associative Memory
• Designing ground states of Hopfield networks for quantum state preparation
• Unitary Evolutions Sourced By Interacting Quantum Memories: Closed Quantum Systems Directing Themselves Using Their State Histories