Research On Quantum Algorithm For Dimension Reduction

The development of quantum computing poses a challenge to the security of classical cryptographic algorithms.For example,the proposal of Shor’s algorithm poses a serious threat to the security of the widely used RSA public key cryptography.The proposal of Grover’s algorithm also greatly weakens the security of symmetric encryption algorithms.Studying the possible applications of quantum computing in more fields has important reference value for designing new cryptanalysis quantum algorithms and exploring the boundaries of quantum computing capabilities.As an important branch of machine learning and data mining,dimensionality reduction aims to reduce the dimensionality of the original data set while maintaining the specific information.Dimensionality reduction is usually used in the data preprocessing step of other algorithms,which plays an important role in alleviating the curse of dimensionality and reducing the complexity of subsequent algorithms.In today’s big data era,with the exponential growth of data scale,dimensionality reduction faces the challenges of computational performance.To solve this problem,in recent years,researchers have introduced quantum computing to dimensionality reduction and designed a series of quantum algorithms with lower complexity than classical dimensionality reduction algorithms.But in general,the field of quantum dimensionality reduction algorithms is still in its infancy,and some important dimensionality reduction problems cannot be solved by existing quantum algorithms.In response to this problem,we propose four quantum dimensionality reduction algorithms,corresponding to four scenarios of three different dimensionality reduction problems.The proposed quantum algorithms have obvious acceleration compared to the classical algorithms.The main works and contributions of this dissertation are as follows:1.A quantum algorithm is proposed for neighborhood preserving embedding which is a dimensionality reduction algorithm that reduces the dimensionality of the data while preserving the local linear manifold structure.The algorithm includes three quantum sub-algorithms,corresponding to the three steps of the classical algorithm respectively.The first sub-algorithm finds the set of neighbors for each data point through quantum amplitude estimation and quantum amplitude amplification,and stores the neighborhood information in a quantum-accessible data structure.The second sub-algorithm uses quantum matrix inversion to get the corresponding quantum states of each column of the weight matrix W one by one,and then obtains its classical information through quantum state tomography.Finally,the classical information of W is stored in a quantum-accessible data structure.The third sub-algorithm uses the quantum singular value estimation technique,the quantum algorithm for finding the minimum and the quantum ridge regression technique to find the projection matrix successively.Under certain conditions,compared with the classical algorithm,our algorithm has a polynomial speedup on the number of data samples,and exponential speedup on the data space dimension.2.For the two scenarios of the spectral regression,which is a framework of dimensionality reduction,a quantum algorithm is proposed respectively.The spectral regression framework includes many dimensionality reduction algorithms,such as the NPE algorithm.Existing quantum algorithms are based on the scenario where the intermediate matrix L is stored in a quantum-accessible data structure,where L=D-1/2WD-1/2,while in practical applications the information of L is often unknown.To address this problem,we propose an improved quantum algorithm based on the weaker assumption that only the information of the weight matrix W is stored in a quantum-accessible data structure.When W is a dense matrix,our algorithm has a polynomial speedup over the existing quantum algorithm,and when W is sparse,our algorithm has the same complexity as the existing quantum algorithm.In addition,a widely used scenario in spectral regression,i.e.,the scenario of using label information to construct W,cannot be solved by the existing quantum algorithm and the above improved algorithm.In response to this problem,we propose a quantum algorithm,which designs the more complex part of spectral regression,i.e.,the ridge regression into a quantum algorithm,and obtains multiple ridge regression results in parallel.Compared with the classical algorithm,Our algorithm has an exponential acceleration on the dimension of the data space.3.A quantum algorithm is proposed for A-optimal projection,an algorithm that minimizes the prediction error of regression models in low-dimensional embedding subspace while reducing the dimensionality of the original data set.The complexity of the A-optimal algorithm is linearly dependent on the number of iterations s while the complexity of the existing quantum algorithm is exponentially dependent on s,which makes the existing quantum algorithm only applicable when s is relatively small.Aiming at this problem,a quantum algorithm is proposed,which encodes the amplitude information into the quantum state in binary form,and then outputs the key information of each iteration as reusable classical information,thus reducing the consumption of the copies of the current candidate.since the complexity of Our algorithm has a square dependence on s,and the dependence on other parameters is also lower than that of the existing quantum algorithm,our algorithm realizes an acceleration of the existing quantum algorithm.In addition,the estimation of s is given by numerical experiments.When κ,k and 1/? take the value of O(polylog(nm))(κ is the condition number of the matrix related to the original data set,k is the dimensionality of the low-dimensional embedding subspace,m is the number of data samples,and n is the dimensionality of the data space),compared with the classical algorithm,our algorithm has an exponential speedup on n and m.