Quantum linear system algorithm with optimal queries to initial state preparation

Quantum algorithms for linear systems produce the solution state A^-1|brangle by querying two oracles: O_A that block encodes the coefficient matrix and O_b that prepares the initial state. We present a quantum linear system algorithm making mathbfΘleft\(1/sqrt{p}right\) queries to O_b, which is optimal in the success probability, and mathbf{O}left\(κlogleft(1/pright\)left\(loglogleft(1/pright\)+logleft\({1}/εright\)right)right) queries to O_A, nearly optimal in all parameters including the condition number and accuracy. Notably, our complexity scaling of initial state preparation holds even when p is not known textit{a priori}. This contrasts with recent results achieving mathbf{O}left\(κlogleft({1}/εright\)right) complexity to both oracles, which, while optimal in O_A, is highly suboptimal in O_b as κ can be arbitrarily larger than 1/sqrt{p}. In various applications such as solving differential equations, preparing ground states of operators with real spectra, and estimating and transforming eigenvalues of non-normal matrices, we can further improve the dependence on p using a block preconditioning scheme to nearly match or outperform best previous results based on other methods, which also furnishes an extremely simple quantum linear system algorithm with an optimal query complexity to O_A. Underlying our results is a new Variable Time Amplitude Amplification algorithm with Tunable thresholds (Tunable VTAA), which fully characterizes generic nested amplitude amplifications, improves the ell₁-norm input cost scaling of Ambainis to an ell_{frac{2}{3}}-quasinorm scaling, and admits a deterministic amplification schedule for the quantum linear system problem.