Quantum Speedup in Dissecting Roots and Solving Nonlinear Algebraic Equations

Nhat A. Nghiem · 2025

Read Quantum Speedup in Dissecting Roots and Solving Nonlinear Algebraic Equations by Nhat A. Nghiem (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-06609.txt.

Introduction

Finding the roots of a function and solving sets of nonlinear equations sit at the heart of much applied math, and classical methods can be slow. Nghiem shows that a quantum computer can spot whether a root exists with almost exponential savings over the best classical checks. The same work builds a quantum state that encodes the solution of nonlinear algebraic equations. It does so about quadratically faster than the best known classical approach.

The paper then traces what such speedups would unlock. Listed uses include solving dense linear systems faster and finding balance states of physical systems. Other uses cover tracking coupled oscillators that do not move in simple cycles. Further uses cover improving quantum solvers for equations of change over time and spotting collisions faster when planning robot motion. The author stresses that none of this needs a special quantum doorway into classical data.

Catalog record

CREATORNhat A. Nghiem
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-06609

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Quantum Speedup in Dissecting Roots and Solving Nonlinear Algebraic Equations Nhat A. Nghiem Abstract It is shown that quantum computer can detect the existence of root of a function almost exponentially more efficient than the classical counterpart. It is also shown that a quantum computer can produce quantum state corresponding to the solution of nonlinear algebraic equations quadratically faster than the best known classical approach. Various applications and implications are discussed, including a quantum algorithm for solving dense linear systems with quadratic speedup, determining equilibrium states, simulating the dynamics of nonlinear coupled oscillators, estimating Lyapunov exponent, an improved quantum partial differential equation solver, and a quantum-enhanced collision detector for robotic motion planning. This provides further evidence of quantum advantage without requiring coherent quantum access to classical data, delivering meaningful real-world applications. I Introduction Quantum mechanics has revolutionized our understanding of the physical world, revealing that microscopic properties can be fundamentally distinct from macroscopic ones. This distinction has inspired a new computational paradigm in which quantum properties are harnessed for information processing. Beyond its impact on physics, quantum mechanics holds the potential to revolutionize technology, a field that has traditionally relied on digital computation. The concept of quantum computing was first proposed in early works [ 1 , 2 ] . Subsequent breakthroughs [ 3 , 4 , 5 , 6 ] demonstrated that by leveraging intrinsic quantum effects such as entanglement and superposition, quantum computers can factorize integers, search unstructured databases, and analyze functions implemented by black-box models faster than any known classical methods. These pioneering works laid the foundation for quantum computing and have had a lasting impact on its development, inspiring numerous subsequent advancements [ 4 , 3 , 7 , 8 , 9 , 10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 , 22 , 23 , 24 , 25 , 26 , 27 , 28 , 29 , 30 , 31 , 32 , 33 , 34 , 35 , 36 , 6 , 37 , 38 , 39 , 40 , 41 , 42 , 43 , 44 , 45 , 46 , 47 , 48 , 49 , 50 ] . The central objective of the field is to demonstrate quantum advantage—a scenario where quantum computers outperform classical ones in solving computational problems. Despite many successes, most claimed quantum speed-ups remain unjustified, as they rely on an oracle or black-box model that assumes quantum computers can access classical data in a coherent quantum manner. This assumption presents a significant challenge to the practical applicability of quantum algorithms. Recent studies [ 51 , 52 , 53 ] have even shown that if classical computers are provided with an analogous technique, known as l_{2} -sampling, they can perform tasks such as supervised learning and principal component analysis with at most a polynomial slowdown compared to quantum methods. Consequently, many previously claimed exponential quantum speed-ups have been refuted. More critical issues surrounding quantum algorithms are discussed in [ 54 ] , raising the fundamental question of whether quantum advantage can be achieved in a meaningful and practical way. Nonetheless, there exist a few rigorous demonstrations of quantum advantage. Bravyi et al. [ 55 ] showed that quantum computers can solve certain linear algebraic problems involving binary quadratic forms with constant depth, and this advantage persists even in the presence of noise [ 56 ] . Maslov et al. [ 57 ] demonstrated that in a space-restricted model, quantum computers outperform classical ones. Liu et al. [ 58 ] identified a supervised learning problem where a quantum computer can achieve efficient performance, whereas a classical computer performs no better than random guessing. While these results are theoretically significant, they remain largely impractical. Most recently, [ 59 , 60 ] demonstrated that quantum computers do not necessarily require coherent quantum access to perform gradient descent. This insight has led to a variety of new quantum algorithms, including quantum linear system solvers, least-square data fitting algorithms, support vector machines, supervised learning models, quantum neural network training methods, and quantum algorithms for determining ground and excited state energies. These developments suggest new prospects for quantum computational advantage and its applications. In this work, we ride on the success established in [ 59 ] and [ 60 ] by investigating analytical function properties in an oracle-free regime. Specifically, we focus on two fundamental problems: the existence of roots and the determination of roots for polynomials. For the first problem, we demonstrate that given knowledge of a function (e.g., polynomial coefficients), a quantum computer can determine whether a root—where the function value is zero—exists within a given domain. Our method is based on the insight that the existence of a root implies a change in the function’s sign. By examining sign changes at multiple points within the domain, we can efficiently detect the presence of a root. The ability of quantum computers to process multiple points simultaneously with logarithmic resources enables us to determine root existence in logarithmic time. Furthermore, by establishing a lower bound for classical algorithms, which requires at least linear time in the number of points, we achieve an almost exponential quantum speed-up. For the second problem, we develop a quantum Newton’s method, which is a direct quantum counterpart of the classical Newton’s method for solving systems of nonlinear algebraic equations. We prove that the quantum state corresponding to the solution of a given nonlinear system can be obtained in quadratic time relative to the system’s dimension, yielding a quadratic speed-up over classical approaches. To highlight the potential applications of our results, we extend and apply our methods to various contexts. A direct application of quantum Newton’s method results in a dense linear system solver with quadratic speed-up. Additionally, we analyze the dynamics of nonlinear coupled oscillators, leveraging our quantum Newton’s method to find equilibrium states and simulate their behavior over time. An unexpected yet significant corollary of our techniques is the development of an efficient circulant matrix construction method, which improves upon the quantum algorithm for solving partial differential equations proposed in [ 25 ] . Finally, we explore a potential application in robotic motion planning, where our quantum root-dissection algorithm can be used for collision detection. Before delving into the technical details, we outline the structure of our paper. We first provide in Sec. II a formal overview, related assumptions, technical summaries and statement of main results, including Theorem 1 , Theorem 1 and Theorem 3 . A more detailed version of quantum root dissecting algorithm is outlined in Sec. III , followed by a detailed analysis and discussion is included. Section IV.4 is devoted for the details of quantum algorithm for solving nonlinear algebraic equations, followed by a thorough discussion on complexity and possible extension in Section IV.5 . Applications and implications of our two main quantum algorithms are provided in Section V . II Overview and Summary of Results As mentioned, this section aims at providing a formal description of our main objectives, including dissecting the existence of a root within a known domain, and solving nonlinear algebraic equations. In addition, we also provide key information and related assumptions for our

Read the complete text