Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2607.19004

The Tractability Landscape of Sampling with Inexact Scores

Anming Gu, Kevin Tian, Hubert Yang, Yusong Zhu

Published Jul 21, 2026• 0 citations
arXivHTMLPDF

Abstract

We provide a simple and tight characterization of the types of inexact score oracle access that permit sampling with vanishing total variation bias, for a standard, well-behaved target family. Our main result shows that any weaker error than the sub-Gaussian assumption used by [YW26] rules out the tractability of unbiased sampling. This strengthens the conclusion of [CCSW26] to be algorithm-agnostic, and to hold for a wider range of error assumptions.

DOI
10.48550/arxiv.2607.19004

Related papers

When Coarse Scores Suffice for Diffusion Steering

Shardul Mishra

Recent work on quadratic diffusion steering raised two questions: whether negative quadratic rewards admit sampling algorithms polynomial in the numerical magnitude of the reward, and how imperfect score access changes their tractability. We answer the first and characterise the second at two ends of the score-precision range. For bounded priors and fixed-rank symmetric quadratic rewards, sufficiently precise isotropic diffusion scores permit sampling in time polynomial in the numerical parameters, including the reward magnitude. This is a pseudopolynomial guarantee, not a bound polynomial in binary encoding length. At fixed absolute score tolerance, however, rank-one negative quadratic rewards exhibit a distinct, unconditional information-access barrier: in dimension m+1, the worst-case query complexity at constant Wasserstein accuracy has exponential order exp(Θ(m log(1+λ/m))), up to polynomial factors. The lower bound holds even for smooth priors with known marginals and reward normaliser. Matching upper-exponent constructions use rare-event likelihood-ratio control and Gaussian auxiliary sampling. Known low-dimensional nuisance geometry permits polynomial-query sampling for fixed auxiliary dimension, while noise cutoffs and prior-average denoising error can conceal reward-relevant rare modes. These results distinguish numerical score precision from access to the information needed for reliable posterior steering.

•Nov 15, 2026•0 citations

Amplification with One NP Oracle Query

Thomas W. Watson

We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, onesided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our inclusions are tight for relativizing techniques.

Computational Complexity•Feb 5, 2022•0 citations

Error estimation of practical convolution discrete Gaussian sampling with rejection sampling

Zhongxiang Zheng, Xiaoyun Wang, Guangwu Xu +1 more

Science China Information Sciences•Feb 4, 2021•2 citations

Robust Dequantization of the Quantum Singular Value Transformation and Quantum Machine Learning Algorithms

François Le Gall

Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been “dequantized” in the past few years. These dequantization results typically hold when classical algorithms can access the data via length-squared sampling. This assumption, which is standard in the field of randomized linear algebra, means that for a unit-norm vector $$u\in\mathbb{C}^{n}$$ , we can sample from the distribution $$p_u\colon\{1,\ldots,n\}\to [0,1]$$ defined as $$p_u(i)=|u(i)|^2$$ for each $$i\in\{1,\ldots,n\}$$ . Since this distribution corresponds to the distribution obtained by measuring the quantum state | $$u$$ > in the computational basis, length-squared sampling access gives a reasonable classical analogue to the kind of quantum access considered in many quantum algorithms for linear algebra problems. In this work we investigate how robust these dequantization results are. We introduce the notion of approximate length-squared sampling, where classical algorithms are only able to sample from a distribution close to the ideal distribution in total variation distance. While quantum algorithms are natively robust against small perturbations, current techniques in dequantization are not. Our main technical contribution is showing how many techniques from randomized linear algebra can be adapted to work under this weaker assumption as well. We then use these techniques to show that the recent low-rank dequantization framework by Chia, Gilyén, Li, Lin, Tang and Wang (JACM 2022) and the dequantization framework for sparse matrices by Gharibian and Le Gall (STOC 2022), which are both based on the Quantum Singular Value Transformation, can be generalized to the case of approximate length-squared sampling access to the input. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms, including quantum algorithms for recommendation systems, supervised clustering and low-rank matrix inversion.

