We review our models of quantum associative memories that represent the “quantization” of fully coupled neural networks like the Hopfield model. The idea is to replace the classical irreversible attractor dynamics driven by an Ising model with pattern-dependent weights by the reversible rotation of an input quantum state onto an output quantum state consisting of a linear superposition with probability amplitudes peaked on the stored pattern closest to the input in Hamming distance, resulting in a high probability of measuring a memory pattern very similar to the input. The unitary operator implementing this transformation can be formulated as a sequence of one-qubit and two-qubit elementary quantum gates and is thus the exponential of an ordered quantum Ising model with sequential operations and with pattern-dependent interactions, exactly as in the classical case. Probabilistic quantum memories, that make use of postselection of the measurement result of control qubits, overcome the famed linear storage limitation of their classical counterparts because they permit to completely eliminate crosstalk and spurious memories. The number of control qubits plays the role of an inverse fictitious temperature. The accuracy of pattern retrieval can be tuned by lowering the fictitious temperature under a critical value for quantum content association while the complexity of the retrieval algorithm remains polynomial for any number of patterns polynomial in the number of qubits. These models thus solve the capacity shortage problem of classical associative memories, providing a polynomial improvement in capacity. The price to pay is the probabilistic nature of information retrieval.
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(eC1N), ${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.
Quantum associative memories (QAM) have storage capacity exponentially larger than classical associative memories. Given an input with n bits, the QAM can load all of 2n binary patterns. In this paper we propose a nonunitary quantum memory retrieval algorithm. The proposed method is used to recover incomplete input information and also in pattern classification task as an ensemble of memories. The advantages of the proposed method are the simplicity of recovery procedure in a unique iteration and the fact the circuit has linear complexity in function of the input length with deterministic output.
We address the question of quantum memory storage for quantum dynamics. In particular, we design an optimal protocol for N→1 probabilistic storage and retrieval of unitary channels on d-dimensional quantum systems. If we access the unknown unitary gate only N times, the optimal success probability of perfect single-use retrieval is N/(N-1+d^{2}). The derived size of the memory system exponentially improves the known upper bound on the size of the program register needed for probabilistic programmable quantum processors. Our results are closely related to probabilistic perfect alignment of reference frames and probabilistic port-based teleportation.
Quantum associative memory (QuAM) in the domain of quantum computation is a model with a capacity exponential in the number of neurons. Most quantum machine learning algorithms including quantum associative memory suffer from the input destruction problem where the classical data must be read and after the measurement the superposition collapses. Most quantum machine learning algorithms including quantum associative memory suffer from the input destruction problem. The efficient preparation of data is possible in part for spares data. However, the input destruction problem is not solved till today, and usually theoretical speed ups are analyzed by ignoring the input problem, which is the main bottleneck for data encoding. The naming of the phases is in analogy to a living organism that prepares itself during the sleep for an active day. The advantage of quantum approach is present in the active phase.
Machine learning (ML) classification tasks can be carried out on a quantum computer (QC) using probabilistic quantum memory (PQM) and its extension, parametric PQM (P-PQM), by calculating the Hamming distance between an input pattern and a database of
rpatterns containing
zfeatures with
adistinct attributes. For PQM and P-PQM to correctly compute the Hamming distance, the feature must be encoded using one-hot encoding, which is memory intensive for multiattribute datasets with
a>2. We can represent multiattribute data more compactly by replacing one-hot encoding with label encoding; both encodings yield the same Hamming distance. Implementing this replacement on a classical computer is trivial. However, replacing these encoding schemes on a QC is not straightforward because PQM and P-PQM operate at the bit level, rather than at the feature level (a feature is represented by a binary string of 0’s and 1’s). We present an enhanced P-PQM, called efficient P-PQM (EP-PQM), that allows label encoding of data stored in a PQM data structure and reduces the circuit depth of the data storage and retrieval procedures. We show implementations for an ideal QC and a noisy intermediate-scale quantum (NISQ) device. Our complexity analysis shows that the EP-PQM approach requires
O(zlog2(a))qubits as opposed to
O(za)qubits for P-PQM. EP-PQM also requires fewer gates, reducing gate count from
O(rza)to
O(rzlog2(a)). For five datasets, we demonstrate that training an ML classification model using EP-PQM requires 48% to 77% fewer qubits than P-PQM for datasets with
a>2. EP-PQM reduces circuit depth in the range of 60% to 96%, depending on the dataset. The depth decreases further with a decomposed circuit, ranging between 94% and 99%. EP-PQM requires less space; thus, it can train on and classify larger datasets than previous PQM implementations on NISQ devices. Furthermore, reducing the number of gates speeds up the classification and reduces the noise associated with deep quantum circuits. Thus, EP-PQM brings us closer to scalable ML on an NISQ device.