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.

arXiv:2609.33686 [quant-ph]

(or arXiv:2609.33686v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.33686 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.