  Simulating many-body quantum systems is a promising task for quantum
computers. However, the depth of most algorithms, such as product formulas,
scales with the number of terms in the Hamiltonian, and can therefore be
challenging to implement on near-term, as well as early fault-tolerant quantum
devices. An efficient solution is given by the stochastic compilation protocol
known as qDrift, which builds random product formulas by sampling from the
Hamiltonian according to the coefficients. In this work, we unify the qDrift
protocol with importance sampling, allowing us to sample from arbitrary
probability distributions, while controlling both the bias, as well as the
statistical fluctuations. We show that the simulation cost can be reduced while
achieving the same accuracy, by considering the individual simulation cost
during the sampling stage.
  Moreover, we incorporate recent work on composite channel and compute
rigorous bounds on the bias and variance, showing how to choose the number of
samples, experiments, and time steps for a given target accuracy. These results
lead to a more efficient implementation of the qDrift protocol, both with and
without the use of composite channels. Theoretical results are confirmed by
numerical simulations performed on a lattice nuclear effective field theory.
