A Quantum Algorithm for Solving Linear Differential Equations: Theory and Experiment

Abstract

We present and experimentally realize a quantum algorithm for efficiently solving the following problem: given an $N\times N$ matrix $\mathcal{M}$, an $N$-dimensional vector $\text{b}$, and an initial vector $\text{x}(0)$, obtain a target vector $\text{x}(t)$ as a function of time $t$ according to the constraint $d\text{x}(t)/dt=\mathcal{M}\text{x}(t)+\text{b}$. We show that our algorithm exhibits an exponential speedup over its classical counterpart in certain circumstances. In addition, we demonstrate our quantum algorithm for a $4\times 4$ linear differential equation using a 4-qubit nuclear magnetic resonance quantum information processor. Our algorithm provides a key technique for solving many important problems which rely on the solutions to linear differential equations.

arXiv comment12 pages, 5 figures, and all comments are welcome!

References in corpus (32)

• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Machine Learning
• Quantum algorithm for solving linear systems of equations
• Experimental realization of Shor's quantum factoring algorithm using nuclear magnetic resonance
• Quantum random access memory
• Geometric quantum computation with NMR
• Simulating Hamiltonian dynamics with a truncated Taylor series
• Experimental realization of a quantum algorithm
• Implementation of a Quantum Search Algorithm on a Nuclear Magnetic Resonance Quantum Computer
• Experimental Realization of Nonadiabatic Holonomic Quantum Computation
• Quantum computers can search arbitrarily large databases by a single query
• Architectures for a quantum random access memory
• Experimental Realization of Quantum Artificial Intelligence
• The General Quantum Interference Principle and the Duality Computer
• High-order quantum algorithm for solving linear differential equations
• Effective Pure States for Bulk Quantum Computation
• Quantum algorithm for linear differential equations with exponentially improved dependence on precision
• Quantum algorithms for systems of linear equations inspired by adiabatic quantum computing
• A Quantum Adiabatic Algorithm for Factorization and Its Experimental Implementation
• Experimental Quantum Computing to Solve Systems of Linear Equations
• Experimental Realization of an Order-Finding Algorithm with an NMR Quantum Computer
• Liquid State NMR as a Test-bed for Developing Quantum Control Methods
• Hamiltonian Simulation Using Linear Combinations of Unitary Operations
• Experimental realization of quantum algorithm for solving linear systems of equations
• Solving systems of linear equations on a quantum computer
• Solving Systems of Linear Equations with a Superconducting Quantum Processor
• Quantum state tomography via reduced density matrices
• Tomography is necessary for universal entanglement detection with single-copy observables
• Experimental realization of quantum algorithms for linear system inspired by adiabatic quantum computing
• Practical experimental certification of computational quantum gates via twirling
• Quantum simulation of quantum channels in nuclear magnetic resonance
• NMRCloudQ: A Quantum Cloud Experience on a Nuclear Magnetic Resonance Quantum Computer

Cited by in corpus (34)

• Noisy intermediate-scale quantum (NISQ) algorithms
• Solving nonlinear differential equations with differentiable quantum circuits
• Variational Quantum Solutions to the Advection-Diffusion Equation for Applications in Fluid Dynamics
• Quantum algorithm for the Navier Stokes equations by using the streamfunction vorticity formulation and the lattice Boltzmann method
• Practical Quantum Computing: solving the wave equation using a quantum approach
• Configurable sublinear circuits for quantum state preparation
• Quantum Algorithms for Solving Ordinary Differential Equations via Classical Integration Methods
• FEqa: Finite Element Computations on Quantum Annealers
• Quantum Fourier analysis for multivariate functions and applications to a class of Schrödinger-type partial differential equations
• Efficient Hamiltonian Simulation for Solving Option Price Dynamics
• Controlling NMR spin systems for quantum computation
• Quantum Computing for Software Engineering: Prospects
• Probabilistic Eigensolver with a Trapped-Ion Quantum Processor
• Quantum Algorithm for Solving a Quadratic Nonlinear System of Equations
• Quantum vs. classical algorithms for solving the heat equation
• Quantum Carleman linearisation efficiency in nonlinear fluid dynamics
• Solving Differential-Algebraic Equations in Power System Dynamic Analysis with Quantum Computing
• Simulations of Future Particle Accelerators: Issues and Mitigations
• Quantum Computing for Location Determination
• Solving Differential-Algebraic Equations in Power System Dynamic Analysis with Quantum Computing
• Quantum algorithm for the Vlasov simulation of the large-scale structure formation with massive neutrinos
• Quantum Newton's method for solving system of nonlinear algebraic equations
• Pricing multi-asset derivatives by finite difference method on a quantum computer
• Optimizing resetting of superconducting qubits
• Adaptive Random Quantum Eigensolver
• Alternatives to a nonhomogeneous partial differential equation quantum algorithm
• Quantum channel decomposition with pre- and post-selection
• Quantum resources in Harrow-Hassidim-Lloyd algorithm
• Experimental semi-autonomous eigensolver using reinforcement learning
• Quantum homotopy perturbation method for nonlinear dissipative ordinary differential equations
• Quantum and classical algorithms for nonlinear unitary dynamics
• Vortex Detection from Quantum Data
• Quantum State Preparation and Non-Unitary Evolution with Diagonal Operators
• Quantum amplitude damping for solving homogeneous linear differential equations: A noninterferometric algorithm