Stratified Sampling for Quasi-Probability Decompositions Joshua W. Dai, Bálint Koczor Abstract 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 ∼ 60 \sim 60 – 80 % 80\% in an oracle model) and robust ∼ 10 % \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. I Introduction Classical randomisation has been used to improve the effectiveness of many quantum algorithms and protocols, particularly in the context of near-term and early fault-tolerant quantum devices 49 ; 28 ; 67 . Rather than repeatedly executing a single fixed quantum process, one samples a family of circuits or channels and combines outcomes in post-processing. This paradigm appears in quasi-probability decomposition (QPD) methods for simulation 44 ; 3 ; 22 ; 53 , error mitigation 58 ; 16 ; 4 ; 55 ; 57 ; 46 ; 5 ; 60 ; 39 ; 25 , probabilistic synthesis 31 ; 32 and circuit cutting/knitting 45 ; 41 ; 38 . Similar algorithmic randomisation ideas also form the basis for techniques such as randomised compiling and twirling 62 ; 20 ; 6 , randomised Hamiltonian simulation (e.g. qDRIFT) 12 ; 7 ; 9 ; 17 ; 30 , and randomised measurement schemes such as classical shadows 23 ; 24 ; 27 ; 15 . While these techniques are often associated with NISQ applications 48 , randomisation can yield substantial resource savings in early fault-tolerant applications and beyond, through ideas such as statistical phase estimation 63 ; 34 ; 18 ; 61 , linear algebra solvers via randomised linear combination of unitaries (LCU) 64 , and randomised QSVT 65 or randomised QSP 40 . While QPDs can reduce quantum resource requirements or mitigate noise, they do introduce an additional variance source beyond intrinsic Born-rule shot noise: configuration variance due to randomisation over quantum circuits/channels. At fixed target precision, this extra variance translates into an overhead in the number of distinct circuit variants (and hence total executions) required. For QPD-based protocols, the dominant scaling of this overhead is well known to be exponential in circuit size through the QPD 1 -norm \|g\|_{1} 56 ; 67 . Even when this exponential factor is tolerable, reducing constant prefactors in the variance can materially extend the regime where QPD-based methods are practically useful. In this work we develop a sampling-design viewpoint on configuration variance and import variance-reduction tools from classical statistics. We model a hybrid protocol as sampling from a joint distribution over channels and outcomes, apply the law of total variance to separate Born-rule and configuration contributions, and then use conditioning sampling (Rao–Blackwellisation) to reduce the classical term without changing the target expectation 33 . For concreteness, we specialise to product-form QPDs: they are widely used, their randomisation structure is explicit, and they provide a clean setting in which algorithmic stratification can be made fully constructive. Our main technical contribution is to adapt stratified sampling 43 ; 13 ; 37 to product-form QPD estimators and make it algorithmically explicit. Specifically, we: (i) prove that proportional allocation on any statistic is unbiased and (under ideal proportional quotas) never worse than naïve Monte Carlo at fixed configuration budget, with strict improvement except in degenerate cases; (ii) construct a universal, index-based stratification of the configuration space using a counts vector of local QPD indices; (iii) for counts-vector stratification, give a dynamic-programming procedure that computes all stratum weights and supports exact conditional sampling, with pre-processing time O(d\,\nu^{d}) and O(\nu^{d}) memory for local width d and depth \nu and per-sample conditional generation cost that matches naïve up to constant-factor d (or identical assuming O(d) categorical draws). Stratification changes the classical sampling plan and requires only classical pre- and post-processing and a conditional sampler, and does not need additional quantum resources beyond a naïve implementation. A schematic is shown in Fig. 1 . We then verified our approach on first-order Trotter TFIM circuits with probabilistic angle interpolation (PAI) and probabilistic error cancellation (PEC), observing \sim 10\% variance reductions in the worst-case shot noise dominant regimes and substantially larger reductions of variance (up to \sim 60 – 80\% ) in oracle-like regimes where shot noise is suppressed. Related work. Conceptually, our approach is orthogonal to work that optimises the QPD design itself (e.g. to reduce \|g\|_{1} ): given any fixed product-form QPD, we address the sampling-design question of how to draw configurations and aggregate their outcomes as efficiently as possible while preserving unbiasedness. We note that there is substantial work on reducing QPD overheads by designing more efficient decompositions and task-specific mitigation schemes 26 ; 19 ; 47 ; 52 ; 59 ; 14 ; 66 . Our contribution is complementary: we focus on unbiased sampling design and classical pre-processing for a fixed product-form QPD. A detailed comparison and connections to previous work on classical variance-reduction techniques in the quantum context, such as 54 ; 11 , are given in Appendix A . Outline. Section II develops the variance decomposition for product-form QPD estimators, introduces stratified sampling and proportional/Neyman allocation, and states the “never worse than naïve” guarantee. We then construct counts-vector stratification and an efficient conditional sampler. Section III presents numerical results on PAI and PEC for TFIM Trotter evolution, including single-shot and oracle regimes. Section IV concludes and outlines extensions, while proofs, implementation details, and extended discussion appear in the appendices. Figure 1: Schematic of product-form QPD sampling and counts-vector stratification on a toy three-gate circuit. (a) Each ideal gate admits a local QPD over implementable primitives, so a circuit configuration is an index string \underline{\ell} . (b) Naïve QPD sampling draws \underline{\ell} directly from p(\underline{\ell})\propto|g(\underline{\ell})| . (c) Counts-vector stratification groups configurations by the number of occurrences of each local primitive, yielding strata indexed by a counts vector \mathbf{M} and a marginal distribution over strata obtained by aggregating the configuration masses. II Product-form QPDs: variance decomposition and stratified sampling In this work we specialise to product-form quasi-probability decompositions (QPDs), encompassing probabilistic error cancellation, probabilistic synthesis, probabilistic angle interpolation (PAI), and related schemes. The input state \rho_{0} , measurement POVM \{M_{x}\} , and observable O are fixed; all design randomness lies in sampling a circuit-level channel from a product ensemble of local QPDs. A more abstract treatment in terms of general channel randomisation is deferred to Appendix I . II.1 Local and circuit-level QPDs Suppose we have a target quantum process built from an ordered composition of \nu building blocks \mathcal{U}_{\mathrm{circ}}=\mathcal{U}^{(\nu)}\circ\cdots\circ\mathcal{U}^{(1)}, where each \mathcal{U}^{(i)} is a Hermiticity-preserving linear map on density operators 1 1 1 In many applications \mathcal{U}^{(i)} is CPTP (e.g. probabilistic synthesis or angle interpolation), but in others such as PEC it can be a formal inverse-noise map and hence not completely positive (see Appendix J ). The only operations we demand to be physical are the implementable primitives \mathcal{C}_{i}(\ell_{i}) . . For each position i\in\{1,\dots,\nu\} we assume a local quasi-probability decomposition \mathcal{U}^{(i)}=\sum_{\ell_{i}\in I_{i}}\gamma_{i}(\ell_{i})\,\mathcal{C}_{i}(\ell_{i}), (1) where I_{i}=\{1,\dots,d_{i}\} indexes implementable CPTP channels \mathcal{C}_{i}(\ell_{i}) and real coefficients \gamma_{i}(\ell_{i})\in\mathbb{R} (possibly negative). Both \gamma_{i} and \mathcal{C}_{i} may vary with i . Although \mathcal{U}_{\mathrm{circ}} may fail to be CPTP when some \mathcal{U}^{(i)} are inverse maps (as in PEC), the estimator remains well-defined because each realised circuit \mathcal{U}(\underline{\ell}) is a composition of CPTP primitives. Define the local 1-norm as \|\bm{\gamma}_{i}\|_{1}:=\sum_{\ell_{i}\in I_{i}}|\gamma_{i}(\ell_{i})| and the associated sampling distribution as p_{i}(\ell_{i}):=|\gamma_{i}(\ell_{i})|/\|\bm{\gamma}_{i}\|_{1}. Then, a single-gate random channel drawn by local index \ell_{i}\sim p_{i} is a random variable \widehat{\mathcal{U}}^{(i)}:=\|\bm{\gamma}_{i}\|_{1}\,\mathrm{sign}(\gamma_{i}(\ell_{i}))\,\mathcal{C}_{i}(\ell_{i}) which is unbiased in the sense that \mathbb{E}[\widehat{\mathcal{U}}^{(i)}]=\mathcal{U}^{(i)} . Taking the product over all local decompositions yields a circuit-level QPD \mathcal{U}_{\mathrm{circ}}=\sum_{\underline{\ell}\in\mathbf{I}}g(\underline{\ell})\,\mathcal{U}(\underline{\ell}), (2) where \underline{\ell}=(\ell_{1},\dots,\ell_{\nu}) is a multi-index labelling a configuration in the Cartesian product \mathbf{I}:=I_{1}\times\cdots\times I_{\nu} , the coefficients factorise as g(\underline{\ell})=\prod_{i=1}^{\nu}\gamma_{i}(\ell_{i}) , and the associated circuit variant can be expanded as \mathcal{U}(\underline{\ell}):=\mathcal{C}_{\nu}(\ell_{\nu})\circ\cdots\circ\mathcal{C}_{1}(\ell_{1}). The circuit-level 1-norm inherits the product structure \|g\|_{1}:=\sum_{\underline{\ell}\in\mathbf{I}}|g(\underline{\ell})|=\prod_{i=1}^{\nu}\|\bm{\gamma}_{i}\|_{1} . This induces a product distribution over the categorical distribution for every configuration p(\underline{\ell}):=\frac{|g(\underline{\ell})|}{\|g\|_{1}}=\prod_{i=1}^{\nu}p_{i}(\ell_{i}), (3) corresponding to independently sampling each local index \ell_{i} from p_{i} . Product-form QPDs are the standard construction in literature 60 ; 31 . Because the number of circuit variants in ( 2 ) grows exponentially with the depth \nu , brute force enumeration of all variants becomes rapidly infeasible, thus motivating a Monte-Carlo sampling based approach. II.2 Per-sample estimator, configuration samples, and repetitions per configuration We now embed the circuit-level QPD into an observable-estimation task and distinguish two natural resources: • the number of configurations (channels) sampled from p(\underline{\ell}) , denoted by K ; • the number of Born-rule repetitions per configuration , denoted by R . A full experiment therefore uses N=KR hardware executions (assuming that all circuit variants receive R repeats uniformly). Let \{M_{x}\} be a POVM and write the observable as O=\sum_{x}O_{x}M_{x} with real eigenvalues O_{x}\in\mathbb{R} . We assume O is bounded, so that |O_{x}|\leq\lVert O\rVert_{\infty} for a finite \lVert O\rVert_{\infty} (for Pauli observables, \lVert O\rVert_{\infty}=1 ). The target quantity is the ideal expectation under the original circuit, \mu:=\Tr\bigl[O\,\mathcal{U}_{\mathrm{circ}}(\rho_{0})\bigr]. For the k th configuration draw, we sample a circuit variant \underline{\ell}_{k}\sim p(\underline{\ell}) from ( 3 ). Conditioned on \underline{\ell}_{k} , we implement \mathcal{U}(\underline{\ell}_{k}) on \rho_{0} , and measure with \{M_{x}\} to obtain a raw outcome O_{x} . For example, for Pauli observables O_{x}\in\{\pm 1\} . This is then scaled by the standard QPD weight w(\underline{\ell}_{k})=\|g\|_{1}\sign(g(\underline{\ell_{k}})) to obtain the single-shot per configuration value \tilde{Y}_{k}:=w(\underline{\ell}_{k})\,O_{x} . Repeating R times i.i.d. we obtain the outcomes \tilde{Y}_{k,1},\dots\tilde{Y}_{k,R} , which we then average to obtain the per-configuration mean Y_{k}^{(R)}:=\frac{1}{R}\sum_{r=1}^{R}\tilde{Y}_{k,r} (4) The natural Monte Carlo estimator for \mu is then the further averaging over the configurations. \widehat{\mu}:=\widehat{Y}_{K}^{(R)}=\frac{1}{K}\sum_{k=1}^{K}Y_{k}^{(R)}. (5) Since |O_{x}|\leq\ \lVert O\rVert_{\infty} and |w(\underline{\ell}_{k})|=\|g\|_{1} we have |Y_{k}^{(R)}|\leq\ \lVert O\rVert_{\infty}\,\|g\|_{1}\quad\Longrightarrow\quad\Var(Y_{k}^{(R)})\leq\ \lVert O\rVert_{\infty}^{2}\,\|g\|_{1}^{2}. The estimator \widehat{\mu} is unbiased for all K and R by linearity and the definition of the QPD weights (Appendix B ). Moreover, if \|\bm{\gamma}_{i}\|_{1}\approx\alpha uniformly, then \|g\|_{1}\approx\alpha^{\nu} , yielding the usual exponential QPD overhead 5 . This can be understood as coming from a deliberately introduced ‘sign problem’ due to the QPD re-weighting needed to ensure unbiasedness. In what follows we call the i.i.d. configuration sampler ( 3 ) as the “naïve” sampler and illustrate how one can reduce its classical variance component (a constant prefactor at fixed K,R ). II.3 Variance decomposition and naïve design There are two sources of randomness in the final estimator \widehat{\mu} (or \widehat{Y}_{K}^{(R)} ) in ( 5 ): • classical randomness over configurations \underline{\ell}_{k} ; • Born-rule noise at fixed configuration \underline{\ell}_{k} . The key observation underlying our approach is that, for product-form QPDs, the first source arises from an artificial and highly structured classical randomization over circuit variants. Unlike Born-rule shot noise, this configuration variance is not intrinsic and can therefore be systematically reduced—independent of the QPD construction—by classical sampling design, with stratification providing a universal and provably safe primitive. To see this, condition the baseline estimator on \underline{\ell} , then use the law of total variance ( 8 , Theorem 4.4.7) to obtain \Var(Y^{(R)})=\frac{1}{R}\,\mathbb{E}_{\underline{\ell}}\!\big[\Var(\tilde{Y}\mid\underline{\ell})\big]+\Var_{\underline{\ell}}\!\big(\mathbb{E}[\tilde{Y}\mid\underline{\ell}]\big), (6) and with K i.i.d. configuration draws, \Var(\widehat{Y}_{K}^{(R)})=\frac{1}{K}\Var(Y^{(R)}). (7) The first term of ( 6 ) is Born-rule noise, suppressed as 1/R ; the second term is from variance between different configurations. We will compare sampling designs at the level of total variance \Var(Y^{(R)}) , with R regarded as part of the measurement model. In particular, changing the configuration-sampling scheme can only affect the corresponding configurational contribution \Var_{\underline{\ell}}(\mu_{\underline{\ell}}) ; the Born-rule term is fixed by the choice of R , circuit, and measurement. Naïve sampling corresponds to drawing configurations i.i.d. from p(\underline{\ell}) , ignoring any additional structure of the underlying distribution. The next subsection introduces stratified sampling over configurations and shows how to use additional structure to guarantee variance reduction at fixed K and R . Henceforth, we use Y to denote the per-configuration average Y^{(R)} under a fixed measurement model R . II.4 Stratified sampling over QPD configurations Let S=S(\underline{\ell}) be a deterministic function of the configuration index. We promote S to a random variable via the product distribution \underline{\ell}\sim p(\underline{\ell}) , and define the shorthand w_{s}:=\Pr(S=s),\,\mu_{s}:=\mathbb{E}[Y|S=s],\,\sigma_{s}^{2}:=\Var(Y|S=s). Such that \sum_{s}w_{s}\mu_{s}=\mu . We call each such possible value of S a stratum . A stratified estimator fixes in advance how many configuration draws are allocated to each stratum. We now show how this reduces the variance. Let K_{s} be the number of configuration draws with S=s , such that K_{s}\geq 0 and \sum_{s}K_{s}=K. Then, within each stratum we form a sample mean, and then combine these in turn to create the stratified estimator \widehat{\mu}_{s}:=\frac{1}{K_{s}}\sum_{t=1}^{K_{s}}Y_{s,t},\quad\widehat{Y}_{K}^{\mathrm{strat}}:=\sum_{s}w_{s}\,\widehat{\mu}_{s}. (8) By construction \mathbb{E}[\widehat{\mu}_{s}]=\mu_{s} and hence \mathbb{E}[\widehat{Y}_{K}^{\mathrm{strat}}]=\mu (unbiasedness proofs are in Appendix B ). Assuming independent sampling across strata, the variance of the stratified estimator is given by \Var(\widehat{Y}_{K}^{\mathrm{strat}})=\sum_{s}\frac{w_{s}^{2}\,\sigma_{s}^{2}}{K_{s}}, (9) So we see that the total variance depends on the number of samples we assign to each stratum. There are two particularly natural ways of budgeting: proportional allocation with K_{s}\propto w_{s} , and Neyman allocation with K_{s}\propto w_{s}\sigma_{s} . Neyman allocation minimises ( 9 ) over \{K_{s}\} but requires (pilot) estimates of the within-stratum standard deviations \sigma_{s} . In this work we focus on proportional allocation, which depends only on the stratum weights w_{s} and already enjoys a “never-worse” guarantee relative to naïve sampling; Neyman allocation and pilot schemes are discussed in Appendix H . Under ideal proportional allocation, we have the following theorem. Theorem 1 (Proportional Stratification is Never Worse than Naïve Sampling) . Consider a QPD estimator \widehat{Y}_{K} with a total budget of K configurations. Let w_{s} be the probability of a configuration falling into stratum s , and let \mu_{s} and \sigma_{s}^{2} denote the mean and variance of the estimator within that stratum, respectively. Under an idealized proportional allocation K_{s}=Kw_{s} (ignoring integrality), the variance reduction compared to naïve sampling is exactly proportional to the between-stratum variance : \displaystyle\Var(\widehat{Y}_{K}^{\mathrm{naive}})-\Var(\widehat{Y}_{K}^{\mathrm{prop}}) \displaystyle=\frac{1}{K}\sum_{s}w_{s}(\mu_{s}-\bar{\mu})^{2} (10) \displaystyle=\frac{1}{K}\Var_{s}(\mu_{s})\geq 0. Consequently, proportional stratification provides a strictly lower variance whenever the stratum means \mu_{s} are not all identical. Proof. We use the Law of Total Variance to decompose the total variance of a single configuration sample Y into “within-stratum” and “between-stratum” components: \Var(Y)=\underbrace{\sum_{s}w_{s}\sigma_{s}^{2}}_{\text{Within}}+\underbrace{\sum_{s}w_{s}(\mu_{s}-\bar{\mu})^{2}}_{\text{Between}}. (11) For K independent naïve samples, the variance is simply \Var(\widehat{Y}_{K}^{\mathrm{naive}})=\frac{1}{K}\Var(Y) . In contrast, the stratified estimator \widehat{Y}_{K}^{\mathrm{prop}}=\sum_{s}w_{s}\widehat{\mu}_{s} (where \widehat{\mu}_{s} is the sample mean of the K_{s} shots taken in stratum s ) has variance: \Var(\widehat{Y}_{K}^{\mathrm{prop}})=\sum_{s}w_{s}^{2}\frac{\sigma_{s}^{2}}{K_{s}}=\sum_{s}w_{s}^{2}\frac{\sigma_{s}^{2}}{Kw_{s}}=\frac{1}{K}\sum_{s}w_{s}\sigma_{s}^{2}. (12) Subtracting ( 12 ) from ( 11 ) yields the claim. ∎ Practical Caveat. The guarantee in Theorem 1 is exact for ideal quotas. However, in general, K_{s}=w_{s}K is not an integer, and so a rounding must be applied. In Appendix C we bound the perturbation introduced by this rounding with a computable certificate, and in Appendix E find that this is empirically negligible in the reported numerics. Theorem 1 can also be explicitly cast in terms of sample complexity through the following corollary. Corollary 1 (Sample complexity under proportional stratification) . Fix the measurement model (i.e. fixed R ) and let \widehat{Y}_{K}^{\mathrm{naive}} and \widehat{Y}_{K}^{\mathrm{prop}} denote the naïve and proportional stratified estimators based on K configurations. For any target standard error \varepsilon^{2}>0 , define \displaystyle K_{\mathrm{naive}}(\varepsilon^{2}) \displaystyle:=\min\{K:\Var(\widehat{Y}_{K}^{\mathrm{naive}})\leq\varepsilon^{2}\} \displaystyle K_{\mathrm{prop}}(\varepsilon^{2}) \displaystyle:=\min\{K:\Var(\widehat{Y}_{K}^{\mathrm{prop}})\leq\varepsilon^{2}\}. Under ideal proportional quotas, \frac{K_{\mathrm{prop}}(v)}{K_{\mathrm{naive}}(v)}=\frac{\Var(Y^{\mathrm{prop}})}{\Var(Y^{\mathrm{naive}})}=\rho\in[0,1]. Equivalently, to achieve the same target error in a given estimation task, proportional stratification reduces the required configuration budget (and hence total executions N=KR ) by a constant factor 0\leq\rho\leq 1 . Interpretation (explained configuration variance). The statistic S(\underline{\ell}) provides a compact description of the configuration \underline{\ell} and therefore induces stratum-conditional means \mu_{s}:=\mathbb{E}[Y\mid S=s] . The law of total variance decomposes the single-configuration variance as \Var(Y)=\mathbb{E}[\Var(Y\mid S)]\;+\;\Var(\mathbb{E}[Y\mid S]), so the between-stratum term \Var(\mathbb{E}[Y\mid S]) is precisely the portion of variability in Y that is explained by knowing S . Under ideal proportional allocation, stratification removes exactly this explained component, leaving only the within-stratum contribution \mathbb{E}[\Var(Y\mid S)] . Equivalently, defining the explained fraction R^{2}_{\mathrm{eff}}(S):=\frac{\Var(\mathbb{E}[Y\mid S])}{\Var(Y)}\in[0,1], the ideal variance ratio satisfies \rho(S)=1-R^{2}_{\mathrm{eff}}(S) : the improvement 1-\rho is exactly the fraction of single-configuration variance captured by S . In the oracle limit (no shot noise), Y is deterministic given \underline{\ell} and R^{2}_{\mathrm{eff}}(S) reduces to the usual fraction of configuration-to-configuration mean variation explained by S ; in this case, achieving the same precision requires only K_{\mathrm{prop}}=\rho(S)\,K_{\mathrm{naive}} configurations. With finite shots, Born noise increases \Var(Y) without increasing \Var(\mathbb{E}[Y\mid S]) , reducing R^{2}_{\mathrm{eff}}(S) and hence the attainable savings. Appendix G formalises these identities and connects them to permutation symmetry for counts-vector strata. Remark (QPD overhead unchanged). Stratification changes only how configurations are selected and aggregated; it does not modify the per-shot weight magnitude. In particular, for bounded observables |O_{x}|\leq\ \lVert O\rVert_{\infty} and our choice |w(\underline{\ell})|=\|g\|_{1} , every realised per-configuration average satisfies |Y^{(R)}|\leq\ \lVert O\rVert_{\infty}\|g\|_{1} , irrespective of whether \underline{\ell} was drawn i.i.d. or conditionally within a stratum. Consequently, we have the upper bound \Var(\widehat{Y}_{K}^{\mathrm{strat}})\leq\frac{\ \lVert O\rVert_{\infty}^{2}\|g\|_{1}^{2}}{K}, so the fundamental 1/K and \|g\|_{1}^{2} scaling (and its typical exponential growth in \nu ) is unchanged; the effect of stratification is a reduction of the constant pre-factor, quantified by the variance ratio \rho (it only removes the additive between-stratum contribution \Var_{s}(\mu_{s}) ). II.5 Counts-vector stratification for QPDs Naïve sampling treats the configuration index \underline{\ell} as an atomic label. However, in many QPD ensembles different configurations contribute similarly to the observable, particularly when there are exact or approximate permutation symmetries across gate locations. We exploit this by stratifying configurations using a permutation-invariant counts vector , which is a concrete instantiation of the stratification statistic S(\underline{\ell}) introduced above. We emphasise that the counts-vector statistic is not unique: there is a natural family of coarser statistics obtained by coarsening \mathbf{M} (see Appendix F ). Padding to a common width. For notational convenience we assume a common local width d . This can be enforced without loss of generality by padding each local decomposition with dummy primitives of zero coefficient: that is, choose d=\max_{i}d_{i} and extend all local index sets I_{i} to \{1,\dots,d\} by setting \gamma_{i}(\ell)=0 for \ell>d_{i} . This leaves the induced product law p(\underline{\ell}) and circuit 1-norm \|g\|_{1} unchanged. Counts-vector strata. With this notational simplification the counts vector associated with a multi-index \underline{\ell}=(\ell_{1},\dots,\ell_{\nu}) records how often each local index appears: \mathbf{M}=(M_{1},\dots,M_{d}),\quad M_{k}:=\#\{i:\ell_{i}=k\}, (13) with \sum_{k=1}^{d}M_{k}=\nu . Configurations that differ only by permuting gate positions share the same \mathbf{M} , so taking S\equiv\mathbf{M} partitions the configuration space into permutation-invariant strata. In the mixed-width case, the padded categories simply have zero probability. For fixed \nu and d , the number of distinct counts vectors is \#\{\mathbf{m}:\sum_{k}m_{k}=\nu\}=\binom{\nu+d-1}{d-1}=O(\nu^{d-1}), (14) which is polynomial in \nu for fixed local width d . The special case d=2 recovers the binomial-type stratifications used for homogeneous QPDs (see 11 and Appendix A ). For comparison, there are O(d^{\nu}) possible circuit configurations in the full product distribution p(\underline{\ell}) . DP preprocessing and conditional sampling. Operationally, stratified sampling with S\equiv\mathbf{M} requires (i) full knowledge of the exact stratum weights w_{\mathbf{m}}:=\Pr(\mathbf{M}=\mathbf{m}) and (ii) an efficient method to sample configurations \underline{\ell} conditionally on \mathbf{M}=\mathbf{m} . In the product-form QPD setting where we have a simple product of categorical distributions p(\underline{\ell})=\prod_{i=1}^{\nu}p_{i}(\ell_{i}) , the induced counts-vector random variable \mathbf{M}(\underline{\ell}) follows a Poisson—multinomial distribution (PMD) determined by the local categories \{p_{i}\} . We can exploit this PMD structure to solve both tasks via a single dynamic programme (DP) that runs as a classical pre-computation, such that quantum run-time is unaffected. This algorithm can be seen as a generalisation of the standard DP for calculating the Poisson—Binomial distribution 21 ; 10 . We also note that the PMD is a well-studied distribution in classical statistics 35 . Concretely, a forward dynamic programme computes all w_{\mathbf{m}} with O(d\,\nu^{d}) arithmetic operations and caches intermediate layers in O(\nu^{d}) memory; a backward pass through the cached table then generates \underline{\ell}\sim p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) in O(\nu d) time per configuration, matching the runtime cost of naïve sampling up to a constant factor. Full recursions and pseudocode for performing the two tasks, namely CountsForwardDP and CountsConditionalSample , are given in Appendix D . Complexity caveat and routes to scalability. The DP state space grows as O(\nu^{d-1}) and the preprocessing cost as O(d\,\nu^{d}) , so while the method is efficient for the small fixed-width regime targeted in our numerics in Section III when d is small (e.g. d=3 for PAI and d=4 for single-qubit Pauli PEC, and \nu up to around 10^{2} ), it can become impractical when the width is large (e.g. multi-qubit noise channels or broader local decompositions like in 32 ) or when \nu is extremely large. This is not a conceptual failure of stratification, but an implementation constraint of the exact PMD/conditional-sampling backbone. In such regimes one can retain the same design viewpoint while introducing problem-dependent refinements: globally coarsening the statistic (reducing effective width d ), using typed/blockwise counts to keep widths small within blocks, or using pruned/approximate pre-processing (potentially with controlled bias) to exploit concentration of the counts-vector distribution. We sketch these refinements in the outlook, where the goal becomes an explicit trade-off between pre-processing cost and variance (and possibly bias). Generality and problem-agnosticism. The counts-vector construction and the associated DP are purely distributional: they depend only on the product-form configuration law p(\underline{\ell})=\prod_{i=1}^{\nu}p_{i}(\ell_{i}) induced by the local QPD coefficients, and do not require additional assumptions about the quantum primitives beyond the ability to index them. In particular, the DP never inspects (or utilises) the underlying channels \{\mathcal{C}_{i}(\ell)\} , the surrounding circuit that they’re embedded in, or the measured observable; it uses only the categorical probabilities \{p_{i}(\cdot)\} . Consequently, the same pre-processing and conditional sampler apply unchanged to inhomogeneous product-form QPDs where the local distributions vary with i , such as when different locations correspond to different physical primitives (e.g. dephasing at one location and bit-flip at another, or different PAI axes), so long as each location is equipped with a local index set and associated probabilities. As such, we emphasise that counts-vector stratification (or statistics coarsened from it) is a universal, quantum agnostic sampling-design layer for product-form QPDs: it is a drop-in replacement for naïve configuration sampling. Any quantum- or observable-specific structure enters only through the conditional means \mu_{\underline{\ell}} and hence through how informative \mathbf{M} is for a given problem instance. II.6 Practical stratified sampling recipe For a product-form QPD and a chosen stratification statistic S(\underline{\ell}) (here the counts vector S\equiv\mathbf{M} ), stratified sampling replaces i.i.d. draws of configurations \underline{\ell}\sim p(\underline{\ell}) by the following end-to-end procedure: 1. Precomputation (once per QPD-problem): run CountsForwardDP to obtain the stratum weights w_{\mathbf{m}}=\Pr(\mathbf{M}=\mathbf{m}) and cache the prefix tables \{W^{(i)}_{\mathbf{m}}\} required for backward conditional sampling. 2. Integer allocation across strata: given a total configuration budget K , choose nonnegative integers K_{\mathbf{m}} with \sum_{\mathbf{m}}K_{\mathbf{m}}=K . To preserve exact unbiasedness at finite K , we use residual-aware Hamilton apportionment: any zero-allocation strata are aggregated into a residual bucket \mathcal{D} with total weight w_{*} and count K_{*} (see Appendix C for details). 3. Stratified configuration generation and circuit execution: (a) For each stratum \mathbf{m} with K_{\mathbf{m}}>0 , repeat K_{\mathbf{m}} times: sample \underline{\ell}\sim p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) via the backward DP, execute \mathcal{U}(\underline{\ell}) , and compress R measurement repetitions into a single scalar outcome Y_{\mathbf{m},t} (Sec. II.2 ). (b) If there are residuals ( K_{*}>0 ) repeat K_{*} times: sample a stratum label \mathbf{m}\sim q(\cdot) on the residual set \mathcal{D} , then sample \underline{\ell}\sim p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) and execute as above to obtain Y_{*,t} . 4. Estimator construction: compute within-stratum means \widehat{\mu}_{\mathbf{m}}=\frac{1}{K_{\mathbf{m}}}\sum_{t=1}^{K_{\mathbf{m}}}Y_{\mathbf{m},t} (and \widehat{\mu}_{*} analogously if K_{*}>0 ), and return \widehat{Y}_{K,R}^{\text{impl}}=\sum_{\mathbf{m}}w_{\mathbf{m}}\,\widehat{\mu}_{\mathbf{m}}+w_{*}\,\widehat{\mu}_{*}. Input: Local probabilities \{p_{i}(k)\}_{i\leq\nu,k\leq d} ; total configuration budget K ; repetitions per configuration R . Output: Estimator \widehat{Y}_{K,R}^{\mathrm{impl}} . 1 (\{w_{\mathbf{m}}\},\ \mathcal{T})\leftarrow\textsc{CountsForwardDP}(\{p_{i}\}) ; // Appendix D (K_{\mathbf{m}},K_{*},\mathcal{D},w_{*},q)\leftarrow\textsc{ResidualHamiltonAllocate}(\{w_{\mathbf{m}}\},K) ; // Appendix C 2 foreach counts vector \mathbf{m} with K_{\mathbf{m}}>0 do 3 for t\leftarrow 1 to K_{\mathbf{m}} do 4 \underline{\ell}\leftarrow\textsc{CountsConditionalSample}(\mathbf{m},\{p_{i}\},\mathcal{T}) ; // Appendix D Run \mathcal{U}(\underline{\ell}) and compress R repetitions into Y_{\mathbf{m},t} ; 5 end for 6 \widehat{\mu}_{\mathbf{m}}\leftarrow\frac{1}{K_{\mathbf{m}}}\sum_{t=1}^{K_{\mathbf{m}}}Y_{\mathbf{m},t} ; 7 end foreach 8 9 if K_{*}>0 then 10 for t\leftarrow 1 to K_{*} do 11 Sample \mathbf{m}\sim q(\cdot) on \mathcal{D} ; 12 \underline{\ell}\leftarrow\textsc{CountsConditionalSample}(\mathbf{m},\{p_{i}\},\mathcal{T}) ; 13 Run \mathcal{U}(\underline{\ell}) and form Y_{*,t} ; 14 end for 15 \widehat{\mu}_{*}\leftarrow\frac{1}{K_{*}}\sum_{t=1}^{K_{*}}Y_{*,t} ; 16 end if 17 else 18 \widehat{\mu}_{*}\leftarrow 0 ; 19 end if 20 21 return \widehat{Y}_{K,R}^{\mathrm{impl}}=\sum_{\mathbf{m}:K_{\mathbf{m}}>0}w_{\mathbf{m}}\widehat{\mu}_{\mathbf{m}}+w_{*}\,\widehat{\mu}_{*} ; 22 Algorithm 1 StratifiedQPDMC (counts-vector strata; residual-aware proportional allocation) Algorithm 1 gives pseudocode for the full routine. Under ideal proportional quotas K_{\mathbf{m}}=Kw_{\mathbf{m}} , the corresponding proportional estimator satisfies the never-worse guarantee in Theorem 1 . The residual-aware implementation preserves exact unbiasedness at finite K and, in our numerics, induces variance perturbations smaller than the reported bootstrap uncertainties. As such, our numerical simulations substantiate the guarantee of Theorem 1 on two specific problems and choice of statistic. III Numerical Results & Discussion We benchmark counts-vector stratification for product-form QPDs using first-order Trotter time evolution of the 1D transverse-field Ising model (TFIM) and two representative QPD schemes: probabilistic angle interpolation (PAI) and probabilistic error cancellation (PEC). Throughout we work at the configuration level: each sampled QPD variant (together with a specified measurement protocol) produces a single scalar outcome Y , possibly by compressing R repeated shots via the Born rule. For a fixed stratification statistic S (here the counts vector \mathbf{M} ), we compare naïve and proportional designs through the design-variance ratio (see Corollary 1 ) \rho(R):=\frac{\Var(\widehat{Y}_{K,R}^{\mathrm{impl}})}{\Var(\widehat{Y}_{K,R}^{\mathrm{naive}})}\in[0,1], (15) where R is the number of Born-rule repetitions per configuration and \widehat{Y}_{K,R}^{\mathrm{impl}} denotes our residual-aware proportional estimator (Algorithm 1 ). In the ideal proportional model \rho(R) is independent of K ; empirically, the finite- K apportionment effects are negligible in our numerics with K=8192 (Appendix E and Appendix C.5 ). Operationally, for fixed R , a ratio \rho(R)<1 corresponds to a constant-factor reduction in the required configuration budget K (and hence total executions N=KR assuming each configuration gets R shots) to reach a target precision. We emphasise that stratification cannot alter the asymptotic performance. III.1 Measurement models and interpretation We utilise three measurement models: (i) a single-shot model ( R=1 ), where each configuration is measured once and Y contains both configuration randomness and Born-rule noise; (ii) an oracle model, where each realised configuration Y=\underline{\ell} is assigned its exact conditional mean \mu_{\underline{\ell}} (equivalently the R\to\infty limit); and (iii) an intermediate choice R=64 , which suppresses the Born-rule contribution by \sim 1/R . This intermediate choice shows how \rho(R) interpolates between the oracle and single-shot limits. III.2 TFIM Trotter benchmark We simulate first-order (Lie–Trotter) time evolution for the TFIM Hamiltonian on a ring of n spins, H=h\sum_{j=1}^{n}X_{j}+J\sum_{j=1}^{n}Z_{j}Z_{j+1},\quad Z_{n+1}\equiv Z_{1}, with h=0.6 , J=0.7 , total time t=1.0 , initial state \rho_{0}=|0\rangle\!\langle 0|^{\otimes n} , and observable \langle X_{1}\rangle . We fix n=6 and vary the Trotter depth L . For each L and each design (naïve versus proportional-stratified) we draw K=8192 configurations, estimate design variances in the oracle and single-shot models, and form empirical ratios with bootstrap confidence bands (Appendix E ). In Appendix E.4 we also report the corresponding normalised absolute variances \Var(\widehat{Y}_{K,R})/\|g\|_{1}^{2} , whose ratios recover the \rho(R) curves shown here. III.3 PAI and PEC: variance ratios versus depth Probabilistic angle interpolation (PAI). In PAI 31 , each rotation is replaced by a three-term local QPD over nearby hardware-available angles. Over \nu rotations, configurations \underline{\ell}\in\{1,2,3\}^{\nu} induce counts-vector strata \mathbf{M}=(M_{1},M_{2},M_{3}),\quad\sum_{i=1}^{3}M_{i}=\nu, where each M_{i} counts up the occurrences of primitive index i in a given configuration, ignoring all order. Fig. 2 shows the variance ratios versus depth. In the single-shot model, stratification yields a modest but consistent improvement ( \widehat{\rho}^{\mathrm{shot}}\approx 0.9 ). In the oracle model, the same statistic yields substantially larger reductions ( \widehat{\rho}^{\mathrm{oracle}}\approx 0.3 – 0.6 ), indicating that counts capture a nontrivial fraction of configuration-level structure. The gradual degradation of \widehat{\rho}^{\mathrm{oracle}} with depth is consistent with increasing non-commutation and position-dependence, which makes configurations within a fixed counts stratum less homogeneous. Figure 2: PAI on TFIM Trotter circuits ( n=6 , h=0.6 , J=0.7 , t=1.0 ) estimating \langle X_{1}\rangle . For each depth L we draw K=8192 configurations and report empirical variance ratios under naïve and counts-vector proportional designs in the oracle (red) and single-shot (blue) models; the green curve shows R=64 . Bands denote bootstrap confidence intervals. The dashed orange curve shows the circuit QPD 1-norm \|g\|_{1} on a secondary axis. The circuit depths are given by \nu=12L . Probabilistic error cancellation (PEC). In PEC 58 , each ideal gate is accompanied by an inverse noise channel expressed as a local QPD over implementable noisy channels. We consider gate-independent single-qubit depolarising noise of strength p=0.01 after each unitary (applied on both qubits for two-qubit gates), giving a fixed-width local QPD over Pauli channels \{I,X,Y,Z\} . Configurations \underline{\ell}\in\{I,X,Y,Z\}^{\nu} induce strata \mathbf{M}=(M_{I},M_{X},M_{Y},M_{Z}),\quad\sum_{P\in\{I,X,Y,Z\}}M_{P}=\nu. Details of the PEC setup are given in Appendix J . Fig. 3 shows the empirical variance ratios. As for PAI, single-shot improvements are modest (typically \widehat{\rho}^{\mathrm{shot}}\approx 0.9 ), whereas the oracle ratios are substantially smaller (typically \widehat{\rho}^{\mathrm{oracle}}\approx 0.2 – 0.4 ), demonstrating that counts-vector stratification can remove a large fraction of the classical configuration variance even in the higher-overhead PEC setting. Why the counts-vector statistic works. For proportional stratification with statistic S , the ideal theory gives \Var(Y^{\mathrm{naive}})-\Var(Y^{\mathrm{prop}})=\Var_{s}(\mu_{s}) so the gain is governed by how much variation in configuration-level conditional means is explained by conditioning on S . In the oracle model this simplifies to \rho^{\mathrm{oracle}}(S)=1-R^{2}(S), where R^{2}(S) is the explained fraction of configuration-to-configuration mean variation. In the TFIM–PAI and TFIM–PEC benchmarks we observe 1-\rho^{\mathrm{oracle}} ranging from 0.26 up to 0.53 over depths L=2,\dots,8 ; see Appendix G for further discussion on this ‘explained variance’ perspective. Put simply, counts-vector stratification helps most when configurations that share the same counts vector also have similar conditional means \mu_{\underline{\ell}} , such that most of the configurational variance \Var_{\underline{\ell}}(\mu_{\underline{\ell}}) is “explained” by \mathbf{M} . Separately, among statistics that are permutation-invariant in the sense of depending only on multiplicities (and not on gate positions), the full counts vector is variance-minimal within the monotone coarsening hierarchy; see Appendix F (and the concrete counts-versus-parity comparison therein). We emphasise that stratification on coarser statistics (such as sign-parity) can be easily recovered from the counts-vector. For d\leq 4 and \nu up to ~10^{2} , the DP Algorithm 4 is practical on a personal workstation; for much larger problems coarsening or pruning will be required. In our implementation we elected to preserve unbiasedness and generality and were consequently limited to modest-depth simulations. We note that introducing a controlled bias can both yield further variance reductions (in the sense of mean-squared error), while simultaneously also improving the pre-compute complexity of the DP and conditional sampling algorithms by allowing for approximations instead. Generalising the results presented here into the bias-variance context is a promising direction for future work. IV Conclusion and Outlook Product-form QPD protocols introduce a purely classical source of uncertainty on top of intrinsic Born-rule shot noise: configuration variance which arises from randomising over circuit variants. Stratification helps reduce this additional variance. While many QPD protocols were originally motivated by NISQ-era constraints (e.g., error mitigation via circuit randomisation), circuit-level randomisation is now a broadly recurring motif across quantum algorithms and benchmarking: whenever an expectation value is ultimately obtained by sampling, one often benefits from introducing and then properly accounting for ensemble randomness. This remains true in early fault-tolerant settings, where shot budgets may be even tighter due to slow logical clock rates: even modest constant-factor reductions in the required number of configurations or shots can materially improve throughput especially on first-generation fault-tolerant machines. We cast these protocols as a two-level Monte Carlo estimator and used the law of total variance to isolate the configuration contribution. This viewpoint yields a general sampling-design principle: for any statistic S(\Lambda) on the configuration space, proportional stratification is unbiased and (under ideal proportional quotas) almost always decreases variance relative to naïve sampling at fixed configuration budget. Figure 3: PEC on the same TFIM Trotter circuits as in Fig. 2 , with gate-independent single-qubit depolarising noise ( p=0.01 ) after each unitary. We draw K=8192 configurations per L and report empirical variance ratios with bootstrap confidence bands. The dashed orange curve shows the circuit QPD 1-norm \|g\|_{1} on a secondary axis. The circuit depths are given by \nu=18L . We then instantiated this principle with a universal, permutation-invariant statistic—the counts vector —and made the resulting stratified design operational. For fixed local width d , a single dynamic programme over the induced Poisson-multinomial distribution computes all stratum weights and enables exact conditional sampling, with a one-off classical cost O(d\,\nu^{d}) and per-configuration sampling cost O(\nu d) . After preprocessing, the stratified routine is a drop-in replacement for naïve configuration sampling. In cases where \nu or d are large, the same variance reduction guarantee (Theorem 1 ) holds for coarser, but cheaper statistics like sign-parity, which has a classical cost O(\nu^{2}) independent of width d (see Appendix F ). On first-order Trotter benchmarks with probabilistic angle interpolation (PAI) and probabilistic error cancellation (PEC), counts-vector stratification consistently reduces configuration-level variance: improvements are modest but robust in Born-dominated single-shot regimes (about 10\% ), and substantially larger in oracle-like regimes where configuration variance dominates (up to \sim 60 – 80\% reduction in our case studies). As expected, these gains do not alter the exponential overhead set by \|g\|_{1}^{2} , but they reduce constant prefactors and therefore expand the practically useful range of existing QPD methods. Looking forward, the same variance-accounting framework suggests clear upgrade paths: (i) statistics that deliberately break permutation symmetry to explain more configuration-to-configuration variation, (ii) pilot schemes approximate variance-optimal (Neyman) allocation across strata, or on-line adaptive schemes to achieve further cost optimisations, (iii) scalable approximate preprocessing and controlled truncation for deeper circuits, and (iv) extensions to hierarchical settings with simultaneous randomisations, such as classical shadows or circuit cutting on top of QPD schemes. In this last case, a hierarchical stratification (derived from recursively applying the law of total variance) will be a natural way of reducing total resource costs. To summarise, our contribution here is to separate ensemble randomness from Born-rule noise and to show that sampling design—independent of QPD construction—offers provable, composable constant-factor savings for product-form QPD protocols. Data availability : The simulation code used is available on GitHub at https://github.com/joshua-dai/stratifiedQPD . Acknowledgements. We thank Simon Benjamin, Po-Wei Huang, Minjun Jeon, and Chusei Kiumi for helpful discussions. We additionally thank Ben Criger and the Cambridge Quantinuum team for stimulating initial conversations and sketching out an adaptive sampling scheme. JWD is supported by a Clarendon Fund Scholarship, University of Oxford. BK thanks UKRI for the Future Leaders Fellowship Theory to Enable Practical Quantum Advantage (MR/Y015843/1). BK also acknowledges funding from the EPSRC project Robust and Reliable Quantum Computing (RoaRQ, EP/W032635/1). This research was funded in part by UKRI (MR/Y015843/1). For the purpose of Open Access, the author has applied a CC BY public copyright licence to any Author Accepted Manuscript version arising from this submission. Appendix A Related Work and Connections to Variance-Reduction Techniques There is extensive work on reducing the overhead of QPD-based protocols by improving the decomposition itself , typically with the goal of reducing the circuit 1-norm \|g\|_{1} by exploiting structure in the circuit, noise model, or observable 26 ; 19 ; 47 ; 52 ; 59 ; 14 ; 32 . Examples include physically informed constructions 26 ; 19 ; 47 , specialised workflows in Clifford-dominated regimes 52 , and locality or light-cone arguments for pruning mitigation on local observables 59 ; 14 . These works primarily address the ensemble design problem: constructing a low-overhead QPD. The present paper addresses the complementary sampling design problem for a fixed product-form QPD. Given such a decomposition, one must still decide how to sample configurations from its typically enormous configuration space and how to aggregate outcomes into an estimator. In classical Monte Carlo, these choices are studied as variance-reduction techniques (VRTs) 33 ; 13 ; 37 , including conditioning/Rao–Blackwellization, stratification, control variates, and importance sampling 36 ; 51 . While standard in stochastic simulation, these tools have been less systematically developed for QPD-based quantum protocols as an explicit outer-layer design problem over circuit configurations (distinct from inner Born-rule sampling). A notable recent example is CV4Quantum 54 , which applies control variates to reduce the variance of PEC estimators under realistic conditions. CV4Quantum is a post-processing VRT: it starts from a fixed dataset of circuit outcomes and constructs a lower-variance estimator without modifying the configuration-sampling plan. By contrast, our approach modifies the configuration-sampling design itself (via stratified sampling with exact conditional draws) while preserving unbiasedness. The two approaches are compatible in principle. Alternatively, Ref. 1 also explicitly decomposes the variance of QP-based estimators into circuit-to-circuit and shot-to-shot contributions via the law of total variance, and observes that circuit-sampling distributions may be improved, including by splitting into complementary sub-distributions. We further develop stratification as a general sampling-design primitive for QPDs. The closest precedent to our work is Ref. 11 , which develops a PEC procedure for a gate-independent noise setting by grouping configurations into “sectors” according to the number of non-identity insertions and allocating sampling effort across sectors proportional to their weights. This sector statistic corresponds to a coarsening of the multinomial counts we present. Our framework generalises this sector picture by treating stratification as a first-class sampling-design primitive for arbitrary product-form QPDs. In particular, our contributions include: 1. Counts-vector stratification for inhomogeneous product QPDs. For general product-form QPDs with position-dependent local supports and weights, we identify the full multinomial counts vector as a canonical permutation-invariant statistic. For fixed local width d , this yields O(\nu^{d-1}) strata. We give a dynamic programme that computes all stratum masses exactly and supports exact conditional sampling (Appendix D ), yielding an unbiased drop-in replacement for naïve i.i.d. configuration sampling after one-off preprocessing. 2. A general “never-worse” guarantee and coarsening hierarchy. We show that under ideal proportional quotas, stratification on any statistic is unbiased and never has larger variance than naïve sampling at fixed configuration budget (Theorem 1 ). Moreover, coarsening a statistic yields a monotone variance hierarchy: conditioning on finer information cannot increase the proportional-stratified variance (Appendix F ). Binomial sectoring 11 arises as a special case. 3. Connections to classical allocation theory. We connect stratified variance decompositions to proportional and Neyman allocation 13 , and discuss pilot-based approximations to variance-optimal allocation in Appendix H . We also address a practical finite- K issue: ideal proportional quotas are non-integer. We therefore use integer apportionment together with a residual-stratum correction that preserves exact unbiasedness. Appendix C gives details, and Appendix E.6 quantifies the resulting (typically small) variance perturbation. Addendum. During the preparation of this manuscript, Myers et al. 42 introduced a stratified sampling approach for noise simulation that groups configurations into “fault-count” sectors and allocates samples across sectors according to their weights, similar to the approach of 11 but for the classical simulation of quantum noise rather than PEC (we note that the QPD mathematics are common to both). Specifically, the method in 42 exploits the weak-noise concentration of the configuration distribution on patterns with few fault insertions. In our framework, this fault-count statistic can be seen as a binomial coarsening of the full counts vector and fits naturally into the variance hierarchy discussed in see Appendix F . Conversely, our results provide a general-purpose stratification backbone for arbitrary product-form QPD ensembles, with a universal never-worse guarantee and an exact Poisson–Multinomial preprocessing scheme that supports conditional sampling. Appendix D of Ref. 42 notes that a dynamic programme can be used to compute Poisson–Binomial weights, corresponding to a one-dimensional special case of the Poisson–Multinomial construction employed here. Our development was carried out independently. Appendix B Exact moments and unbiasedness This appendix records exact finite-sum expressions for the mean and (design-level) variances induced by a product-form QPD, and clarifies unbiasedness for naïve and stratified estimators. These expressions provide ground truth for small instances where explicit enumeration is feasible. B.1 QPD ensemble and target mean Let a target channel admit a circuit-level QPD \mathcal{U}_{\mathrm{circ}}=\sum_{\underline{\ell}\in\mathbf{I}}g(\underline{\ell})\,\mathcal{U}(\underline{\ell}),\quad\|g\|_{1}:=\sum_{\underline{\ell}\in\mathbf{I}}|g(\underline{\ell})|, where \underline{\ell}=(\ell_{1},\dots,\ell_{\nu}) indexes a configuration in the product space \mathbf{I} of local primitives. Fix an input state \rho_{0} and a Pauli observable O with eigenvalues in \{\pm 1\} . Define the configuration-level oracle mean \mu_{\underline{\ell}}:=\Tr\!\big[O\,\mathcal{U}(\underline{\ell})(\rho_{0})\big]=\mathbb{E}[Z\mid\underline{\ell}], where Z\in\{\pm 1\} denotes a single measurement outcome when running configuration \underline{\ell} (Born-rule randomness). By linearity, \mu:=\Tr\!\big[O\,\mathcal{U}_{\mathrm{circ}}(\rho_{0})\big]=\sum_{\underline{\ell}}g(\underline{\ell})\,\mu_{\underline{\ell}}. (16) B.2 Naïve QPD sampling and unbiasedness The standard QPD sampling distribution is p(\underline{\ell}):=\frac{|g(\underline{\ell})|}{\|g\|_{1}}. (17) Given a sampled configuration \underline{\ell}\sim p and a measurement outcome Z (possibly compressed after R repeated shots), define the single-configuration estimator Y:=\|g\|_{1}\,\sign(g(\underline{\ell}))\,Z. (18) Then \mathbb{E}[Y\mid\underline{\ell}]=\|g\|_{1}\,\sign(g(\underline{\ell}))\,\mu_{\underline{\ell}}, and taking expectation over \underline{\ell}\sim p gives \displaystyle\mathbb{E}[Y] \displaystyle=\sum_{\underline{\ell}}p(\underline{\ell})\,\mathbb{E}[Y\mid\underline{\ell}] \displaystyle=\sum_{\underline{\ell}}\frac{|g(\underline{\ell})|}{\|g\|_{1}}\,\|g\|_{1}\,\sign(g(\underline{\ell}))\,\mu_{\underline{\ell}} \displaystyle=\sum_{\underline{\ell}}g(\underline{\ell})\,\mu_{\underline{\ell}}=\mu. (19) Thus the naïve QPD estimator is unbiased. B.3 Stratification and unbiasedness Let S=S(\underline{\ell}) be a deterministic stratification statistic with strata indexed by s\in\mathcal{S} . For example, the counts-vector statistic \mathbf{M} from the main text. Define stratum weights under the sampling distribution p : w_{s}:=\Pr(S=s)=\sum_{\underline{\ell}:\,S(\underline{\ell})=s}p(\underline{\ell})=\frac{1}{\|g\|_{1}}\sum_{\underline{\ell}\in s}|g(\underline{\ell})|. The conditional distribution within a stratum is p(\underline{\ell}\mid s)=\frac{p(\underline{\ell})}{w_{s}}=\frac{|g(\underline{\ell})|}{\sum_{\underline{\ell}^{\prime}\in s}|g(\underline{\ell}^{\prime})|}. Define the stratum conditional mean of Y (under p ) by \mu_{s}:=\mathbb{E}[Y\mid S=s]=\sum_{\underline{\ell}\in s}p(\underline{\ell}\mid s)\,\mathbb{E}[Y\mid\underline{\ell}]. Substituting ( 18 ) yields the convenient closed form \mu_{s}=\frac{1}{w_{s}}\sum_{\underline{\ell}\in s}g(\underline{\ell})\,\mu_{\underline{\ell}}. (20) Therefore \sum_{s}w_{s}\mu_{s}=\mu by summing over all partitions. This can also be obtained by using the law of total expectation. Unbiased stratified estimator. If one draws K_{s}\geq 1 samples within each stratum with w_{s}>0 and sets \widehat{\mu}_{s} to the sample mean within stratum s , then \widehat{\mu}_{\mathrm{strat}}:=\sum_{s}w_{s}\,\widehat{\mu}_{s}\quad\text{satisfies}\quad\mathbb{E}[\widehat{\mu}_{\mathrm{strat}}]=\mu. If some positive-mass strata receive K_{s}=0 , unbiasedness is preserved by the residual-bucket construction described in Appendix C (by sampling from the conditional mixture over the dropped set and adding a residual term w_{*}\widehat{\mu}_{*} ). B.4 Exact second moments and design variances This section records exact expressions for the single-sample/design variance \Var(Y) under a specified measurement model. The variance of the Monte Carlo estimator with K i.i.d. configuration draws is \Var(\widehat{\mu})=\Var(Y)/K in the naïve case, and \Var(\widehat{\mu})=\sum_{s}w_{s}^{2}\sigma_{s}^{2}/K_{s} (plus a residual term if present) in the stratified case. Oracle model In the oracle model we replace the measurement outcome by its conditional mean, i.e. Z\leftarrow\mu_{\underline{\ell}} , so Y becomes deterministic given \underline{\ell} (no shot noise): Y(\underline{\ell})=\|g\|_{1}\,\sign(g(\underline{\ell}))\,\mu_{\underline{\ell}}. The second moment under p is \displaystyle\mathbb{E}[Y^{2}] \displaystyle=\sum_{\underline{\ell}}p(\underline{\ell})\,Y(\underline{\ell})^{2}=\sum_{\underline{\ell}}\frac{|g(\underline{\ell})|}{\|g\|_{1}}\,\|g\|_{1}^{2}\,\mu_{\underline{\ell}}^{2} \displaystyle=\|g\|_{1}\sum_{\underline{\ell}}|g(\underline{\ell})|\,\mu_{\underline{\ell}}^{2}. (21) Hence the naïve oracle design variance is \Var_{\mathrm{oracle}}(Y^{\mathrm{naive}})=\|g\|_{1}\sum_{\underline{\ell}}|g(\underline{\ell})|\,\mu_{\underline{\ell}}^{2}-\mu^{2}. (22) Stratum moments (oracle). Within stratum s , Y takes values Y(\underline{\ell}) with probabilities p(\underline{\ell}\mid s) , so \sigma_{s}^{2}:=\Var(Y\mid S=s)=\mathbb{E}[Y^{2}\mid S=s]-\mu_{s}^{2}. Using Y(\underline{\ell})^{2}=\|g\|_{1}^{2}\mu_{\underline{\ell}}^{2} and the definition of p(\underline{\ell}\mid s) , \mathbb{E}[Y^{2}\mid S=s]=\frac{\|g\|_{1}}{w_{s}}\sum_{\underline{\ell}\in s}|g(\underline{\ell})|\,\mu_{\underline{\ell}}^{2},\quad\mu_{s}=\frac{1}{w_{s}}\sum_{\underline{\ell}\in s}g(\underline{\ell})\,\mu_{\underline{\ell}}. (23) The proportional stratified single-sample design variance is then \Var_{\mathrm{oracle}}(Y^{\mathrm{prop}})=\sum_{s}w_{s}\,\sigma_{s}^{2}, and the corresponding estimator variance under ideal proportional allocation is \Var(\widehat{\mu}^{\mathrm{prop}})=\Var(Y^{\mathrm{prop}})/K . Single-shot Pauli measurement model For Pauli observables with outcomes Z\in\{\pm 1\} , \Var(Z\mid\underline{\ell})=1-\mu_{\underline{\ell}}^{2} . Conditioned on \underline{\ell} , the estimator in ( 18 ) satisfies \Var(Y\mid\underline{\ell})=\|g\|_{1}^{2}\,\Var(Z\mid\underline{\ell})=\|g\|_{1}^{2}(1-\mu_{\underline{\ell}}^{2}). Applying the law of total variance over \underline{\ell}\sim p gives \displaystyle\Var(Y) \displaystyle=\mathbb{E}_{\underline{\ell}}\!\big[\Var(Y\mid\underline{\ell})\big]+\Var_{\underline{\ell}}\!\big(\mathbb{E}[Y\mid\underline{\ell}]\big) \displaystyle=\|g\|_{1}^{2}\sum_{\underline{\ell}}p(\underline{\ell})(1-\mu_{\underline{\ell}}^{2})+\Big(\|g\|_{1}\sum_{\underline{\ell}}|g(\underline{\ell})|\,\mu_{\underline{\ell}}^{2}-\mu^{2}\Big) \displaystyle=\|g\|_{1}^{2}-\mu^{2}. (24) Thus in Pauli \pm 1 special case the single-shot model the naïve design variance depends only on \|g\|_{1} and \mu . Intermediate R . If each configuration is measured R times and averaged before applying the QPD weight, then \Var(Z\mid\underline{\ell}) is replaced by \Var(Z\mid\underline{\ell})/R , so the Born-rule contribution interpolates between ( 24 ) and ( 22 ). B.5 Use in the main numerics The expressions above define exact ground truth quantities for small instances where the configuration space can be enumerated. This was done in Appendix E for PEC on a small Trotter instance. In the main simulations we estimate variances from sampled outcomes, and for stratified designs we use the residual-aware allocation and estimator-variance formulas described in Appendix C . Appendix C Integer allocation, truncation bias, and the residual-stratum fix This appendix specifies the finite- K allocation used in our experiments and its implications. Ideal proportional allocation assigns quota q_{s}\equiv Kw_{s} to each stratum s , which is generally non-integer. Since in practice we can only sample an integer number of times, to ensure unbiasedness we must carefully design our sampling scheme. In this section we (i) recall Hamilton (largest-remainder) apportionment as a deterministic rounding rule, (ii) quantify the truncation bias that results if strata with K_{s}=0 are dropped following a straightforward Hamilton apportionment scheme, and (iii) present a residual-stratum modification that restores exact unbiasedness for any finite K . The results in this appendix section hold for arbitrary stratification statistics S , as any proportional allocation scheme necessarily needs to deal with rounding. In the main text and Algorithm 1 we exclusively focus on the counts-vector statistic \mathbf{M} for simplicity. C.1 Setup Let S=S(\underline{\ell}) be the stratum statistic, with stratum weights w_{s}:=\Pr(S=s) , \sum_{s}w_{s}=1 . Let Y denote the per-configuration random variable (including any within-configuration averaging over R , if applicable), with \mu_{s}:=\mathbb{E}[Y\mid S=s],\,\sigma_{s}^{2}:=\Var(Y\mid S=s) such that \mu=\sum_{s}w_{s}\mu_{s} . We use the boundedness assumption |Y|\leq B,\quad B:=\ \lVert O\rVert_{\infty}\,\|g\|_{1}, (25) which holds for Hermitian observables with |O_{x}|\leq\ \lVert O\rVert_{\infty} and QPD weights bounded by \|g\|_{1} . C.2 Hamilton (largest remainder) apportionment Hamilton’s method maps quotas q_{s}=Kw_{s} to an array of non-negative integers (K_{s})_{s} with \sum_{s}K_{s}=K by rounding down and distributing the remaining units to the largest fractional remainders 2 ; 50 . In the following we will use (\cdot)_{s=1}^{S} to denote the array indexed from s=1 up to s=S . The pseudocode for Hamilton Apportionment is given in Algorithm 2 . Input: w=(w_{s})_{s=1}^{S} with w_{s}\geq 0 , \sum_{s}w_{s}=1 ; K\in\mathbb{Z}_{\geq 1} . Output: (K_{s})_{s=1}^{S}\in\mathbb{Z}_{\geq 0} with \sum_{s}K_{s}=K . q_{s}\leftarrow Kw_{s} for all s 1 K_{s}\leftarrow\lfloor q_{s}\rfloor for all s 2 r\leftarrow K-\sum_{s}K_{s} 3 \delta_{s}\leftarrow q_{s}-\lfloor q_{s}\rfloor for all s 4 Let I be the indices of the r largest \delta_{s} (ties broken deterministically) 5 for s\in I do 6 K_{s}\leftarrow K_{s}+1 end for 7 return (K_{s})_{s=1}^{S} 8 Algorithm 2 HamiltonApportion (w,K) Hamilton apportionment closely matches the quota in the sense that the output allocation satisfies |K_{s}-Kw_{s}|<1 for all s and also preserves total budget \sum_{s}K_{s}=K . However, it can assign K_{s}=0 to strata with w_{s}>0 (whenever w_{s}<1/K ). If such strata are omitted from estimation, the resulting estimator is biased for finite K , as this is mathematically equivalent to truncating all strata with w_{s}<1/K . C.3 Bias from dropping zero-allocation strata To see how this bias arises, let \mathcal{A}:=\{s:K_{s}>0\} and \mathcal{D}:=\{s:K_{s}=0,\ w_{s}>0\} for a given integer allocation, and let w_{\mathrm{drop}}:=\sum_{s\in\mathcal{D}}w_{s}. If one defines the truncated estimator \widehat{\mu}_{\mathrm{drop}}:=\sum_{s\in\mathcal{A}}w_{s}\,\widehat{\mu}_{s}, (26) then \mathrm{Bias}(\widehat{\mu}_{\mathrm{drop}})=\mathbb{E}[\widehat{\mu}_{\mathrm{drop}}]-\mu=-\sum_{s\in\mathcal{D}}w_{s}\mu_{s}, (27) and by ( 25 ) we obtain the worst-case bound on the bias due to truncation \bigl|\mathrm{Bias}(\widehat{\mu}_{\mathrm{drop}})\bigr|\leq B\,w_{\mathrm{drop}}=\ \lVert O\rVert_{\infty}\,\|g\|_{1}\,w_{\mathrm{drop}}. (28) So when the QPD distribution has a long tail with many strata with w_{s}<1/K (or for very small K ) w_{\mathrm{drop}} can be large, leading to a potentially significant bias if we use Hamilton apportionment directly. This motivates explicitly sampling the dropped mass via a residual stratum to correct the bias, which we implement in Algorithm 3 ResidualHamiltonAllocate . C.4 Residual-stratum construction for exact unbiasedness We introduce a residual stratum * that aggregates all zero-allocation strata, and allocate it an explicit budget K_{*} while preserving the global budget constraint. This restores exact unbiasedness for finite values of K . Residual stratum. Given a dropped set \mathcal{D} from processing the output of HamiltonApportion , define w_{*}:=\sum_{s\in\mathcal{D}}w_{s},\quad q(s):=\Pr(S=s\mid S\in\mathcal{D})=\frac{w_{s}}{w_{*}}\ \ \ (s\in\mathcal{D}). To sample from the stratum means in the residual we draw s\sim q(\cdot) , then draw \underline{\ell}\sim p(\underline{\ell}\mid S=s) , and evaluate Y on this circuit variant. Allocation routine (Hamilton + residual). Our implementation ResidualHamiltonAllocate is specified in Algorithm 3 . It (i) computes a Hamilton allocation with HamiltonApportion , (ii) plans a residual budget based on the initially dropped mass, (iii) borrows that many units from donor strata to keep the total budget fixed, and (iv) recomputes the dropped set (and hence the residual mixture) after borrowing. We then construct the proportional-stratified estimator.. Estimator construction. For each retained stratum s\in\mathcal{A}:=\{s:K_{s}>0\} , draw K_{s} i.i.d. samples from p(\underline{\ell}\mid S=s) and form \widehat{\mu}_{s} . For the residual stratum, draw K_{*} samples via the residual mixture and form \widehat{\mu}_{*} . Define \widehat{\mu}_{\mathrm{impl}}:=\sum_{s\in\mathcal{A}}w_{s}\,\widehat{\mu}_{s}+w_{*}\,\widehat{\mu}_{*}. (29) Proposition 1 (Exact unbiasedness with a residual stratum) . For any finite K , any allocations with K_{s}\geq 1 for s\in\mathcal{A} and K_{*}\geq 1 whenever w_{*}>0 , the estimator ( 29 ) satisfies \mathbb{E}[\widehat{\mu}_{\mathrm{impl}}]=\mu . Proof. For s\in\mathcal{A} , \mathbb{E}[\widehat{\mu}_{s}]=\mu_{s} . For the residual bucket, sampling is from the conditional mixture S\in\mathcal{D} , hence \mathbb{E}[\widehat{\mu}_{*}]=\sum_{s\in\mathcal{D}}(w_{s}/w_{*})\mu_{s} . Substituting into ( 29 ) gives \mathbb{E}[\widehat{\mu}_{\mathrm{impl}}]=\sum_{s}w_{s}\mu_{s}=\mu . ∎ Lemma 1 (Borrowing cannot exhaust donors) . Assume HamiltonApportion returns (K_{s})_{s=1}^{S} with \sum_{s}K_{s}=K , and the residual plan satisfies K_{*}\leq K . Then the borrowing phase in Algorithm 3 always achieves \mathrm{deficit}=0 (possibly creating additional zeros in the second pass, which we then re-group into the dropped set afterwards). Proof. In the second pass, a decrement is permitted whenever the current donor has K_{s}\geq 1 . The total number of admissible decrements before all donors reach zero equals \sum_{s}K_{s}=K . Since K_{*}\leq K , it is always possible to perform K_{*} decrements in total; hence \mathrm{deficit} must reach zero. ∎ Remark (why we recompute \mathcal{D} ). Since borrowing in the second pass may create new zero-allocated strata, to preserve exact unbiasedness, the residual mixture must be defined using the final dropped set \mathcal{D}=\{s:K_{s}=0,\ w_{s}>0\} after borrowing, as in Algorithm 3 . C.5 Variance impact of rounding and the residual fix Under ideal proportional allocation K_{s}=Kw_{s} (non-integer in general), the proportional stratified estimator has the simple variance result (see also ( 9 )) \Var(\widehat{\mu}_{\mathrm{prop}})=\sum_{s}\frac{w_{s}^{2}\sigma_{s}^{2}}{Kw_{s}}=\frac{1}{K}\sum_{s}w_{s}\sigma_{s}^{2}. (30) With integer allocations and a residual stratum, the implemented estimator variance is \Var(\widehat{\mu}_{\mathrm{impl}})=\sum_{s\in\mathcal{A}}\frac{w_{s}^{2}\sigma_{s}^{2}}{K_{s}}+\frac{w_{*}^{2}\sigma_{*}^{2}}{K_{*}}, (31) where \sigma_{*}^{2}:=\Var(Y\mid S\in\mathcal{D}) and \mathcal{A},\mathcal{D} are defined by the final allocation. Residual variance decomposition. Under the residual mixture q(s)=w_{s}/w_{*} , the law of total variance gives \sigma_{*}^{2}=\sum_{s\in\mathcal{D}}q(s)\,\sigma_{s}^{2}+\Var_{q}(\mu_{s}). (32) Input: w=(w_{s})_{s=1}^{S} with w_{s}\geq 0 , \sum_{s}w_{s}=1 ; K\in\mathbb{Z}_{\geq 1} . Output: Allocations (K_{s})_{s=1}^{S} , residual count K_{*} , final dropped set \mathcal{D} , dropped mass w_{*} , residual mixture q(\cdot) . (K_{s})_{s=1}^{S}\leftarrow\textsc{HamiltonApportion}(w,K) 1 \mathcal{D}_{0}\leftarrow\{s:K_{s}=0,\ w_{s}>0\} ; w_{\mathrm{drop},0}\leftarrow\sum_{s\in\mathcal{D}_{0}}w_{s} 2 K_{*}\leftarrow 0 3 if w_{\mathrm{drop},0}>0 then 4 K_{*}\leftarrow\max\{1,\mathrm{round}(K\,w_{\mathrm{drop},0})\} 5 \mathrm{deficit}\leftarrow K_{*} 6 Order strata by decreasing current K_{s} 7 foreach s in order do 8 while \mathrm{deficit}>0 and K_{s}\geq 2 do 9 K_{s}\leftarrow K_{s}-1 ; \mathrm{deficit}\leftarrow\mathrm{deficit}-1 10 end while 11 if \mathrm{deficit}=0 then 12 break end if 13 end foreach 14 if \mathrm{deficit}>0 then 15 Re-order strata by decreasing current K_{s} 16 foreach s in order do 17 while \mathrm{deficit}>0 and K_{s}\geq 1 do 18 K_{s}\leftarrow K_{s}-1 ; \mathrm{deficit}\leftarrow\mathrm{deficit}-1 19 end while 20 if \mathrm{deficit}=0 then 21 break end if 22 end foreach 23 end if 24 // Donors cannot be exhausted (Lemma 1 ). assert \mathrm{deficit}=0 25 end if 26 \mathcal{D}\leftarrow\{s:K_{s}=0,\ w_{s}>0\} ; w_{*}\leftarrow\sum_{s\in\mathcal{D}}w_{s} 27 if K_{*}>0 and w_{*}>0 then 28 Define q(s)=w_{s}/w_{*} for s\in\mathcal{D} 29 end if 30 else 31 K_{*}\leftarrow 0 ; \mathcal{D}\leftarrow\emptyset ; w_{*}\leftarrow 0 32 end if 33 assert \sum_{s=1}^{S}K_{s}+K_{*}=K 34 return (K_{s})_{s=1}^{S},\ K_{*},\ \mathcal{D},\ w_{*},\ q(\cdot) 35 Algorithm 3 ResidualHamiltonAllocate (w,K) Exact perturbation identity. Combining ( 30 )–( 32 ) yields \displaystyle\Var(\widehat{\mu}_{\mathrm{impl}})- \displaystyle\Var(\widehat{\mu}_{\mathrm{prop}})=\sum_{s\in\mathcal{A}}w_{s}^{2}\sigma_{s}^{2}\Bigl(\frac{1}{K_{s}}-\frac{1}{Kw_{s}}\Bigr) \displaystyle+\Bigl(\frac{w_{*}}{K_{*}}-\frac{1}{K}\Bigr)\sum_{s\in\mathcal{D}}w_{s}\sigma_{s}^{2}+\frac{w_{*}^{2}}{K_{*}}\Var_{q}(\mu_{s}). (33) A single computable certificate. Using ( 25 ), we have \sigma_{s}^{2}\leq B^{2} and \Var_{q}(\mu_{s})\leq B^{2} , hence \bigl|\Var(\widehat{\mu}_{\mathrm{impl}})-\Var(\widehat{\mu}_{\mathrm{prop}})\bigr|\leq\mathsf{Cert}_{\mathrm{var}}, (34) where \mathsf{Cert}_{\mathrm{var}}:=B^{2}\Bigg[\sum_{s\in\mathcal{A}}w_{s}^{2}\Bigl|\frac{1}{K_{s}}-\frac{1}{Kw_{s}}\Bigr|\;+\;w_{*}\Bigl|\frac{w_{*}}{K_{*}}-\frac{1}{K}\Bigr|\;+\;\frac{w_{*}^{2}}{K_{*}}\Bigg]. (35) Equivalently, \sqrt{\mathsf{Cert}_{\mathrm{var}}} upper-bounds the possible perturbation in estimator standard error induced purely by integer apportionment and residual aggregation. Typical scaling. If K_{s}\approx Kw_{s} for s\in\mathcal{A} and K_{*}\approx Kw_{*} , then the certificate terms are small; in particular, when K_{*}\asymp Kw_{*} the residual contributions scale as w_{*}\Bigl|\frac{w_{*}}{K_{*}}-\frac{1}{K}\Bigr|=O\!\left(\frac{w_{*}}{K^{2}}\right),\quad\frac{w_{*}^{2}}{K_{*}}=O\!\left(\frac{w_{*}}{K}\right), so small final dropped mass w_{*} suppresses the residual effect relative to the baseline O(1/K) Monte Carlo scaling. We will use the certificate values in Appendix E to verify that the implemented sampling routine under residual Hamilton apportionment does not significantly deviate from the ideal (non-integer) proportional allocation scheme. Specifically, we find that the certificate values obtained in our numerics are substantially smaller than the error bars, suggesting that the integerisation process do not materially affect our conclusions as to the variance reduction that proportional stratified sampling achieves. Appendix D Dynamic programmes for counts-vector strata This appendix records the dynamic programmes used to (i) compute counts-vector stratum weights w_{\mathbf{m}}=\Pr(\mathbf{M}=\mathbf{m}) and (ii) sample configurations \underline{\ell} conditionally on a target counts vector \mathbf{m} . Throughout, we focus on product distributions of the form p(\underline{\ell})=\prod_{i=1}^{\nu}p_{i}(\ell_{i}),\quad\ell_{i}\in[d]:=\{1,\dots,d\}, as induced by product-form QPD sampling with individual-primtiive probabilities p_{i}(\ell_{i})\propto|\gamma_{i}(\ell_{i})| (after converting signed coefficients into probabilities via \|g\|_{1} ). The statistic is the counts vector \mathbf{M}(\underline{\ell}) in ( 13 ). The induced distribution of \mathbf{M} is a Poisson-multinomial distribution (PMD), i.e. a sum of independent (but not necessarily identically distributed) categorical variables. D.1 Forward DP for stratum weights For i\in\{0,1,\dots,\nu\} and any \mathbf{m}\in\mathbb{Z}_{\geq 0}^{d} with \sum_{k}m_{k}=i , define W^{(i)}_{\mathbf{m}}:=\Pr\!\bigl(\mathbf{M}^{(i)}=\mathbf{m}\bigr), where \mathbf{M}^{(i)} is the counts vector of the prefix vector (\ell_{1},\dots,\ell_{i}) . Initialise W^{(0)}_{\mathbf{0}}=1 and W^{(0)}_{\mathbf{m}\neq\mathbf{0}}=0 . The standard PMD recursion is W^{(i)}_{\mathbf{m}}=\sum_{k=1}^{d}p_{i}(k)\,W^{(i-1)}_{\mathbf{m}-e_{k}}, (36) where e_{k} is the k th unit vector and W^{(i-1)}_{\mathbf{m}-e_{k}} is interpreted as 0 if any component of \mathbf{m}-e_{k} is negative. The desired stratum weights are the final layer w_{\mathbf{m}}:=W^{(\nu)}_{\mathbf{m}}\quad(\sum_{k}m_{k}=\nu). At layer i , the number of admissible states is \binom{i+d-1}{d-1} ; hence for fixed d , the total work needed to traverse all layers is O(d\,\nu^{d}) . Storing all layers uses O(\nu^{d}) memory and is convenient for the backward sampler below. (If only w_{\mathbf{m}} are needed, a rolling two-layer implementation suffices; however in our implementation we always store the full table). Note also that if we store \mathbf{m} as a tuple of length d-1 (since the last coordinate is determined by \sum m_{k}=i ), we can reduce memory by one row; however this means that look-ups become correspondingly more expensive and we lose the ability to sanity check each intermediate calculation). For simplicity we did not implement this optimisation. D.2 Backward conditional sampling given a counts vector Fix a target \mathbf{m} with \sum_{k}m_{k}=\nu and w_{\mathbf{m}}>0 . We generate \underline{\ell}\sim p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) by sampling indices in reverse order using the cached table \mathcal{T} and Bayes’ Rule. The details are in Algorithm 5 . Specifically, let \mathbf{m}^{(\nu)}=\mathbf{m} . For i=\nu,\nu-1,\dots,1 , define \displaystyle q_{i}(k\mid\mathbf{m}^{(i)}) \displaystyle:=\Pr(\ell_{i}=k\mid\mathbf{M}^{(i)}=\mathbf{m}^{(i)}) \displaystyle=\frac{p_{i}(k)\,W^{(i-1)}_{\mathbf{m}^{(i)}-e_{k}}}{W^{(i)}_{\mathbf{m}^{(i)}}}, (37) with the convention q_{i}(k\mid\mathbf{m}^{(i)})=0 when \mathbf{m}^{(i)}-e_{k} is invalid (any negative integer entries). Sample \ell_{i}\sim q_{i}(\cdot\mid\mathbf{m}^{(i)}) and update \mathbf{m}^{(i-1)}\leftarrow\mathbf{m}^{(i)}-e_{\ell_{i}} . The resulting \underline{\ell}=(\ell_{1},\dots,\ell_{\nu}) has counts vector \mathbf{m} by construction. Since this only requires traversing all rows in the table once, the time-complexity of each conditional sample is just O(\nu d) . Input: Local categorical probabilities p_{i}(\cdot) on [d] for each i\in[\nu] . Output: Final weights \{w_{\mathbf{m}}\} and cached table \mathcal{T}=\{W^{(i)}_{\mathbf{m}}\}_{i=0}^{\nu} . 1 Initialise W^{(0)}_{\mathbf{0}}\leftarrow 1 and W^{(0)}_{\mathbf{m}\neq\mathbf{0}}\leftarrow 0 2 for i\leftarrow 1 to \nu do 3 foreach \mathbf{m}\in\mathbb{Z}_{\geq 0}^{d} with \sum_{k}m_{k}=i do 4 W^{(i)}_{\mathbf{m}}\leftarrow 0 5 for k\leftarrow 1 to d do 6 if m_{k}>0 then 7 W^{(i)}_{\mathbf{m}}\leftarrow W^{(i)}_{\mathbf{m}}+p_{i}(k)\,W^{(i-1)}_{\mathbf{m}-e_{k}} 8 end if 9 end for 10 end foreach 11 end for 12 Set w_{\mathbf{m}}\leftarrow W^{(\nu)}_{\mathbf{m}} for all \mathbf{m} with \sum_{k}m_{k}=\nu 13 return (\{w_{\mathbf{m}}\},\ \mathcal{T}) 14 Algorithm 4 CountsForwardDP (\{p_{i}\}_{i=1}^{\nu}) D.3 Correctness (sketch) We briefly justify that (i) the forward DP computes the exact PMD prefix probabilities, and (ii) the backward procedure produces exact conditional samples. Proposition 2 (Forward DP correctness) . For every i\in\{0,1,\dots,\nu\} and every \mathbf{m}\in\mathbb{Z}_{\geq 0}^{d} with \sum_{k}m_{k}=i , the forward DP values satisfy W^{(i)}_{\mathbf{m}}\;=\;\Pr\!\bigl(\mathbf{M}^{(i)}=\mathbf{m}\bigr)\quad\text{under}\quad p(\ell_{1:i})=\prod_{j=1}^{i}p_{j}(\ell_{j}). In particular, the stratum weights are w_{\mathbf{m}}=W^{(\nu)}_{\mathbf{m}} . Proof. We argue by induction on i . The base case i=0 holds by construction: W^{(0)}_{\mathbf{0}}=1=\Pr(\mathbf{M}^{(0)}=\mathbf{0}) and W^{(0)}_{\mathbf{m}}=0 otherwise. For the inductive step, fix i\geq 1 and an admissible \mathbf{m} with \sum_{k}m_{k}=i . Partition on the last index \ell_{i}\in[d] , then: \Pr(\mathbf{M}^{(i)}=\mathbf{m})=\sum_{k=1}^{d}\Pr(\ell_{i}=k)\,\Pr(\mathbf{M}^{(i-1)}=\mathbf{m}-e_{k}). Since \Pr(\ell_{i}=k)=p_{i}(k) and \Pr(\mathbf{M}^{(i-1)}=\mathbf{m}-e_{k})=0 when \mathbf{m}-e_{k} has a negative entry, the recursion is exactly ( 36 ). Applying the inductive hypothesis to the (i\!-\!1) -prefix probabilities yields W^{(i)}_{\mathbf{m}}=\Pr(\mathbf{M}^{(i)}=\mathbf{m}) . ∎ Proposition 3 (Backward sampler correctness) . Fix any target \mathbf{m} with \sum_{k}m_{k}=\nu and w_{\mathbf{m}}=W^{(\nu)}_{\mathbf{m}}>0 . Algorithm 5 outputs a configuration \underline{\ell}=(\ell_{1},\dots,\ell_{\nu}) distributed as p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) . Proof. Let \mathbf{m}^{(\nu)}=\mathbf{m} , and after sampling \ell_{i} define the update \mathbf{m}^{(i-1)}=\mathbf{m}^{(i)}-e_{\ell_{i}} as in the algorithm. For each i and any admissible \mathbf{m}^{(i)} with W^{(i)}_{\mathbf{m}^{(i)}}>0 , Bayes’ rule gives \displaystyle\Pr(\ell_{i}=k\mid\mathbf{M}^{(i)}=\mathbf{m}^{(i)}) \displaystyle=\frac{\Pr(\ell_{i}=k,\mathbf{M}^{(i)}=\mathbf{m}^{(i)})}{\Pr(\mathbf{M}^{(i)}=\mathbf{m}^{(i)})} \displaystyle=\frac{p_{i}(k)\,W^{(i-1)}_{\mathbf{m}^{(i)}-e_{k}}}{W^{(i)}_{\mathbf{m}^{(i)}}} which is exactly ( 37 ) and matches the categorical law used in Algorithm 5 . Applying the chain rule for conditional probabilities yields the joint law of the sampled sequence: \Pr(\ell_{1:\nu}=\underline{\ell}\mid\mathbf{M}=\mathbf{m})=\prod_{i=\nu}^{1}\Pr(\ell_{i}\mid\mathbf{M}^{(i)}=\mathbf{m}^{(i)}). The update rule \mathbf{m}^{(i-1)}=\mathbf{m}^{(i)}-e_{\ell_{i}} ensures that the sampled prefix always remains consistent with the remaining counts. Therefore, the algorithm samples exactly from p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) . ∎ Input: Target \mathbf{m}\in\mathbb{Z}_{\geq 0}^{d} with \sum_{k}m_{k}=\nu ; local probabilities \{p_{i}\} ; cached table \mathcal{T}=\{W^{(i)}_{\mathbf{m}}\} . Output: Configuration \underline{\ell}\sim p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) . 1 \mathbf{m}^{(\nu)}\leftarrow\mathbf{m} 2 for i\leftarrow\nu to 1 do 3 for k\leftarrow 1 to d do 4 if m^{(i)}_{k}>0 and W^{(i)}_{\mathbf{m}^{(i)}}>0 then 5 q_{i}(k)\leftarrow\dfrac{p_{i}(k)\,W^{(i-1)}_{\mathbf{m}^{(i)}-e_{k}}}{W^{(i)}_{\mathbf{m}^{(i)}}} 6 else 7 q_{i}(k)\leftarrow 0 8 end if 9 end for 10 Sample \ell_{i} from the categorical distribution q_{i}(\cdot) 11 \mathbf{m}^{(i-1)}\leftarrow\mathbf{m}^{(i)}-e_{\ell_{i}} 12 end for 13 return \underline{\ell}=(\ell_{1},\dots,\ell_{\nu}) 14 Algorithm 5 CountsConditionalSample (\mathbf{m},\{p_{i}\}_{i=1}^{\nu},\mathcal{T}) Intuition. The backward pass is a sequence of exact conditional draws: at step i it samples \ell_{i} from the correct conditional distribution given the remaining counts \mathbf{m}^{(i)} , then updates the remaining counts accordingly. This enforces \mathbf{M}(\underline{\ell})=\mathbf{m} while preserving the correct conditional law. D.4 Implementation notes and alternatives The forward DP described above is an exact algorithm for Poisson–multinomial probabilities; it is a generalisation of the DP for calculating the density function of a Poisson-binomial distribution 21 and also see the PMD review in Ref. 35 . The Poisson-binomial case can be easily recovered as a special case. Alternatively, computing only the PMD marginal weights \{w_{\mathbf{m}}\} can also be done by polynomial/convolution methods (including FFT/DFT variants) and by Gaussian approximation schemes that scale to substantially larger (\nu,d) 35 . Our application, however, requires repeated sampling from the conditional law p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) across many strata, which these other algorithms do not readily facilitate. However, there are trade-offs to our approach. Scaling, memory, and parallelism. A practical limitation of our implementation of counts-vector stratification is the growth of the DP state space with width d . The number of distinct counts vectors for fixed (\nu,d) is |\mathcal{S}|=\binom{\nu+d-1}{d-1}=O(\nu^{d-1}) , and caching the intermediate tables required for exact backward sampling scales as O(\nu^{d}) in memory. So while the complexity scales polynomially in \nu for a fixed d , it scales exponentially in d . Figure 4 reports the total number of cached DP states \sum_{i=0}^{\nu}\binom{i+d-1}{d-1} as a function of (\nu,d) . In our numerical experiments (Section III ), moderate depths together with modest widths already approach memory limits on consumer hardware ( \nu\sim 100 , d=4 ). The forward pass costs O(d\,\nu^{d}) arithmetic operations, while exact backward sampling requires access to the cached tables \{W^{(i)}_{\mathbf{m}}\} . We note that it is also possible to compute marginal values “on-the-fly” rather than storing the full table, at the cost of increasing the run-time required to generate each sample. However, this is fairly inefficient, as once these tables are cached conditional samples \underline{\ell}\sim p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) can be generated independently, so the backward sampler can be parallelised (with shared read-only access to the cached DP table). Numerical stability. Because w_{\mathbf{m}} can become very small for large \nu , numerical underflow can arise in principle. Standard safeguards include storing W in log space, or renormalising each layer and tracking scaling factors. We did not encounter instabilities in the instances benchmarked here, but guarding against underflow is important for larger depths and/or more extreme inhomogeneity. Figure 4: State-space scaling of the cached counts-vector DP. Shown is the number of reachable DP states \sum_{i=0}^{\nu}\binom{i+d-1}{d-1} , i.e. the size of the cached forward table required to compute exact counts-marginals and to enable exact backward conditional sampling. As a simple architecture-agnostic proxy, we annotate 1 GB/1 TB reference lines assuming one float64 (8 bytes) stored per state. Real implementations typically incur constant-factor overheads (data type, number of cached layers, metadata, etc.), or benefit from sparse/compressed representations, but the state count captures the fundamental scaling with (\nu,d) . State-space concentration and motivation for pruning. Although the DP must enumerate all reachable counts vectors to compute exact marginals and support exact conditional sampling, the induced Poisson–multinomial distribution is often sharply concentrated in practical product-form QPDs, because certain local primitives are much rarer than others (e.g. antipodal rotations in PAI, or non-identity inverse-error insertions in PEC). Figure 5 quantifies this effect for the TFIM–PAI instances of Section III : for each Trotter depth L we sort strata by decreasing mass and plot the cumulative mass \sum_{i\leq t}w_{(i)} . Across depths, the smallest index t_{0.99} capturing 99\% of the total mass corresponds to only \sim 2\% – 9\% of the reachable strata. Operationally, this strongly motivates approximate variants in which the DP computation and/or cached state space are pruned toward the high-mass region. However, we do not use pruning in the main experiments: all results in the paper use the exact DP to compute \{w_{\mathbf{m}}\} and to enable exact sampling from p(\underline{\ell}\mid\mathbf{M}=\mathbf{m}) . Nevertheless, Fig. 5 suggests that for larger (\nu,d) one can plausibly trade a controlled approximation (or controlled bias, if desired) for substantial reductions in preprocessing cost. Developing pruning/coarsening rules that preserve a usable backward sampler is therefore a natural next step. Figure 5: Counts-vector stratum mass concentration for TFIM–PAI. For each Trotter depth L , we compute the counts-vector stratum weights w_{\mathbf{m}}=\Pr(\mathbf{M}=\mathbf{m}) (Poisson–multinomial marginals) and sort strata by decreasing mass w_{(1)}\geq w_{(2)}\geq\cdots . Shown is the cumulative mass \sum_{i\leq t}w_{(i)} versus sorted index t (log-scale). The horizontal dashed line marks 0.99, and the vertical dashed line marks the smallest index t_{0.99} such that \sum_{i\leq t_{0.99}}w_{(i)}\geq 0.99 . Each panel reports the threshold t_{0.99} and the ratio t_{0.99}/|\mathcal{S}| (labelled ‘Thresh’ and ‘Ratio’ respectively), where |\mathcal{S}| is the number of reachable DP states (counts-vector strata). In this TFIM–PAI instance ( d=3 at every location), |\mathcal{S}|=\binom{\nu+d-1}{d-1} . Across depths, 99\% of the stratum mass is supported on only \sim 2\% – 9\% of strata, illustrating a pronounced head–tail structure and motivating truncated/coarsened variants of the exact DP. Appendix E Numerical methodology: variance estimation, bootstrap uncertainty, absolute variances, and validation This appendix documents the numerical procedures used in Section III to (i) estimate the estimator variance under each sampling design, (ii) attach uncertainty bands via a nonparametric bootstrap, (iii) report \|g\|_{1} -normalised absolute variances (Appendix E.4 ), and (iv) validate our implementations against an exactly enumerable toy instance (Appendix E.5 ). Throughout, a single run of a sampling design (naïve or proportional-stratified) produces realised per-configuration scalars \{Y_{j}\}_{j=1}^{K} , where each Y_{j} may already include an R -shot average as in ( 4 ). We write \hat{\mu}:=\widehat{Y}^{(R)}_{K} for the corresponding mean estimator (naïve or stratified) of this dataset. E.1 Estimator variance versus design variance The main reported quantity is the variance of the mean estimator \Var(\hat{\mu}) . For the naïve i.i.d. design, \Var(\hat{\mu}_{\mathrm{naive}})=\Var(Y)/K . For ideal proportional stratification (non-integer quotas) one has \Var(\hat{\mu}_{\mathrm{prop}})=(1/K)\sum_{s}w_{s}\sigma_{s}^{2} , while our implemented estimator uses the residual-aware form from Appendix C which has an additional correction term to the variance (which we emphasise is small in our experiments). In figures intended to compare against K -independent reference values (e.g. convergence checks), we additionally report the scaled estimator variance K\,\widehat{\Var}(\hat{\mu}), which equals \Var(Y) for the i.i.d. design and equals \sum_{s}w_{s}\sigma_{s}^{2} for ideal proportional stratification. Since this is a linear scaling, all confidence intervals scale directly. E.2 Plug-in estimators for the Variance Here we note the formulae for estimating \Var(\hat{\mu}) . Naïve design. Given realised samples \{Y_{j}\}_{j=1}^{K} , define \bar{Y}:=\frac{1}{K}\sum_{j=1}^{K}Y_{j},\quad s^{2}:=\frac{1}{K-1}\sum_{j=1}^{K}(Y_{j}-\bar{Y})^{2}. We use the standard plug-in estimator \widehat{\Var}(\hat{\mu}_{\mathrm{naive}}):=\frac{s^{2}}{K}. (38) Residual-aware stratified design. Let \mathcal{A} be the retained strata with realised counts K_{s}\geq 1 , and let (w_{*},K_{*}) denote the residual bucket weight and realised count (Appendix C ). Within each retained stratum compute the unbiased sample variance s_{s}^{2} from the realised \{Y_{s,t}\}_{t=1}^{K_{s}} , and similarly compute s_{*}^{2} from residual draws if K_{*}>1 . We then estimate \widehat{\Var}(\hat{\mu}_{\mathrm{impl}}):=\sum_{s\in\mathcal{A}}w_{s}^{2}\,\frac{s_{s}^{2}}{K_{s}}\;+\;w_{*}^{2}\,\frac{s_{*}^{2}}{K_{*}} (39) using the exact population quantities w_{s} and w_{*} obtained via the DP. The resulting estimator of the variance is the empirical quantity used both for absolute variances and for variance ratios in the main text. E.3 Nonparametric bootstrap uncertainty bands To obtain uncertainty bands on our estimate of the variance we use a nonparametric bootstrap with B=1024 resamples in all plots. Bootstrap for \widehat{\Var}(\hat{\mu}) : naïve. For b=1,\dots,B , draw a resample \{Y_{j}^{*(b)}\}_{j=1}^{K} by sampling with replacement from \{Y_{j}\}_{j=1}^{K} . Compute s_{*(b)}^{2} and set \widehat{\Var}^{(b)}(\hat{\mu}_{\mathrm{naive}}):=s_{*(b)}^{2}/K. Percentile intervals of \{\widehat{\Var}^{(b)}(\hat{\mu}_{\mathrm{naive}})\}_{b=1}^{B} define the reported bands. Bootstrap for \widehat{\Var}(\hat{\mu}) : stratified (residual-aware). For each stratum s\in\mathcal{A} , resample within the stratum by sampling with replacement from the realised \{Y_{s,t}\}_{t=1}^{K_{s}} , preserving K_{s} . If a residual bucket is present, resample within the residual pool of size K_{*} . Compute the resampled variances s_{s,*(b)}^{2} and (if applicable) s_{*,*(b)}^{2} , and set \widehat{\Var}^{(b)}(\hat{\mu}_{\mathrm{impl}}):=\sum_{s\in\mathcal{A}}w_{s}^{2}\,\frac{s_{s,*(b)}^{2}}{K_{s}}\;+\;w_{*}^{2}\,\frac{s_{*,*(b)}^{2}}{K_{*}}. Percentile intervals over b again yield uncertainty bands. Bootstrap for variance ratios. For a fixed problem instance and fixed K , let \widehat{\Var}(\hat{\mu}_{\mathrm{impl}}) and \widehat{\Var}(\hat{\mu}_{\mathrm{naive}}) be the plug-in estimator variances from independent runs. We report \widehat{\rho}:=\frac{\widehat{\Var}(\hat{\mu}_{\mathrm{impl}})}{\widehat{\Var}(\hat{\mu}_{\mathrm{naive}})}. To attach bands, we bootstrap the two runs independently and form \widehat{\rho}^{(b)}:=\frac{\widehat{\Var}^{(b)}(\hat{\mu}_{\mathrm{impl}})}{\widehat{\Var}^{(b)}(\hat{\mu}_{\mathrm{naive}})}. Percentiles of \{\widehat{\rho}^{(b)}\}_{b=1}^{B} define the reported confidence bands. When both designs use the same K (as in this paper), the factor of K cancels in the ratio, so \widehat{\rho} is identical whether interpreted in terms of \Var(\hat{\mu}) or K\Var(\hat{\mu}) . E.4 Absolute variances Section III emphasised the ratio between the naïve and proportional-stratified estimators which isolated the constant-factor improvement due to stratified configuration sampling. For completeness, here in Fig. 7 and 6 we report the corresponding absolute estimator variances normalised by the circuit QPD 1-norm squared, i.e. \Var(\widehat{Y}_{K,R})/\|g\|_{1}^{2} , for both naïve and proportional designs to emphasise the identical asymptotic scaling. For Pauli-valued observables |O_{x}|\leq 1 and QPD weights satisfy |w(\underline{\ell})|=\|g\|_{1} , so |Y^{(R)}|\leq\|g\|_{1} almost surely. Hence \frac{\Var(\widehat{Y}_{K,R})}{\|g\|_{1}^{2}}=\frac{1}{K}\frac{\Var(Y^{(R)})}{\|g\|_{1}^{2}}\leq\frac{1}{K}, independently of depth L and measurement model R . The grey horizontal line in both plots shows this bound for our fixed K=8192 . Specifically, normalising by \|g\|_{1}^{2} removes the dominant exponential scale set by the QPD overhead, allowing remaining dependence on L and R to be compared directly. The variance ratios \rho(R) in the main text are obtained by taking, at each (L,R) , the ratio of the stratified and naïve curves. Normalised absolute estimator variances for the TFIM benchmark. We plot \widehat{\Var}(\widehat{Y}_{K,R})/\|g\|_{1}^{2} versus Trotter depth L at fixed configuration budget K=8192 , for naïve sampling and counts-vector proportional stratification, under three measurement models: single-shot (blue R=1 ), intermediate (green R=64 ), and oracle (red R=\infty ). The horizontal grey line shows the bound 1/K , which follows from |Y^{(R)}|\leq\|g\|_{1} for Pauli observables. Importantly, note how both naive and stratified exhibit the same asymptotic scaling with \|g\|_{1}^{2} . The corresponding variance ratios \rho(R) plotted in the main text are obtained by taking, at each L and R , the ratio of the stratified (solid) and naïve (dashed) curves. Figure 6: TFIM-PAI absolute variance scaling against 1-norm Figure 7: TFIM-PEC absolute variance scaling against 1-norm E.5 Monte Carlo validation and implementation diagnostics To validate our implementations (naïve sampling, stratified sampling, and the residual-aware apportionment), we performed convergence checks on a small PEC instance where exact enumeration is feasible. Enumerable PEC instance. We consider a TFIM Trotter circuit with n=3 qubits, L=1 , and open boundary conditions. As in the main text we fix h=0.6 , J=0.7 , and t=1.0 , and add a single-qubit depolarising noise channel of strength p=0.01 after each gate (independently for the two legs of two-qubit gates). This yields \nu=7 local PEC QPD locations. Each location has a 4-term local QPD, so there are 4^{7}=16384 circuit variants. In the oracle model, exact reference values for the mean and the design variances are available by explicit summation. (When performing classical simulations, Born-rule noise is just an additional sampling layer on top of oracle outputs, so we focus on the oracle setting here.) Figure 8: Trotter TFIM circuit with n=3 , L=1 , open boundary conditions. In the convergence checks we apply a single-qubit depolarising channel of strength p=0.01 after each gate (independently for the two-qubit rotations). Convergence of mean and variance estimates. Fig. 9 shows Monte Carlo convergence of (a) the mean estimator and (b) the scaled estimator variance K\,\widehat{\Var}(\hat{\mu}) , for both naïve and stratified designs, against the exact values obtained by full enumeration. Bands are 95\% bootstrap intervals with B=1024 resamples, using the procedures in Appendix E.3 . Figure 9: Monte Carlo convergence checks for an exactly enumerable PEC instance in the oracle model. The mean and the scaled estimator variances K\,\widehat{\Var}(\hat{\mu}) converge to the exact values obtained by explicit summation over all 4^{7} configurations. Shaded bands denote 95\% bootstrap confidence intervals with B=1024 resamples. E.6 Certificate for apportionment-induced variance perturbations The proportional stratification results in Section II.4 are stated for ideal (generally non-integer) quotas K_{s}=Kw_{s} . Our implementation uses integer apportionment (Hamilton’s method) together with a residual stratum aggregating all zero-allocation strata, which preserves exact unbiasedness at finite K (Appendix C ). This subsection records a deterministic certificate bounding the deviation between the implemented estimator variance and the ideal proportional-allocation variance due purely to finite- K rounding and residual aggregation. Deterministic certificate. Assume the per-configuration random variable is almost surely bounded as |Y|\leq B (in our PEC/PAI numerics with Pauli observables, B=\ \lVert O\rVert_{\infty}\|g\|_{1} with \ \lVert O\rVert_{\infty}=1 ). Let K_{s} denote the final integer allocations over the original strata, and let (w_{*},K_{*}) denote the residual weight and residual shot count after borrowing. Define \mathcal{A}:=\{s:K_{s}>0\} and \mathcal{D}:=\{s:K_{s}=0,\,w_{s}>0\} so that w_{*}=\sum_{s\in\mathcal{D}}w_{s} . Using the perturbation decomposition in Appendix C.5 together with the bounds \sigma_{s}^{2}\leq B^{2} and \Var_{\pi}(\mu_{s})\leq B^{2} , we obtain \displaystyle\bigl|\Var(\widehat{\mu}_{\mathrm{impl}})-\Var(\widehat{\mu}_{\mathrm{prop}})\bigr|\leq\mathrm{Cert}_{\mathrm{var}}, (40) with \mathrm{Cert}_{\mathrm{var}}:=B^{2}\left(T_{\mathrm{i}}+T_{\mathrm{ii}}+T_{\mathrm{iii}}\right), where \displaystyle T_{\mathrm{i}} \displaystyle:=\sum_{s\in\mathcal{A}}w_{s}^{2}\left|\frac{1}{K_{s}}-\frac{1}{Kw_{s}}\right|\quad\text{(retained rounding)}, (41) \displaystyle T_{\mathrm{ii}} \displaystyle:=w_{*}\left|\frac{w_{*}}{K_{*}}-\frac{1}{K}\right|\quad\text{(residual quota mismatch)}, (42) \displaystyle T_{\mathrm{iii}} \displaystyle:=\frac{w_{*}^{2}}{K_{*}}\quad\text{(residual aggregation penalty)}. (43) Moreover, since \bigl|\sqrt{u}-\sqrt{v}\bigr|\leq\sqrt{|u-v|} for u,v\geq 0 , the quantity \sqrt{\mathrm{Cert}_{\mathrm{var}}} gives a conservative scale for possible standard-error perturbations induced by finite- K apportionment and residual aggregation. Observed scale. On the enumerable PEC instance above, the certificate is conservative by one to three orders of magnitude, consistent with the use of worst-case bounds. On the main TFIM benchmarks ( K=8192 ), we observe small residual masses ( w_{*}\sim 10^{-4} – 10^{-3} with K_{*} of order 1 – 10 ), and \sqrt{\mathrm{Cert}_{\mathrm{var}}} is a modest fraction of the empirical standard error. This supports interpreting the reported variance reductions as insensitive to the finite- K apportionment details. Appendix F Coarsening and hierarchy of permutation-invariant strata Stratification depends on a choice of statistic S(\underline{\ell}) that partitions the configuration space into strata. This appendix records a simple but useful monotonicity principle: refining the statistic (i.e. using more information) cannot increase the variance of the proportional-allocation stratified estimator, for a fixed measurement model (fixed R ). Refinements and monotonicity. Let S and S^{\prime} be two statistics of \underline{\ell} , and say that S^{\prime} refines S if S=f(S^{\prime}) for some deterministic map f (equivalently, every S^{\prime} -stratum is contained in an S -stratum). Write \Var(\widehat{Y}_{K}^{\mathrm{prop}};S) for the variance of the proportional stratified estimator when strata are defined by S . Under ideal proportional quotas K_{s}=K\,w_{s} (ignoring integrality), we have \Var(\widehat{Y}_{K}^{\mathrm{prop}};S^{\prime})\;\leq\;\Var(\widehat{Y}_{K}^{\mathrm{prop}};S). (44) One way to see this is to note that, under proportional allocation, \Var(\widehat{Y}_{K}^{\mathrm{prop}};S)=\frac{1}{K}\,\mathbb{E}\!\left[\Var(Y\mid S)\right], and conditioning on a finer \sigma -algebra can only decrease conditional variance on average (i.e. \mathbb{E}[\Var(Y\mid S^{\prime})]\leq\mathbb{E}[\Var(Y\mid S)] when S=f(S^{\prime}) ). The finest statistic and an absolute lower bound. The finest possible statistic is the full configuration label S_{\mathrm{full}}(\underline{\ell}):=\underline{\ell}. In this case each stratum contains a single configuration, so \mu_{S_{\mathrm{full}}}=\mu_{\underline{\ell}} and \sigma^{2}_{S_{\mathrm{full}}}=\Var(Y\mid\underline{\ell}) , and proportional stratification yields \displaystyle\Var(\widehat{Y}_{K}^{\mathrm{prop}};S_{\mathrm{full}}) \displaystyle=\frac{1}{K}\sum_{\underline{\ell}}p(\underline{\ell})\,\Var(Y\mid\underline{\ell}) \displaystyle=\frac{1}{K}\mathbb{E}_{\underline{\ell}}\!\left[\Var(Y\mid\underline{\ell})\right]. (45) Comparing ( 45 ) with the law of total variance, \Var(Y)=\mathbb{E}_{\underline{\ell}}[\Var(Y\mid\underline{\ell})]+\Var_{\underline{\ell}}(\mu_{\underline{\ell}}), shows that S_{\mathrm{full}} removes all configuration variance \Var_{\underline{\ell}}(\mu_{\underline{\ell}}) and leaves only within-configuration noise (Born-rule noise under the measurement model). It is therefore an absolute lower bound among stratified designs that use the same per-configuration estimator Y . Permutation-invariant coarsenings: counts-vector and sign parity. In product-form QPDs, S_{\mathrm{full}} has exponentially many strata and consequently calculating the marginal distribution is infeasible. The counts vector \mathbf{M} introduced in the main text can be viewed as the permutation-invariant coarsening of S_{\mathrm{full}} that remains tractable (polynomially many strata for fixed width d ) and already guarantees never-worse performance relative to naïve sampling (under ideal proportional quotas). It can be understood as the finest possible (and consequently variance-minimal) of the class of statistics that are permutation-invariant. Further coarsenings of the counts-vector can further reduce preprocessing cost at the price of more configuration variance. A notable example is sign parity , as used in 11 and very recently in 42 . Partition each local index set into positive and negative coefficient labels, I_{i}^{+}:=\{\ell:\gamma_{i}(\ell)>0\},\quad I_{i}^{-}:=\{\ell:\gamma_{i}(\ell)<0\}, and define \mathbf{P}=(P_{+},P_{-}),\quad P_{\pm}:=\#\{i:\ell_{i}\in I_{i}^{\pm}\},\quad P_{+}+P_{-}=\nu. Equivalently, \mathbf{P} is obtained from \mathbf{M} by merging all labels with the same sign, so each \mathbf{P} -stratum is a union of \mathbf{M} -strata. Hence we have the refinement chain S_{\mathrm{full}}\;\succ\;\mathbf{M}\;\succ\;\mathbf{P}, and corresponding variance hierarchy (corresponding to successive applications of Theorem 1 ) \Var(\widehat{Y}_{K}^{\mathrm{prop}};S_{\mathrm{full}})\;\leq\;\Var(\widehat{Y}_{K}^{\mathrm{prop}};\mathbf{M})\;\leq\;\Var(\widehat{Y}_{K}^{\mathrm{prop}};\mathbf{P}). (46) The second inequality is tight when the additional multinomial detail in \mathbf{M} does not change stratum means beyond what is already captured by \mathbf{P} ; conversely, it can be strict when different primitive labels (even of the same sign) have systematically different effects. We also note that \mathbf{P} is a universally applicable statistic for all product-form QPDs, since it essentially just partitions based on the amount of ‘negativity’ in a given configuration. However, we choose to focus on the more costly counts-vector scheme since it is the more general construction. Cost–variance trade-off. The appeal of \mathbf{P} is that it has only \nu+1 values and admits a binomial-style DP with O(\nu^{2}) time and memory, independent of the original width d . A homogeneous version of sign-parity was used in Ref. 11 . In symmetric settings (e.g. homogeneous single-qubit depolarising PEC), sign parity can capture most of the explainable configuration variance while being far cheaper than the full counts vector. In less symmetric settings, \mathbf{M} typically yields stronger variance reduction at higher (but still polynomial-in- \nu for fixed d ) preprocessing cost. More generally, one can interpolate between \mathbf{M} and \mathbf{P} by merging subsets of primitive labels whose detailed counts have little impact on the conditional means \mu_{\mathbf{m}} , leading to various polynomial powers in \nu between \nu^{2} and the full width \nu^{d} . F.1 Counts-vector vs sign-parity stratification on a small PEC instance To illustrate this trade-off, we compare counts-vector stratification with sign-parity stratification on the small PEC instance from Appendix E : TFIM Trotter on n=3 qubits, L=1 step, open boundaries, and homogeneous single-qubit depolarising noise p=0.01 after each gate. The resulting PEC QPD has \nu=7 local factors and 4^{7}\approx 10^{4} circuit variants. For the full counts-vector statistic \mathbf{M} there are \#\{\mathbf{M}\}=\binom{\nu+4-1}{4-1}=120 strata, indexed by \mathbf{M}=(M_{I},M_{X},M_{Y},M_{Z}) with M_{I}+M_{X}+M_{Y}+M_{Z}=7 . For sign parity \mathbf{P}=(P_{+},P_{-}) there are only \#\{\mathbf{P}\}=\nu+1=8 strata. Because this instance is small, we compute exact design variances by enumerating all 4^{7} configurations (oracle model): \displaystyle\Var_{\text{naive}}(Y) \displaystyle\approx 2.099\times 10^{-2}, \displaystyle\Var_{\text{strat}}^{\text{(counts)}}(Y) \displaystyle\approx 8.246\times 10^{-3}, \displaystyle\Var_{\text{strat}}^{\text{(parity)}}(Y) \displaystyle\approx 8.404\times 10^{-3}. Both stratifications reduce configuration variance by \sim 2.5\times , and sign parity recovers more than 98\% of the variance reduction achieved by the full counts vector, while using only 8 strata instead of 120 . Fig. 10 shows empirical variance estimates converging to these exact baselines as K increases. This toy example demonstrates that, in specific settings, very coarse statistics can capture most of the explainable configuration variance at dramatically reduced preprocessing cost. Importantly, the results still verify the hierarchy in ( 46 ). We emphasise that we expect the gap between \mathbf{M} and \mathbf{P} to widen in circumstances where the class of negative events is large and when individual primitives within it have drastically different effects. We leave investigating when exactly a coarser vs. finer statistic is optimal (which depends strongly on available resources and problem structure) for future work. Figure 10: Design-variance convergence for a small PEC instance in the oracle model, comparing naïve sampling (blue) with counts-vector stratification (red) and sign-parity stratification (green). The horizontal dashed lines show the exact design variances obtained by enumerating all 4^{7} PEC configurations: \Var_{\text{naive}}(Y)\approx 0.02099 , \Var_{\text{strat}}^{\text{(counts)}}(Y)\approx 0.00825 , and \Var_{\text{strat}}^{\text{(parity)}}(Y)\approx 0.00840 (both under proportional allocation). Solid curves show empirical variance estimates as a function of the number of sampled configurations K , with shaded bands indicating 95\% bootstrap confidence intervals ( M=1024 resamples). Both stratified schemes converge quickly to their baselines and achieve a \sim 2.5\times reduction relative to naïve sampling, while the coarse sign-parity statistic recovers more than 98\% of the variance reduction of the full counts-vector statistic using only 8 strata instead of 120 . Appendix G Sufficiency, explained variance, and symmetry This appendix collects a few formal consequences of the variance-accounting viewpoint used in Section II and motivates when a stratification statistic S should be expected to help. G.1 Explained-variance identity Let Y denote the single-configuration scalar random variable used in Monte Carlo estimation (including QPD reweighting and, in the shot model, Born noise and any R -fold averaging), and let S=S(\underline{\ell}) be any finite-valued stratification statistic with strata \mathcal{S} . Write w_{s}=\Pr(S=s) , \mu_{s}=\mathbb{E}[Y\mid S=s] , and \sigma_{s}^{2}=\Var(Y\mid S=s) . Proposition 4 (Explained-variance interpretation) . For any statistic S , \Var(Y)=\mathbb{E}[\Var(Y\mid S)]+\Var(\mathbb{E}[Y\mid S]). Under ideal proportional allocation K_{s}=Kw_{s} , \Var(\widehat{\mu}_{\mathrm{prop}})=\frac{1}{K}\sum_{s}w_{s}\sigma_{s}^{2},\quad\Var(\widehat{\mu}_{\mathrm{naive}})=\frac{1}{K}\Var(Y), so the design-level variance reduction is \Var(Y^{\mathrm{naive}})-\Var(Y^{\mathrm{prop}})=\Var(\mathbb{E}[Y\mid S]). Defining R^{2}_{\mathrm{eff}}(S):=\frac{\Var(\mathbb{E}[Y\mid S])}{\Var(Y)}, the ideal variance ratio is \rho(S)=1-R^{2}_{\mathrm{eff}}(S) (as stated in the main text). Thus S is effective precisely when it explains a large fraction of the single-configuration variability in Y . G.2 Oracle specialisation and configuration-budget savings In the oracle model, the per-configuration scalar is deterministic given \underline{\ell} : Y=\mu_{\underline{\ell}}:=\mathbb{E}[Y\mid\underline{\ell}]. Then \Var(Y) is purely configuration-to-configuration mean variation, and R^{2}_{\mathrm{eff}}(S) reduces to the usual explained fraction R^{2}(S) of \mu_{\underline{\ell}} by conditioning on S . In particular, \rho^{\mathrm{oracle}}(S)=1-R^{2}(S). (47) Moreover, because \Var(\widehat{\mu})=\Var(Y)/K in both designs, matching a fixed target variance implies \frac{\Var(Y^{\mathrm{prop}})}{K_{\mathrm{prop}}}=\frac{\Var(Y^{\mathrm{naive}})}{K_{\mathrm{naive}}}\Longrightarrow K_{\mathrm{prop}}=\rho^{\mathrm{oracle}}(S)\,K_{\mathrm{naive}}, so in the oracle setting the configuration-budget savings fraction is exactly 1-\rho^{\mathrm{oracle}}(S)=R^{2}(S) . Outside the oracle model, shot noise increases \Var(Y) without increasing \Var(\mathbb{E}[Y\mid S]) , so R^{2}_{\mathrm{eff}}(S)\leq R^{2}(S) and the attainable savings are reduced accordingly. G.3 Counts vectors, permutation symmetry, and symmetry breaking The counts-vector statistic \mathbf{M}=S_{\mathrm{count}}(\underline{\ell}) forgets gate ordering and records only the multiplicities of local primitive indices. If the oracle means \mu_{\underline{\ell}} are invariant under a permutation group \mathbb{G} of gate positions that preserves \mathbf{M} , then \mu_{\underline{\ell}} is constant on each counts-vector stratum and \Var(\mu_{\underline{\ell}}\mid\mathbf{M})=0 . In this mean-sufficient limit, R^{2}(\mathbf{M})=1 and \rho^{\mathrm{oracle}}(\mathbf{M})=0 , i.e. counts-vector stratification removes all configuration-to-configuration mean variation and only measurement noise remains. In realistic circuits this symmetry is only approximate (e.g. due to non-commutation across layers in \nu ), so \Var(\mu_{\underline{\ell}}\mid\mathbf{M})>0 and R^{2}(\mathbf{M})<1 . Consequently \rho^{\mathrm{oracle}}(\mathbf{M})>0 , and growth of \rho^{\mathrm{oracle}} with circuit depth can be read as a symmetry-breaking effect: the counts vector explains a smaller fraction of mean variation as depth increases. Appendix H Cost models, pilot schemes, and adaptive allocation The main text compares configuration-sampling designs at a fixed measurement model, i.e. at a fixed number of Born-rule repetitions R per configuration. In that setting, the relevant single-sample object is the per-configuration average Y^{(R)} , and the estimator satisfies \Var(\widehat{Y}_{K,R})=\frac{1}{K}\Var\!\bigl(Y^{(R)}\bigr). Consequently, variance ratios between sampling designs translate directly into constant-factor reductions in the number of configurations K required to achieve a target precision. In hardware experiments, budgets are typically expressed in terms of total cost (e.g. wall-clock time), which couples configuration count K and shot count R and motivates joint budgeting and pilot-based variance estimation. A detailed treatment of such hardware-relevant cost models and optimal budgeting between K and R under a joint circuit- and shot-level variance decomposition is given in Ref. 1 . Here we only record the basic link between our variance ratios and cost models, and then discuss adaptive (pilot/Neyman-type) allocation across strata. H.1 Connection to cost models via the variance decomposition For any fixed configuration-sampling design (naïve or stratified), the law of total variance gives \Var\!\bigl(Y^{(R)}\bigr)=\frac{1}{R}\,\mathbb{E}_{\underline{\ell}}\!\left[\Var(\tilde{Y}\mid\underline{\ell})\right]+\Var_{\underline{\ell}}\!\left(\mu_{\underline{\ell}}\right), (48) where \tilde{Y} denotes a single reweighted shot and Y^{(R)} is the average of R i.i.d. shots at fixed \underline{\ell} , with \mu_{\underline{\ell}}:=\mathbb{E}[\tilde{Y}\mid\underline{\ell}] . The first term is Born-rule noise and scales as 1/R ; the second term is configuration variance and is independent of R . Stratification modifies ( 48 ) only through the configuration-variance term. In the ideal proportional model, replacing naïve configuration sampling by stratified sampling reduces the configuration variance by a constant factor \rho\leq 1 , and therefore reduces \Var(\widehat{Y}_{K,R}) by the same constant factor at fixed (K,R) . Under any hardware cost model that constrains (K,R) (or allows nonuniform R_{k} ), this improvement can be interpreted as a constant-factor reduction in the cost required to reach a fixed target precision, once the remaining budgeting problem is solved. Related analysis of such joint budgeting appears with more hardware error-mitigation focus in 1 . H.2 Pilot and Neyman allocation across strata For a fixed stratification statistic S and fixed repetitions R_{k}\equiv R , classical sampling theory shows that the variance-minimising allocation across strata is the Neyman rule K_{s}^{\star}=K\,\frac{w_{s}\,\sigma_{s}}{\sum_{t}w_{t}\,\sigma_{t}},\qquad\sigma_{s}^{2}:=\Var\!\bigl(Y^{(R)}\mid S=s\bigr), which yields \Var(\widehat{Y}_{K,R}^{\min})=\frac{1}{K}\Bigl(\sum_{s}w_{s}\sigma_{s}\Bigr)^{2}\leq\frac{1}{K}\sum_{s}w_{s}\sigma_{s}^{2}=\Var(\widehat{Y}_{K,R}^{\mathrm{prop}}) by Cauchy–Schwarz. We focus on proportional allocation because it depends only on stratum masses w_{s} , which are available exactly from the DP, whereas Neyman allocation requires (possibly approximate) within-stratum variance information \sigma_{s} . A standard approximation is a two-stage pilot scheme: expend a small fraction of the budget to obtain rough within-stratum variance estimates \widehat{\sigma}_{s}^{2} , then allocate the remaining configurations according to K_{s}\propto w_{s}\widehat{\sigma}_{s} . Pilot data can be included in the final estimator, so no samples are discarded; the trade-off is that allocation decisions are made using noisy variance estimates. Such pilot-based budgeting is also natural in hardware pipelines, since one typically needs variance estimation even for the naïve protocol (see, e.g., Algorithm 2 in Appendix B of 1 ). In the stratified setting, the additional granularity is that one estimates \sigma_{s}^{2} per stratum rather than a single global variance. We leave a detailed empirical study of pilot/Neyman schemes for QPD stratification to future work. Appendix I General channel randomisation viewpoint The main text develops all variance statements in the concrete setting of product-form QPDs, where circuit variants are labelled by multi-indices \underline{\ell} and the configuration law p(\underline{\ell}) factorises over gates. This QPD problem structure is convenient a operational point of view since it admits an efficient DP and sampling procedure, but the mathematics translate readily into more general settings. In this appendix we briefly record how the same variance-accounting and stratification ideas extend to arbitrary classical randomisation over quantum channels. I.1 From QPD indices to arbitrary channel ensembles Let \rho_{0} be a fixed input state, \{M_{x}\} a fixed POVM, and O=\sum_{x}O_{x}M_{x} a fixed observable, as in the main text. Consider now an arbitrary ensemble of CPTP maps \Lambda\in\{\lambda\},\quad\Pr(\Lambda=\lambda)=p(\lambda), which we interpret as the “configuration” random variable. For each realisation \Lambda=\lambda , the hybrid protocol: • applies \lambda to \rho_{0} , • measures with \{M_{x}\} , obtaining X\sim p(x\mid\lambda) , • maps X to a scalar Z=O(X) , • and optionally rescales by a weight w(\lambda) to produce Y=w(\lambda)\,Z . In Sec. II , we assumed that p(\lambda) and w(\lambda) were chosen so that Y is unbiased for some target expectation (typically the ideal expectation under a reference channel), but this assumption can be easily dropped to allow for bias or even more general problem settings entirely. All of the variance formulas used in the main text follow directly by applying the law of total variance to this joint law p(y,\lambda)=p(y\mid\lambda)p(\lambda) : • the decomposition into a Born-rule term and a classical channel term; • the shot-accounting formula for \Var(\widehat{Y}_{K,R}) in terms of K configuration draws and R repetitions per configuration (analogue of Eq. ( 7 )); • the stratified-variance formula with statistic S=C(\Lambda) and the hierarchy \Var(\widehat{Y}_{K}^{\min})\;\leq\;\Var(\widehat{Y}_{K}^{\mathrm{prop}})\;\leq\;\Var(\widehat{Y}_{K}^{\mathrm{naive}}) for Neyman, proportional, and naïve allocation (Sec. II.4 ). No step in those derivations uses product structure or QPD-specific properties; only the existence of a discrete channel ensemble and an unbiased scalar estimator is required. The caveat is that to make this variance framework operational in the general setting is non-trivial in general. In QPD language, the random variable \Lambda is simply relabelled as the multi-index \underline{\ell} , the ensemble p(\lambda) becomes the QPD-induced ensemble p(\underline{\ell}) , and the weight w(\lambda) takes the familiar form \|g\|_{1}\,\mathrm{sign}(g(\underline{\ell})) . The QPD setting is therefore a special case of a more general “channel randomisation” picture. I.2 Stratification beyond product-form ensembles From this viewpoint, a stratification statistic is just a measurable map S=C(\Lambda), which partitions the channel ensemble p(\lambda) into strata labelled by s\in\mathcal{S} , with marginal probability w_{s}=\Pr(S=s) and conditional law p(\lambda\mid S=s) . Given any such statistic, and a way to: 1. evaluate or approximate w_{s} , and 2. sample \lambda conditionally on S=s (possibly from an approximate distribution) one can implement proportional (or perhaps pilot-based Neyman) stratified sampling exactly as in Sec. II . The variance guarantees are identical: at fixed measurement model and fixed number of configuration draws K , stratified sampling never increases variance compared to naïve sampling, and strictly reduces it whenever the stratum means differ. The special role of product-form QPDs in the main text is therefore algorithmic . For general channel ensembles there is no reason to expect the stratum masses w_{s} or the conditional laws p(\lambda\mid S=s) to admit efficient exact computation. In generic cases one would need to rely on approximate methods (e.g. importance sampling, MCMC over configurations, or heuristic groupings of channels) to implement stratification. In product-form QPDs, by contrast: • the ensemble is indexed explicitly by multi-indices \underline{\ell} ; • the product-distribution p(\underline{\ell}) factorises over gates; • permutation-invariant statistics such as the counts vector \mathbf{M} and sign parity \mathbf{P} are natural and easy to define; and • for these statistics the Poisson–multinomial structure yields an exact dynamic programme which computes both w_{s} and conditional samplers in time polynomial in the circuit depth \nu (for fixed local width d ). This is what makes counts-vector (and related permutation-invariant) stratification practically attractive in the QPD setting. Additionally, since QPDs experience an exponential variance blow-up with the circuit-depth, variance optimisation is a highly relevant goal in practice. In other randomisation settings variance reduction may not be so important. I.3 Other randomisation schemes Many hybrid protocols outside the QPD family fit into this general channel-randomisation template: randomised compiling, Pauli or Clifford twirling, randomised product formulae/time evolution, classical shadows and related measurement schemes, and stochastic-phase estimation, among others. In all these cases, one can in principle: • identify the induced channel ensemble p(\lambda) over compiled circuits, time steps, or measurement settings; • choose statistics S(\Lambda) that capture relevant structure (e.g. numbers of non-identity twirling gates, light-cone properties, coarse features of the random unitary); and • apply the same stratification logic and variance decompositions as in the QPD case. Working out efficient stratification schemes for these more general settings requires problem-specific analysis, since the clean product structure and Poisson–multinomial DP may no longer be available in general (or may be intractable). Nevertheless, the conceptual message is simple: the “extra” configurational variance induced by any channel-randomisation scheme can, in principle, be partially removed by stratified sampling over channels. Variance reduction techniques have been investigated previously outside the QPD setting in e.g. for randomised time evolution 29 . Product-form QPDs provide a particularly transparent testbed where this idea can be made both rigorous and algorithmically explicit. It will be an interesting line of research to investigate how the ideas presented here can generalise. Appendix J PAI and PEC constructions used in the TFIM benchmark This appendix records the two product-form QPD instances used in the TFIM Trotter experiments of Section III : probabilistic angle interpolation (PAI) and probabilistic error cancellation (PEC). Both fit the local-QPD framework of Section II : each protocol specifies (i) a local index set I_{i} , (ii) implementable CPTP primitives \mathcal{C}_{i}(\ell_{i}) , and (iii) real coefficients \gamma_{i}(\ell_{i}) , inducing a product-form circuit-level ensemble over configuration strings \underline{\ell} . In both cases we stratify by the counts vector S(\underline{\ell})\equiv\mathbf{M}(\underline{\ell}) , with stratum weights and conditional sampling implemented via the DP of Appendix D and residual-aware allocation via Appendix C . J.1 Probabilistic angle interpolation (PAI) PAI 31 implements a target single-qubit rotation in expectation on hardware that supports only a discrete set of rotation angles. Each ideal rotation is expressed as a signed combination of three implementable rotations about the same axis; sampling from this local QPD yields an unbiased estimator whose local variance inflation is controlled by the corresponding local 1-norm. Single-gate PAI decomposition. Fix a Pauli (or SWAP-type) rotation generated by a Hermitian involution G , R_{G}(\theta):=e^{-i\theta G/2},\quad G^{\dagger}=G,\quad G^{2}=\mathbb{I}, and write the associated channel as \mathcal{R}_{G}(\theta)(\rho):=R_{G}(\theta)\rho R_{G}(\theta)^{\dagger} . Assume the hardware supports a discrete grid of angles \Theta_{k}:=k\Delta with step \Delta=\frac{2\pi}{2^{B_{\mathrm{PAI}}}}, where B_{\mathrm{PAI}} is the angular precision (in bits). For a target angle \theta , choose k such that \theta=\Theta_{k}+\vartheta,\quad 0\leq\vartheta<\Delta, and define three implementable primitives \mathcal{C}_{1}:=\mathcal{R}_{G}(\Theta_{k}),\quad\mathcal{C}_{2}:=\mathcal{R}_{G}(\Theta_{k+1}),\quad\mathcal{C}_{3}:=\mathcal{R}_{G}(\Theta_{k}+\pi). PAI provides coefficients \gamma_{\ell}(\vartheta)\in\mathbb{R} such that the target channel admits the exact local QPD \mathcal{R}_{G}(\Theta_{k}+\vartheta)=\gamma_{1}(\vartheta)\,\mathcal{C}_{1}+\gamma_{2}(\vartheta)\,\mathcal{C}_{2}+\gamma_{3}(\vartheta)\,\mathcal{C}_{3}. (49) Define the local 1-norm and categorical sampling distribution \|\bm{\gamma}(\vartheta)\|_{1}:=\sum_{\ell=1}^{3}|\gamma_{\ell}(\vartheta)|,\quad p(\ell\mid\vartheta):=\frac{|\gamma_{\ell}(\vartheta)|}{\|\bm{\gamma}(\vartheta)\|_{1}}. Sampling follows the standard QPD rule: draw \ell\sim p(\cdot\mid\vartheta) , implement \mathcal{C}_{\ell} , and rescale the measured observable outcome by \|\bm{\gamma}(\vartheta)\|_{1}\,\mathrm{sign}(\gamma_{\ell}(\vartheta)) . This yields an unbiased single-gate estimator for the ideal rotation channel, with variance inflation controlled by \|\bm{\gamma}(\vartheta)\|_{1}^{2} . Closed-form expressions for \gamma(\vartheta) are given in Ref. 31 . Mapping to the product-form QPD notation. Consider a circuit with \nu parametrised rotations, where gate i has generator G_{i} and target angle \theta_{i} . For each i , choose the nearest notch \Theta_{k_{i}} and write \theta_{i}=\Theta_{k_{i}}+\vartheta_{i} with \vartheta_{i}\in[0,\Delta) . The local PAI decomposition has uniform width d=3 and matches Section II by taking: • index set I_{i}=\{1,2,3\} ; • implementable channels \mathcal{C}_{i}(1)=\mathcal{R}_{G_{i}}(\Theta_{k_{i}}) , \mathcal{C}_{i}(2)=\mathcal{R}_{G_{i}}(\Theta_{k_{i}+1}) , \mathcal{C}_{i}(3)=\mathcal{R}_{G_{i}}(\Theta_{k_{i}}+\pi) ; • coefficients \gamma_{i}(\ell):=\gamma_{\ell}(\vartheta_{i}) . The resulting circuit-level QPD has the standard product form \mathcal{U}_{\mathrm{circ}}=\sum_{\underline{\ell}\in\{1,2,3\}^{\nu}}g(\underline{\ell})\,\mathcal{U}(\underline{\ell}),\;g(\underline{\ell})=\prod_{i=1}^{\nu}\gamma_{i}(\ell_{i}),\;\|g\|_{1}=\prod_{i=1}^{\nu}\|\bm{\gamma}_{i}\|_{1}, with configuration distribution p(\underline{\ell})=|g(\underline{\ell})|/\|g\|_{1} . Counts-vector stratification for PAI. A PAI configuration is the index string \underline{\ell}\in\{1,2,3\}^{\nu} specifying whether each rotation uses the lower notch ( \ell=1 ), upper notch ( \ell=2 ), or antipodal rotation ( \ell=3 ). The induced counts vector \mathbf{M}=(M_{1},M_{2},M_{3}),\quad M_{\ell}:=\#\{i:\ell_{i}=\ell\}, with M_{1}+M_{2}+M_{3}=\nu forgets gate positions and records only primitive multiplicities. We stratify with S(\underline{\ell})\equiv\mathbf{M} . The DP in Appendix D computes w_{\mathbf{m}}=\Pr(\mathbf{M}=\mathbf{m}) for the generally inhomogeneous product distribution induced by \{p_{i}(\cdot)\} , and provides an exact sampler for \underline{\ell}\mid\mathbf{M}=\mathbf{m} . Integer proportional allocations and exact unbiasedness at finite K use the residual-aware procedure of Appendix C . J.2 Probabilistic error cancellation (PEC) This subsection specifies the PEC model used in Section III : a gate-independent single-qubit depolarising noise model, the inverse-channel QPD, and the induced product-form configuration ensemble. Gate-independent depolarising noise. We assume a single-qubit depolarising channel of strength p applied after each logical unitary acting on that qubit: \mathcal{D}_{p}(\rho):=(1-p)\rho+\frac{p}{3}\bigl(X\rho X+Y\rho Y+Z\rho Z\bigr). (50) In the Pauli-transfer representation, \mathcal{D}_{p} fixes I and contracts the Bloch components by \lambda_{p}=1-\tfrac{4p}{3} . Given an ideal gate channel \mathcal{U}^{(i)} acting on one or two qubits, the corresponding hardware-realised noisy gate is \widetilde{\mathcal{U}}^{(i)}:=\mathcal{N}^{(i)}\circ\mathcal{U}^{(i)}, where \mathcal{N}^{(i)} is the tensor product of \mathcal{D}_{p} on the qubits in the support of \mathcal{U}^{(i)} (i.e. \mathcal{N}^{(i)}=\mathcal{D}_{p} for single-qubit gates and \mathcal{N}^{(i)}=\mathcal{D}_{p}\otimes\mathcal{D}_{p} for two-qubit gates). Inverse-channel QPD for depolarising noise. PEC inserts an inverse noise map so that, as linear superoperators, \mathcal{D}_{p}^{-1}\circ\mathcal{D}_{p} equals the identity. Since \mathcal{D}_{p} is diagonal in the Pauli-transfer representation, the inverse linear map satisfies I\mapsto I and P\mapsto\lambda_{p}^{-1}P for P\in\{X,Y,Z\} . While \mathcal{D}_{p}^{-1} is not CPTP for p>0 , it admits a 4-term QPD over Pauli conjugation channels \mathcal{P}_{P}(\rho):=P\rho P , namely \mathcal{D}_{p}^{-1}=\sum_{P\in\{I,X,Y,Z\}}\gamma(P)\,\mathcal{P}_{P}, (51) with coefficients \gamma(I)=\frac{\lambda_{p}+3}{4\lambda_{p}},\quad\gamma(X)=\gamma(Y)=\gamma(Z)=\frac{\lambda_{p}-1}{4\lambda_{p}}. We define the local 1-norm and sampling probabilities \|\bm{\gamma}\|_{1}:=\sum_{P}|\gamma(P)|,\quad p(P):=\frac{|\gamma(P)|}{\|\bm{\gamma}\|_{1}}, and signed CPTP primitives \mathcal{C}(P):=\mathrm{sign}(\gamma(P))\,\mathcal{P}_{P} , so that ( 51 ) matches the standard local-QPD form ( 1 ) with uniform width d=4 . For a two-qubit gate with independent depolarising noise on each leg, we take the tensor-product inverse \mathcal{D}_{p}^{-1}\otimes\mathcal{D}_{p}^{-1} , i.e. each noisy leg contributes one independent 4-term single-qubit QPD over \{I,X,Y,Z\} . Circuit-level product QPD for PEC. Let \nu denote the total number of single-qubit noise locations (“noisy legs”) after expanding each two-qubit gate into two independent legs. At each location i\in[\nu] we have the same local QPD \mathcal{N}^{(i)}{}^{-1}=\sum_{\ell_{i}\in\{I,X,Y,Z\}}\gamma(\ell_{i})\,\mathcal{C}(\ell_{i}), acting on the corresponding qubit. Expanding the product over \nu locations yields the product-form circuit-level QPD \mathcal{U}_{\mathrm{circ}}=\sum_{\underline{\ell}\in\{I,X,Y,Z\}^{\nu}}g(\underline{\ell})\,\mathcal{U}(\underline{\ell}),\quad g(\underline{\ell})=\prod_{i=1}^{\nu}\gamma(\ell_{i}), where \underline{\ell}=(\ell_{1},\dots,\ell_{\nu}) records which Pauli conjugations are applied by the inverse-noise gadgets and \mathcal{U}(\underline{\ell}) is the resulting “dressed” circuit. Counts-vector stratification for PEC. Under the induced product sampling distribution p(\underline{\ell})\propto|g(\underline{\ell})| , a configuration is a Pauli label string \underline{\ell}\in\{I,X,Y,Z\}^{\nu} . The associated counts vector \mathbf{M}=(M_{I},M_{X},M_{Y},M_{Z}),\quad\sum_{P\in\{I,X,Y,Z\}}M_{P}=\nu, records how often each Pauli channel is selected across noisy legs, independent of position. We stratify with S(\underline{\ell})\equiv\mathbf{M} . Relative to naïve PEC sampling, the only operational change is how \underline{\ell} is chosen: we allocate a deterministic number of draws to each \mathbf{m} (via the residual-aware integer proportional allocation of Appendix C ), and then sample \underline{\ell} conditionally within each stratum using Appendix D . All subsequent steps (running the dressed circuit and reweighting outcomes by the standard PEC weight w(\underline{\ell})=\|g\|_{1}\,\mathrm{sign}(g(\underline{\ell})) ) are unchanged.