  The System of Linear Equations Problem (SLEP) is specified by a complex
invertible matrix $A$, the condition number $\kappa$ of $A$, a vector $b$, a
Hermitian matrix $M$ and an accuracy $\epsilon$, and the task is to estimate
$x^\dagger Mx$, where $x$ is the solution vector to the equation $Ax = b$. We
aim to establish a lower bound on the complexity of the end-to-end quantum
algorithms for SLEP with respect to $\epsilon$, and devise a quantum algorithm
that saturates this bound. To make lower bounds attainable, we consider query
complexity in the setting in which a block encoding of $M$ is given, i.e., a
unitary black box $U_M$ that contains $M/\alpha$ as a block for some $\alpha
\in \mathbb R^+$. We show that the quantum query complexity for SLEP in this
setting is $\Theta(\alpha/\epsilon)$. Our lower bound is established by
reducing the problem of estimating the mean of a black box function to SLEP.
Our $\Theta(\alpha/\epsilon)$ result tightens and proves the common assertion
of polynomial accuracy dependence (poly$(1/\epsilon)$) for SLEP, and shows that
improvement beyond linear dependence on accuracy is not possible if $M$ is
provided via block encoding.
