Exponential separations between classical and quantum learners

Contributions

• The paper frames the work as a response to the goal of proving exponential quantum advantages for practically relevant learning problems.It also reviews related topics, including the classical-shadow framework and parameterized quantum circuit evaluation.Source: §1 · p. 1, Section 5 · p. 3

Section 2

• The paper distinguishes identifying a labeling function from evaluating it, because the distinction changes whether a problem exhibits a learning separation.It also clarifies that these categories concern the learner and hypothesis class, not whether the examples are quantum-generated.Source: §1 · p. 1, Section 2 · p. 2
• The paper outlines computational hardness assumptions for efficient PAC separations and defines HeurBPP/samp to capture classically learnable functions.It relates this class to HeurP/poly.Source: Section 2 · p. 2

Section 3

• Existing separations largely rely on the classical hardness of evaluating the data-generating function, while two new separations place the hardness in identifying it.The paper also identifies discrepancies between prior definitions and its framework, then gives stronger assumptions and a new translation approach to support separations under its definitions.Source: Section 3 · p. 2

Section 4

• The paper gives a generic method for separations from BQP-complete functions and applies it to problems in quantum many-body physics.It also gives natural assumptions under which the method's criteria are satisfied.Source: Section 4 · p. 3

Section 5

• The paper constructs Hamiltonians whose ground-state properties cannot be predicted by classical-shadow-based classical machine learning under cryptographic assumptions.It also discusses Hamiltonian learning and identifying order parameters and phases as fixed-hypothesis-class learning settings.Source: Section 5 · p. 3

2.1 Learning separations in the PAC learning framework

• Efficient PAC learning uses labeled examples from an oracle and requires a polynomial-time learner to output a hypothesis close to the target concept.The framework specifies concept and hypothesis classes, an input and label space, and target distributions.Source: §2.1 · pp. 3–4
• The four categories CC, CQ, QC, and QQ distinguish whether the learner is classical or quantum and whether its hypotheses are classically or quantumly evaluatable.These distinctions apply even when the examples themselves are classical.Source: §2.1 · p. 5
• For quantumly evaluatable hypotheses, CQ = QQ, but this collapse relies on changing the hypothesis class and does not apply when that class is fixed.The learner can effectively offload its computation onto hypothesis evaluation.Source: §2.1 · p. 6
• A singleton concept that is classically hard to evaluate but quantumly easy yields a CC/QQ separation without data, illustrating a potentially trivial learning separation.The quantum learner can evaluate the sole concept without needing examples.Source: §2.1 · p. 6

2.1.1 Learning separations with a fixed hypothesis class and proper PAC learning

• Fixed hypothesis classes capture tasks such as identifying phase-characterizing order parameters, even when evaluating those hypotheses may be QMA-hard.The standard PAC setting permits arbitrary hypotheses and therefore may not ensure that the learner outputs a physically meaningful order parameter.Source: §2.1.1 · pp. 6–7
• With a fixed hypothesis class, classical and quantum learners differ by their learning algorithm, and proper PAC learning is the case where outputs must belong to the concept class.Fixed-class hypotheses may be computationally intractable without trivializing the learning definition.Source: §2.1.1 · p. 7

2.1.2 Identification versus Evaluation

• CC/QC separations require quantum help to identify how to label unseen examples using classical evaluation, whereas CC/QQ separations also require quantum help to evaluate those labels.For fixed hypothesis classes, the learner need only identify the matching hypothesis, not evaluate it on unseen examples.Source: §2.1.2 · p. 8

2.2 Complexity theory

