Design of Quantum Associative Classifier based on Hamming Distance and Grover’s Algorithm.

In this paper, we design a quantum associative classifier, which includes pattern storage and pattern classification. For pattern storage, we present a method to construct quantum superposition states with arbitrary number of basis states. The method employs three groups of qubits to encode the sequence number, category, and value of each sample respectively. Firstly, according to the total number of samples N to be stored, the number of sequence number qubits needed by associative classifier is calculated. Then, some quantum rotation gates and Hadamard gates are used to transform the sequence number qubits with initial state of | 0 ⟩ into the quantum equilibrium superposition state which contains exactly N basis states. Finally, according to the category and value of the sample to be stored, the remaining two groups of qubits with initial state of | 0 ⟩ are converted into corresponding quantum basis states by some controlled operations. For associative classification, we design a classification method based on quantum minimum search. Firstly, the Hamming distances between the input sample and all the stored samples are calculated, and then Grover’s algorithm with fixed phase is used to search the minimum value of these Hamming distances. At this time, the category of the stored sample corresponding to the minimum value is the category of the input sample. The specific classification results can be obtained through the measurement of quantum state in the register. The number of iterations of the search is exponentially lower than that of its classical counterpart, so that pattern classification can be realized quickly. [ABSTRACT FROM AUTHOR]