A Quantum/Classical Example Oracle Separation for Making Things Up

The paper studies the power of quantum examples compared to classical examples in the Probably Approximately Correct (PAC) learning framework. The authors consider two learning algorithms, both with access to quantum computation, but one receives quantum examples while the other receives classical examples. The central question is whether there are learning tasks that can be efficiently performed by the former but not by the latter.

The paper's primary result is to show that relative to an oracle, there are distributions that can be efficiently generated by a quantum learner with access to quantum examples, but not by a quantum learner with access to only classical examples. This makes progress toward answering the question in the affirmative.

The paper first addresses a conjecture by Sweke et al. (Conjecture 3.1), which states that if a function class is not efficiently PAC learnable, then the induced distribution class cannot be efficiently generated. The authors provide a counterexample to this conjecture relative to an oracle, assuming the existence of one-way permutations. Specifically, Theorem 3.2 states: "Assume one-way permutations exist, and let W be a (classical) oracle providing query access to a one-way permutation. Then there is a concept class C that can be efficiently generated with respect to the SAMPLE oracle and TV-distance, but is not efficiently learnable with respect to the uniform distribution and the PEX oracle."

The construction uses a one-way permutation g and a hardcore predicate Br (x) = ⟨x, r⟩ mod 2. The concept class C consists of functions f defined as:

• f(x) = f(tb) = Br (t) if b = 0

• f(x) = f(tb) = Br (g −1 (t)) if b = 1

The proof shows that learning this function class is hard because predicting f(x) for strings with b = 1 requires predicting the hardcore predicate, which is equivalent to inverting the one-way permutation. However, generating the induced distribution is easy because the generator can sample a random string t, query the oracle to get s = g(t), and then output s1Br (t), effectively inverting the function on a point it chose itself.

The main result, Theorem 4.2, states: "For the concept class C described above, with additional access to the function g encoded via oracle W, there is a quantum algorithm with QSAMPLE access to f that can efficiently PAC-generate this concept class. However, no quantum algorithm with only SAMPLE access to f can efficiently PAC-generate this concept class."

The construction for this separation uses a random function g: 0, 1 n → 0, 1 n. For each nonzero string a, the authors define a Probably Approximate Simon's (PAS) function fa (x) = g(x) + g(x + a). These functions have period a but may also have pseudoperiods. The concept class C consists of the 2n − 1 distributions induced by these functions.

The authors prove Lemma 4.1, which shows that with probability 1 − o(1) over the choice of g, for all nonzero a, the pseudoperiod factor ε(fa, a) = O(n log n / 2n). This low pseudoperiod factor allows Simon's algorithm to recover the period a with high probability using quantum examples (Theorem 4.1 from Kaplan et al.).

The quantum learner with QSAMPLE access can run Simon's algorithm to find the period a, then generate the distribution exactly by sampling x uniformly and computing f(x) = g(x) + g(x + a) using oracle queries to g. This requires only O(n) quantum examples.

In contrast, the authors argue that a quantum learner with only classical SAMPLE access cannot efficiently generate this distribution. They note that finding the period a with classical samples requires exponential sample complexity (omega(2n/2) queries, due to Cleve). Furthermore, they show that without learning a, any generator will produce a distribution at total variation distance 1 − 2−omega(n) from the true distribution. This is because for most points x, the learner has no information about x + a, so f(x) behaves like a uniformly random string, and the learner can only guess it with probability 2−n.

The paper concludes with several open questions, including:

1. Whether hard instances can be constructed without auxiliary oracle access

2. Whether the assumptions for Theorem 3.2 can be relaxed from one-way permutations to one-way functions

3. What the maximal separation between quantum and classical examples could be in this setting

Based on the paper, here are specific improvements for AI systems:

1. Quantum-Enhanced Generative Modeling: Build an AI system that uses quantum examples (QSAMPLE) to learn and generate probability distributions that are classically intractable. The improved system can efficiently generate distributions from hidden periodic structures (e.g., Simon's problem) using quantum algorithms, whereas classical-only systems would require exponential samples. This enables AI to model complex data distributions with quantum speedup.

2. Oracle-Based Learning Separations: Implement a framework where AI systems can exploit oracle access (e.g., one-way permutations) to achieve learning tasks that are provably impossible with classical examples alone. The improved system can use quantum superposition to query oracles and extract hidden structure (like hardcore predicates) that classical learners cannot access efficiently.

3. Hardness-Aware Distribution Generation: Design an AI generator that, when given a concept class, can determine whether to use quantum or classical sampling based on the pseudoperiod factor (ε). The improved system can automatically switch to quantum algorithms (e.g., Simon's) when ε is low, ensuring efficient generation, while falling back to classical methods for simpler distributions.

4. Sample-Complexity Optimization: Develop an AI learner that minimizes the number of examples needed by leveraging quantum superposition. The improved system can achieve O(n) quantum examples for tasks that require Ω(2(n/2)) classical examples, reducing data acquisition costs in quantum machine learning pipelines.

5. Robust Distribution Recovery: Create an AI system that can recover a target distribution even when it has partial information about the underlying function. The improved system uses quantum algorithms to identify periods or symmetries, then reconstructs the distribution exactly, avoiding the 1 - 2(-Ω(n)) total variation distance error that classical generators would incur.

6. Theoretical Verification of Quantum Advantages: Build an AI framework that automatically verifies whether a given learning task has a quantum advantage by checking for the presence of one-way permutations or periodic structures. The improved system can certify that certain distributions are quantum-generatable but classically hard, providing guarantees for quantum AI applications.

7. Adaptive Quantum-Classical Hybrid Learning: Implement a hybrid AI system that dynamically allocates quantum resources (e.g., QSAMPLE) only when classical learning fails, based on the hardness criteria from the paper. The improved system can reduce quantum resource usage while maintaining performance, making it practical for near-term quantum devices.

We study the power of quantum examples, as compared to classical examples, in the PAC learning framework. Here, we have two learning algorithms, both with access to quantum computation, but one gets quantum examples, whereas the other gets classical examples. It was previously unknown whether there were learning tasks that can be efficiently performed but not by the latter. Our primary result is to show that relative to an oracle, there are distributions that can be efficiently generated by a quantum learner with access to quantum examples, but not by a quantum learner with access to only classical examples, making progress to answering this question in the affirmative.