基于Hamming距离和量子搜索算法的联想分类器设计  

Design of Associative Classifier Based on Hamming Distance and Quantum Search Algorithm

作　　者：肖红[1] 刘新彤 XIAO Hong;LIU Xintong(School of Computer and Information Technology,Northeast Petroleum University,Daqing 163318,Heilongjiang Province,China)

机构地区：[1]东北石油大学计算机与信息技术学院,黑龙江大庆163318

出　　处：《吉林大学学报（理学版）》2024年第6期1426-1438,共13页Journal of Jilin University:Science Edition

基　　金：黑龙江省自然科学基金(批准号:LH2019F004).

摘　　要：针对现有联想分类器不能存储重复样本的问题,提出一种基于Hamming距离和量子搜索算法的量子联想分类器设计方法,并给出联想分类器存储和分类的线路图.该方法需提前准备5组量子比特,分别对Hamming距离、输入样本、模式样本、类别和序号进行编码.首先,根据样本总体N,计算联想分类器所需的量子位数,再利用量子旋转门和Hadamard门将初态为|0〉的量子位旋转为恰好包含N个基态的均衡叠加态;其次,根据待存储样本的类别和值,将剩余两组初始状态为|0〉的量子位通过可控操作转换为相应的量子基态;最后,基于量子最小搜索的分类方法,计算输入样本与所有存储样本之间的Ha mming距离,再使用固定相位Grover量子搜索算法搜索这些Hamming距离的最小值,最小值对应存储样本的类别即为输入样本的类别,具体的分类结果可通过测量寄存器中的量子态得到.Aiming at the problem that the existing associative classifier could not store duplicate samples,we proposed a design method of associative classifier based on Hamming distance and quantum search algorithm,and gave a line diagram for the storage and classification of the associative classifier.The method required the preparation of five sets of qubits in advance to encode Hamming distance,input sample,pattern sample,category and sequence number respectively.Firstly,according to the total N of the sample,the number of qubits required by the associative classifier was calculated,and then the qubits with an initial state of |0〉were rotated to an equilibrium superposition state containing exactly N ground states by using the quantum revolving gate and the Hadamard gate.Secondly,according to the category and value of the sample to be stored,the remaining two sets of qubits with initial state of |0〉were converted into the corresponding quantum ground state through controllable operation.Finally,based on the classification method of quantum minimum search,the Hamming distance between the input sample and all the stored samples was calculated,and then the fixed phase Grover quantum search algorithm was used to search for the minimum value of these Hamming distances.The category of the stored sample corresponding to the minimum value was the category of the input sample,and the specific classification results could be obtained by measuring the quantum states in the register.

关 键 词：量子联想分类器 均衡叠加态 HAMMING距离 量子最小搜索 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]