On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number

Quantum algorithms for solving the Quantum Linear System (QLS) problem are among the most investigated quantum algorithms of recent times, with potential applications including the solution of computationally intractable differential equations and speed-ups in machine learning. A fundamental paramet...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Davide Orsucci, Vedran Dunjko
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/6a00a8e6873b490a9b117df26c85838e
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:6a00a8e6873b490a9b117df26c85838e
record_format	dspace
spelling	oai:doaj.org-article:6a00a8e6873b490a9b117df26c85838e2021-11-08T17:14:22ZOn solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number2521-327X10.22331/q-2021-11-08-573https://doaj.org/article/6a00a8e6873b490a9b117df26c85838e2021-11-01T00:00:00Zhttps://quantum-journal.org/papers/q-2021-11-08-573/pdf/https://doaj.org/toc/2521-327XQuantum algorithms for solving the Quantum Linear System (QLS) problem are among the most investigated quantum algorithms of recent times, with potential applications including the solution of computationally intractable differential equations and speed-ups in machine learning. A fundamental parameter governing the efficiency of QLS solvers is $\kappa$, the condition number of the coefficient matrix $A$, as it has been known since the inception of the QLS problem that for worst-case instances the runtime scales at least linearly in $\kappa$ [Harrow, Hassidim and Lloyd, PRL 103, 150502 (2009)]. However, for the case of positive-definite matrices classical algorithms can solve linear systems with a runtime scaling as $\sqrt{\kappa}$, a quadratic improvement compared to the the indefinite case. It is then natural to ask whether QLS solvers may hold an analogous improvement. In this work we answer the question in the negative, showing that solving a QLS entails a runtime linear in $\kappa$ also when $A$ is positive definite. We then identify broad classes of positive-definite QLS where this lower bound can be circumvented and present two new quantum algorithms featuring a quadratic speed-up in $\kappa$: the first is based on efficiently implementing a matrix-block-encoding of $A^{-1}$, the second constructs a decomposition of the form $A = L L^\dagger$ to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems.Davide OrsucciVedran DunjkoVerein zur Förderung des Open Access Publizierens in den QuantenwissenschaftenarticlePhysicsQC1-999ENQuantum, Vol 5, p 573 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Physics QC1-999
spellingShingle	Physics QC1-999 Davide Orsucci Vedran Dunjko On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
description	Quantum algorithms for solving the Quantum Linear System (QLS) problem are among the most investigated quantum algorithms of recent times, with potential applications including the solution of computationally intractable differential equations and speed-ups in machine learning. A fundamental parameter governing the efficiency of QLS solvers is $\kappa$, the condition number of the coefficient matrix $A$, as it has been known since the inception of the QLS problem that for worst-case instances the runtime scales at least linearly in $\kappa$ [Harrow, Hassidim and Lloyd, PRL 103, 150502 (2009)]. However, for the case of positive-definite matrices classical algorithms can solve linear systems with a runtime scaling as $\sqrt{\kappa}$, a quadratic improvement compared to the the indefinite case. It is then natural to ask whether QLS solvers may hold an analogous improvement. In this work we answer the question in the negative, showing that solving a QLS entails a runtime linear in $\kappa$ also when $A$ is positive definite. We then identify broad classes of positive-definite QLS where this lower bound can be circumvented and present two new quantum algorithms featuring a quadratic speed-up in $\kappa$: the first is based on efficiently implementing a matrix-block-encoding of $A^{-1}$, the second constructs a decomposition of the form $A = L L^\dagger$ to precondition the system. These methods are widely applicable and both allow to efficiently solve BQP-complete problems.
format	article
author	Davide Orsucci Vedran Dunjko
author_facet	Davide Orsucci Vedran Dunjko
author_sort	Davide Orsucci
title	On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
title_short	On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
title_full	On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
title_fullStr	On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
title_full_unstemmed	On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
title_sort	on solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number
publisher	Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften
publishDate	2021
url	https://doaj.org/article/6a00a8e6873b490a9b117df26c85838e
work_keys_str_mv	AT davideorsucci onsolvingclassesofpositivedefinitequantumlinearsystemswithquadraticallyimprovedruntimeintheconditionnumber AT vedrandunjko onsolvingclassesofpositivedefinitequantumlinearsystemswithquadraticallyimprovedruntimeintheconditionnumber
_version_	1718441481920839680

On solving classes of positive-definite quantum linear systems with quadratically improved runtime in the condition number

Ejemplares similares