Research On Quantum Algorithms For Several Data Mining Problems

As an interdisciplinary subfield of computer science and statistics,data mining aims to mine some hidden valuable information from a large dataset,which is the key step in knowledge discovery.In addition,data mining can be used to analyze the security of cryptosystems by mining patterns from plaintext and ciphertext,thus it is also an important tool for cryptanalysis.However,with rapid development of information technology,global data grows exponentially every year,which poses great challenges to the computational performance of classical data mining algorithms for tackling big data in the future.Quantum computing makes use of quantum mechanical principals(such as quantum superposition and quantum entanglement)to perform computational tasks,and exhibits significant speedup over classical computing for solving certain problems.For examples,Shor's quantum algorithm for factoring large numbers achieves exponential speedup over the classical algorithms,seriously threatening the security of widely used RSA ciyptosystems.In recent years,quantum computing has been applied to the field of data mining,and a number of efficient quantum algorithms for various big data mining problems have been proposed.However,the development of quantum data mining algorithms is still in its infancy,and there are still a number of data mining problems for which no efficient quantum algorithm has ever been proposed.This dissertation per-forms further study in this direction,and puts forward quantum algorithms for solving several important data mining problems,which are significantly faster than their classical counterparts.The proposed quantum algorithms can also serve as important references for designing quantum cryptanalysis algorithms.In detail,this dissertation includes four aspects as shown below.1.A quantum algorithm is proposed to address the key task of association rules mining,finding out frequent itemsets from the candidate itemsets.Specif-ically,for the case in which there are Mf(k)frequent k-itemsets in the MC(k)candi-date k-itemsets(Mf(k)?Mc(k)),the algorithm can efficiently mine these frequent k-itemsets and estimate their supports by using parallel amplitude estimation and amplitude amplification with complexity O(k(?)),wheere ? isthe error for estimating the supports.Compared with the classical counterpart whose complexity is O(kMc(k)/?2),our quantum algorithm quadratically im-proves the dependence on both ? and Mc(k)in the best case when Mf(k)?Mc(k)and on ? alone in the worst case when Mf(k)?Mc(k).2.Based on principal component analysis(PCA),the most popular clas-sical dimensionality reduction algorithm,a quantum algorithm for data dimen-sionality reduction is proposed.It in quantum parallel proj ects an exponentially large high-dimensional dataset onto a lower-dimensional space,and obtains a corresponding lower-dimensional dataset.The proposed algorithm achieves ex-ponential speedup over the classical PCA algorithm when the dimension of the lower-dimensional space,denoted by d,and the dimension of the original high-dimensional space,denoted by D,satisfy d=D(polylogD).Moreover,it is also shown that the algorithm can be applied to two important quantum ma-chine learning algorithms:quantum support vector machine and quantum linear regression for prediction,to release them from "the curse of dimensionality".3.A quantum algorithm for ridge regression(RR),a linear regression method which introduces regularization to ordinary linear regression for an-alyzing data suffering from multicollimearity,is put forward.By designing par-allel Hamiltonian simulation that can simulate a number of Hermitian matrices in parallel.the algoitlum presents a quantum version of K-fold cross-validation approach to efficiently estimate the predictive performance of RR.The whole algorithm in the first place uses the quantum K-fold cross-validation to effi-ciently determine a good regularization hyperparameter for RR with which RR can achieve good predictive performance,and then generates a quantum state encoding the optimal fitting parameters of RR with such hyperparameter,which can be further utilized to predict new data.Since the dense Hamiltonian simula-tion is adopted as the basic subroutine,the algorithm is able to handle non-sparse data matrices.Furthermore,our algorithm can achieve exponential speedup over the classical counterpart when K=O(polylog N),where K and N are the condition number and the dimension of the data matrix,respectively.When K is large to be amenable to full or approximately full ranks of the data matrix,polynomial speedup can be achieved.4.Based on a famous classical visual tracking algorithm proposed in re-cent years,a quantum algorithm for visual tracking is proposed.It comprises two phases:training and detection.In the training phase,in order to discrimi-nate the obj ect and background,the algorithm trains a ridge regression classifier in the quantum state form,where the optimal fitting parameters of ridge regres-sion are encoded in the amplitudes.In the detection phase,the classifier is then employed to generate a quantum state whose amplitudes encode the responses of all the candidate image patches.The proposed algoritlim is exponentially faster than the classical counterpart when KX,KZ=O(polylogn),where KX and KZ are respectively the condition number of image matrix in the training phase and the detection phase,and n is the dimension of data matrices in both phases.In addition,this dissertation also discusses how to apply this algorithm to solve two problems related to visual tracking:(1)object disappearance detection and(2)motion behavior matching.The algorithm demonstrates the power of quan-tum computing in solving computer vision problems.