arXiv:2304.04932•Computational Complexity•Jan 18, 2025•16 citations

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

Mohamed Faisal Sindhi, Hammaz Buksh

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.

•Oct 13, 2026•0 citations

A Nonstandard Variant of Learning with Rounding with Polynomial Modulus and Unbounded Samples

Hart William Montgomery

Lecture notes in computer science•Jan 1, 2018•5 citations
We provide a simple and tight characterization of the types of inexact score oracle access that permit sampling with vanishing total variation bias, for a standard, well-behaved target family. Our main result shows that any weaker error than the sub-Gaussian assumption used by [YW26] rules out the tractability of unbiased sampling. This strengthens the conclusion of [CCSW26] to be algorithm-agnostic, and to hold for a wider range of error assumptions.
Recent work on quadratic diffusion steering raised two questions: whether negative quadratic rewards admit sampling algorithms polynomial in the numerical magnitude of the reward, and how imperfect score access changes their tractability. We answer the first and characterise the second at two ends of the score-precision range. For bounded priors and fixed-rank symmetric quadratic rewards, sufficiently precise isotropic diffusion scores permit sampling in time polynomial in the numerical parameters, including the reward magnitude. This is a pseudopolynomial guarantee, not a bound polynomial in binary encoding length. At fixed absolute score tolerance, however, rank-one negative quadratic rewards exhibit a distinct, unconditional information-access barrier: in dimension m+1, the worst-case query complexity at constant Wasserstein accuracy has exponential order exp(Θ(m log(1+λ/m))), up to polynomial factors. The lower bound holds even for smooth priors with known marginals and reward normaliser. Matching upper-exponent constructions use rare-event likelihood-ratio control and Gaussian auxiliary sampling. Known low-dimensional nuisance geometry permits polynomial-query sampling for fixed auxiliary dimension, while noise cutoffs and prior-average denoising error can conceal reward-relevant rare modes. These results distinguish numerical score precision from access to the information needed for reliable posterior steering.
Several quantum algorithms for linear algebra problems, and in particular quantum machine learning problems, have been “dequantized” in the past few years. These dequantization results typically hold when classical algorithms can access the data via length-squared sampling. This assumption, which is standard in the field of randomized linear algebra, means that for a unit-norm vector u∈Cnu\in\mathbb{C}^{n}u∈Cn , we can sample from the distribution pu ⁣:{1,…,n}→[0,1]p_u\colon\{1,\ldots,n\}\to [0,1]pu​:{1,…,n}→[0,1] defined as pu(i)=∣u(i)∣2p_u(i)=|u(i)|^2pu​(i)=∣u(i)∣2 for each i∈{1,…,n}i\in\{1,\ldots,n\}i∈{1,…,n} . Since this distribution corresponds to the distribution obtained by measuring the quantum state | uuu > in the computational basis, length-squared sampling access gives a reasonable classical analogue to the kind of quantum access considered in many quantum algorithms for linear algebra problems. In this work we investigate how robust these dequantization results are. We introduce the notion of approximate length-squared sampling, where classical algorithms are only able to sample from a distribution close to the ideal distribution in total variation distance. While quantum algorithms are natively robust against small perturbations, current techniques in dequantization are not. Our main technical contribution is showing how many techniques from randomized linear algebra can be adapted to work under this weaker assumption as well. We then use these techniques to show that the recent low-rank dequantization framework by Chia, Gilyén, Li, Lin, Tang and Wang (JACM 2022) and the dequantization framework for sparse matrices by Gharibian and Le Gall (STOC 2022), which are both based on the Quantum Singular Value Transformation, can be generalized to the case of approximate length-squared sampling access to the input. We also apply these results to obtain a robust dequantization of many quantum machine learning algorithms, including quantum algorithms for recommendation systems, supervised clustering and low-rank matrix inversion.
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.