• Heuristic complexity classes incorporate the target distribution, with HeurBPP and HeurBQP capturing polynomial-time classical and quantum algorithms, respectively.This distribution-aware view is relevant because PAC correctness is required only over a fraction of examples drawn from the target distribution.Source: §2.2 · p. 8
• In heuristic complexity an algorithm may err, whereas average-case complexity requires correctness but permits a “don’t know” output; PAC learning uses heuristic complexity.If solution correctness is efficiently checkable, heuristic and average-case algorithms can be converted into one another in the ways described.Source: §2.2 · pp. 8–9
• Worst-to-average-case reductions can yield heuristic hardness for cryptographic problems, including discrete logarithms, where correctness on any poly(n) fraction of inputs is as hard as correctness on all inputs.The discrete-log example relies on efficient checking of proposed solutions via modular exponentiation.Source: §2.2 · p. 9
• PAC learners receive sample-derived advice, unlike standard polynomial advice; sampling advice is no more powerful than standard advice, since BPP/samp ⊆ P/poly.The example oracle’s advice consists of sampled inputs paired with their labels.Source: §2.2 · pp. 9–10
• A polynomial-time classical learner implies its concepts lie in HeurBPP/samp, where an algorithm uses labeled samples from the example oracle.HeurBPP/samp captures randomized computation with sample access and bounded error over the input distribution.Source: §2.2 · p. 10
• Because HeurBPP/samp ⊆ HeurP/poly, any concept class containing concepts outside HeurP/poly is not classically learnable.Thus, proving that a concept lies outside HeurP/poly is sufficient for a non-learnability result.Source: §2.2 · p. 10
• The roadmap presents Section 3 separations with efficiently evaluatable concepts or fixed-class hypotheses, then Section 4 quantum-generated-data separations extending to essentially all BQP-complete problems.The paper positions the latter constructions as extending beyond the cryptographic problems discussed in Section 3.Source: §2.2 · p. 10, Table 1 · p. 11

3 Learning separations with efficient data generation

• Efficient classical example generation lets hardness of the concepts imply classical non-learnability, because an efficient learner would yield an efficient classical algorithm.The section also distinguishes separations where classical difficulty comes from evaluating hypotheses from those designed to make the difficulty lie in identifying the generating concept.Source: §3 · pp. 11–12

3.1 Learning separation based on heuristic hardness: case of discrete logarithm

• The original class has a CC/QQ separation under DLP intractability for fixed prime-generator sequences; a related class gets one under canonical hardness by leaking prime and generator base information.Source: §3.1 · pp. 14–15
• For singleton discrete-log classes, binary concepts require the stronger DLP-fixed assumption, whereas the standard [BM84] assumption yields a CC/QQ separation only for non-binary concepts.The latter construction uses a related modified class; this is the trade-off between assumption strength and label type.Source: §3 · p. 12, §3.1 · p. 15

3.2 Learning separation based on obfuscation: the case of discrete cube root

• The cube-root class has a CC/QC separation: a quantum learner uses Shor’s algorithm to recover a key and select a hypothesis from a classically evaluatable hypothesis class.The function is hard to evaluate from its cube-root specification under DCRA, but an alternate specification using the key makes it classically tractable.Source: §3.2 · pp. 16–17
• The cube-root argument lets the input distribution depend on the target concept, contrary to the stated PAC framework; fixing moduli by instance size makes the distribution common across concepts.Examples remain efficiently generatable for the fixed-moduli cube-root class.Source: §3.2 · p. 16
• For a modified cube-root concept class, CC/QC separation follows either from the stronger DCR-fixed assumption or from canonical discrete-cube-root hardness using different inputs and functions.DCR-fixed requires intractability for a fixed sequence of moduli; the alternative construction relaxes that requirement by modifying the class.Source: §3.2 · pp. 17–18
• For singleton cube-root classes, CC/QC separation uses DCR-fixed, while a related construction permits canonical hardness in exchange for a CC/QQ separation.The canonical-hardness singleton construction changes the closely related concept class, as in the modified construction above.Source: §3.2 · p. 18

3.3 Learning separation with efficiently evaluatable concepts

• The modular-exponentiation class yields a CC/QC separation under 2c-DCRA despite classically efficient evaluation, placing classical learning hardness in identifying the generating concept.The quantum learner combines order-finding and discrete-log algorithms to recover the exponent from examples. The concepts are not binary-valued, and whether the separation extends to binary-valued concepts remains open; restricting the modulus to 2c-integers may also affect the hardness assumption.Source: §3.3 · pp. 18–19

3.4 Learning separation with a fixed hypothesis class

• The cube-root identification class gives a CH/QH separation under DCRA when learners must output from a fixed hypothesis class, making the task proper PAC learning.The quantum learner uses examples to reconstruct m^3 and N, then applies Shor’s algorithm to identify the concept; the classical hardness lies in identification, not evaluating unseen examples.Source: §3.4 · pp. 20–21

4 Learning separations without efficient data generation

