Quantum Nearest Neighbor Classification Algorithm And Its Applications

Machine learning is one of branches in the field of artificial intelligence.With the demand for data analysis in various industries in the era of big data increasing,acquiring knowledge efficiently via machine learning has gradually become the main driving force for the development of machine learning.However,the amount of global data grows exponentially every year,which makes the classical machine algorithms face great challenges in computing performance in the future.With the emergence of quantum computing,a new way is provided to solve some machine learning problems with high computational complexity so that machine learning has a new research direction.Quantum machine learning is a quantum version of machine learning algorithm constructed by quantum computing,which can achieve quantum acceleration which is a potential advantage of that.In recent years,quantum computation has been applied to machine learning,and efficient quantum algorithms to solve a variety of data mining problems have been proposed.In this thesis,the nearest neighbor classifier is mainly studied,and two quantum nearest neighbor classification algorithms with significant acceleration are proposed.The main contents of this thesis are as follows.1.A quantum nearest neighbor classification algorithm based on Hamming distance and its application are proposed.In this algorithm,quantum computation is utilized to obtain Hamming distance in parallel at first.Then,a core sub algorithm for searching the minimum of unordered integer sequence is presented to find out the minimum distance.Based on these two sub algorithms,the whole quantum frame of nearest neighbor classification algorithm is presented.It is shown that the presented algorithm can achieve a significant speedup by analyzing its time complexity briefly.At last,an application in image classification is proposed,which effectively speeds up the classification process.2.A quantum selective nearest neighbor classification algorithm and its application are proposed.By setting a threshold ,the training samples whose distance from the test samples are less than are taken as the nearest neighbor samples.In this thesis,presenting a quantum selective nearest neighbor algorithm based on an optimal threshold at first,and then using amplitude estimation techniques to efficiently estimate the classification performance of candidate thresholds.Compared with the classical algorithm,when the sample size is large,the algorithm can achieve a quadratic speedup.In addition,this thesis proposes the application of quantum selective nearest neighbor classification algorithm in the neighborhood preserving embedding algorithm,and gives the basic framework of quantum neighborhood preserving embedding algorithm.