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...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
2021-11-01
|
| Series: | Quantum |
| Online Access: | https://quantum-journal.org/papers/q-2021-11-10-574/pdf/ |
| _version_ | 1818684140590989312 |
|---|---|
| author | Andrew M. Childs Jin-Peng Liu Aaron Ostrander |
| author_facet | Andrew M. Childs Jin-Peng Liu Aaron Ostrander |
| author_sort | Andrew M. Childs |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-17T10:45:54Z |
| format | Article |
| id | doaj.art-fd5b1323d391416f8b295dc5981b37d7 |
| institution | Directory Open Access Journal |
| issn | 2521-327X |
| language | English |
| last_indexed | 2024-12-17T10:45:54Z |
| publishDate | 2021-11-01 |
| publisher | Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften |
| record_format | Article |
| series | Quantum |
| spelling | doaj.art-fd5b1323d391416f8b295dc5981b37d72022-12-21T21:52:07ZengVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenQuantum2521-327X2021-11-01557410.22331/q-2021-11-10-57410.22331/q-2021-11-10-574High-precision quantum algorithms for partial differential equationsAndrew M. ChildsJin-Peng LiuAaron OstranderQuantum 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.https://quantum-journal.org/papers/q-2021-11-10-574/pdf/ |
| spellingShingle | Andrew M. Childs Jin-Peng Liu Aaron Ostrander High-precision quantum algorithms for partial differential equations Quantum |
| title | High-precision quantum algorithms for partial differential equations |
| title_full | High-precision quantum algorithms for partial differential equations |
| title_fullStr | High-precision quantum algorithms for partial differential equations |
| title_full_unstemmed | High-precision quantum algorithms for partial differential equations |
| title_short | High-precision quantum algorithms for partial differential equations |
| title_sort | high precision quantum algorithms for partial differential equations |
| url | https://quantum-journal.org/papers/q-2021-11-10-574/pdf/ |
| work_keys_str_mv | AT andrewmchilds highprecisionquantumalgorithmsforpartialdifferentialequations AT jinpengliu highprecisionquantumalgorithmsforpartialdifferentialequations AT aaronostrander highprecisionquantumalgorithmsforpartialdifferentialequations |