A Quantum/Classical Example Oracle Separation for Making Things Up

Technical Summary: A Quantum/Classical Example Oracle Separation for Making Things Up

Problem Statement
This paper investigates the relative power of quantum examples versus classical examples within the Probably Approximately Correct (PAC) learning framework. Specifically, it addresses whether there exist learning tasks that can be efficiently performed by a quantum learner with access to quantum examples (superpositions of samples) but cannot be efficiently performed by a quantum learner restricted to only classical examples (standard samples), even when both learners possess quantum computational capabilities.

While previous work established separations between quantum and classical computation in learning (e.g., Sweke et al. [SSHE21]), and between quantum and classical query complexity (e.g., Simon's problem), the specific separation between quantum and classical examples in the PAC setting remained an open question. Prior results by Arunachalam and De Wolf [AW18] suggested that for arbitrary distributions, quantum examples offer at most a constant factor advantage in sample complexity, while Salmon et al. [SSG24] showed a quadratic advantage if the underlying circuit is accessible. However, a strict separation in efficiency (i.e., polynomial vs. exponential) for learning tasks using only examples was not established.

Methodology and Approach
The author adopts an oracle-based approach, a standard technique in complexity theory when unconditional separations are difficult to prove. They construct learning instances relative to an oracle encoding an auxiliary function $g$. The learning algorithms are granted access to:

1. Examples from a concept class $C_g$ induced by $g$ (either via a SAMPLE oracle for classical examples or a QSAMPLE oracle for quantum examples).
2. Oracle access to the auxiliary function $g$ itself.

The study focuses on two distinct tasks:

1. PAC Learning of Functions: Outputting a hypothesis that approximates the target function.
2. PAC Generation of Distributions: Outputting a generator that produces samples from a distribution close (in Total Variation distance) to the target distribution induced by the concept class.

The paper utilizes two primary cryptographic and algorithmic tools:

• One-way Permutations: Used to construct a concept class that is hard to learn but easy to generate.
• Simon's Algorithm and Pseudoperiods: Used to construct a concept class where quantum examples allow efficient period recovery (and thus generation), while classical examples require exponential samples.

Key Contributions and Results

1. Refuting the "Function Hardness Implies Distribution Hardness" Conjecture
The paper first addresses a conjecture by Sweke et al. [SSHE21], which posited that if a function class is not efficiently PAC learnable, then its induced distribution class cannot be efficiently PAC generated.

• Result: The author disproves this conjecture relative to an oracle (Theorem 3.2).
• Construction: They define a concept class based on the hardcore predicate of a one-way permutation $g$.
  • Learning Hardness: Predicting the function on inputs where a specific bit is set requires inverting the one-way permutation, which is computationally hard.
  • Generation Efficiency: A generator can efficiently produce samples from the induced distribution by sampling a pre-image $s$, computing $t = g(s)$, and outputting the tuple $(t, \text{hardcore}(s))$. Since $g$ is a permutation, $t$ is uniformly distributed, and the generator does not need to invert $g$; it only needs to evaluate it.
• Implication: This demonstrates that distribution generation can be strictly easier than function learning, even in the presence of quantum computation.

2. Separation Between Quantum and Classical Examples
The primary contribution is the demonstration of a separation between quantum and classical examples specifically in the context of PAC generation of distributions relative to an oracle (Theorem 4.2).

• Construction: The author defines a concept class $C_g$ induced by a random boolean function $g$. For a random non-zero vector $a$, they define functions $f_a(x) = g(x) + g(x+a)$. These functions have a hidden period $a$ but may contain "pseudoperiods" (collisions not equal to $a$).
• Quantum Advantage:
  • Using Lemma 4.1, the author shows that for a random $g$, the number of pseudoperiods is low with high probability.
  • A quantum learner with access to quantum examples (uniform superpositions of $x$ and $f_a(x)$) can run Simon's algorithm to recover the period $a$ efficiently. Once $a$ is known, the learner can generate the distribution by sampling $x$ and computing $f_a(x)$.
• Classical Limitation:
  • A learner with only classical examples cannot efficiently recover the period $a$. Recovering the period from classical samples requires $\Omega(\sqrt{2^n})$ samples (based on Cleve's query lower bound).
  • Without knowing $a$, any generator attempting to mimic the distribution will fail. The paper proves that without knowledge of $a$, the Total Variation (TV) distance between the generated distribution and the true distribution is $1 - o(1)$ (effectively 1), meaning the generator fails to approximate the target.
• Result: Relative to an oracle, there exists a distribution class that can be efficiently PAC-generated by a quantum learner with quantum examples, but cannot be efficiently PAC-generated by a quantum learner with only classical examples.

Significance and Claims
The paper claims to provide the first oracle separation between quantum and classical examples in the learning setting.

• Novelty: Unlike previous works that relied on access to the unitary circuit generating the examples (e.g., Gilyen et al. [GL20]), this separation relies solely on the nature of the examples (superposition vs. classical sample) without requiring access to the generating circuit.
• Context: The work clarifies the relationship between learning functions and generating distributions, showing that hardness in one does not necessarily imply hardness in the other.
• Modesty: The author explicitly states that their results are relative to an oracle. They acknowledge that proving oracle-less separations remains an open and difficult problem in quantum complexity theory. They do not claim to have solved the separation for all distributions unconditionally, but rather to have made significant progress by isolating the power of quantum examples in a rigorous theoretical framework.

Conclusion
By leveraging one-way permutations and the properties of Simon's problem under noise (pseudoperiods), the author establishes that quantum examples provide a strictly stronger resource than classical examples for certain distribution generation tasks relative to an oracle. This result advances the understanding of quantum learning theory by isolating the advantage of quantum data access from the advantage of quantum computation.