Quantum Newton's method for solving system of nonlinear algebraic equations

Abstract

While quantum computing provides an exponential advantage in solving system of linear equations, there is little work to solve system of nonlinear equations with quantum computing. We propose quantum Newton's method (QNM) for solving $N$-dimensional system of nonlinear equations based on Newton's method. In QNM, we solve the system of linear equations in each iteration of Newton's method with quantum linear system solver. We use a specific quantum data structure and $l_{\infty }$ tomography with sample error ${\epsilon }_s$ to implement the classical-quantum data conversion process between the two iterations of QNM, thereby constructing the whole process of QNM. The complexity of QNM in each iteration is $O({\log }^{4}N/{\epsilon }_s^2)$. Through numerical simulation, we find that when ${\epsilon }_s>>1/\sqrt{N}$, QNM is still effective, so the complexity of QNM is sublinear with $N$, which provides quantum advantage compared with the optimal classical algorithm.

arXiv comment8 pages, 4 figures

References in corpus (15)

• Quantum algorithm for solving linear systems of equations
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Variational quantum algorithms for nonlinear problems
• Architectures for a quantum random access memory
• Preconditioned quantum linear system algorithm
• High-order quantum algorithm for solving linear differential equations
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Quantum algorithms and the finite element method
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum Algorithm for Simulating the Wave Equation
• Quantum spectral methods for differential equations
• Quantum algorithm for non-homogeneous linear partial differential equations
• A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment
• Quantum Analog-Digital Conversion
• Quantum Algorithm for the Vlasov Equation

Cited by in corpus (4)

• A hybrid quantum-classical framework for computational fluid dynamics
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• Nonlinear path-following via the asymptotic numerical method on a quantum processor
• Quantum Algorithm For Solving Nonlinear Algebraic Equations