High-precision quantum algorithms for partial differential equations
Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | article |
| Language: | EN |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2021
|
| Subjects: | |
| Online Access: | https://doaj.org/article/fd5b1323d391416f8b295dc5981b37d7 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | Quantum computers can produce a quantum encoding of the solution of a system of differential equations exponentially faster than a classical algorithm can produce an explicit description. However, while high-precision quantum algorithms for linear ordinary differential equations are well established, the best previous quantum algorithms for linear partial differential equations (PDEs) have complexity $\mathrm{poly}(1/\epsilon)$, where $\epsilon$ is the error tolerance. By developing quantum algorithms based on adaptive-order finite difference methods and spectral methods, we improve the complexity of quantum algorithms for linear PDEs to be $\mathrm{poly}(d, \log(1/\epsilon))$, where $d$ is the spatial dimension. Our algorithms apply high-precision quantum linear system algorithms to systems whose condition numbers and approximation errors we bound. We develop a finite difference algorithm for the Poisson equation and a spectral algorithm for more general second-order elliptic equations. |
|---|