Source-linked AI summary
On the Quantum versus Classical Learnability of Discrete Distributions
Ryan Sweke, Jean-Pierre Seifert, Dominik Hangleiter, Jens Eisert
TL;DR
The paper asks whether quantum learners can PAC-learn discrete distributions for generative modelling when classical learners cannot. It constructs a DDH-based distribution class using a modified pseudorandom-function construction, establishing such a separation for classical samples and classical output generators.
Problem
The paper asks whether a class of discrete distributions can be efficiently PAC-learnable by a quantum learner but not by a classical learner for generative modelling from samples.
Source: §1 · pp. 1–2Method
The authors modify the KMRRSS construction using a DDH-based pseudorandom function collection that permits quantum secret-key learning from random examples.
Source: §3 · p. 9, §3.3 · p. 19Results
Under the DDH assumption for quadratic residues, the constructed class is not efficiently classically PAC GEN-learnable but is efficiently quantum PAC GEN-learnable using the SAMPLE oracle and TV distance.
Source: §3 · p. 9, §3.3 · p. 19Takeaways & Limitations
The construction establishes a provable quantum advantage for this generative-modelling class within the PAC framework.
Source: §3 · p. 9, §3.3 · p. 19The reduction strategy for Boolean-function hardness remains unresolved when moving beyond exact learning, since efficiently learning an approximation to the inverse from random examples is unknown.
Source: §4.2 · p. 30
Abstract
from arXiv · showhide
Here we study the comparative power of classical and quantum learners for generative modelling within the Probably Approximately Correct (PAC) framework. More specifically we consider the following task: Given samples from some unknown discrete probability distribution, output with high probability an efficient algorithm for generating new samples from a good approximation of the original distribution. Our primary result is the explicit construction of a class of discrete probability distributions which, under the decisional Diffie-Hellman assumption, is provably not efficiently PAC learnable by a classical generative modelling algorithm, but for which we construct an efficient quantum learner. This class of distributions therefore provides a concrete example of a generative modelling problem for which quantum learners exhibit a provable advantage over classical learning algorithms. In addition, we discuss techniques for proving classical generative modelling hardness results, as well as the relationship between the PAC learnability of Boolean functions and the PAC learnability of discrete probability distributions.
1 Introduction
The paper studies classical versus quantum PAC learnability for generative modelling of discrete distributions. Under the DDH assumption, it constructs a class that is hard for efficient classical learners but efficiently learnable by a quantum learner.
1 Introduction
- The authors frame generative modelling as learning from samples to output an efficient generator for an approximation of the unknown distribution, distinct from density estimation.The paper focuses on generating samples rather than learning a description that evaluates the distribution.Source: §1 · p. 1
- Under the DDH assumption, the constructed distribution class is not efficiently PAC-learnable by classical algorithms but is efficiently PAC-learnable by a quantum algorithm.The learners use classical samples and output classical generators.Source: §1 · p. 2
- The construction adapts a KMRRSS distribution-class technique to a pseudorandom function collection whose secret key a quantum adversary can learn from random examples.The collection is built from the DDH assumption via a slight modification of the GGM construction.Source: §1 · p. 2
- The paper also examines whether weak pseudorandom functions or hardness results for Boolean-function PAC learning can yield classical generative-modelling hardness results.These questions are also motivated by possible applications to near-term quantum learners and quantum samples.Source: §1 · p. 2
2 Quantum and Classical PAC Learning
The section extends PAC learning from Boolean functions to discrete distributions, formalizing learners that output approximate sample generators. It then poses the paper’s separation question under a specific sampling, output, and distance setting.
2 Quantum and Classical PAC Learning
- PAC learning provides an abstract framework for comparing the computational properties of supervised learning algorithms and generative modelling.The section introduces Boolean-function PAC learning before developing the distribution-learning formulation.Source: §2 · p. 3, §2.2 · p. 5
2.1 PAC Learning of Boolean Functions
- For Boolean-function classes, the section distinguishes membership-query and random-example oracles, classical and quantum access, and distribution-dependent versus distribution-independent learners.Efficiency is defined through learner time and sample complexity, with polynomial time in the problem parameters for efficient learners.Source: §2.1 · pp. 3–4
2.2 PAC Learning of Discrete Distributions
- The distribution-learning framework defines sample oracles and allows learner type, sample access, and output-generator type to vary independently.A quantum learner may use classical or quantum samples, and either learner type may output a classical or quantum generator.Source: §2.2 · pp. 5–6
- Generative learning asks for a generator of an approximate distribution, whereas evaluator learning asks for an estimate of the distribution’s probabilities; the two tasks are incomparable.The paper focuses on generator learning, with approximation measured using a distance between distributions.Source: §2.2 · pp. 5–6
- The paper asks whether a classically generated distribution class can be hard for classical PAC GEN-learning yet efficiently learnable by a quantum learner using classical samples and outputting classical generators.The target distance is total variation; a positive result there is stronger than hardness only for KL divergence because efficient KL learnability implies efficient TV learnability.Source: §2.2 · pp. 7–8
3 A Quantum/Classical Distribution Learning Separation
The section develops a DDH-based separation between classical and quantum PAC generative learning, using classical hardness results and an efficient quantum learner. It also discusses how the learning advantage can be verified and how sample parameterization supports key recovery.
3 A Quantum/Classical Distribution Learning Separation
- Under DDH for quadratic-residue groups, a keyed function is classically pseudorandom but quantum adversaries can distinguish it with membership queries and learn its key from random examples, yielding a distribution-learning separation.The construction modifies the KMRRSS approach and gives an efficient quantum learner for a class that is not efficiently classically PAC GEN-learnable.Source: §3 · pp. 8–9
3.1 Cryptographic Primitives
- The cryptographic preliminaries define several PRF security notions by adversary type and oracle access; the standard setting gives quantum adversaries classical membership-query access to the unknown function.The section also introduces parameterization sets and indexed collections of efficiently computable keyed functions as construction ingredients.Source: §3.1 · p. 10
3.2 Classical Hardness from Classical-Secure Pseudorandom Functions
- Theorem 1 generalizes KMRRSS to arbitrary parameterization sets meeting mild requirements and strengthens its classical hardness result from KL-divergence to TV-distance.It constructs distribution classes that are not efficiently classically PAC GEN-learnable with SAMPLE access; the authors provide a full proof of the strengthened result.Source: §3.2 · pp. 10–11
- Corollary 1.1 adds an efficient bit encoding of the parameterization and defines a modified distribution class that remains not efficiently classically PAC GEN-learnable under SAMPLE access and TV-distance.This modification is used to construct a class that is also efficiently quantum learnable.Source: §3.2 · pp. 11, 14
- In the modified distribution class, each sample encodes P, so the learner needs to learn only key k; the earlier construction requires learning both P and k.Source: §3.2 · p. 14
3.3 Quantum Learnability and Classical Hardness for a DDH Based Distribution Class
- For all sufficiently large n, the DDH-based class is not efficiently classically PAC GEN-learnable under SAMPLE and TV distance, but is efficiently quantum PAC GEN-learnable under the same conditions.The construction uses a classical-secure PRF and a quantum key learner that recovers the key exactly; the resulting key and parameterization specify the exact generator.Source: §3.3 · pp. 18–19
- A quantum key learner reverses the GGM tree using the input path and quantum discrete-log computation to recover the root key exactly.The construction relies on the ability to invert the tree’s steps, including the bijection used in the PRG and discrete logarithms in the quadratic-residue group.Source: §3.3 · pp. 18–20
3.4 Verification of Quantum GEN-Learning Advantage
- The proposed verification question is whether Alice can efficiently convince a referee that her learned generator is within TV distance ϵ of the target; weak-membership verification is tolerant identity testing.The simplest black-box protocol gives the referee sample access to the learned generator, while allowing membership queries is stronger.Source: §3.4 · p. 20
- Lemma 3 bounds total variation distance between distributions by the distance between their classical generators.This bound supports the efficient verifier when the hypothesis generator and target generator share a domain.Source: §3.4 · p. 21
- When the hypothesis domain differs, membership queries do not resolve closeness, and black-box tolerant identity testing can require exponential sample complexity.The target distribution is uniform over a size 2^n subset of {0, 1}^{2n+m}; the passage also gives lower bounds for tolerant and exact-target verification.Source: §3.4 · p. 22
- The quantum learner outputs the exact target generator on the same domain, enabling efficient membership-query verification of its learning advantage.For matching domains, the verifier estimates the fraction of uniformly sampled inputs on which the hypothesis and target generators agree, repeating the test to estimate their distance.Source: §3.4 · pp. 21–22
4 On Classical Hardness Results From Alternative Primitives
Section 4 examines alternative routes to classical hardness for generative learning, including weaker-secure PRFs and hard-to-learn Boolean concept classes. It characterizes the distribution’s exact generators and discusses obstacles to transferring hardness through concept-class reductions or other techniques under uniform-random-example constraints.
4.1 Classical Hardness Results from Weak-Secure Pseudorandom Function Collections
- Theorem 1’s hardness proof still works when its inference algorithm has only random-example access, motivating a conjecture that weak-secure PRFs also yield classically unlearnable distribution classes.The conjecture concerns sufficiently large n and PAC GEN-learning with SAMPLE access and total variation distance.Source: §4.1 · p. 23
- Proving the weak-secure PRF conjecture is nontrivial: a distinguisher with only random examples cannot obtain the inference algorithm’s chosen exam value, while forcing a random exam breaks the existing reduction.If true, the conjecture could enable LPWN-based classical/quantum distribution-learning separations using quantum random samples, potentially on near-term devices.Source: §4.1 · pp. 23–24
4.2 Classical Hardness Results from Hard to Learn Function Concept Classes
- Efficient classical or quantum PAC learning of a Boolean concept class under the uniform distribution with PEX access implies corresponding GEN-learning of its constructed distribution class under SAMPLE and total variation distance.The reduction works because PEX examples can simulate samples from the associated distribution, and a close function hypothesis yields a close generator.Source: §4.2 · pp. 25, 27
- The converse—that hardness of uniform-distribution function learning implies distribution GEN-learning hardness—is only Conjecture 2, in part because approximate generators need not reveal a function hypothesis.Exact generators can be non-unique, including generators formed by composing with input permutations; exact generators also require at least n input bits.Source: §4.2 · pp. 25, 27, 28
- Existing function-learning separations do not yet meet the conditions needed to transfer a classical/quantum separation to distributions: the factoring-based class is uniform-learnable, while the s-term DNF quantum learner uses quantum random examples.Kharitonov’s classes provide uniform-distribution classical hardness, so Conjecture 2 would imply classically unlearnable distribution classes, but a matching quantum learner is not established here.Source: §4.2 · pp. 25–26
- The optimal generator assigns probability 1/2^m to 2^m strings of the form x||c(x), and zero to the remaining strings.This describes the generator minimizing total variation distance when m ≤ n.Source: §4.2 · p. 28
- If dTV(D,Dc) < 1/2, any generator GEND:{0,1}^m→{0,1}^(n+1) must have m ≥ n.Source: §4.2 · p. 29
- An exact classical generator exists only when m ≥ n, and every such generator has the form GEN(Dc,m,P) for a permutation P.The result characterizes all exact generators, not just a particular construction.Source: §4.2 · p. 29
- A proposed reduction assumes exact distribution learning and uses the resulting generator to construct a PAC learner for the concept class, but the generator’s permutation P is unknown.Even for m=n, learning P^-1 exactly is ruled out by the lack of an efficient exact learner for permutations, even with membership queries; efficient approximate learning from random examples remains unknown.Source: §4.2 · pp. 29–30
- This obstacle illustrates a conceptual and technical difference between PAC learning Boolean concept classes and generator learning distributions, while uniform-random-example constraints complicate other approaches.Alternative approaches might use efficient-learnability characterizations, Occam algorithms [57], or VC dimensions [58], but their applicability under this constraint is unclear.Source: §4.2 · p. 30
5 Discussion and Conclusion
The paper constructs a class separating classical and quantum PAC generative learnability under DDH, and identifies open questions about quantum-generated distributions, fault tolerance, learner complexity, and quantum samples.
5 Discussion and Conclusion
- Under the DDH assumption, the constructed class is not efficiently PAC GEN-learnable classically but has an efficient quantum GEN-learner using classical samples.This gives a provable quantum advantage for generative modelling.Source: §5 · p. 30
- Whether quantum-circuit output distributions are classically unlearnable from samples remains open; linking a learner to efficient black-box verification is difficult because generators are non-unique and PAC behavior outside the class is unconstrained.The discussion also asks whether efficient quantum PAC learners exist for these distributions; efficient quantum generators alone do not establish that.Source: §5 · pp. 30–31
- The quantum learner relies on discrete logarithms, so its advantage most likely requires a universal fault-tolerant quantum computer and does not provide a new separation primitive.Whether a learning separation can avoid relying on that known quantum advantage remains open.Source: §5 · p. 31
- The constructed quantum GEN-learner uses one oracle query and always outputs an exact generator, prompting the question of whether a learner needing nontrivial queries can achieve approximate generation.The discussion suggests such learners may be less task-specific and potentially suitable for near-term devices.Source: §5 · pp. 31–32
- The work uses classical samples; whether quantum-sample access enables a quantum advantage for some distribution class remains an open question.The discussion connects this possibility to conjectured results for Boolean-function concept classes.Source: §5 · p. 32