Concise Quantum Associative Memories with Nonlinear Search Algorithm

The model of quantum associative memories proposed here is quietly similar to that of Rigui Zhou et al. [1] based on quantum matrix with binary decision diagram and nonlinear search algorithm put forth by David Rosenbaum [2] and Abrams and Llyod [3] respectively. Our model that simplifies and generalizes that of Ref. [1], gives the possibility to retrieve one of the sought states in multi-values retrieving, when a measure on the first register is done. If n is the number of qubit of the first register, p ≤ 2n the number of stored patterns, q ≤ p the number of stored patterns if the values of t are known (i.e., t qubits have been measured or are already be disentangled to others, or the oracle acts on a subspace of (n − t) qubits), m ≤ q the number of values x for which f(x) = 1, c = ceil(log2 q) the least integer greater or equal to log2 q, and r = int(log2m) the integer part of log2m, then the time complexity of our algorithm is O(c − r). It is better than Grover’s algorithm and its modified form which need O