acceptodds
Under review as a conference paper at ICLR 2027

Limits of quantum generative models with classical sampling hardness

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 following 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.

Primary area:
generative models
Keywords:
Quantum Computing, Quantum Machine Learning, Generative Quantum Machine Learning

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_7XxoOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

Sampling from certain distributions is believed to be inefficient classically yet efficient for quantum computers. This has led sampling problems to become a leading proposal for demonstrating quantum computers performing a task beyond what efficient classical algorithms can achieve, sometimes known as "quantum supremacy." Proofs of classical hardness in many of these quantum supremacy proposals rely on demonstrating the "anti-concentration" of the distribution in question, which allows one to leverage existing complexity theory results to show classical hardness conditioned on reasonable complexity theory conjectures. The authors of this work note that anti-concentration is similar to a phenomenon widely studied in the quantum machine learning literature: loss concentration, otherwise known as barren plateaus. The authors formally compute, for three examples, whether the distribution in question anti-concentrates and whether training objectives based on either the MMD or SD loss exhibit loss concentration. The authors then end with numerical simulations to validate these properties.

Critical strengths

What I found most surprising about this work was the authors showing how loss concentration can substantially differ between the MMD and SD loss functions, and also how loss concentration under either of these objectives does not necessarily imply anti-concentration. The authors' results lead them to suggest that sampling problems with "peaked" distributions might be viable candidates as machine learning problems that are both classically hard and quantumly easy. This echoes some other recent results in the field (which the authors cite) proposing biased quantum models as quantum learning algorithms, and provides nice theoretical backing to these prior observations.

Critical weaknesses

The distributions the authors consider are fairly specific: one is a product distribution with no correlations, one heavily inspired by the random circuit sampling experiments which motivated the anti-concentration property to begin with, and the final inspired by proposals for verifiable quantum supremacy experiments. It would have been nice to see a concrete statement linking loss concentration and anti-concentration for more general choices of loss function, or otherwise showing results for distributions which haven't already been extensively studied in the quantum supremacy literature. I do acknowledge that the authors' numerical results do go further than their analytic results by investigating circuit classes like IQP circuits and MPS distributions, which mitigates this weakness.

Additionally, as the authors state, anti-concentration does not actually indicate hardness generally. In other words, while the results of this paper are useful heuristics guiding further development, they do not explicitly show a link between classical hardness and training complexity.

In short, the main weaknesses of the work are the narrow scope of their theoretical analyses; overall, I think this weakness is outweighed by the strengths of the work, and I recommend acceptance.

Questions for authors

Do the authors believe their techniques generalize to other distributions beyond what's already currently seen in the quantum supremacy literature? For instance, what is the barrier to using these methods to study MPSs, which the authors only look at numerically? I imagine at low bond dimension the results would mirror the authors' product distribution results and would provide a nice analytic generalization.

The authors state on page 6: "There exists a compact representation of the circuit, implying a loss function sensitive to it"; I didn't follow this. What do the authors mean by this?

Reviewer_jN5bOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper shows limitations to training quantum generative models whose outputs have the anticoncentration, a property used in the classical hardness proofs for IQP and random-circuit sampling. The paper studies three families: product distributions, pseudo-independent distributions and peaked version of these distributions. The idea is that costs (SD and MMD) are small with respect to the uniform distribution implying that these cost functions don't have useful signal to distinguish them from uniform distribution. In contrast, models with peaked outputs can be trained, but they classical hardness results do not apply in this setting.

Critical strengths

I think this is a relevant and timely study. Several recent proposals justify quantum generative models by the classical hardness of sampling from IQP or random circuits. The paper asks whether anticoncentration, the property behind these hardness proofs, poses any obstructions for trainability. Its answer is that standard losses become uninformative for anticoncentrated families, which is a useful caution for this line of work.

  • The pseudo-independent family makes Haar like output statistics exactly computable. Figures 2–3 show that IQP, random-circuit, boson-sampling and fermion-sampling outputs follow it closely at small sizes. This proxy could be useful beyond the paper.
  • Table 1 clearly organizes the three families by anticoncentration, loss concentration and classical simulability. For product distributions, large-bandwidth MMD is only polynomially small. For pseudo-independent distributions, it vanishes at every bandwidth. This contrast shows well that low-order structure is what makes MMD training possible.
  • The discussion of peaked distributions identifies a candidate that avoids this obstructions. Their outputs are sparse, and their probabilities are hard to estimate classically. A classical sampler might exist but it may be hard to find.
