Analysis of the sample complexity for PAC-learning functions defined over quantum states

Technical Summary: Analysis of the Sample Complexity for PAC-Learning Functions Defined Over Quantum States

Problem Statement
The paper investigates the sample complexity of Probably Approximately Correct (PAC) learning in a specific quantum setting. Unlike previous quantum generalizations where examples are provided as superpositions of classical states ($|x\rangle|f(x)\rangle$), this work considers a model where concepts are functions acting directly on quantum states. In this framework, the instance space $\mathcal{X}$ consists of quantum states $|\psi\rangle$ in a Hilbert space $\mathcal{H}$, and the learner receives pairs $(|\phi\rangle, c(|\phi\rangle))$, where $|\phi\rangle$ is drawn from an unknown distribution $D$ and $c$ is an unknown concept. The objective is to output a hypothesis $h$ such that the error $\text{dist}_D(h, c)$ is at most $\epsilon$ with probability $1-\delta$.

The central question addressed is whether the VC-dimension ($d$), which uniquely characterizes sample complexity in classical PAC learning, remains sufficient to characterize sample complexity in this quantum setting.

Methodology and Framework
The authors adopt the standard PAC learning definitions adapted for quantum inputs. They analyze the relationship between the sample complexity $t_{Q,C}(\epsilon, \delta)$ and the geometric properties of the concept class and the underlying state space.

Key methodological tools include:

1. Opposite Pairs: The introduction of "opposite pairs" of quantum states $\{|\psi\rangle, |\psi'\rangle\}$ relative to a concept class, where two concepts $c, c'$ exist such that $c(|\psi\rangle)=c'(|\psi'\rangle)=1$ and $c(|\psi'\rangle)=c'(|\psi\rangle)=0$.
2. Quantum Chernoff Distance: The use of the quantum Chernoff distance, $C_Q(\sigma, \rho) = -\ln \min_{s \in [0,1]} \text{Tr}(\sigma^s \rho^{1-s})$, to quantify the distinguishability of induced density matrices derived from the learning distribution.
3. Density Matrix Analysis: The construction of induced density matrices $\sigma^c_D = \mathbb{E}_{|\psi\rangle \sim D} [|\psi\rangle\langle\psi| \otimes |c(|\psi\rangle)\rangle\langle c(|\psi\rangle)|]$ to analyze the information available to the learner.
4. Linear Independence: The analysis of scenarios where the states in the domain are linearly independent, utilizing the Gram matrix $G$ of the states.

Key Contributions and Results

1. Insufficiency of VC-Dimension
The paper demonstrates that the VC-dimension alone is insufficient to characterize the sample complexity in this quantum setting.

• Proposition 1: If a concept class contains an opposite pair of states, the sample complexity is lower bounded by a term involving $F$, the supremum of the squared overlap $|\langle \psi | \psi' \rangle|^2$ over all opposite pairs. Specifically, if $F=1$ (implying the existence of opposite pairs with arbitrarily high overlap), the concept class is not PAC-learnable, even if the VC-dimension is finite.
• Proposition 3: The authors provide a counterexample (a concept class over four states $\{|0\rangle, |1\rangle, |+\rangle, |-\rangle\}$) where both the VC-dimension and $-\ln F$ are finite, yet the class is unlearnable. This proves that the pair $(d, F)$ is also insufficient to fully characterize learnability.

2. Refined Lower Bound via $\Lambda_C(\alpha)$
To address the limitations of the previous bounds, the authors introduce a new function $\Lambda_C(\alpha)$ based on the quantum Chernoff distance between induced density matrices of different concepts under distributions that are close in total variation distance.

• Theorem 1: The sample complexity is lower bounded by:
  $$t_{Q,C}(\epsilon, \delta) \geq c_L \left( \frac{d}{\epsilon} + \ln\frac{1}{\delta} \left( \frac{1}{\epsilon} + \frac{1}{\Lambda_C(3\epsilon)} \right) \right)$$
  This bound captures cases where $\Lambda_C(\alpha) = 0$, correctly identifying unlearnable classes. The paper shows that $\Lambda_C(\alpha)$ cannot be characterized solely by a constant like $B_C$ (derived from opposite density matrices), as the rate of change of $\Lambda_C(\alpha)$ also impacts complexity.

3. Upper Bound for Linearly Independent States
The authors establish an upper bound for the specific case where the states in the domain are linearly independent.

• Theorem 2: If the domain states $\{|\psi_i\rangle\}$ are linearly independent, the concept class is PAC-learnable with sample complexity:
  $$t_{Q,C}(\epsilon, \delta) \leq c_U \left( \frac{d + \ln(1/\delta)}{\epsilon \lambda_{\min}(G)} \right)$$
  where $\lambda_{\min}(G)$ is the minimum eigenvalue of the Gram matrix of the states. This result recovers the classical bound when states are orthogonal ($\lambda_{\min}(G)=1$) and shows that the complexity scales inversely with the linear independence of the states.

4. Analysis of Multi-Copy Examples
The paper examines a variant where the learner receives $k$ copies of the state, $(|\phi\rangle^{\otimes k}, c(|\phi\rangle))$.

• Proposition 8: If the domain is finite and $k$ is chosen sufficiently large (dependent on the domain size and overlaps), the states become linearly independent, and the sample complexity matches the classical bound.
• Proposition 9: Crucially, even if $k$ is allowed to depend on $\epsilon$ and $\delta$, there exist concept classes with finite VC-dimension that remain unlearnable. This occurs when the distribution is concentrated on boundaries where the overlap between opposite pairs approaches 1, rendering finite copies insufficient to distinguish concepts.

Significance and Claims
The paper claims that the transition from classical to quantum PAC learning, where examples are quantum states rather than classical labels, fundamentally alters the relationship between VC-dimension and sample complexity.

• The VC-dimension is no longer a complete descriptor; geometric properties of the state space (specifically overlaps and linear independence) play a critical role.
• The function $\Lambda_C(\alpha)$ is introduced as a necessary parameter to characterize learnability, capturing the indistinguishability of concepts under specific distributions.
• The results highlight a strict separation between settings where classical descriptions are available versus where only quantum states are provided: finite VC-dimension guarantees learnability in the former but not necessarily in the latter, regardless of the number of copies provided (unless the number of copies scales to infinity or the domain is finite with specific constraints).

The work concludes that while classical bounds can be recovered under specific conditions (linear independence), a general characterization of quantum sample complexity requires new metrics beyond the VC-dimension.