Resource Requirements and Practicality of Randomized Quantum Linear Solvers

Randomized quantum algorithms for linear systems problems have attracted attention as potential candidates for early fault-tolerant quantum computers due to their potentially shallower circuit depths compared to block encoding-based methods. However, questions remain about whether they can offer practical advantages in near-term applications. We present a comprehensive resource analysis of a randomized quantum linear systems solver that estimates scalar properties of matrix inverses by combining Fourier series sampling with Hamiltonian simulation. Our analysis provides explicit bounds on all algorithmic parameters that control the total error, enabling concrete resource estimates. We compare two Hamiltonian simulation approaches: second-order product formulas and random Taylor expansion (RTE). Through numerical demonstrations, we validate our analytical bounds and reveal that the sampling complexity can exhibit exponential growth, calling into question the practical utility of the randomized Fourier series approach. By deriving explicit resource requirements rather than asymptotic scalings, our work enables fair comparisons to algorithms with different complexity trade-offs. These results highlight the importance of end-to-end resource analysis in bridging the gap between theoretical algorithmic proposals and quantum computing applications.