• Polynomial-size concept classes of efficiently quantum-evaluable concepts that lie outside HeurP/poly under a distribution yield a CC/QQ learning separation.Polynomial class size lets a quantum learner search the concepts; non-membership in HeurP/poly supplies classical non-learnability.Source: §4 · pp. 21–22
• A BQP problem outside HeurP/poly under some distribution suffices to transfer heuristic hardness to every BQP-complete problem, though the induced distribution may be artificial.The section notes discrete logarithm as an example and says its reduction-induced distributions are artificial.Source: §4 · p. 22
• If a BQP problem is outside P/poly and polynomially random self-reducible, it lies outside HeurP/poly, yielding a CC/QQ separation for every BQP-complete problem.The section presents this as a sufficient assumption, not an established fact about a particular problem.Source: §4 · p. 22
• Discrete logarithm gives an efficiently samplable-distribution separation for each BQP-complete problem unless DLP is in BPP.The section connects DLP's random self-reducibility and random verifiability to this conditional result.Source: §4 · p. 23
• For generative modeling, classical non-learnability could follow if not all SampBQP problems are in SampBPP/poly, an assumption argued to follow from polynomial-hierarchy non-collapse.This is described as a possible route, rather than a proved separation.Source: §4 · p. 23

4.1 Learning separations from physical systems

• Physical-system separations use reduction-induced distributions, which the authors call artificial and unsupported by evidence of practical relevance.The separation framework establishes a construction, not that these distributions occur in physical practice.Source: §4.1 · pp. 23–24
• Universal Hamiltonian families and some high-energy-physics problems provide BQP- or QMA-complete concepts; QMA-complete cases can be restricted or relaxed to BQP-complete ones.Examples include Bose-Hubbard and antiferromagnetic Heisenberg models, and scalar quantum-field-theory scattering.Source: §4.1 · pp. 23–24

5.1 Provably efficient machine learning with classical shadows

• Under cryptographic assumptions, classical methods like those of Huang et al. cannot retain constant-error prediction for certain physical systems when the constant-gap or smoothness requirements are relaxed.The stated implication is that such a method would place DLP in P/poly.Source: §5.1 · p. 25
• Classical-shadow data differ from PAC examples, and thresholding real-valued predictions to obtain discrete labels introduces a data-type mismatch.Shadow data can be used across multiple observables, while the paper's PAC setup uses function evaluations and discrete labels.Source: §5.1 · p. 25

5.2 Power of data

• Although a parameterized circuit function may be hard to evaluate from its description, three examples suffice to fit its single-parameter form and evaluate it classically.The coefficients are independent of the free parameter, so distinct examples determine them.Source: §5.2 · p. 26
• For multiple free parameters, polynomially many Fourier frequencies make polynomially many examples sufficient to fit and evaluate the circuit expectation.The section distinguishes fixed-parameter evaluation from the harder task where circuit parameters are part of the input.Source: §5.2 · p. 26
• In the described circuit setting, examples are quantum-generated and each function lies in HeurP/poly, while exponentially many Fourier terms leave classical learnability unclear.Thus difficulty evaluating a function from its description alone does not by itself establish classical non-learnability with data.Source: §5.2 · p. 26

5.3 Physically-motivated PAC learning settings with fixed hypothesis classes

• Hamiltonian learning fits fixed-hypothesis PAC learning as identification of the generating Hamiltonian, but classical algorithms identify its parameters in many natural settings.The task is to select the generating concept, not merely to output a hypothesis that matches the examples.Source: §5.3 · p. 27
• Identifying an order parameter is likewise a fixed-hypothesis task, but predicting a phase does not itself provide a physically meaningful order-parameter description.The candidate hypotheses encode observables intended to characterize a phase.Source: §5.3 · pp. 27–28

A.1 Constraining hypothesis classes to those that are efficiently evaluatable

• Allowing superpolynomial-time hypotheses makes the polynomial-time learner restriction vacuous, because a polynomial-time learner can encode example sets whose hypotheses run the slower learner.The section motivates restricting hypotheses to those that are efficiently evaluatable.Source: §A.1 · p. 32

A.2 Proof of Lemma 1

• The lemma states that CQ = QQ.The proof shows both inclusions, with the reverse inclusion providing the substantive construction.Source: §A.2 · p. 32
• For the reverse inclusion, hypotheses indexed by polynomial-size training sets run the quantum learner and evaluate its resulting hypothesis.A classical polynomial-time learner queries examples and outputs the hypothesis corresponding to the observed set.Source: §A.2 · p. 32
• Because the encoded hypotheses may use quantum evaluation, a classical polynomial-time learner can realize any learning task in QQ under the stated setup.The proof also uses that an efficient classical algorithm can be simulated by an efficient quantum algorithm for the other inclusion.Source: §A.2 · p. 32

