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.

arXiv:2609.28802 [quant-ph]

(or arXiv:2609.28802v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2609.28802 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.