Limits of quantum generative models with classical sampling hardness
Sabrina Herbst, Ivona Brandić, Adrián Pérez-Salinas · 2025
Read Limits of quantum generative models with classical sampling hardness by Sabrina Herbst, Ivona Brandić, Adrián Pérez-Salinas (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24801.txt.
Introduction
Sabrina Herbst, Ivona Brandic, and Adrian Perez-Salinas set limits on quantum generative models that aim to sample from classically hard distributions. Sampling tasks have driven claims of quantum advantage, so learning such distributions on a quantum device would seem powerful. Looking at output distributions, they show models that anticoncentrate are, on average, not trainable.
That untrainability includes models displaying quantum advantage, drawing a boundary around the hope. Contrasts with trainable cases sharpen where quantum generative learning might still work. Readers in quantum machine learning get a caution grounded in theory: hardness of sampling and ease of training pull in opposite directions.
Catalog record
| CREATOR | Sabrina Herbst, Ivona Brandić, Adrián Pérez-Salinas |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 94 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-24801
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Limits of quantum generative models with classical sampling hardness Sabrina Herbst, Ivona Brandić, Adrián Pérez-Salinas Abstract Sampling tasks have been successful in establishing quantum advantages both in theory and experiments. This has fueled the use of quantum computers for generative modeling to create samples following the probability distribution underlying a given dataset. In particular, the potential to build generative models on classically hard distributions would immediately preclude classical simulability, due to theoretical separations. In this work, we study quantum generative models from the perspective of output distributions, showing that models that anticoncentrate are not trainable on average, including those exhibiting quantum advantage. In contrast, models outputting data from sparse distributions can be trained. We consider special cases to enhance trainability, and observe that this opens the path for classical algorithms for surrogate sampling. This observed trade-off is linked to verification of quantum processes. We conclude that quantum advantage can still be found in generative models, although its source must be distinct from anticoncentration. I Introduction Quantum computers are known to have extended capabilities with respect to their classical counterparts, which has been established through examples such as Shor factorization Shor 1997 , Grover search Grover 1996 , or experimental demonstrations of quantum advantages Arute et al. 2019 ; Broome et al. 2013 . Inspired by the success of classical Machine Learning (ML), quantum machine learning (QML) explores recipes to process data through quantum resources and surpass current computational capabilities. The presence of data, however, incorporates subtleties for showing formal separations, since simulating a computational process and learning from data are fundamentally different tasks Schreiber et al. 2023 ; Gil-Fuster et al. 2025 ; Huang et al. 2021 . Still, in certain cases, it is possible to show robust separations Jerbi et al. 2024 ; Gyurik et al. 2024 ; Sweke et al. 2021 ; Coyle et al. 2020 , e.g., by planting the seed of a quantumly easy and classically hard problem inside a learning algorithm Liu et al. 2021 . For that, strong assumptions on data, as the central element of (Q)ML, are necessary. However, realistic data might be noisy, incomplete, imperfect or redundant, reducing the scope of applicability of these separations. The central difficulty thus lies in finding practically useful algorithms that perform better or are more efficient compared to classical counterparts. Quantum computers suit a natural interpretation as generative models, i.e., ML models learning data distributions to subsequently sample from them. Sampling is inherent to quantum processes, since measurements are the only way to retrieve information from quantum states. In particular, the measurement process probabilistically generates samples based on the underlying state through Born’s rule. This property is exploited in generative QML (GQML) models, such as parameterized quantum circuits, Boltzmann machines or Gibbs states Barthe et al. 2025 ; Shen et al. 2025 ; Kurkin et al. 2025 ; Zoufal 2021 . We recall that sampling tasks were the first framework where quantum advantage was found, with the examples of Boson sampling Aaronson and Arkhipov 2011 , Instantaneous Quantum Polynomial (IQP) Bremner et al. 2010 ; Bremner et al. 2016 circuits or random quantum circuits (RQC) Boixo et al. 2018 ; Arute et al. 2019 . Using these circuits as subroutines open the potential for quantum-advantageous generative models Kasture et al. 2023 ; Recio-Armengol and Bowles 2025 . In this work, we show that classical hardness of circuits has its reflections in QGML. Shortly, classical hardness requires anticoncentration , that is, the underlying probability distribution is on average almost but not exactly uniform. As a consequence, most loss functions required to train the generative models will strongly concentrate, preventing any training. The result shows reminiscence of barren plateaus McClean et al. 2018 ; Larocca et al. 2025 ; Cerezo et al. 2025 . This observation is tightly related to verification of a quantum sampling task, and deeply rooted in the assumptions allowing for quantum advantage. To show these results, we analytically study three abstractions of quantum circuits; (1) a circuit description corresponding to product states, (2) a family yielding pseudo-independent probability distributions, which we connect to quantumly-advantageous circuits, and (3) pseudo-independent sparse distributions, which are related in spirit to classically verifiable circuits with quantum advantage Aaronson and Zhang 2024 ; Zhang 2025 . We show that the first two families lead to exponential concentration of the square distance between probability distributions, although only pseudo-independent states can show classical hardness. For the sparse case, loss functions do not concentrate, however, due to missing anticoncentration, classical sampling hardness is not established. We further provide numerical experiments to interpolate between analytical results and practically relevant circuits. The concentration results we find have direct implications for GQML, targeting the subtle difference between sampling hardness and utility of the model. The lack of trainability, implied by the on-average impossibility to distinguish between the target function and the produced one, preclude the on-average usage of hard-to-sample generative models. While it is possible to find trainable instances, the sampling hardness guarantees are severely compromised in this case. The paper is organized as follows. Section II provides relevant background on QGML and classical sampling hardness. Section III states our theoretical framework and proves concentration for loss functions. Section IV numerically extends the theoretical statements. Connection to verification and implications for QML are detailed in Section V and Section VI . We conclude in Section VII . II Background II.1 Quantum computers as generative models Quantum computers are easily interpreted as discrete sampling machines, in which the probability of sampling a possible outcome, e.g., a bitstring, follows Born’s rule. Given a circuit C , this probability is given as p_{C}(x)=\left|\bra{x}C\ket{0}\right|^{2},\quad x\in\{0,1\}^{n}. (1) Interestingly, the task of sampling bitstrings from a quantum computer has been fertile in showing quantum advantages, both theoretically and experimentally, through, e.g., IQP Bremner et al. 2016 , RQC Boixo et al. 2018 ; Aaronson and Chen 2016 ; Arute et al. 2019 or Boson sampling Aaronson and Arkhipov 2011 . This perspective opens a path for using quantum computers as a generative ML model, where the goal is to learn the underlying distribution q of a dataset of samples. For GQML, this is done, e.g., with Quantum Circuit Born machines Benedetti et al. 2019 , Quantum Boltzmann Machines Amin et al. 2018 and Quantum Generative Adversarial Networks Lloyd and Weedbrook 2018 . Any generative model based on a sampling task with provable quantum advantage has the potential to inherit the classical hardness, thus, no classical algorithm could - even approximately - substitute the quantum machine. This has, in particular, been explored for IQP circuits Kasture et al. 2023 ; Recio-Armengol et al. 2025 , which even allow for universality if ancillary qubits are used Kurkin et al. 2025 . In this scenario, classical sampling hardness – in the assumptions of the original IQP hardness proofs – is, to the best of our knowledge, an open problem. From a practical point of view, a (Q)GML model must be trainable to be useful, that is, there must exist an efficient algorithm that finds one particular instance of the model that accurately mimics the training data Gil-Fuster et al. 2025 . The notion of trainability has been widely addressed in quantum variational models, for instance