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

• URL: http://arxiv.org/abs/2109.08470v1
• Date: Fri, 17 Sep 2021 11:20:26 GMT
• Title: Quantum Newton's method for solving system of nonlinear algebraic equations
• Authors: Cheng Xue, Yu-Chun Wu, Guo-Ping Guo
• Abstract summary: We propose quantum Newton's method (QNM) for solving $N$-dimensional system of nonlinear equations based on Newton's method. We use a specific quantum data structure and $l_infty$ tomography with sample error $epsilon_s$ to implement the classical-quantum data conversion process.
• Score: 0.25782420501870296
• License: http://creativecommons.org/licenses/by/4.0/
• 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^4N/\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.

Related papers

• Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
  We show that every computation problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any problem, both inversion, constraint satisfaction and optimization.
  arXiv  Detail & Related papers  (2025-02-09T18:16:53Z)
• Quantum simulation of Burgers turbulence: Nonlinear transformation and direct evaluation of statistical quantities [0.0]
  It is still challenging to solve nonlinear equations in fluid dynamics, such as the Burgers equation, using quantum computers. We propose a novel quantum algorithm to solve the Burgers equation.
  arXiv  Detail & Related papers  (2024-12-23T01:17:26Z)
• Calculating response functions of coupled oscillators using quantum phase estimation [40.31060267062305]
  We study the problem of estimating frequency response functions of systems of coupled, classical harmonic oscillators using a quantum computer. Our proposed quantum algorithm operates in the standard $s-sparse, oracle-based query access model. We show that a simple adaptation of our algorithm solves the random glued-trees problem in time.
  arXiv  Detail & Related papers  (2024-05-14T15:28:37Z)
• Quantum algorithms for calculating determinant and inverse of matrix and solving linear algebraic systems [43.53835128052666]
  We propose quantum algorithms for calculating the determinant and inverse of an $(N-1)times (N-1)$ matrix. The basic idea is to encode each row of the matrix into a pure state of some quantum system.
  arXiv  Detail & Related papers  (2024-01-29T23:23:27Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• Fast quantum algorithm for differential equations [0.5895819801677125]
  We present a quantum algorithm with numerical complexity that is polylogarithmic in $N$ but is independent of $kappa$ for a large class of PDEs. Our algorithm generates a quantum state that enables extracting features of the solution.
  arXiv  Detail & Related papers  (2023-06-20T18:01:07Z)
• Accelerating the training of single-layer binary neural networks using the HHL quantum algorithm [58.720142291102135]
  We show that useful information can be extracted from the quantum-mechanical implementation of Harrow-Hassidim-Lloyd (HHL) This paper shows, however, that useful information can be extracted from the quantum-mechanical implementation of HHL, and used to reduce the complexity of finding the solution on the classical side.
  arXiv  Detail & Related papers  (2022-10-23T11:58:05Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations [0.22940141855172036]
  The complexity of our algorithm is $O(rm polylog(n/epsilon))$, which provides an exponential improvement over the optimal classical algorithm in dimension $n$. Our algorithm exponentially accelerates the solution of QNSE and has wide applications in all kinds of nonlinear problems.
  arXiv  Detail & Related papers  (2021-12-03T00:27:16Z)
• An Algebraic Quantum Circuit Compression Algorithm for Hamiltonian Simulation [55.41644538483948]
  Current generation noisy intermediate-scale quantum (NISQ) computers are severely limited in chip size and error rates. We derive localized circuit transformations to efficiently compress quantum circuits for simulation of certain spin Hamiltonians known as free fermions. The proposed numerical circuit compression algorithm behaves backward stable and scales cubically in the number of spins enabling circuit synthesis beyond $mathcalO(103)$ spins.
  arXiv  Detail & Related papers  (2021-08-06T19:38:03Z)
• Efficient quantum algorithm for dissipative nonlinear differential equations [1.1988695717766686]
  We develop a quantum algorithm for dissipative quadratic $n$-dimensional ordinary differential equations. Our algorithm has complexity $T2 qmathrmpoly(log T, log n, log 1/epsilon)/epsilon$, where $T$ is the evolution time, $epsilon$ is the allowed error, and $q$ measures decay of the solution.
  arXiv  Detail & Related papers  (2020-11-06T04:27:00Z)
• Enhancing the Quantum Linear Systems Algorithm using Richardson Extrapolation [0.8057006406834467]
  We present a quantum algorithm to solve systems of linear equations of the form $Amathbfx=mathbfb$. The algorithm achieves an exponential improvement with respect to $N$ over classical methods.
  arXiv  Detail & Related papers  (2020-09-09T18:00:09Z)
• Variational Quantum Linear Solver [0.3774866290142281]
  We propose a hybrid quantum-classical algorithm for solving linear systems on near-term quantum computers. We numerically solve non-trivial problems of size up to $250times250$ using Rigetti's quantum computer.
  arXiv  Detail & Related papers  (2019-09-12T17:28:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.