Critical weaknesses
  • The link from anticoncentration to untrainability is incomplete. Combined with the triangle inequality (11), Propositions 6–7 show that for a fixed target the loss barely varies across random instances of the model. This is a barren plateau at random initialization. For the SD it follows from anticoncentration alone, but for the MMD it follows from the i.i.d. assumption, which anticoncentration does not imply. The conclusion that anticoncentrated models "will not be usable in practice" therefore does not follow. Moreover, the i.i.d. model cannot describe structured IQP models trained with large-bandwidth MMD (Recio-Armengol et al., 2025). Also trainability usually refers to the behavior of signals such as gradients, hessian becoming uninformative during the training. This result mostly concerns the loss functions considered in the paper.

  • Proposition 8 is an upper bound, so it does not show that the loss does not concentrate, yet Table 1 cites this result.

  • For random sparse distributions, the model and the target typically have disjoint supports. Then Δ(p,q)\Delta(p,q) does not depend on how close the model is to the target.

  • Statistical-query (SQ) lower bounds for learning output distributions of local and random circuits (Hinsche et al., 2023, Nietner et al., 2023) prove rigorous versions of the paper's message. These SQ results are not cited.

  • Some of the proofs in Appendix E are not rigorous.

    • Several steps are approximations rather than bounds. In Proposition 1, the last steps approximate the bound. I think it is a minor issue but make the theorem nonrigorous for no reason.
    • Eq. (77) writes the MMD of a product distribution as the nn-th power of a sum instead of a product over qubits. I guess the exponent should be ⊗n\otimes n?
    • The constants proposed after Lemma 6 (α=1/3\alpha=1/3, k=1/2k=1/2) make the bound in eq 99 vacuous. Not sure why authors choose this parameters.
Questions for authors
  1. What do Propositions 4–7 add beyond the inequality Δ(p,q)≤2∑p2+2∑q2\Delta(p,q)\le2\sum p^2+2\sum q^2?
  2. Anticoncentration alone does not make the large-bandwidth MMD small, as the biased-bit example shows. Which property of IQP or random-circuit families makes it small, and does it persist for structured case rather than random parameters?
  3. The loss of peaked models is constant whenever the supports do not overlap. In what sense are they trainable? Can you show a lower bound on the SD and a statement about the landscape?
  4. What do your results add to the SQ lower bounds of Hinsche et al. and Nietner et al.?
  5. Hardness proofs use anticoncentration to pass from multiplicative to additive error. Is there evidence that hardness of sampling requires anticoncentration, as the abstract and conclusion suggest?
Reviewer_4rbDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

This paper studies the trainability limitations faced by quantum generative models when they inherit classical sampling hardness. Its central claim is that distributions whose classical sampling hardness is established via anticoncentration (typified by IQP, RQC, and Haar-random states) have output probabilities fluctuating around the 2−n2^{-n} scale. This causes squared distance (SD) and global MMD losses, together with their variances, to concentrate exponentially as the number of qubits grows. The author establishes concentration/anticoncentration inequalities through three analytically tractable distribution families (product distributions, pseudo-independent distributions, and pseudo-independent peaked distributions) and supplements these with numerical experiments for n≤13n\le 13. The conclusion is that anticoncentration models are untrainable in the average-case sense; trainable sparse/peaked models cannot establish sampling hardness through the anticoncentration route; and the source of advantage for quantum generative models must therefore differ from anticoncentration.

Critical strengths

(1) The distribution-level analytical characterization has intrinsic value. The concentration/anticoncentration inequalities for the three distribution families (Propositions 1-3 and 6-8) provide a clean, testable example of "exponential loss concentration in anticoncentration models." The observation is not itself novel, but its concrete formulation for SD and MMD offers a useful technical reference for future work citing or extending these results under specified losses and distribution families.

(2) The link between training and verification is conceptually suggestive. Section 5 points out that anticoncentration distributions not only cause training signals to vanish but also require exponential resources for sample-based verification, connecting this difficulty to the exponential decay of TVD variance. The connection is not fully developed, but it suggests that generative models on the anticoncentration route face constraints both at the optimization level and at the statistical verification level.

Critical weaknesses

(1) The core conclusion is incremental rather than paradigmatic relative to Gil-Fuster et al. (ICLR 2025). Gil-Fuster, Gyurik, Pérez-Salinas, and Dunjko already established a general connection between trainability and classical dequantization at ICLR 2025: trainable variational quantum learning models can often be dequantized classically, and thus do not retain quantum advantage. The paper's chain "anticoncentration → untrainability → classically samplable trainable models" is essentially a special case of this more general trade-off, instantiated at the level of generative model output distributions. The introduction cites this work only in passing and does not explain what new content the distribution-level SD/MMD calculations provide beyond what dequantization arguments already cover. A top-tier conference paper needs to answer clearly: if a general dequantization trade-off already exists, what is the incremental contribution of rederiving concentration inequalities within a specific distribution family? The paper offers no convincing answer.

