Quantum Algorithm For Solving Nonlinear Algebraic Equations

Abstract

Nonlinear equations are challenging to solve due to their inherently nonlinear nature. As analytical solutions typically do not exist, numerical methods have been developed to tackle their solutions. In this article, we give a quantum algorithm for solving a system of nonlinear algebraic equations, in which each equation is a multivariate polynomial of known coefficients. Building upon the classical Newton method and some recent works on quantum algorithm plus block encoding from the quantum singular value transformation, we show how to invert the Jacobian matrix to execute Newton's iterative method for solving nonlinear equations, where each contributing equation is a homogeneous polynomial of an even degree. A detailed analysis are then carried out to reveal that our method achieves polylogarithmic time in relative to the number of variables. Furthermore, the number of required qubits is logarithmic in the number of variables. In particular, we also show that our method can be modified with little effort to deal with polynomial of various types, thus implying the generality of our approach. Some examples coming from physics and algebraic geometry, such as Gross-Pitaevski equation, Lotka-Volterra equations, and intersection of algebraic varieties, involving nonlinear partial differential equations are provided to motivate the potential application, with a description on how to extend our algorithm with even less effort in such a scenario. Our work thus marks a further important step towards quantum advantage in nonlinear science, enabled by the framework of quantum singular value transformation.

References in corpus (25)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• Quantum algorithm for solving linear systems of equations
• Quantum machine learning in feature Hilbert spaces
• Quantum Amplitude Amplification and Estimation
• Evaluating analytic gradients on quantum hardware
• Circuit-centric quantum classifiers
• Hamiltonian Simulation by Qubitization
• Exponential algorithmic speedup by quantum walk
• Optimal Hamiltonian Simulation by Quantum Signal Processing
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Efficient quantum algorithms for simulating sparse Hamiltonians
• The quest for a Quantum Neural Network
• Quantum algorithm for systems of linear equations with exponentially improved dependence on precision
• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics
• Quantum Data Fitting
• Hamiltonian simulation with nearly optimal dependence on all parameters
• High-order quantum algorithm for solving linear differential equations
• Efficient quantum algorithm for dissipative nonlinear differential equations
• Scaling of variational quantum circuit depth for condensed matter systems
• Decomposition of Unitary Matrices for Finding Quantum Circuits: Application to Molecular Hamiltonians
• Quantum Algorithms for Estimating Physical Quantities using Block-Encodings
• Approximate Quantum Circuit Synthesis using Block-Encodings
• A variational quantum algorithm for the Feynman-Kac formula
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• Quantum Newton's method for solving system of nonlinear algebraic equations