Quantum Hierarchical Clustering And Its Related Subalgorithms

Hierarchical clustering is the key way to learn the rules of things and find the information contained in things.However,with the rapid development of scientific and technological information,classical algorithms are weak in the face of the exponential growth of data.And,classical hierarchical clustering algorithms are also difficult to efficiently apply in a large number of high-dimensional data.Scholars have incorporated quantum mechanics theory into classical machine learning algorithms to solve some problems that are intractable for traditional computers.In this case,many quantum algorithms have emerged.More and more quantum algorithms are showing impressive speed advantages for solving specific problems.In this thesis,we combine the theory,thinking,and techniques of quantum computing with hierarchical clustering.The characteristics of quantum computing are used to preprocess dimensionality reduction of data,estimate the similarity between the data and aggregate the similar data together.These works could improve the running efficiency of the classical hierarchical clustering algorithm and provide a new idea for other quantum algorithms.The specific work of this study includes:1.Designing a quantum data dimension reduction based on linear discriminant analysis.Taking the high-dimensional data marked by simple categories but still needing clustering to discover the correlation or deep information between them as the research object,we map them from the exponential high-dimensional space to the low-dimensional space.Firstly,the proposed algorithm improves the existing dimensionality reduction algorithm of quantum linear discriminant analysis,which avoid the error caused by the irreversibility of the inter-class matrix in the original algorithm.Secondly,the proposed quantum data dimensionality reduction algorithm and the corresponding quantum circuit can not only obtain the projection direction but also obtain the corresponding quantum states of all the data in the low-dimensional space.Thus,the obtained quantum data can be directly applied to other quantum algorithms to avoid the "dimensional disaster".Moreover,compared with the classical algorithm,the quantum algorithm has the effect of exponential acceleration in the number of data and quadratic acceleration in the dimension scale of the original high-dimensional space when the dimension of the pre-reduced low-dimensional space is a logarithmic polynomial of the original high-dimensional space dimension.2.Proposing a quantum hierarchical clustering algorithm based on Euclidean distance is proposed.Firstly,a quantum algorithm based on Euclidean distance similarity is proposed to estimate the similarity between data sets,which is the core task of hierarchical clustering.In this way,the average linkage,the complete linkage,and the single linkage are used to describe the similarity between data sets.Then,using quantum entanglement,parallelism,and other properties,the results of the three measurement methods are estimated by using quantum measurement technology.Compared with the classical algorithm,the quantum similarity estimation algorithm can achieve exponential acceleration in the number or dimension of the sample space.Finally,the quantum hierarchical agglomeration clustering process of quantum-classical interaction is given,and it is proved that quantum computer can effectively accelerate the classical hierarchical clustering algorithm.The thesis shows that it is feasible to implement classical hierarchical clustering and its related subalgorithms by using theories and techniques of quantum computing.In addition,the proposed quantum algorithms have a certain speed advantage,which provides an efficient scheme for learning data information and rules in the era of "big data".What's more,this study has the potential to provide a reference for other quantum algorithms.