Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2109.08470 · SPIN

Quantum Newton’s Method for Solving the System of Nonlinear Equations

Cheng Xue, Yu-Chun Wu, Guo‐Ping Guo

Published Sep 1, 2021• 12 citations
arXivHTMLPDF

Abstract

While quantum computing provides an exponential advantage in solving the system of linear equations, there is little work to solve the system of nonlinear equations with quantum computing. We propose quantum Newton’s method (QNM) for solving [Formula: see text]-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 [Formula: see text] tomography with sample error [Formula: see text] 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 [Formula: see text]. Through numerical simulation, we find that when [Formula: see text], QNM is still effective, so the complexity of QNM is sublinear with [Formula: see text], which provides quantum advantage compared with the optimal classical algorithm.

DOI
10.1142/s201032472140004x

Related papers

Solving Nonlinear Partial Differential Equations via a Hybrid Newton Method Using Quantum Linear System Solver

Maximilian Mandelt Buxadé, Stefan Langer, Philipp Bekemeyer

To approximate solutions of complex nonlinear partial differential equations remains a computational challenge, especially for sets of equations relevant in industry, such as Euler or Navier-Stokes equations. Even the most sophisticated computational fluid dynamic algorithms coupled with powerful supercomputers can not find approximate solutions for several design challenges in both adequate time and scale-resolving accuracy. One difficulty arises from solving high dimensional, strongly nonlinear partial differential equations, such as the Navier-Stokes equations, which capture the underlying physics. For nearly all classical algorithms, methods closely related to Newton's method are used to approximate a solution to the problem. Approximately solving the large-scale linear systems of equations occurring in this iterative scheme is generally a main contributor to the total computational complexity. In this paper a new quantum linear system solver supporting Newton's classical method to solve nonlinear partial differential equations is introduced. We present a new variant of the HHL algorithm, requiring less apriori information regarding the eigenvalues of the corresponding matrix. We apply this quantum linear system solver in a hybrid quantum-classical fashion to solve nonlinear partial differential equations. Moreover, a resource estimation for advanced use-cases of practical relevance is provided. Our results demonstrate how quantum computation may improve existing classical methodologies for solving nonlinear partial differential equations. This approach provides another promising application of quantum computers and presents a possible way forward for handling nonlinearities on inherently linear quantum systems.

quant-pharXiv:2603.23258•Mar 25, 2026•1 citation

Quantum algorithm for solving a quadratic nonlinear system of equations

