Quantum algorithms for linear systems produce the solution state A 1 | b 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 ( 1 / p ) queries to O b , which is optimal in the success probability, and O ( log ( 1 / p ) ( log log ( 1 / p ) + log ( 1 / ) ) ) 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 a priori . This contrasts with recent results achieving O ( log ( 1 / ) ) complexity to both oracles, which, while optimal in O A , is highly suboptimal in O b as can be arbitrarily larger than 1 / 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 p
Low et al. (Mon,) studied this question.