Simultaneously Query-Optimal Quantum Linear-System Algorithm

@misc{gao2026simultaneously,
  title = {{Simultaneously Query-Optimal Quantum Linear-System Algorithm}},
  author = {Minbo Gao and Zhengfeng Ji and Chenghua Liu},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.33686},
  eprint = {2609.33686},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.33686},
}

TY  - UNPB
TI  - Simultaneously Query-Optimal Quantum Linear-System Algorithm
AU  - Minbo Gao
AU  - Zhengfeng Ji
AU  - Chenghua Liu
PY  - 2026
DA  - 2026/09/27
PB  - arXiv
DO  - 10.48550/arxiv.2609.33686
UR  - https://arxiv.org/abs/2609.33686
AB  - 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(κlog(1/ε)) queries to U_A and O(κ/s) queries to U_b, where s=α|A^−1b|. 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 ε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to U_A and O(κ/s) 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 Ω(κlog(1/ε)) matrix queries and Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
ER  -