Title: AN ASSOCIATIVE MODEL BASED ON QUANTUM SEARCH ALGORITHMS

Year of Publication: 2013
Page Numbers: 98-107
Authors: Hiromi Miyajima, Masataka Fujisaki, Noritaka Shigei
Conference Name: The Second International Conference on Digital Enterprise and Information Systems (DEIS2013)
- Malaysia

Abstract:


In this paper, an algorithm of quantum associative memory is proposed using quantum search algorithms. In the associative memory, the problem is to find the data or the nearest data in the meaning of hamming distance from designated data. If the search data in memorized dataset is contained, the problem becomes data search one. In associative memory, it is difficult to find the nearest data in hamming distance. For searching any item in an unsorted database with N items, a classical takes O(N) steps but Grover’s quantum searching algorithm takes only O(pN) steps on perfect graph. By generalizing the idea, Ventura has proposed the associative memory model, but it does not solve the problem of finding the nearest data. On the other hand, quantum search algorithm with O(pN) steps on hypercube is also proposed. Therefore, the idea in this paper is formalizing the problem as quantum search algorithm in hypercube but not in the conventional perfect graph. First, we perform quantum search algorithm by considering quantum walk on hypercube. Further, it is observed search data or the nearest data by using the conventional algorithm with high probability.