  Quantum computers have the potential to speed-up important matrix-arithmetic
tasks. A prominent framework for that is the quantum singular-value
transformation (QSVT) formalism, which uses Chebyshev approximations and
coherent access to the input matrix via a unitary block encoding to design a
target matrix function. Nonetheless, physical implementations for useful
end-user applications require large-scale fault-tolerant quantum computers.
Here, we present a hybrid quantum-classical framework for Monte-Carlo
simulation of generic matrix functions more amenable to early fault-tolerant
quantum hardware. Serving from the ideas of QSVT, we randomize over the
Chebyshev polynomials while keeping the matrix oracle quantum. The method is
assisted by a variant of the Hadamard test that removes the need for
post-selection. As a result, it features a similar statistical overhead to the
fully quantum case of standard QSVT and does not incur any circuit depth
degradation. On the contrary, the average circuit depth is shown to get
smaller, yielding equivalent reductions of noise sensitivity, as we explicitly
show for depolarizing noise and coherent errors. We apply our technique to four
specific use cases: partition-function estimation via quantum Markov-chain
Monte Carlo and via imaginary-time evolution; end-to-end linear system solvers;
and ground-state energy estimation. For these cases, we prove advantages on
average depths, including quadratic speed-ups on costly parameters and even the
removal of the approximation-error dependence. All in all, our framework
provides a pathway towards early fault-tolerant quantum linear algebra
applications.
