Research On Quantum Algorithms For Matrix Eigenproblem

Matrix eigen-problem has wide applications in mathematics,data science,machine learning,quantum computing,cryptography and other fields.For example,the multi-party strict coin-tossing protocol based on the eigenvalue of the secret matrix can not only resist matrix tampering attacks,but also has the advantage of low complexity and practicability.In the age of big data,with the exponential growth of data scale,how to efficiently solve large-scale matrix eigen-problem has been a hot research issue for scholars from all over the world.At the same time,the complexity of solving the problem and the high requirement of the algorithm precision in the industrial and commercial fields make the computational performance of the current classical computer facing severe challenges.If the method of the classical computer is used to deal with the problem,the computational resources required will be unacceptable.To meet this challenge,exploring an efficient algorithm for solving matrix eigen-problem is of great research significance.Quantum computing has the capability of parallel computing due to the unique superposition property of quantum states.This capability enables quantum computing to achieve polynomial or even exponential acceleration in solving some specific problems compared with classical counterpart.With the rapid development of quantum technology,researchers have proposed a variety of quantum algorithms with remarkable acceleration effects to solve matrix eigen-problem.However,so far,the relevant research is still in the initial stage,and some important matrix eigen-problem have not yet corresponding efficient quantum algorithms,which need to be further explored.This thesis carries out relevant research on solving matrix eigen-problem by quantum technology,mainly including the design of quantum algorithms with significant acceleration effect compared with the classical counterpart,that is,solving eigen-problem of the Laplacian matrix of a fully connected weighted graph and matrix eigen-problem with mean centering.as well as designing a variational quantum algorithm to solve the Poisson equation.Its essence lies in designing a variational quantum algorithm to solve the eigenvector corresponding to the minimum eigenvalue of a particular Hamiltonian matrix(related to linear systems generated by the discretization of the Poisson equation),that is,the ground state problem.The proposed quantum algorithm is expected to promote the cross-integration of quantum computing,mathematics and machine learning,and may also provide important references for designing new quantum algorithms to solve cryptography problems in the future.Specifically,the main contributions of this thesis include the following three aspects:1.A quantum algorithm is proposed for solving eigen-problem of the Laplacian matrix of a fully connected weighted graph.The corresponding eigen-problem has wide applications in graph network,image processing,reinforcement learning and so on.The optimal Hamiltonian simulation based on the block-encoding framework and phase estimation techniques are adopted to design the quantum algorithm.The main innovation of quantum technology is to design the specific controlled unitary operators and combine some basic quantum algorithms such as controlled rotation operator and amplitude amplification to construct block-encodings of the weight matrix and the degree matrix,and then obtain the block-encoding of the Laplacian matrix(the difference between the weight matrix and the degree matrix).Compared with its classical counterpart,this algorithm has a polynomial speedup on the number of vertices and an exponential speedup on the dimension of each vertex.The quantum algorithm can also be extended to solve eigen-problems of the weight matrix,symmetric and asymmetric normalized Laplacian matrix.2.A quantum algorithm is proposed for solving matrix eigen-problem with mean centering pre-processing.Mean centering is an important data preprocessing technology,which has a wide range of applications in data mining,machine learning and multivariate statistical analysis.And many classical problems involving mean centering(such as principal component analysis)can be reduced to solving the eigen-problem of the corresponding mean-centered data matrix.Faced with the massive growth of data sets,solving the above problem classically needs to consume a large amount of computing resources.Therefore,an efficient quantum algorithm based on block-encoding is designed to solve this problem.Specifically,the strategy of multiplying by the centering matrix is first adopted to simplify the process of mean centering.Secondly,the block-encoding of the mean-centered data matrix is constructed.Finally,how to apply it to solving matrix eigen-problem of classical algorithms is analyzed in detail.It is worth noting that this algorithm not only reduces the dependence of the existing quantum mean centering algorithm’s complexity on the inverse of the error,but also is more suitable for algorithms involving matrix algebra problems,such as extreme learning machine.3.A variational quantum algorithm is proposed for solving the Poisson equation.The essence of this algorithm is to transform the problem of the linear system derived from the finite-difference method to discretize the Poisson equation into the ground state problem of a specific Hamiltonian matrix,and then design a variational quantum algorithm to solve the corresponding ground state problem.This quantum algorithm can not only be realized on noisy intermediate-scale quantum devices,but also is expected to show potential quantum advantages.Our works as shown below:Firstly,finding an explicit tensor product decomposition of the coefficient matrix A of the above linear system under a set of simple operators {I,σ+=|0><1|,σ_=|1><0|} which mainly utilize the special symmetric structure of the coefficient matrix A.And the number of decomposition items is only(2log(n)+1),where n is the dimension of the coefficient matrix,which means that the proposed algorithm needs fewer quantum measurement terms than the decomposition under the Pauli basis and will save quantum resources.Secondly,to efficiently evaluate the expectation values of the above simple operators on a quantum computer,the corresponding quantum observables are designed.Thirdly,in order to show that the algorithm can solve the Poisson equation,numerical simulation experiments are carried out on the PROJECTQ simulator.In addition,the proposed algorithm can also be used to solve the one-dimensional Poisson equations of other boundaries(e.g.,Von Neumann,Robin)and the general the general tridiagonal and pentadiagonal Toeplitz systems.