Research On Quantum K-Nearest-Neighbor And K-Means Algorithms Based On Divide-and-Conquer Strategy

Machine learning algorithms have received extensive attention from the scientific community since their introduction and have experienced rapid development in recent decades.Machine learning algorithms have pervaded various aspects of human life,including but not limited to industrial,medical,financial,and self-media fields.As the size and the dimensionality of datasets continue to expand,the performance of classical machine learning algorithms gradually becomes inadequate to meet practical demands.How to leverage the features of quantum computing to optimize classical machine learning algorithms has become a highly researched area of interest.The K-nearestneighbor algorithm performs classification tasks on unknown data based on known labeled data.The K-means algorithm can classify unknown data into different clusters without relying on known labeled data.In this paper,these two similar machine learning algorithms are improved based on quantum computing theory and divide-andconquer strategy.The specific research work is as follows:The K-nearest-neighbor algorithm is one of the most frequently used machine learning algorithms.Similarity calculation is considered the most crucial and timeconsuming step of the classical K-nearest-neighbor.A quantum K-nearest-neighbor classification algorithm is proposed based on quantum computing theory.A quantum circuit based on the divide-and-conquer strategy is designed to calculate the fidelity between the test sample set and each sample in the training set.The quantum K-nearestneighbor algorithm is more efficient than the classical K-nearest-neighbor algorithm for processing high-dimensional datasets.The proposed algorithm provides a classification accuracy comparable to the classical K-nearest-neighbor algorithm on the IRIS dataset.The classification algorithm achieves higher accuracy with less running time than the typical quantum K-nearest-neighbor algorithm.Similar to the K-nearest-neighbor algorithm,the K-means algorithm is a typical machine learning algorithm based on distance calculation.The distance calculation process of the K-means algorithm requires a significant time cost,and the algorithm is prone to getting stuck in local optima due to its sensitivity to the selection of initial cluster centroids.A quantum K-means clustering algorithm is presented based on the divide-and-conquer theory and the initial clustering optimization strategy.A quantum distance measurement circuit containing parameter s is designed in this algorithm to calculate the relative distance between sample points and cluster centroids.The parameter s allows flexible adjustment of the depth and width of the distance measurement circuit.Theoretical analysis indicates that the quantum K-means clustering algorithm has lower time complexity than the classical algorithm when dealing with high-dimensional data.The quantum K-means algorithm achieved satisfactory clustering results in experiments on the Iris and Banknote datasets,considering evaluation metrics such as the silhouette coefficient and the CalinskiHarabasz index.Comparative experiments demonstrate that the proposed quantum Kmeans algorithm can complete clustering tasks with fewer iterations than the classical K-means clustering algorithm and typical quantum K-means clustering algorithm.