On Certifying Source Sampling Hardness in Quantum Generative Modeling
Abstract
Quantum generative models are often motivated by circuit families whose output distributions are believed to be classically hard to sample from. When such models are trained on ordinary classical datasets, however, this hardness does not automatically transfer to the unknown data-generating distribution. We show that transferring sampling hardness via total-variation closeness from a quantum model to an unknown source requires certifying a global relation between the two distributions, thereby reducing the problem to distribution certification. Combining this reduction with existing certification lower bounds yields an exponential sample requirement for the high-entropy distributions relevant to many sampling-hardness proposals. Consequently, polynomially many samples cannot, in general, justify attributing sampling hardness to an unknown data-generating distribution. Moreover, even classically trivial distributions, such as the uniform distribution and product distributions, require exponentially many samples to certify in the absence of structural assumptions. Our results clarify the role of sampling hardness in quantum generative modeling and distinguish generator-level hardness from source-level hardness when learning from ordinary datasets.
Related
- Generative learning of time series with holographic quantum circuit sampling
- Verifiable Sampling for Delegated Generative Quantum Machine Learning
- Quantum MeanFlow: single-shot generative sampling on NISQ hardware
- A Coherent Memory Register for Sequential Quantum Generative Modeling, with Application to Calorimeter Showers
- Logarithmic-Depth Fermion Sampling: Anticoncentration and Average-Case Hardness
BibTeX
@misc{liu2026certifying,
title = {{On Certifying Source Sampling Hardness in Quantum Generative Modeling}},
author = {Chen-Yu Liu and Leonardo Placidi and Enrico Rinaldi},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.28802},
eprint = {2609.28802},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.28802},
}
RIS
TY - UNPB
TI - On Certifying Source Sampling Hardness in Quantum Generative Modeling
AU - Chen-Yu Liu
AU - Leonardo Placidi
AU - Enrico Rinaldi
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.28802
UR - https://arxiv.org/abs/2609.28802
AB - Quantum generative models are often motivated by circuit families whose output distributions are believed to be classically hard to sample from. When such models are trained on ordinary classical datasets, however, this hardness does not automatically transfer to the unknown data-generating distribution. We show that transferring sampling hardness via total-variation closeness from a quantum model to an unknown source requires certifying a global relation between the two distributions, thereby reducing the problem to distribution certification. Combining this reduction with existing certification lower bounds yields an exponential sample requirement for the high-entropy distributions relevant to many sampling-hardness proposals. Consequently, polynomially many samples cannot, in general, justify attributing sampling hardness to an unknown data-generating distribution. Moreover, even classically trivial distributions, such as the uniform distribution and product distributions, require exponentially many samples to certify in the absence of structural assumptions. Our results clarify the role of sampling hardness in quantum generative modeling and distinguish generator-level hardness from source-level hardness when learning from ordinary datasets.
ER -