  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.
