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...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Andrew M. Childs, Jin-Peng Liu, Aaron Ostrander
Formato:	article
Lenguaje:	EN
Publicado:	Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften 2021
Materias:	Physics QC1-999
Acceso en línea:	https://doaj.org/article/fd5b1323d391416f8b295dc5981b37d7
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:fd5b1323d391416f8b295dc5981b37d7
record_format	dspace
spelling	oai:doaj.org-article:fd5b1323d391416f8b295dc5981b37d72021-11-10T11:49:01ZHigh-precision quantum algorithms for partial differential equations2521-327X10.22331/q-2021-11-10-574https://doaj.org/article/fd5b1323d391416f8b295dc5981b37d72021-11-01T00:00:00Zhttps://quantum-journal.org/papers/q-2021-11-10-574/pdf/https://doaj.org/toc/2521-327XQuantum 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.Andrew M. ChildsJin-Peng LiuAaron OstranderVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenarticlePhysicsQC1-999ENQuantum, Vol 5, p 574 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Physics QC1-999
spellingShingle	Physics QC1-999 Andrew M. Childs Jin-Peng Liu Aaron Ostrander High-precision quantum algorithms for partial differential equations
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.
format	article
author	Andrew M. Childs Jin-Peng Liu Aaron Ostrander
author_facet	Andrew M. Childs Jin-Peng Liu Aaron Ostrander
author_sort	Andrew M. Childs
title	High-precision quantum algorithms for partial differential equations
title_short	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_sort	high-precision quantum algorithms for partial differential equations
publisher	Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
publishDate	2021
url	https://doaj.org/article/fd5b1323d391416f8b295dc5981b37d7
work_keys_str_mv	AT andrewmchilds highprecisionquantumalgorithmsforpartialdifferentialequations AT jinpengliu highprecisionquantumalgorithmsforpartialdifferentialequations AT aaronostrander highprecisionquantumalgorithmsforpartialdifferentialequations
_version_	1718440063512084480

High-precision quantum algorithms for partial differential equations

Ejemplares similares