Time-marching based quantum solvers for time-dependent linear differential equations

• URL: http://arxiv.org/abs/2208.06941v1
• Date: Sun, 14 Aug 2022 23:49:19 GMT
• Title: Time-marching based quantum solvers for time-dependent linear differential equations
• Authors: Di Fang, Lin Lin, Yu Tong
• Abstract summary: The time-marching strategy is a natural strategy for solving time-dependent differential equations on classical computers. We show that a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms.
• Score: 3.1952399274829775
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The time-marching strategy, which propagates the solution from one time step to the next, is a natural strategy for solving time-dependent differential equations on classical computers, as well as for solving the Hamiltonian simulation problem on quantum computers. For more general linear differential equations, a time-marching based quantum solver can suffer from exponentially vanishing success probability with respect to the number of time steps and is thus considered impractical. We solve this problem by repeatedly invoking a technique called the uniform singular value amplification, and the overall success probability can be lower bounded by a quantity that is independent of the number of time steps. The success probability can be further improved using a compression gadget lemma. This provides a path of designing quantum differential equation solvers that is alternative to those based on quantum linear systems algorithms (QLSA). We demonstrate the performance of the time-marching strategy with a high-order integrator based on the truncated Dyson series. The complexity of the algorithm depends linearly on the amplification ratio, which quantifies the deviation from a unitary dynamics. We prove that the linear dependence on the amplification ratio attains the query complexity lower bound and thus cannot be improved in general. This algorithm also surpasses existing QLSA based solvers in three aspects: (1) the coefficient matrix $A(t)$ does not need to be diagonalizable. (2) $A(t)$ can be non-smooth, and is only of bounded variation. (3) It can use fewer queries to the initial state. Finally, we demonstrate the time-marching strategy with a first-order truncated Magnus series, while retaining the aforementioned benefits. Our analysis also raises some open questions concerning the differences between time-marching and QLSA based methods for solving differential equations.

Related papers

• Quantum and classical algorithms for nonlinear unitary dynamics [0.5729426778193399]
  We present a quantum algorithm for a non-linear differential equation of the form $fracd|urangledt. We also introduce a classical algorithm based on the Euler method allowing comparably scaling to the quantum algorithm in a restricted case.
  arXiv  Detail & Related papers  (2024-07-10T14:08:58Z)
• Nonlinear dynamics as a ground-state solution on quantum computers [39.58317527488534]
  We present variational quantum algorithms (VQAs) that encode both space and time in qubit registers. The spacetime encoding enables us to obtain the entire time evolution from a single ground-state computation.
  arXiv  Detail & Related papers  (2024-03-25T14:06:18Z)
• Further improving quantum algorithms for nonlinear differential equations via higher-order methods and rescaling [0.0]
  We present three main improvements to existing quantum algorithms based on the Carleman linearisation technique. By using a high-precision technique for the solution of the linearised differential equations, we achieve logarithmic dependence of the complexity on the error and near-linear dependence on time. A rescaling technique can considerably reduce the cost, which would otherwise be exponential in the Carleman order for a system of ODEs.
  arXiv  Detail & Related papers  (2023-12-15T03:52:44Z)
• Increasing the dimension of linear systems solved by classical or quantum binary optimization: A new method to solve large linear equation systems [41.94295877935867]
  We propose a new method to solve linear systems written as a binary optimization problem. The procedure solves the problem efficiently and allows it to handle large linear systems.
  arXiv  Detail & Related papers  (2023-09-18T16:51:03Z)
• The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts [0.0]
  We give the first non-asymptotic computation of the cost of encoding the solution to general linear ordinary differential equations into quantum states. We show that the stability properties of a large class of classical dynamics allow their fast-forwarding. We find that the history state can always be output with complexity $O(T1/2)$ for any stable linear system.
  arXiv  Detail & Related papers  (2023-09-14T17:25:43Z)
• An Inexact Feasible Quantum Interior Point Method for Linearly Constrained Quadratic Optimization [0.0]
  Quantum linear system algorithms (QLSAs) have the potential to speed up algorithms that rely on solving linear systems. In our work, we propose an Inexact-Feasible QIPM (IF-QIPM) and show its advantage in solving linearly constrained quadratic optimization problems.
  arXiv  Detail & Related papers  (2023-01-13T01:36:13Z)
• Quantum algorithm for time-dependent differential equations using Dyson series [0.0]
  We provide a quantum algorithm for solving time-dependent linear differential equations with logarithmic dependence of the complexity on the error and derivative. Our method is to encode the Dyson series in a system of linear equations, then solve via the optimal quantum linear equation solver.
  arXiv  Detail & Related papers  (2022-12-07T09:50:40Z)
• Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing [58.720142291102135]
  We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions.
  arXiv  Detail & Related papers  (2021-08-18T09:26:17Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  The ability to compare and align related datasets living in heterogeneous spaces plays an increasingly important role in machine learning. The Gromov-Wasserstein (GW) formalism can help tackle this problem.
  arXiv  Detail & Related papers  (2021-06-02T12:50:56Z)
• Covariance-Free Sparse Bayesian Learning [62.24008859844098]
  We introduce a new SBL inference algorithm that avoids explicit inversions of the covariance matrix. Our method can be up to thousands of times faster than existing baselines. We showcase how our new algorithm enables SBL to tractably tackle high-dimensional signal recovery problems.
  arXiv  Detail & Related papers  (2021-05-21T16:20:07Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  We propose two single-timescale single-loop algorithms that require only one data point each step. Our results are expressed in a form of simultaneous primal and dual side convergence.
  arXiv  Detail & Related papers  (2020-08-23T20:36:49Z)

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.