Fast quantum algorithm for differential equations
- URL: http://arxiv.org/abs/2306.11802v2
- Date: Tue, 19 Sep 2023 14:44:46 GMT
- Title: Fast quantum algorithm for differential equations
- Authors: Mohsen Bagherimehrab, Kouhei Nakaji, Nathan Wiebe, Al\'an Aspuru-Guzik
- Abstract summary: 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.
- Score: 0.5895819801677125
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Partial differential equations (PDEs) are ubiquitous in science and
engineering. Prior quantum algorithms for solving the system of linear
algebraic equations obtained from discretizing a PDE have a computational
complexity that scales at least linearly with the condition number $\kappa$ of
the matrices involved in the computation. For many practical applications,
$\kappa$ scales polynomially with the size $N$ of the matrices, rendering a
polynomial-in-$N$ complexity for these algorithms. Here we present a quantum
algorithm with a 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. Central to our methodology is
using a wavelet basis as an auxiliary system of coordinates in which the
condition number of associated matrices is independent of $N$ by a simple
diagonal preconditioner. We present numerical simulations showing the effect of
the wavelet preconditioner for several differential equations. Our work could
provide a practical way to boost the performance of quantum-simulation
algorithms where standard methods are used for discretization.
Related papers
- Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP)
We generalize the SDP-inspired quantum algorithm to sum-of-squares.
Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
arXiv Detail & Related papers (2024-08-14T19:04:13Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
We study the problem of PAC learning a linear combination of $k$ ReLU activations under the standard Gaussian distribution on $mathbbRd$ with respect to the square loss.
Our main result is an efficient algorithm for this learning task with sample and computational complexity $(dk/epsilon)O(k)$, whereepsilon>0$ is the target accuracy.
arXiv Detail & Related papers (2023-07-24T14:37:22Z) - Efficient quantum linear solver algorithm with detailed running costs [0.0]
We introduce a quantum linear solver algorithm combining ideasdiabatic quantum computing with filtering techniques based on quantum signal processing.
Our protocol reduces the cost of quantum linear solvers over state-of-the-art close to an order of magnitude for early implementations.
arXiv Detail & Related papers (2023-05-19T00:07:32Z) - A hybrid quantum-classical algorithm for multichannel quantum scattering
of atoms and molecules [62.997667081978825]
We propose a hybrid quantum-classical algorithm for solving the Schr"odinger equation for atomic and molecular collisions.
The algorithm is based on the $S$-matrix version of the Kohn variational principle, which computes the fundamental scattering $S$-matrix.
We show how the algorithm could be scaled up to simulate collisions of large polyatomic molecules.
arXiv Detail & Related papers (2023-04-12T18:10:47Z) - A single $T$-gate makes distribution learning hard [56.045224655472865]
This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits.
We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
arXiv Detail & Related papers (2022-07-07T08:04:15Z) - Alternatives to a nonhomogeneous partial differential equation quantum
algorithm [52.77024349608834]
We propose a quantum algorithm for solving nonhomogeneous linear partial differential equations of the form $Apsi(textbfr)=f(textbfr)$.
These achievements enable easier experimental implementation of the quantum algorithm based on nowadays technology.
arXiv Detail & Related papers (2022-05-11T14:29:39Z) - A Quantum Computer Amenable Sparse Matrix Equation Solver [0.0]
We study problems involving the solution of matrix equations, for which there currently exists no efficient, general quantum procedure.
We develop a generalization of the Harrow/Hassidim/Lloyd algorithm by providing an alternative unitary for eigenphase estimation.
This unitary has the advantage of being well defined for any arbitrary matrix equation, thereby allowing the solution procedure to be directly implemented on quantum hardware.
arXiv Detail & Related papers (2021-12-05T15:42:32Z) - Quantum homotopy perturbation method for nonlinear dissipative ordinary
differential equations [0.25782420501870296]
We propose a quantum algorithm for solving $n$-dimensional nonlinear dissipative ordinary differential equations (ODEs)
Our algorithm provides exponential improvement over the best classical algorithms or previous quantum algorithms in $n$ or $epsilon$.
arXiv Detail & Related papers (2021-11-15T01:34:43Z) - Quantum algorithms for spectral sums [50.045011844765185]
We propose new quantum algorithms for estimating spectral sums of positive semi-definite (PSD) matrices.
We show how the algorithms and techniques used in this work can be applied to three problems in spectral graph theory.
arXiv Detail & Related papers (2020-11-12T16:29:45Z) - 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) - High-precision quantum algorithms for partial differential equations [1.4050836886292872]
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm.
We develop quantum algorithms based on adaptive-order finite difference methods and spectral methods.
Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound.
arXiv Detail & Related papers (2020-02-18T20:32:45Z)
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.