Simultaneously Query-Optimal Quantum Linear-System Algorithm

Abstract

Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$. The optimal query complexities of these two oracles are known separately: $O(\kappa \log (1/\epsilon ))$ queries to $U_A$ and $O(\kappa /s)$ queries to $U_b$, where $s=\alpha \Vert A^{-1}b\Vert$. Whether a single algorithm can achieve both bounds simultaneously has remained open. We resolve this question affirmatively. Given a constant-factor estimate of $s$, we give a quantum linear-system algorithm that prepares the normalized solution to error $\epsilon$ using simultaneously $O\left(\kappa \log \frac{1}{\epsilon }\right)$ queries to $U_A$ and $O\left(\kappa /s\right)$ queries to $U_b$. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy. We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both $\Omega (\kappa \log (1/\epsilon ))$ matrix queries and $\Omega (\kappa /s)$ state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.

arXiv comment37 pages