A.3 Proof of Lemma 2

• HeurBPP/samp is contained in HeurP/poly.The proof adapts a strategy used to show BPP/samp is contained in P/poly, encoding suitable training data and random seeds as advice.Source: §A.3 · pp. 32–33

B.1 CC/QQ separation from intractability assumption in [BM84]

• The assumption rules out polynomial-size circuits that compute the discrete logarithm on the specified fraction of primes.The appendix states that circuits meeting that success condition must grow faster than any polynomial.Source: §B.1 · p. 33
• Under the discrete-logarithm hardness assumption, the constructed concept class exhibits a CC/QQ separation.The quantum learner recovers the relevant tuple from examples and then uses Shor's algorithm to evaluate the concept.Source: §B.1 · pp. 33–34
• A classical learner would yield circuits computing a discrete-logarithm-related predicate on a sufficiently large fraction of inputs, contradicting the stated hardness.The proof invokes random self-reducibility to relate that average-case computation to the assumed hardness.Source: §B.1 · p. 34

B.2 Singleton CC/QQ separation from intractability assumption in [BM84]

• The non-binary singleton class exhibits a CC/QQ separation assuming discrete-log intractability.The quantum learner needs no data: it outputs a hypothesis that computes the discrete logarithm using Shor’s algorithm.Source: §B.2 · p. 34
• An efficient classical learner for the non-binary singleton class would imply a polynomial-time algorithm violating the discrete-log intractability assumption [BM84].The proof uses random self-reducibility to turn partial success into an algorithm that computes the logarithm for all inputs.Source: §B.2 · pp. 34, 36

C.1 CC/QC separation from intractability assumption in [KV94b]

• The binary concept class exhibits a CC/QC separation assuming discrete cube-root intractability.The quantum learner recovers the modulus from examples and uses Shor’s algorithm to compute the inverse cube root.Source: §C.1 · pp. 36–37
• An efficient classical learner for the binary class would yield circuits computing the inverse cube root on a substantial fraction of inputs, contradicting the assumed hardness.The reduction uses the learner to compute the binary representation of the inverse cube root.Source: §C.1 · pp. 36–37

• The binary singleton class exhibits a CC/QQ separation assuming discrete cube-root intractability.A quantum learner can output a hypothesis that computes the inverse cube root using Shor’s algorithm.Source: §C.2 · p. 37
• An efficient classical learner would yield a polynomial-time algorithm computing the inverse cube root for an inverse-polynomial fraction of moduli, violating the hardness assumption [KV94b].The proof uses random self-reducibility to extend partial correctness to computing the inverse function.Source: §C.2 · p. 37

D Proof of Theorem 7

• The modular-exponentiation class exhibits a CC/QC separation under the discrete cube-root assumption for 2^c-integer moduli.The assumption concerns classical intractability of computing the inverse cube root on an inverse-polynomial fraction of moduli and inputs.Source: D Proof of Theorem 7 · p. 38
• An efficient classical learner would provide a classically evaluatable hypothesis agreeing with the inverse cube root on a polynomial fraction of inputs, violating the 2^c-DCRA.The argument uses the modular-exponentiation class’s inclusion of the cube-root function.Source: D Proof of Theorem 7 · p. 38
• The quantum learner identifies exponent d from examples by using Shor’s algorithm to recover element orders and discrete logarithms, then combining congruences.It recovers d modulo prime-power factors and brute-forces modulo 2^c, where c is constant.Source: D Proof of Theorem 7 · p. 39

D.1 Discrete cube root assumption for moduli of Definition 20

• The hardness implications of modulus conditions (b) and (c) remain relatively unexplored, although the paper gives reasons to believe the DCRA still holds under them.The authors note that cryptographically strong primes and several recently factored RSA numbers satisfy both conditions.Source: §D.1 · pp. 39–40

