Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations

Abstract

Solving a quadratic nonlinear system of equations (QNSE) is a fundamental, but important, task in nonlinear science. We propose an efficient quantum algorithm for solving $n$-dimensional QNSE. Our algorithm embeds QNSE into a finite-dimensional system of linear equations using the homotopy perturbation method and a linearization technique; then we solve the linear equations with a quantum linear system solver and obtain a state which is $\epsilon$-close to the normalized exact solution of the QNSE with success probability $\Omega (1)$. The complexity of our algorithm is $O(\mathrm{polylog}(n/\epsilon ))$, which provides an exponential improvement over the optimal classical algorithm in dimension $n$, and the dependence on $\epsilon$ is almost optimal. Therefore, our algorithm exponentially accelerates the solution of QNSE and has wide applications in all kinds of nonlinear problems, contributing to the research progress of nonlinear science.

arXiv comment12 pages;

References in corpus (31)

• Quantum algorithm for solving linear systems of equations
• Quantum Amplitude Amplification and Estimation
• Quantum random access memory
• 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
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Solving nonlinear differential equations with differentiable quantum circuits
• Quantum algorithms and the finite element method
• Quantum algorithm and circuit design solving the Poisson equation
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• Variational algorithms for linear algebra
• High-precision quantum algorithms for partial differential equations
• Quantum Algorithm for Simulating the Wave Equation
• Quantum spectral methods for differential equations
• Improved quantum algorithms for linear and nonlinear differential equations
• Quantum algorithm for non-homogeneous linear partial differential equations
• A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment
• Quantum Recommendation Systems
• Quantum Algorithms for Deep Convolutional Neural Networks
• Quantum Algorithm for the Vlasov Equation
• A quantum algorithm to solve nonlinear differential equations
• Quantum algorithm for the Navier Stokes equations by using the streamfunction vorticity formulation and the lattice Boltzmann method
• Algorithm for the solution of the Dirac equation on digital quantum computers
• Challenges for quantum computation of nonlinear dynamical systems using linear representations
• Quantum Newton's method for solving system of nonlinear algebraic equations
• A quantum algorithm for solving systems of nonlinear algebraic equations
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations

Cited by in corpus (4)

• Simulating fluid flows with quantum computing
• Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling
• Nonlinear path-following via the asymptotic numerical method on a quantum processor
• Quantum Algorithm For Solving Nonlinear Algebraic Equations