Research On Some Quantum Algorithms For Solving Nonlinear Equations

Quantum computing is a new computing framework developed in recent decades that utilizes the fundamental principles of quantum mechanics.Compared with classical computing,quantum computing provides quantum advantage in solving some specific problems,so it receives extensive attention.Researchers in various fields have begun to try to use quantum computing to speed up the solution of some problems in their fields.Up to now,quantum algorithms have emerged in many disciplines and industries,including number theory,quantum chemistry,optimization,machine learning,finance,and more.An important class of quantum algorithms is to use quantum computing to accelerate some classical numerical computing problems.In 2009,Harrow et al.proposed a quantum algorithm for solving system of linear equations,namely HHL algorithm.Compared with the classical algorithm,HHL algorithm provides an exponential speedup in the dimension of the equation.Since solving system of linear equations is a basic task that widely appears in various problems in academia and industry,a series of new quantum algorithms have been derived based on HHL algorithm,including the optimization of HHL algorithm,quantum machine learning algorithms,quantum optimization algorithms,quantum algorithms for solving linear ordinary differential equations,quantum algorithms for solving linear partial differential equations,etc.At present,the development of quantum algorithms for solving linear problems has been relatively mature,and researchers begin to focus on intersection of nonlinear problems and quantum computing.Nonlinear problems are a class of problems that appear more widely in nature.Compared with linear problems,the difficulty of solving nonlinear problems is greatly increased.When the scale of the nonlinear problem is relatively large,the computing resources required for the solution process may exceed the computing power of the classical computer.A new research idea is to use quantum computing to accelerate the solution of nonlinear problems.However,due to the linearity of quantum mechanics,there are some challenges in constructing quantum algorithms for solving nonlinear problems.At present,there are relatively few quantum algorithms for solving nonlinear problems.The main research content of this thesis is to construct quantum algorithms for solving nonlinear problems.We propose three quantum algorithms for solving nonlinear equations.The details are as follows:1.First of all,we propose a quantum finite volume method for solving computational fluid dynamics equations.The core idea of the quantum finite volume method is to solve the system of linear equations of each iteration step with quantum linear system solver and construct the classical-quantum data conversion process of in each iteration with the help of quantum data storage structure and a sample algorithm.We analyze the complexity of the quantum finite volume method,and do some related numerical simulations,and finally verify the quantum advantage of the quantum finite volume method.2.Then we use a similar idea to the quantum finite volume method to construct a quantum Newton’s method for solving system of nonlinear equations.The core idea of the quantum Newton’s method is also to solve the system of linear equations of each iteration step with quantum linear system solver and construct the classical-quantum data conversion process of in each iteration with the help of quantum data storage structure and a sample algorithm.Through complexity analysis and numerical simulation,we also verify the quantum advantage of quantum Newton’s method.3.Both the quantum finite volume method and the quantum Newton’s method have some limitations.Specifically,these two algorithms are iterative algorithms.Each iteration includes the classical-quantum data conversion process.We use a quantum data storage structure and a sampling algorithm to build a process that compresses the resource consumption of the classical-quantum data conversion process as much as possible,but it still leads to a decrease in the performance of the two algorithms.To overcome the above limitations,we construct a quantum algorithm for solving weak nonlinear equations,namely the quantum homotopy perturbation method.The core idea of the quantum homotopy perturbation method is to use the homotopy perturbation method to construct a linearization process that embeds weak nonlinear equations into finite-dimensional linear equations,and then solves the linear equations with quantum algorithms.We use the quantum homotopy perturbation method to solve quadratic nonlinear system of equations and dissipative quadratic nonlinear ordinary differential equations,then we analyze the performance of the quantum homotopy perturbation method in solving these two kinds of equations and derive the whole complexity expression.Compared with the classical algorithm,the quantum homotopy perturbation method provides an exponential acceleration in the dimension of the equations,and the dependence of the algorithm complexity on the solution error is also logarithmic,which is the optimal result known so far.All in all,our work expands the application range of quantum computing from linear problems to nonlinear problems,fills some gaps in the research field of quantum algorithms for solving nonlinear problems,and provides references for subsequent related research.