Cheng Xue, Xiao‐Fan Xu, Yu-Chun Wu +1 more

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 $\ensuremath{\epsilon}$-close to the normalized exact solution of the QNSE with success probability $\mathrm{\ensuremath{\Omega}}(1)$. The complexity of our algorithm is $O(\mathrm{polylog}(n/\ensuremath{\epsilon}))$, which provides an exponential improvement over the optimal classical algorithm in dimension $n$, and the dependence on $\ensuremath{\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:2112.01655•Physical Review A•Sep 22, 2022•13 citations

Nonlinear quantum computation by amplified encodings

M. Deiml, Daniel Peterseim

This paper presents a novel framework for high-dimensional nonlinear quantum computation that exploits tensor products of amplified vector and matrix encodings to efficiently evaluate multivariate polynomials. The approach enables the solution of nonlinear equations by quantum implementations of the fixed-point iteration and Newton's method, with quantitative runtime bounds derived in terms of the error tolerance. These results show that a quantum advantage, characterized by a logarithmic scaling of complexity with the dimension of the problem, is preserved. While Newton's method attains near-optimal theoretical complexity, the fixed-point iteration may be better suited to near-term noisy hardware, as supported by our numerical experiments.

arXiv:2411.16435•Nov 25, 2024•6 citations

Efficient quantum algorithm for dissipative nonlinear differential equations

Jin-Peng Liu, Herman Øie Kolden, Hari Krovi +3 more

Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic n-dimensional ordinary differential equations. Assuming [Formula: see text], where R is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity [Formula: see text], where T is the evolution time, ϵ is the allowed error, and q measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for [Formula: see text] Finally, we discuss potential applications, showing that the [Formula: see text] condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of R.

arXiv:2011.03185•Proceedings of the National Academy of Sciences•Aug 26, 2021•310 citations

A Hybrid Quantum Solver for the Lorenz System

Sajad Fathi Hafshejani, Daya Ram Gaur, Arundhati Dasgupta +3 more

We develop a hybrid classical-quantum method for solving the Lorenz system. We use the forward Euler method to discretize the system in time, transforming it into a system of equations. This set of equations is solved by using the Variational Quantum Linear Solver (VQLS) algorithm. We present numerical results comparing the hybrid method with the classical approach for solving the Lorenz system. The simulation results demonstrate that the VQLS method can effectively compute solutions comparable to classical methods. The method is easily extended to solving similar nonlinear differential equations.

arXiv:2410.15417•Entropy•Nov 22, 2024•10 citations

An Optimal Linear-combination-of-unitaries-based Quantum Linear System Solver

Sander Gribling, Iordanis Kerenidis, Dániel Szilágyi

Solving systems of linear equations is one of the most important primitives in many different areas, including in optimization, simulation, and machine learning. Quantum algorithms for solving linear systems have the potential to provide a quantum advantage for these problems. In this work, we recall the Chebyshev iterative method and the corresponding optimal polynomial approximation of the inverse. We show that the Chebyshev iteration polynomial can be efficiently evaluated both using quantum singular value transformation (QSVT) as well as linear combination of unitaries (LCU). We achieve this by bounding the 1-norm of the coefficients of the polynomial expressed in the Chebyshev basis. This leads to a considerable constant-factor improvement in the runtime of quantum linear system solvers that are based on LCU or QSVT (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth).

ACM Transactions on Quantum Computing•Feb 24, 2024•6 citations
While quantum computing provides an exponential advantage in solving the system of linear equations, there is little work to solve the system of nonlinear equations with quantum computing. We propose quantum Newton’s method (QNM) for solving [Formula: see text]-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 [Formula: see text] tomography with sample error [Formula: see text] 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 [Formula: see text]. Through numerical simulation, we find that when [Formula: see text], QNM is still effective, so the complexity of QNM is sublinear with [Formula: see text], which provides quantum advantage compared with the optimal classical algorithm.
To approximate solutions of complex nonlinear partial differential equations remains a computational challenge, especially for sets of equations relevant in industry, such as Euler or Navier-Stokes equations. Even the most sophisticated computational fluid dynamic algorithms coupled with powerful supercomputers can not find approximate solutions for several design challenges in both adequate time and scale-resolving accuracy. One difficulty arises from solving high dimensional, strongly nonlinear partial differential equations, such as the Navier-Stokes equations, which capture the underlying physics. For nearly all classical algorithms, methods closely related to Newton's method are used to approximate a solution to the problem. Approximately solving the large-scale linear systems of equations occurring in this iterative scheme is generally a main contributor to the total computational complexity. In this paper a new quantum linear system solver supporting Newton's classical method to solve nonlinear partial differential equations is introduced. We present a new variant of the HHL algorithm, requiring less apriori information regarding the eigenvalues of the corresponding matrix. We apply this quantum linear system solver in a hybrid quantum-classical fashion to solve nonlinear partial differential equations. Moreover, a resource estimation for advanced use-cases of practical relevance is provided. Our results demonstrate how quantum computation may improve existing classical methodologies for solving nonlinear partial differential equations. This approach provides another promising application of quantum computers and presents a possible way forward for handling nonlinearities on inherently linear quantum systems.
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 nnn-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 $\ensuremath{\epsilon}$-close to the normalized exact solution of the QNSE with success probability $\mathrm{\ensuremath{\Omega}}(1)$. The complexity of our algorithm is $O(\mathrm{polylog}(n/\ensuremath{\epsilon}))$, which provides an exponential improvement over the optimal classical algorithm in dimension nnn, and the dependence on $\ensuremath{\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.
This paper presents a novel framework for high-dimensional nonlinear quantum computation that exploits tensor products of amplified vector and matrix encodings to efficiently evaluate multivariate polynomials. The approach enables the solution of nonlinear equations by quantum implementations of the fixed-point iteration and Newton's method, with quantitative runtime bounds derived in terms of the error tolerance. These results show that a quantum advantage, characterized by a logarithmic scaling of complexity with the dimension of the problem, is preserved. While Newton's method attains near-optimal theoretical complexity, the fixed-point iteration may be better suited to near-term noisy hardware, as supported by our numerical experiments.
Nonlinear differential equations model diverse phenomena but are notoriously difficult to solve. While there has been extensive previous work on efficient quantum algorithms for linear differential equations, the linearity of quantum mechanics has limited analogous progress for the nonlinear case. Despite this obstacle, we develop a quantum algorithm for dissipative quadratic n-dimensional ordinary differential equations. Assuming [Formula: see text], where R is a parameter characterizing the ratio of the nonlinearity and forcing to the linear dissipation, this algorithm has complexity [Formula: see text], where T is the evolution time, ϵ is the allowed error, and q measures decay of the solution. This is an exponential improvement over the best previous quantum algorithms, whose complexity is exponential in T. While exponential decay precludes efficiency, driven equations can avoid this issue despite the presence of dissipation. Our algorithm uses the method of Carleman linearization, for which we give a convergence theorem. This method maps a system of nonlinear differential equations to an infinite-dimensional system of linear differential equations, which we discretize, truncate, and solve using the forward Euler method and the quantum linear system algorithm. We also provide a lower bound on the worst-case complexity of quantum algorithms for general quadratic differential equations, showing that the problem is intractable for [Formula: see text] Finally, we discuss potential applications, showing that the [Formula: see text] condition can be satisfied in realistic epidemiological models and giving numerical evidence that the method may describe a model of fluid dynamics even for larger values of R.
We develop a hybrid classical-quantum method for solving the Lorenz system. We use the forward Euler method to discretize the system in time, transforming it into a system of equations. This set of equations is solved by using the Variational Quantum Linear Solver (VQLS) algorithm. We present numerical results comparing the hybrid method with the classical approach for solving the Lorenz system. The simulation results demonstrate that the VQLS method can effectively compute solutions comparable to classical methods. The method is easily extended to solving similar nonlinear differential equations.
Solving systems of linear equations is one of the most important primitives in many different areas, including in optimization, simulation, and machine learning. Quantum algorithms for solving linear systems have the potential to provide a quantum advantage for these problems. In this work, we recall the Chebyshev iterative method and the corresponding optimal polynomial approximation of the inverse. We show that the Chebyshev iteration polynomial can be efficiently evaluated both using quantum singular value transformation (QSVT) as well as linear combination of unitaries (LCU). We achieve this by bounding the 1-norm of the coefficients of the polynomial expressed in the Chebyshev basis. This leads to a considerable constant-factor improvement in the runtime of quantum linear system solvers that are based on LCU or QSVT (or, conversely, a several orders of magnitude smaller error with the same runtime/circuit depth).