qDRIFT and Randomized Simulation
A stochastic product formula that samples Hamiltonian terms by weight, giving gate counts independent of the number of terms.
The idea
Deterministic Trotterization applies every term of H = sum_l c_l H_l in each step, so its cost grows with the number of terms L. qDRIFT (Campbell, 2019) instead builds the evolution from randomly sampled single-term rotations, chosen with probability proportional to each term's coefficient magnitude. The number of gates then depends on the total coefficient weight, not on L.
The protocol
- Let lambda = sum_l |c_l| be the total coefficient norm.
- Sample term l with probability |c_l| / lambda.
- Apply the rotation e^(-i sign(c_l) H_l tau) with a fixed small angle tau = lambda t / N.
- Repeat N times; the average channel approximates e^(-iHt).
The cost scaling
The number of gates to reach error epsilon scales as N = O(lambda^2 t^2 / epsilon), independent of L. This is a large advantage for Hamiltonians with many terms of small individual weight, notably molecular electronic structure with O(N^4) terms, where most terms are tiny. It replaces a sum over terms with a sum over samples weighted by importance.
Trade-offs
The dependence on epsilon is 1/epsilon (worse than the log(1/epsilon) of post-Trotter methods) and on lambda^2 (which can be large). qDRIFT wins when L is huge and coefficients are skewed, and loses when high precision is required or when the Hamiltonian has few, roughly equal terms. It is a mixed channel, so it produces the correct average evolution rather than a fixed unitary, which suits expectation-value estimation.
Randomization more broadly
qDRIFT belongs to a family of randomized simulation methods that also includes random-permutation Trotter (shuffling term order each step to cancel systematic bias) and importance-sampled higher-order formulas. Randomization can turn coherent, adversarial error into incoherent, averaging error, often improving the effective accuracy for a given gate count. These methods are attractive on near-term hardware because they need no ancillas and can reduce circuit depth for term-heavy Hamiltonians, complementing deterministic product formulas and post-Trotter algorithms.