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/\varepsilon))$ queries to $U_A$ and $O(\kappa/s)$ queries to $U_b$, where $s=\alpha\|A^{-1}b\|$. 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 $\varepsilon$ using simultaneously $ O\left(\kappa\log\frac1\varepsilon\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/\varepsilon))$ 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.