• The construction exhibits a CH/QH separation assuming discrete cube-root intractability.The quantum learner recovers the modulus from examples and uses Shor’s algorithm to compute the exponent needed to invert cubing.Source: E Proof of Theorem 8 · p. 40
• The quantum learner reconstructs m^3 from examples revealing selected bits, then computes m using the inverse exponent modulo N.The proof states that polynomially many examples suffice to reconstruct m^3 with high probability.Source: E Proof of Theorem 8 · p. 40
• A classical learner would identify m′ with m by matching the cube-root bits, thereby solving the discrete cube-root instances.Any differing bit would contradict the learner’s stated agreement condition; bijectivity of cubing then gives m = m′.Source: E Proof of Theorem 8 · pp. 40–41

F Proof of Theorem 9

• The stated conditions imply that L exhibits a CC/QQ learning separation.They require polynomial-time quantum evaluation of each concept, polynomial concept-class size, and a concept sequence outside HeurP/poly under the distributions.Source: F Proof of Theorem 9 · p. 41
• A quantum learner can implement empirical risk minimization by brute-force search over Cn, placing L in QQ.It iterates over the concepts and selects one matching the oracle examples.Source: F Proof of Theorem 9 · p. 41
• A classical learner would place the designated concept sequence in HeurBPP/samp and thus HeurP/poly, contradicting the assumption and excluding L from CC.The proof combines the learner with its classically evaluatable hypothesis-class evaluation algorithm.Source: F Proof of Theorem 9 · p. 41

F.1 Proof of Lemma 3

• Given L in BQP with (L, D) outside HeurP/poly, the lemma concludes that each BQP-complete L′ has a distribution D′ for which (L′, D′) is outside HeurP/poly.The distribution is constructed from a many-to-one reduction from L to L′.Source: §F.1 · pp. 41–42
• The proof defines D′ as the pushforward of D under the reduction f, which maps each sampled instance x to f(x).The output instance size may be polynomially larger than the input.Source: §F.1 · p. 41
• A HeurP/poly algorithm for (L′, D′) would yield an advice-based classical algorithm for (L, D), contradicting the premise.The proof transfers the algorithm through the reduction and uses the pushforward distribution to preserve the relevant success guarantee.Source: §F.1 · p. 42

F.2 Proof of Lemma 4

• If L is outside P/poly and polynomially random self-reducible with respect to D, then (L, D) is outside HeurP/poly.Source: §F.2 · p. 42
• Random self-reducibility supplies a polynomial-time procedure using x and O(poly(n)) sampled instances whose labels are L(y_i).The proof invokes the definition of random self-reducibility and a distribution over the sampled instances.Source: §F.2 · p. 42
• A HeurP/poly solver for (L, D) would imply L is in BPP/poly = P/poly, contradicting the lemma’s assumption.The proof combines the solver's advice and sampled-instance guarantees to reach this implication.Source: §F.2 · p. 42

F.3 Proof of Corollary 5

• Every BQP-complete L has an efficiently samplable D_L such that (L, D_L) is outside HeurBPP/samp, unless DLP is in BPP.Source: §F.3 · p. 42
• Assuming every efficiently samplable distribution makes L heuristically solvable, the proof uses the pushforward of the uniform distribution under a reduction from DLP to L.The resulting algorithm for (L, D_L) also solves DLP under the uniform distribution.Source: §F.3 · p. 42
• Because DLP is random self-reducible and random verifiable, that uniform-distribution solver would imply DLP is in BPP.Source: §F.3 · p. 42

G Proof of Theorem 10

• The theorem concludes DLP ∈ P/poly under its stated randomized-algorithm premise.The conclusion follows from the constructed Hamiltonian family and the associated ground-state observable.Source: G Proof of Theorem 10 · p. 43
• A polynomial-depth Shor circuit is parameterized into U(x), which underlies the constructed Hamiltonian H(x).The construction adds identity layers to U(x) before defining H(x).Source: G Proof of Theorem 10 · p. 43
• H(x) is 5-local, and its ground state ρH(x) defines the observable fH,O(x) = Tr[ρH(x)O].The observable O is local and has constant norm.Source: G Proof of Theorem 10 · pp. 43–44
• Estimating the average fH,O over a corner Cy to additive inverse-polynomial error allows computation of DLP(y).Cy consists of points near the coordinates of the bitstring y, mapped to {−1, 1}^n.Source: G Proof of Theorem 10 · p. 44
• The constructed Hamiltonians have inverse-polynomial spectral gap, while the rapid parameter transition makes a constant-bounded average gradient unlikely.The passage notes that the gradient may instead scale with the number of parameters m, which scales with n here.Source: G Proof of Theorem 10 · p. 44