📊 statistics

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

This paper introduces a total-variation certification framework to evaluate approximate samplers for covariate-constrained cluster randomization, demonstrating on a fixed benchmark and synthetic extensions that current quantum and classical approximations often deviate significantly from exact targets, thereby inflating type-I error rates and altering p-values in randomization tests.

Original authors: Mohamed Faisal Sindhi, Hammaz Buksh

Published 2026-10-13

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Mohamed Faisal Sindhi, Hammaz Buksh

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of researchers trying to decide which of two new medical treatments works better. To be fair, they cannot simply pick the patients who look healthiest for the new drug; they must assign patients to groups by chance, a process called randomization. However, when the groups are small, like a handful of clinics or counties, pure chance can sometimes accidentally create an unfair imbalance. One group might end up with mostly older patients while the other has mostly younger ones, skewing the results. To fix this, scientists often restrict their randomization to a specific list of assignments that are perfectly balanced, ensuring that every group has a fair mix of characteristics before the experiment even begins. The entire scientific conclusion relies on the fact that the assignment was drawn uniformly from this specific, balanced list.

The question at the heart of this new research is what happens when a computer tries to pick from that list but doesn't do it perfectly. In recent years, scientists have been exploring whether quantum computers, which operate on different physical principles than standard machines, can help generate these random assignments faster. But if a quantum computer, or any approximate method, picks an assignment that isn't truly random according to the strict rules of the balanced list, does the final medical conclusion become wrong? This study, conducted by researchers at the University of South Florida, sets out to measure exactly how much error is introduced when the random selection process is only an approximation, and to see if we can certify that the error is small enough to ignore.

The researchers built a rigorous test using a real-world example involving sixteen counties in Colorado that were part of a past study. They first created a master list of every single possible way to split these sixteen counties into two equal groups of eight that met the strict balance requirements. There were 12,870 such valid ways. From this massive list, they selected the top 1,287 that were the most perfectly balanced, creating a "gold standard" target. The goal was to see how well different computer methods could mimic the act of picking one of these 1,287 perfect assignments at random. They tested several approaches, including a standard classical computer method that simply shuffled through the list, and three different methods designed to run on a quantum computer.

The results were a mix of success and clear failure, offering a stark reality check for the field. One quantum method, which used a technique called amplitude amplification, performed exceptionally well. It produced a distribution of choices that was almost indistinguishable from the perfect gold standard, with a tiny error rate of just 0.00144. This was good enough to be considered a certified success. However, two other quantum approaches, which used a popular algorithm known as QAOA, failed to meet the mark. One of these methods produced results that were wildly off-target, with an error rate of 0.833, meaning it was picking the wrong assignments most of the time. The other was even worse, with an error rate of 0.948. In fact, this second method was so flawed that it frequently produced assignments that didn't even have the correct number of counties in each group, rendering the results unusable for a fair test.

The study went further to see how these errors actually affected the final scientific conclusion. The researchers simulated thousands of medical trials using the data from the counties, running the analysis with the perfect gold standard and then again with the flawed quantum methods. They found that the errors in the random selection did not always lead to the same kind of mistake. Sometimes, a flawed method made the test too strict, missing real effects that were actually there. Other times, it made the test too loose, suggesting a treatment worked when it didn't. Crucially, the size of the error in the random selection did not perfectly predict the size of the error in the final conclusion. A method that was "far" from perfect in its random selection did not always produce a "far" wrong answer in the final test, and vice versa. This means that simply knowing a computer is "close enough" to the perfect random list is not enough; scientists must also check how that specific imperfection changes the specific test they are running.

Perhaps most importantly, the researchers demonstrated a way to certify these results before they are used. They established a framework where a computer program can be checked against the gold standard using a specific mathematical distance measure. If the distance is small enough, the program is certified as safe to use. If the distance is too large, the program is flagged as unsafe. In their tests, the successful quantum method passed this certification, while the two failing methods were correctly identified as too far from the target to be trusted. The study also highlighted that for the failing methods, the error was so severe that the final statistical answer was technically undefined without making extra assumptions, which the researchers then bounded to show the worst-case scenario.

This work does not claim that quantum computers have solved the problem of randomization or that they are ready to replace classical computers in clinical trials. In fact, the results suggest that current quantum approaches are often too noisy and imprecise for this specific task without significant improvement. The researchers explicitly state that they did not find a quantum advantage, nor did they prove that these methods work on real, noisy hardware in a way that beats classical computers. Instead, they provided a clear, certified workflow for checking if a randomization method is good enough. They showed that while some quantum-inspired methods can work, others fail spectacularly, and that the only way to know for sure is to measure the distance between the computer's output and the perfect target. The study serves as a necessary quality control check, proving that in the high-stakes world of medical research, the way you pick your groups matters just as much as the groups themselves.

Technical Summary: Approximate Sampling for Randomization Tests

Problem Statement
Cluster randomized trials often restrict randomization to a set of balanced allocations to ensure covariate balance, particularly when the number of clusters is small. Inference in these designs relies on the randomization distribution defined by this constrained set. As approximate sampling methods (including quantum algorithms like QAOA) are proposed to generate these allocations, a critical gap exists: these methods do not inherently guarantee that their output distribution matches the exact target distribution (the uniform distribution over the accepted set). If an approximate sampler replaces the exact target, the randomization distribution changes, potentially invalidating the inferential guarantees (e.g., Type-I error control) of the randomization test. This paper investigates the inferential consequences of replacing the exact target with an approximate sampler's distribution.

Methodology
The study employs a rigorous certification framework anchored on a specific empirical benchmark and extended by synthetic instances.