(2) Neglect of the frequency-resolved trainability of sparse IQP leaves the central claim untested in its most important counterexample direction. Shen et al. (NeurIPS 2026) directly challenge the paper's implicit premise, namely that IQP behavior relevant to hardness must be accompanied by gradient suppression in the corresponding frequency range; they show that sparse IQP can remain trainable on low-weight frequencies while retaining classical intractability. The paper's numerical experiments use fully connected IQP and peaked circuits with K∈Θ(n)K\in\Theta(n), precisely missing the region that subsequent work identifies as a key exception. The "average-case untrainability" conclusion may hold within the paper's own distribution-family setup, but it cannot support the general limit suggested by the title for "quantum generative models with classical sampling hardness." From the current manuscript, I cannot determine whether Shen et al.'s frequency-resolved trainability constitutes a substantive counterexample, or, if so, how the paper's framework would need to be modified to accommodate it. This gap is a major soundness defect.

Questions for authors

Q1 (substantive; affects evaluation). Shen et al. (NeurIPS 2026) show that sparse IQP distributions can be classically intractable while remaining trainable on low-weight frequencies. Please clarify whether this result contradicts your "anticoncentration models are untrainable" conclusion, or merely qualifies it. If you regard it as a qualification, please argue that "trainability on low-weight frequencies is insufficient to constitute an effective generative training signal." This argument is entirely missing from the current paper, yet it is necessary for your central claim to remain valid in the face of sparse IQP.

Q2 (substantive). You classify peaked circuits as "trainable but classical sampling hardness not established." Zhang (2025) proves #P-hardness for estimating peaked weights, not sampling hardness. Please clarify whether your stated limitation applies to generative models whose advantage source is estimation hardness rather than sampling hardness. If the training objective of a generative model (for example, estimating peakedness) can be decoupled from the sampling task, is "classical sampling hardness" still the appropriate entry point for analyzing generative-model advantage?

Q3 (clarification). The pseudo-independent distribution (Definition 2) discards correlations by construction. You also acknowledge in Appendix B that genuinely quantum effects may lie in correlations. In what sense does proving SD/MMD concentration within the pseudo-independent family constrain circuits with nontrivial correlation structures (for example, IQP circuits with nontrivial high-order Fourier terms)? If such a constraint does not hold, how should the scope of the paper's conclusions be restated?

Comments on the paper

1 comment
AuthorsOpenReview ↗

Response to all reviewers and changes

We would like to once again thank all referees for their effort and time. We just uploaded a revised version of the manuscript with further context and discussion, factoring in the comments, which we believe significantly improved the manuscript. For simplicity, we list the changes below.

  • Background: We extended the background with further discussion on Gil-Fuster et al. (2025), as suggested by Review 4rbD, and connected our results to the distribution learning results via the statistical query framework, as suggested by Reviewer JN5b.
  • Loss concentration: we added an interpretation of the difference between SD and MMD concentration of the product distributions and pseudo-independent distributions, as highlighted by Reviewer 4rbD. The clarification for the product distribution also clarifies question 2 from reviewer 7Xxo.
  • Section 3.3 Connection to other results: We have further elaborated on the connection to Shen et al. (Review 4rbD) and structured IQP circuits (Reviewer jN5b). In a nutshell, we are currently preparing a manuscript discussing the possibility to classically compute expectation values of O(1)\mathcal O(1)-local observables, whereas observables with a locality of n/2n/2 become difficult to compute. In the standard IQP picture, low-order correlations constitute an exponentially small fraction, whereas global correlations constitute the majority by combinatorial arguments. Erdös-Renyi graphs may have non-vanishing computable low-order correlations. However, they can keep their hardness if the (non-computable) global correlations are non-negligible. We see this line of work, fueled by Shen et al., as a technique to profile the transition between theoretical sampling hardness (relying only on #P-hardness an anticoncentration) and the practical utility of these circuits as generative models. This future research line is explicitly mentioned in the new version.
  • The section 3.3 further elaborates on the usefulness and potential of quantum advantage of peaked circuits as generative models as discussed with Reviewer 4rbD.

We hope the changes help clarify the referees' doubts. We are happy to answer any further questions until the discussion period ends.

We have also given a comparative document of old and new versions with highlighted changes in the supplementary material.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.