Stratified Sampling for Quasi-Probability Decompositions

Quasi-probability decompositions (QPDs) have proven essential in many quantum algorithms and protocols - one replaces a "difficult" quantum circuit with an ensemble of "easier" circuit variants whose weighted outcomes reproduce any target observable. This, however, inevitably yields an increased configuration variance beyond Born-rule shot noise. We develop a broad framework for accounting for and reducing this variance and prove that stratified sampling - under ideal proportional allocation - results in an unbiased estimator with a variance that is never worse than naïve sampling (with equality only in degenerate cases). Furthermore, we provide a classical dynamic programme to enable stratification on arbitrary product-form QPDs. Numerical simulations of typical QPDs, such as Probabilistic Error Cancellation (PEC) and Probabilistic Angle Interpolation (PAI), demonstrate constant-factor reductions in overall variance up to $sim 60$--$80\%$ in an oracle model and robust sim 10\% savings in the pessimistic single-shot regime. Our results can be applied immediately to reduce the net sampling cost of practically relevant QPDs that are commonly used in near term and early fault-tolerant algorithms without requiring additional quantum resources.