Exact Target Definition:
- Benchmark: Based on the 16-county Dickinson cluster-randomization example.
- Constraint: Allocations must satisfy an $\ell_2$ covariate balance score threshold (top 10% of 12,870 possible 8-vs-8 allocations).
- Precision: The target set ( $A$ ) contains exactly 1,287 allocations. The target distribution $P^\star$ is uniform on $A$ .
- Arithmetic: Scores are computed using exact rational arithmetic to resolve ties deterministically via a canonical index (lexicographic order), avoiding floating-point ambiguities.
Certification Framework:
- Metric: Samplers are assessed using Total Variation (TV) distance to $P^\star$ .
- Thresholds: Pre-specified thresholds define "close" ( $\tau_{close} = 0.02$ ) and "far" ( $\tau_{far} = 0.10$ ).
- Representation: TV is calculated on a 1,288-bin space (1,287 accepted allocations + 1 bin for all rejected/wrong-weight strings).
- Statistical Bounds: For sampled distributions, confidence intervals are derived using distribution-free method-of-types inequalities. For ideal quantum simulations, full-statevector probabilities provide exact TV values.
Sampler Constructions:
- Classical Controls: Direct uniform sampling (exact), rejection sampling, a swap-chain Markov chain (evaluated at specific steps), and a biased steepest-descent control.
- Quantum Arms (Ideal Statevector):
  - Amplitude Amplification (Phase 5): A Grover-style construction with a fixed phase oracle for the accepted set.
  - XY-QAOA (Phase 6): Hamming-weight-preserving mixer with a balance-score phase separator.
  - Penalty-QAOA (Phase 6): Uses $RX$ mixers and a quadratic penalty cost to enforce balance and weight constraints.
Inference Simulation:
- Setup: Outcomes are simulated under a cluster-level Gaussian model with pre-specified covariates and intra-cluster correlation.
- Statistics: Two test statistics are used: unadjusted difference in means ( $T_1$ ) and OLS coefficient adjusted for covariates ( $T_2$ ).
- Protocol: The observed allocation is drawn from the exact target $P^\star$ to isolate the error introduced by the reference distribution. P-values are computed using both the exact target and the approximate sampler's distribution.

Key Contributions

Certification Workflow: The paper defines a workflow to certify approximate samplers by measuring their TV distance to an exact, rational-arithmetic target. It distinguishes between "raw" distributions (the actual sampler output) and "conditional" distributions (post-selected on valid allocations), arguing that raw certification is necessary for validity.
Theoretical Bound: It applies the standard inequality $|Q(E) - P(E)| \leq TV(Q, P)$ to show that for any fixed outcome and fully defined test event, the difference in p-values between a sampler and the exact target is bounded by their TV distance.
Empirical Benchmarking: The study provides a fixed, reproducible benchmark (Dickinson 16-county) with hash-recorded protocols to evaluate specific sampler implementations.
Inferential Consequences: It demonstrates that while TV bounds the worst-case error, the realized error for specific statistics varies significantly. A "far" TV does not necessarily imply large error for every statistic, and different statistics respond differently to the same distributional distortion.

Results

Amplitude Amplification: The Phase 5 control achieved a raw TV of 0.00144, certified as "close." Its downstream Type-I error rates were nearly identical to the exact target (e.g., 5.12% vs. 5.20% for $T_1$ ).
QAOA Performance:
- XY-QAOA: The headline run had a raw TV of 0.833 ("far"). It produced a highly conservative Type-I error (0.18% for $T_1$ ) and a 37.12% disagreement rate with the exact target's decision.
- Penalty-QAOA: The headline run had a raw TV of 0.948 ("far"). Crucially, 51% of its mass was on "wrong-weight" strings (allocations not having 8 treated/8 control). Consequently, the randomization p-value was undefined without an extension rule. The study reported an envelope of bounds, showing potential Type-I error rates ranging from 0% to 9.16% depending on the extension rule.
Classical Controls:
- The swap-chain required 170 steps to reach a TV < 0.01. At step 10 (TV $\approx$ 0.73), it showed significant disagreement with the target.
- The biased descent control (TV $\approx$ 0.96) inflated Type-I error to 16.68% for $T_1$ .
Synthetic Extension: Across four synthetic instances, the XY-QAOA arm consistently remained "far" from the target (raw TV 0.59–0.72), confirming the workflow's consistency across different problem sizes and covariate strengths.

Significance and Claims

The paper explicitly states what it does and does not claim:

What it establishes: A certification workflow for approximate sampling in randomization tests and the quantitative impact of distributional distortion on specific inferential outcomes. It proves that a "close" certificate bounds the worst-case p-value error, while a "far" certificate indicates the sampler is invalid for exact inference without further correction.
What it does NOT claim:
- Quantum Advantage: The study does not demonstrate quantum speedup, hardware performance, or scalability. The quantum results are ideal statevector simulations, and the Grover construction is a correctness control, not a scalable resource estimate.
- General QAOA Performance: The results describe specific runs of bounded local search optimizers; they do not generalize to all QAOA configurations or optimizers.
- Clinical Benefit: No clinical outcomes were analyzed; all outcomes were simulated.
- Noise Robustness: The study does not evaluate noise robustness on actual hardware (though an exploratory hardware run is mentioned in an appendix, it is not part of the certification study).

The authors conclude that before an approximate sampler replaces an exact target, three questions must be answered: the exact TV distance, the handling of invalid outputs (e.g., wrong-weight strings), and the specific test statistics used, as the worst-case bound does not predict the error magnitude for a specific test. The paper advocates for reporting raw distributions separately from conditional/post-selected diagnostics.

Technical Summary: Approximate Sampling for Randomization Tests

More like this