  Simulation of quantum chemistry is expected to be a principal application of
quantum computing. In quantum simulation, a complicated Hamiltonian describing
the dynamics of a quantum system is decomposed into its constituent terms,
where the effect of each term during time-evolution is individually computed.
For many physical systems, the Hamiltonian has a large number of terms,
constraining the scalability of established simulation methods. To address this
limitation we introduce a new scheme that approximates the actual Hamiltonian
with a sparser Hamiltonian containing fewer terms. By stochastically
sparsifying weaker Hamiltonian terms, we benefit from a quadratic suppression
of errors relative to deterministic approaches. Relying on optimality
conditions from convex optimisation theory, we derive an appropriate
probability distribution for the weaker Hamiltonian terms, and compare its
error bounds with other probability ansatzes for some electronic structure
Hamiltonians. Tuning the sparsity of our approximate Hamiltonians allows our
scheme to interpolate between two recent random compilers: qDRIFT and
randomized first order Trotter. Our scheme is thus an algorithm that combines
the strengths of randomised Trotterisation with the efficiency of qDRIFT, and
for intermediate gate budgets, outperforms both of these prior methods.
