Quantum machine learning advantages beyond hardness of evaluation

1. Problem Statement

The paper addresses a fundamental gap in the understanding of Quantum Machine Learning (QML) advantages.

• Context: Previous rigorous proofs of quantum advantage in learning (e.g., Huang et al., 2021; Gyurik & Dunjko, 2023) typically rely on the hardness of evaluation. In these scenarios, a classical learner can efficiently generate labeled data (random generatability) but cannot efficiently evaluate the learned hypothesis on new inputs because the target function is cryptographically hard or BQP-complete.
• The Gap: These results do not isolate the advantage of the learning process itself (identifying the target function from data). If a classical learner can generate the data, one might argue the learning step is trivial or that the advantage only manifests at the final evaluation stage.
• Core Question: Can a quantum computer provide an exponential advantage in identifying the labeling function (the "learning step") even when the classical computer cannot efficiently evaluate the function, and specifically when the classical computer cannot even efficiently generate the labeled data?
• Challenge: For BQP-complete functions (fully quantum functions), it is conjectured that labeled data cannot be efficiently generated classically (lack of "random generatability"). This prevents the use of standard cryptographic proof techniques used in prior works, necessitating a new proof strategy.

2. Methodology and Framework

The authors employ tools from computational complexity theory, specifically the Polynomial Hierarchy (PH), to establish hardness results for classical learners.

• Learning Framework: The paper uses the Proper PAC Learning framework. The learner receives labeled examples $(x, f(x))$ and must output a description of the target function $f$ (identified by a parameter $\alpha$) from a concept class $\mathcal{F}$. Crucially, the hypothesis class is restricted to be identical to the concept class ($\mathcal{H} = \mathcal{F}$), forcing the learner to identify the specific target function rather than just outputting a circuit that hardwires the data.
• Task Definitions:
  1. Random Generatability: The ability of a classical algorithm to efficiently generate samples $(x, f(x))$ for random $x$.
  2. Verifiable Identification: The learner must identify the target $\alpha$ and reject datasets that are inconsistent with any concept in the class.
  3. Non-Verifiable (Approximate-Correct) Identification: The learner must identify $\alpha$ without necessarily rejecting invalid datasets, provided it satisfies specific consistency conditions (never outputting a concept totally inconsistent with the data).
• Concept Classes: The paper focuses on two specific types of concept classes containing BQP-complete functions:
  • $c$-distinct: Concepts differ on at least a fraction $c$ of inputs.
  • Average-case-smooth: Closeness in function output implies closeness in parameter space.

3. Key Contributions and Results

A. Hardness of Random Generatability for Quantum Functions

The authors prove that quantum functions are not randomly generatable unless the Polynomial Hierarchy collapses.

• Theorem 1: If a classical algorithm can exactly generate random labeled samples $(x, f(x))$ for a BQP function $f$, then $\mathsf{BQP} \subseteq \mathsf{P}^{\mathsf{NP}}$.
• Theorem 2: If a classical algorithm can approximately generate these samples, then $(L, \text{Unif}) \in \mathsf{HeurBPP}^{\mathsf{NP}}$.
• Significance: This establishes that for BQP functions, the data itself is hard to generate classically. This rules out the "easy data" scenario used in cryptographic learning proofs, forcing the learning advantage to stem from the processing of inherently hard-to-generate data.

B. Hardness of Verifiable Identification

The paper proves that identifying a BQP target function is classically hard even if the learner can verify the validity of the dataset.

• Theorem 3: If a verifiable identification algorithm exists for a concept class containing a BQP function, then $(L, \text{Unif}) \in \mathsf{HeurBPP}^{\mathsf{NP}}$.
• Mechanism: The proof constructs an algorithm that uses the identification oracle and an $\mathsf{NP}$ oracle to invert the learning process, effectively deciding the BQP language.
• Proposition 1 & Theorem 4: Even for singleton concept classes, if a dataset can be verified as valid/invalid, it implies $\mathsf{BQP} \subseteq \mathsf{P/poly}$ (non-uniform polynomial time), which is considered highly unlikely.

C. Hardness of Non-Verifiable Identification (Main Result)

This is the paper's primary contribution: proving quantum advantage in the identification step without requiring the learner to reject invalid datasets.

• Theorem 5: For concept classes that are either $c$-distinct ($c \ge 1/3$) or average-case-smooth, if a classical approximate-correct identification algorithm exists, then $\mathsf{BQP} \subseteq \mathsf{HeurBPP}^{\mathsf{NP}^{\mathsf{NP}^{\mathsf{NP}}}}$ (BQP is contained in the 4th level of the Polynomial Hierarchy).
• Proof Strategy:
  1. Show that an approximate-correct learner can be "upgraded" to an approximate-verifiable learner within the Polynomial Hierarchy (specifically $\mathsf{NP}$) for these specific concept classes.
  2. Use the result from the verifiable case (Theorem 3) to show that if such a verifier exists, the hierarchy collapses.
• Corollary 1: There exists a natural learning problem involving quantum functions where a quantum learner can identify the target, but no efficient classical learner can, unless $\mathsf{BQP}$ is in a low level of the Polynomial Hierarchy.

D. Physical Application

The authors provide a concrete example (Appendix G.1) based on learning parametrized observables (Molteni et al., 2024).

• They construct a concept class using Reed-Solomon codes to ensure the concepts are $c$-distinct ($c=1/3$).
• They demonstrate that a quantum algorithm can solve the identification task, while a classical algorithm would require solving a BQP-complete problem to identify the correct observable, leading to a formal separation.

4. Significance and Implications

1. Beyond Evaluation: This work provides the first rigorous proof that quantum advantage in machine learning can arise solely from the learning/identification process, independent of the hardness of evaluating the final hypothesis. It shifts the focus from "data is hard to compute" to "learning from data is hard."
2. New Proof Paradigm: The paper introduces a novel proof strategy that does not rely on "random generatability" (which fails for quantum functions). Instead, it leverages the structure of the concept class (distinctness/smoothness) to invert the learning process within the Polynomial Hierarchy.
3. Complexity-Theoretic Boundaries: The results clarify the relationship between QML and complexity classes. It suggests that for many physically motivated tasks (like learning observables or order parameters), the entire learning pipeline benefits from quantum computation, not just the final inference step.
4. Distinction from Hamiltonian Learning: The authors discuss why their hardness results do not apply to standard Hamiltonian learning (which is classically tractable). They argue that Hamiltonian learning fails to meet the specific structural assumptions (like $c$-distinctness or average-case smoothness of the concepts in the specific sense defined) required for their hardness proofs, highlighting the specific conditions under which quantum learning advantages emerge.

Conclusion

Molteni et al. establish that for a broad class of quantum learning tasks involving BQP-complete functions, the task of identifying the underlying labeling function is classically intractable (assuming standard complexity conjectures like $\mathsf{BQP} \not\subseteq \mathsf{PH}$). This proves that quantum machine learning offers advantages that are intrinsic to the learning process itself, extending the scope of proven quantum advantages beyond mere evaluation hardness.