Fast quantum algorithm for differential equations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914038814867456 |
|---|---|
| author | Bagherimehrab, Mohsen Nakaji, Kouhei Wiebe, Nathan Brennen, Gavin K. Sanders, Barry C. Aspuru-Guzik, Alán |
| author_facet | Bagherimehrab, Mohsen Nakaji, Kouhei Wiebe, Nathan Brennen, Gavin K. Sanders, Barry C. Aspuru-Guzik, Alán |
| contents | 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 $κ$ of the matrices involved in the computation. For many practical applications, $κ$ scales polynomially with the size $N$ of the matrices, rendering a polynomial complexity in $N$ for these algorithms. Here we present a quantum algorithm with a complexity that is polylogarithmic in $N$ but is independent of $κ$ for a large class of PDEs. Our algorithm generates a quantum state from which features of the solution can be extracted. Central to our methodology is using a wavelet basis as an auxiliary system of coordinates in which the condition number of associated matrices becomes 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_11802 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Fast quantum algorithm for differential equations Bagherimehrab, Mohsen Nakaji, Kouhei Wiebe, Nathan Brennen, Gavin K. Sanders, Barry C. Aspuru-Guzik, Alán Quantum Physics Computational Complexity Data Structures and Algorithms 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 $κ$ of the matrices involved in the computation. For many practical applications, $κ$ scales polynomially with the size $N$ of the matrices, rendering a polynomial complexity in $N$ for these algorithms. Here we present a quantum algorithm with a complexity that is polylogarithmic in $N$ but is independent of $κ$ for a large class of PDEs. Our algorithm generates a quantum state from which features of the solution can be extracted. Central to our methodology is using a wavelet basis as an auxiliary system of coordinates in which the condition number of associated matrices becomes 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. |
| title | Fast quantum algorithm for differential equations |
| topic | Quantum Physics Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2306.11802 |