Approximate Sampling for Randomization Tests: A Total-Variation Certification Framework

Abstract Covariate-constrained cluster randomization draws a treatment assignment from a constrained set of balanced allocations, and randomization-based inference relies on that set's distribution. We study what happens when an approximate sampler replaces the exact target. On one fixed, reproducible benchmark built from the 16-county Dickinson cluster-randomization example, we define an exact accepted set of 1,287 of 12,870 balanced allocations, obtained by exact rational scoring with a canonical index tie-break. We certify sampler outputs by total variation (TV) distance to this target, using full-statevector probabilities where available. On the anchor, ideal statevector results show that a fixed-step amplification control retains raw leakage of 0.00144, while two fixed-depth QAOA headline runs remain far from the target (raw TV 0.833 and 0.948). On four small synthetic instances, the energy-selected XY-QAOA outputs also remain far from the target (raw TV 0.59 to 0.72). The penalty control places 51% of its raw mass on wrong-weight strings. Its randomization-test p-value is undefined without an extension rule; we report an envelope from two fully defined extensions. For any fixed outcome realization and fully defined randomization-test event, the difference between the p-value under a sampler and under the exact target is bounded by TV. In a simulation anchored on the observed covariates with simulated outcomes, the exact reference holds sharp-null rejection near 5%, a biased classical control inflates type-I error, and the two statistics respond differently to the same distortion. The study demonstrates a certification workflow and its inferential consequences on one empirical-anchor benchmark, with a synthetic extension that is pre-specified, hash-recorded, and frozen before the relevant execution; it was not externally preregistered. Primary inference in the extension is limited to equal-size Gaussian outcomes; binary, heterogeneous, and unequal-size analyses are sensitivity-only. The study does not establish quantum advantage, hardware performance, noise robustness, or clinical benefit.