The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
- URL: http://arxiv.org/abs/2309.07881v2
- Date: Fri, 15 Mar 2024 14:53:52 GMT
- Title: The cost of solving linear differential equations on a quantum computer: fast-forwarding to explicit resource counts
- Authors: David Jennings, Matteo Lostaglio, Robert B. Lowrie, Sam Pallister, Andrew T. Sornborger,
- Abstract summary: 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.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: How well can quantum computers simulate classical dynamical systems? There is increasing effort in developing quantum algorithms to efficiently simulate dynamics beyond Hamiltonian simulation, but so far exact resource estimates are not known. In this work, we provide two significant contributions. First, we give the first non-asymptotic computation of the cost of encoding the solution to general linear ordinary differential equations into quantum states -- either the solution at a final time, or an encoding of the whole history within a time interval. Second, we show that the stability properties of a large class of classical dynamics allow their fast-forwarding, making their quantum simulation much more time-efficient. From this point of view, quantum Hamiltonian dynamics is a boundary case that does not allow this form of stability-induced fast-forwarding. In particular, we find that the history state can always be output with complexity $O(T^{1/2})$ for any stable linear system. We present a range of asymptotic improvements over state-of-the-art in various regimes. We illustrate our results with a family of dynamics including linearized collisional plasma problems, coupled, damped, forced harmonic oscillators and dissipative nonlinear problems. In this case the scaling is quadratically improved, and leads to significant reductions in the query counts after inclusion of all relevant constant prefactors.
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) - Quantum algorithms to simulate quadratic classical Hamiltonians and optimal control [0.0]
We develop quantum algorithms to estimate quantities of interest in a given classical mechanical system.
We consider the problem of designing optimal control of classical systems, which can be cast as the second variation of the Lagrangian.
We give an efficient quantum algorithm to solve the Riccati differential equation well into the nonlinear regime.
arXiv Detail & Related papers (2024-04-10T18:53:22Z) - Neural Time-Reversed Generalized Riccati Equation [60.92253836775246]
Hamiltonian equations offer an interpretation of optimality through auxiliary variables known as costates.
This paper introduces a novel neural-based approach to optimal control, with the aim of working forward-in-time.
arXiv Detail & Related papers (2023-12-14T19:29:37Z) - Exponential quantum speedup in simulating coupled classical oscillators [1.9398245011675082]
We present a quantum algorithm for the classical dynamics of $2n$ coupled oscillators.
Our approach leverages a mapping between the Schr"odinger equation and Newton's equation for harmonic potentials.
We show that our approach solves a potentially practical application with an exponential speedup over classical computers.
arXiv Detail & Related papers (2023-03-23T03:24:03Z) - Time-marching based quantum solvers for time-dependent linear
differential equations [3.1952399274829775]
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.
arXiv Detail & Related papers (2022-08-14T23:49:19Z) - Efficient Fully-Coherent Quantum Signal Processing Algorithms for
Real-Time Dynamics Simulation [3.3917542048743865]
We develop fully-coherent simulation algorithms based on quantum signal processing (QSP)
We numerically analyze these algorithms by applying them to the simulation of spin dynamics of the Heisenberg model.
arXiv Detail & Related papers (2021-10-21T17:56:33Z) - Quantum algorithms for quantum dynamics: A performance study on the
spin-boson model [68.8204255655161]
Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator.
variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware.
We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
arXiv Detail & Related papers (2021-08-09T18:00:05Z) - Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
We present a constructive algorithm for generating quantum circuits with time-independent depth.
We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model.
In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
arXiv Detail & Related papers (2021-04-01T19:06:00Z) - Fast and differentiable simulation of driven quantum systems [58.720142291102135]
We introduce a semi-analytic method based on the Dyson expansion that allows us to time-evolve driven quantum systems much faster than standard numerical methods.
We show results of the optimization of a two-qubit gate using transmon qubits in the circuit QED architecture.
arXiv Detail & Related papers (2020-12-16T21:43:38Z) - Linear embedding of nonlinear dynamical systems and prospects for
efficient quantum algorithms [74.17312533172291]
We describe a method for mapping any finite nonlinear dynamical system to an infinite linear dynamical system (embedding)
We then explore an approach for approximating the resulting infinite linear system with finite linear systems (truncation)
arXiv Detail & Related papers (2020-12-12T00:01:10Z) - Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
Random quantum circuits are commonly viewed as hard to simulate classically.
We show that approximate simulation of typical instances is almost as hard as exact simulation.
We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
arXiv Detail & Related papers (2019-12-31T19:00:00Z)
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.