Research On Quantum Dimension Reduction Algorithm

Because of the parallelism of quantum computing,quantum computing has attracted extensive attention.Compared with classical algorithms,quantum algorithms can achieve polynomial acceleration or even exponential acceleration by using the unique entanglement,superposition and coherence of quantum systems.Although the running time of quantum algorithm is shorter,when the dimension of data is too high,quantum algorithm will fall into"dimension curse"like classical algorithm,that is,as the dimension of data becomes higher,the amount of calculation increases exponentially.Dimensionality reduction algorithm,which maps high-dimensional data into low-dimensional data,is a method to solve the problem of"dimension curse"in classical computing.Similarly,in order to solve the problem of"dimension disaster"in quantum computing,this paper studies the quantum dimension reduction algorithm.The specific research work and results are as follows.（1）A quantum locality preserving projections algorithm（QLPP）for dimension reduction algorithm is proposed by using the quantum algorithm for solving linear equations.locality preserving projections（LPP）is a linear classical dimensionality reduction algorithm.Compared with other linear dimensionality reduction algorithms,LPP can maintain the local neighborhood information of the original data to a certain extent.Compared with the nonlinear dimensionality reduction algorithm,LPP can map new data into low dimensional space,and the amount of computation of LPP is less.Therefore,LPP is widely used in face recognition and other fields.QLPP first uses the quantum algorithm for solving linear equations to find the density matrix proportional to the symmetric matrix,and then uses quantum phase estimation（QPE）to find the eigenvector of the density matrix.The computational complexity analysis shows that when the number of data is m,the data dimension is n and the error is ε,the computational complexity of QLPP is （?）,where k_eff is a predefined condition number and d is the dimension of low dimensional space.The computational complexity of LPP is O（m²n）,that is,compared with LPP,QLPP realizes polynomial acceleration.（2）Based on quantum analog-digital conversion（QADC）and quantum amplitude estimation（QAE）,a quantum metric multidimensional scaling algorithm（QMDS）for dimensionality reduction is proposed.Metric multidimensional scaling（MDS）is a classical dimensionality reduction algorithm that requires the Euclidean distance between any two data before and after dimensionality reduction to remain unchanged.It is widely used in data visualization,positioning,human motion capture and other fields.Firstly,this paper designs a method to encode the part of amplitude of quantum states into qubit strings by using QADC and QAE.Then,QMDS is designed by using this method,and the specific process of each step of QMDS is given in detail.The computational complexity analysis shows that when the number of data is m and the error is ε,the computational complexity of MDS is O（m³）,the computational complexity of QMDS is （?）,that is,compared with MDS,QMDS realizes polynomial acceleration,whereis the condition number of matrix B^TB,B=X^TX and X is the original data matrix.