Stratified Sampling for Quasi-Probability Decompositions

• URL: http://arxiv.org/abs/2602.11245v1
• Date: Wed, 11 Feb 2026 17:46:40 GMT
• Title: Stratified Sampling for Quasi-Probability Decompositions
• Authors: Joshua W. Dai, Bálint Koczor,
• Abstract summary: Quasi-probability decompositions (QPDs) have proven essential in many quantum algorithms and protocols.<n>We develop a broad framework for accounting for and reducing this variance.<n> Numerical simulations of typical QPDs demonstrate constant-factor reductions in overall variance.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $\sim 60$--$80\%$ in an oracle model) and robust $\sim 10\%$ savings in the pessimistic single-shot regime. Our results can be applied immediately to reduce the net sampling cost of practically relevant QPDs that are commonly used in near term and early fault-tolerant algorithms without requiring additional quantum resources.

Related papers

• Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum [62.691095807959215]
  We establish an optimal sample complexity of $O(-2)$ for obtaining an $$-optimal global policy using a single-timescale actor-critic (AC) algorithm.<n>These mechanisms are compatible with existing deep learning architectures and require only minor modifications, without compromising practical applicability.
  arXiv  Detail & Related papers  (2026-02-02T00:35:42Z)
• Orders of magnitude runtime reduction in quantum error mitigation [0.0]
  We introduce a mitigation framework that combines virtual noise scaling with a layered mitigation architecture.<n>The proposed approach is compatible with dynamic circuits and can be seamlessly integrated with error detection and quantum error correction schemes.
  arXiv  Detail & Related papers  (2026-01-30T10:07:31Z)
• Quantum-Circuit Framework for Two-Stage Stochastic Programming via QAOA Integrated with a Quantum Generative Neural Network [1.7240671897505615]
  Two-stage programming often discretizes uncertainty into scenarios, but scenario makes recourse expected evaluation scale at least linearly in the scenario count.<n>We propose a unified quantum-circuit workflow in which a pre-trained adversarial network encodes the scenario distribution.
  arXiv  Detail & Related papers  (2025-12-27T02:03:33Z)
• Variational quantum algorithms with invariant probabilistic error cancellation on noisy quantum processors [13.51474348538291]
  We propose a novel noise-adaptable strategy that combines PEC with the quantum approximate optimization algorithm (QAOA)<n>We experimentally validated this technique on a superconducting quantum processor, cutting sampling cost by 90.1%.<n>These results open promising avenues for executing VQAs with large-scale, low-noise quantum circuits, paving the way for practical quantum computing advancements.
  arXiv  Detail & Related papers  (2025-06-08T08:25:47Z)
• Faster Probabilistic Error Cancellation [6.418044102466421]
  We propose a new method to perform PEC, which results in a lower sampling cost than the standard way.<n>We show the saving both analytically and numerically over the standard PEC.<n>We also demonstrated this method experimentally and found excellent agreement between the mitigated and the ideal values.
  arXiv  Detail & Related papers  (2025-06-04T21:38:56Z)
• Harmonic Path Integral Diffusion [0.4527270266697462]
  We present a novel approach for sampling from a continuous multivariate probability distribution, which may either be explicitly known (up to a normalization factor) or represented via empirical samples. Our method constructs a time-dependent bridge from a delta function centered at the origin of the state space at $t=0$, transforming it into the target distribution at $t=1$. We contrast these algorithms with other sampling methods, particularly simulated and path integral sampling, highlighting their advantages in terms of analytical control, accuracy, and computational efficiency.
  arXiv  Detail & Related papers  (2024-09-23T16:20:21Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms. In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
  arXiv  Detail & Related papers  (2023-12-19T13:17:43Z)
• A Robustness Analysis of Blind Source Separation [91.3755431537592]
  Blind source separation (BSS) aims to recover an unobserved signal from its mixture $X=f(S)$ under the condition that the transformation $f$ is invertible but unknown. We present a general framework for analysing such violations and quantifying their impact on the blind recovery of $S$ from $X$. We show that a generic BSS-solution in response to general deviations from its defining structural assumptions can be profitably analysed in the form of explicit continuity guarantees.
  arXiv  Detail & Related papers  (2023-03-17T16:30:51Z)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. Our novel insights into the particle-based algorithms for continuous distribution strategies are presented.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Importance sampling for stochastic quantum simulations [68.8204255655161]
  We introduce the qDrift protocol, which builds random product formulas by sampling from the Hamiltonian according to the coefficients. We show that the simulation cost can be reduced while achieving the same accuracy, by considering the individual simulation cost during the sampling stage. Results are confirmed by numerical simulations performed on a lattice nuclear effective field theory.
  arXiv  Detail & Related papers  (2022-12-12T15:06:32Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way Partial AUC (OPAUC) and Two-way Partial AUC (TPAUC) measures the average performance of a binary classifier. Most of the existing methods could only optimize PAUC approximately, leading to inevitable biases that are not controllable. We present a simpler reformulation of the PAUC problem via distributional robust optimization AUC.
  arXiv  Detail & Related papers  (2022-10-08T08:26:22Z)
• Sampling diverse near-optimal solutions via algorithmic quantum annealing [0.3506539188356145]
  One of the main open problems is the lack of ergodicity, or mode collapse, for typical Monte Carlo solvers. Here, we introduce a new diversity measure for quantifying the number of independent approximate solutions for NP-hard optimization problems.
  arXiv  Detail & Related papers  (2021-10-20T13:33:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.