⚛️ quantum physics

Stratified Sampling for Quasi-Probability Decompositions

This paper introduces a framework utilizing stratified sampling with a classical dynamic programming approach to reduce the configuration variance of quasi-probability decompositions, offering significant sampling cost savings for quantum algorithms without requiring additional quantum resources.

Original authors: Joshua W. Dai, Bálint Koczor

Published 2026-02-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Joshua W. Dai, Bálint Koczor

Original paper licensed under CC BY 4.0 (http://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 you are trying to guess the average height of everyone in a massive, chaotic stadium. You can't measure everyone, so you have to take a sample.

In the world of quantum computing, scientists face a similar problem. They want to calculate a specific result (like the energy of a molecule), but the quantum circuits required are too "noisy" or complex to run perfectly. To fix this, they use a clever trick called Quasi-Probability Decomposition (QPD).

Here is the problem with the current trick, and the new solution this paper offers, explained simply.

The Problem: The "Noisy Dice" Strategy

Imagine you need to roll a perfect, fair die to get a number, but you only have a bag of broken, weighted dice. Some dice are heavy, some are light, and some are even "negative" (a weird quantum concept).

To get the right answer, you don't just roll one die. You:

Pick a die at random from your bag (this is the "configuration").
Roll it many times to get an average.
Multiply the result by a special "weight" (because some dice are broken).
Repeat this whole process thousands of times with different random dice.

The Catch:
While this method gives you the correct answer on average (it's "unbiased"), it is incredibly noisy. Because you are randomly picking different broken dice every time, your results bounce around wildly. To get a precise answer, you have to roll the dice millions of times, which takes a long time and uses up expensive computer resources.

This "bouncing around" is called Configuration Variance. It's like trying to hear a whisper in a room where people are randomly shouting different things.

The Solution: Stratified Sampling (The "Smart Organizer")

The authors of this paper say: "Stop picking dice completely at random! Let's organize the bag first."

They introduce a method called Stratified Sampling. Here is how it works with our stadium analogy:

1. The Naïve Way (Old Method):
You walk into the stadium and grab 1,000 people completely at random. You might accidentally grab 500 people from the VIP section and only 5 from the cheap seats. Your average height will be way off, and you'll have to grab more people to fix the error.

2. The Stratified Way (New Method):
You look at the stadium map. You know there are VIPs, students, and seniors. You decide: "I will grab exactly 300 VIPs, 500 students, and 200 seniors."

You don't pick them randomly from the whole crowd.
You pick them randomly within their specific groups.
Then you combine the results.

Why is this better?
By forcing the sample to represent every group perfectly, you eliminate the "noise" caused by accidentally over-sampling one group. You get a much more stable, accurate average with fewer people.

The Paper's Specific Innovation: "The Counting Trick"

In quantum circuits, the "groups" are defined by how many times you used a specific type of "broken die" (or quantum gate).

The authors realized that in many quantum circuits, the order of the gates doesn't matter as much as the count.

Example: If you use a "Type A" gate 5 times and a "Type B" gate 3 times, it doesn't matter if the A's came first or the B's came first. They produce similar results.

The Algorithm:

Pre-computation (The Brain Work): Before running the quantum computer, a classical computer runs a smart math program (Dynamic Programming). It counts how many ways you can arrange the gates to get specific "counts" (e.g., 5 Type A, 3 Type B). It calculates the "weight" of each group.
The Allocation: It decides exactly how many times to run the "5 Type A / 3 Type B" group, the "4 Type A / 4 Type B" group, etc.
The Execution: The quantum computer runs these specific groups the exact number of times needed.

The Results: Saving Time and Money

The paper tested this on two common quantum tasks:

Probabilistic Error Cancellation (PEC): Fixing errors in the computer.
Probabilistic Angle Interpolation (PAI): Making precise rotations.

The Outcome:

In the "Oracle" scenario (where we ignore the basic quantum noise and look only at the randomization noise): They reduced the variance (the bouncing around) by 60% to 80%. This means they could get the same answer with only a fraction of the work.
In the "Real World" scenario (where basic quantum noise is also present): They still saw a 10% improvement. In the world of quantum computing, a 10% saving is huge because it means you can run the algorithm faster or on smaller, cheaper machines.

The Bottom Line

This paper doesn't invent a new quantum computer or a new way to fix errors. Instead, it invents a smarter way to organize the work.

Think of it like this:

Old Way: Throwing darts at a board blindfolded and hoping you hit the bullseye eventually.
New Way: Dividing the board into sections, aiming for each section with a specific number of throws, and then combining the scores.

You still need the same skill (the quantum hardware), but you get a better result with fewer throws. This makes quantum algorithms more practical for the near future, allowing us to solve problems without needing a supercomputer to wait for the answer.

1. Problem Statement

Quasi-probability decompositions (QPDs) are essential tools in quantum computing for simulating difficult quantum processes, mitigating errors (e.g., Probabilistic Error Cancellation, PEC), and performing probabilistic synthesis. A QPD replaces a target unitary channel with an ensemble of "easier" implementable channels, weighted by quasi-probabilities (which can be negative).

While QPDs allow for unbiased estimation of observables, they introduce a significant overhead: configuration variance.

The Issue: Standard QPD protocols use "naïve" sampling, where circuit configurations are drawn independently and identically distributed (i.i.d.) from a product distribution. This introduces a classical variance component (configuration variance) on top of the intrinsic quantum shot noise (Born-rule noise).
The Consequence: To achieve a target precision, the total number of circuit executions ( $N$ ) must scale with the square of the QPD 1-norm ( $\|g\|_1^2$ ). This exponential scaling often renders QPD-based methods impractical for deep circuits.
The Gap: Existing work focuses on optimizing the design of the QPD to minimize $\|g\|_1$ . However, for a fixed QPD, the efficiency of the sampling strategy itself has not been systematically optimized to reduce the constant prefactors in the variance.

2. Methodology

The authors propose a framework based on Stratified Sampling, a technique from classical statistics, adapted for product-form QPDs.

A. Variance Decomposition

The authors model the QPD estimator as a two-level Monte Carlo process:

Configuration Level: Sampling a circuit variant $\ell$ from the distribution $p(\ell)$ .
Shot Level: Repeating the measurement $R$ times for a fixed $\ell$ to average out Born-rule noise.

Using the Law of Total Variance, they decompose the total variance of the estimator:
$\text{Var}(Y) = \underbrace{\mathbb{E}[\text{Var}(Y|\ell)]}_{\text{Born-rule noise}} + \underbrace{\text{Var}(\mathbb{E}[Y|\ell])}_{\text{Configuration variance}}$
Stratified sampling targets the second term (configuration variance) without altering the target expectation or the Born-rule noise.

B. Stratified Sampling Strategy

Instead of drawing configurations i.i.d., the authors partition the configuration space into strata based on a deterministic statistic $S(\ell)$ .

Proportional Allocation: They allocate a fixed number of samples $K_s$ to each stratum $s$ proportional to the stratum's probability mass $w_s$ (i.e., $K_s \approx K \cdot w_s$ ).
Theoretical Guarantee: They prove Theorem 1: Under ideal proportional allocation, the variance of the stratified estimator is never worse than naïve sampling. The variance reduction is exactly equal to the "between-stratum" variance (the variance of the stratum means).
$\text{Var}_{\text{naïve}} - \text{Var}_{\text{strat}} = \frac{1}{K} \sum_s w_s (\mu_s - \bar{\mu})^2 \geq 0$

C. Counts-Vector Stratification

To make this algorithmically explicit for product-form QPDs, they introduce a specific statistic: the Counts Vector.

Definition: For a circuit of depth $\nu$ with local width $d$ , a configuration is a string $\ell = (\ell_1, \dots, \ell_\nu)$ . The counts vector $M = (M_1, \dots, M_d)$ records the frequency of each local primitive index, ignoring the order (permutation invariance).
Efficiency: While the total number of configurations is $O(d^\nu)$ , the number of distinct counts vectors (strata) is only $O(\nu^{d-1})$ , which is polynomial in depth for fixed width.
Dynamic Programming (DP):
- Forward Pass: Computes the exact probability weights ( $w_m$ ) for every counts vector using a Poisson-Multinomial distribution DP. Complexity: $O(d \nu^d)$ .
- Backward Pass: Enables exact conditional sampling of a configuration $\ell$ given a target counts vector $M=m$ . Complexity: $O(\nu d)$ per sample.
Residual Handling: Since sample counts must be integers, the authors use a Residual-Aware Hamilton Apportionment scheme. This ensures exact unbiasedness even when the ideal proportional quota is not an integer, by aggregating "leftover" strata into a residual bucket.

3. Key Contributions

Theoretical Framework: Established that stratified sampling is an unbiased, variance-reducing primitive for QPDs, with a rigorous proof that it is never worse than naïve sampling.
Algorithmic Construction: Developed a universal, permutation-invariant stratification using counts vectors, supported by an efficient Dynamic Programming algorithm for weight calculation and conditional sampling.
Practical Implementation: Provided a complete "drop-in" replacement for naïve QPD sampling that requires no additional quantum resources, only classical pre-processing and post-processing.
Variance Reduction Analysis: Demonstrated that the method effectively removes the "explained variance" of the configuration space, particularly in regimes where shot noise is suppressed.

4. Numerical Results

The authors benchmarked their method on Transverse-Field Ising Model (TFIM) circuits using two standard QPD schemes:

Probabilistic Angle Interpolation (PAI): Approximating continuous rotations with discrete hardware angles.
Probabilistic Error Cancellation (PEC): Mitigating depolarizing noise.

Key Findings:

Oracle Regime (Shot noise suppressed, $R \to \infty$ ): Stratification achieved massive variance reductions of 60–80%. This indicates that the counts vector captures a significant portion of the configuration-to-configuration variation in the ideal circuit output.
Single-Shot Regime ( $R=1$ ): In the presence of dominant Born-rule noise, reductions were modest but robust, around 10%.
Scalability: The method remains practical for moderate depths (e.g., $\nu \approx 100$ ) and small local widths ( $d=3$ for PAI, $d=4$ for PEC). The preprocessing cost is polynomial, and the per-sample generation cost matches naïve sampling up to a constant factor.

5. Significance and Impact

Resource Savings: By reducing the constant prefactor in the variance, the method effectively lowers the total number of circuit executions required to reach a target precision. This extends the practical utility of QPDs in near-term and early fault-tolerant devices where shot budgets are tight.
Orthogonality to QPD Design: This approach complements existing work on designing better QPDs (minimizing $\|g\|_1$ ). It operates on any fixed product-form QPD, offering a "free" variance reduction without changing the underlying quantum circuit or noise model.
Generalizability: While focused on product-form QPDs, the conceptual framework (separating configuration variance from shot noise and using stratification) applies broadly to other randomized quantum algorithms, such as randomized compiling, twirling, and classical shadows.
Immediate Applicability: The method requires no new quantum hardware capabilities; it is purely a classical optimization of the sampling protocol, making it immediately deployable in current quantum software stacks.

In summary, the paper provides a rigorous, algorithmic solution to the "configuration variance" bottleneck in QPDs, proving that intelligent sampling design can yield substantial, provable resource savings for quantum error mitigation and simulation.