New Bounds on Quantum Sample Complexity of Measurement Classes

Mohsen Heidari, Wojciech Szpankowski

Introduction: The Fragility of Quantum Data

In classical machine learning, data is robust. A single dataset can be copied, stored, and reused to train or validate an arbitrary number of models. However, in the quantum realm, data is inherently "fragile" due to two fundamental principles of quantum mechanics: the No-Cloning Theorem, which prevents the creation of identical copies of an unknown quantum state, and State Collapse, where the act of measurement destroys or alters the state being observed.

Historically, these constraints led to the belief that quantum learning might be exponentially less efficient than classical learning. Specifically, early theoretical bounds suggested that the "sample complexity"—the number of training examples required to learn a concept—might scale linearly with the number of possible predictors ($|C|$). In contrast, classical sample complexity typically scales logarithmically ($\log |C|$). This paper, authored by Mohsen Heidari and Wojciech Szpankowski, introduces a framework to bridge this gap, demonstrating that quantum learning can indeed achieve classical-like efficiency.

The Quantum Shadow Risk Minimization (QSRM) Framework

To overcome the destructive nature of quantum measurements, the authors propose the Quantum Shadow Risk Minimization (QSRM) algorithm. The core innovation lies in the use of "classical shadows." Instead of measuring a quantum sample against a specific hypothesis, the learner applies a random unitary transformation and then performs a standard measurement. This process generates a classical mathematical description—a "shadow"—that serves as an unbiased estimate of the original quantum state.

Schematic of the QSRM process: converting quantum states into classical shadows for parallel evaluation.

As shown in the figure above, once the quantum state $\rho_i$ is converted into a classical outcome $j_i$, it can be processed through various inverse channels ($\Gamma^{-1}$) to estimate the outcomes of multiple different measurements ($\mathcal{M}_k$) simultaneously. Because these shadows are classical data, they can be reused infinitely on a conventional computer to evaluate every predictor in a concept class.

Algorithm 1: The Quantum Shadow Risk Minimization (QSRM) procedure.

The QSRM algorithm (Algorithm 1) formalizes this by first generating $n$ training samples and their corresponding classical shadows. It then computes the empirical loss for each measurement $\mathcal{M}$ in the concept class $C^*$ and returns the predictor that minimizes this loss.

Theoretical Foundations: Convex Geometry and Shadow Norms

The efficiency of QSRM is rooted in the geometry of quantum measurements. The authors utilize the fact that the optimal predictor in a set of measurements must be an extreme point of the set's convex closure. By focusing the search on these extreme points ($C^*$), the algorithm can bound complexity more tightly than if it considered the entire model space.

Furthermore, the authors introduce the Shadow-Norm ($V_{C^*}$). This metric accounts for the "incompatibility" of quantum measurements—the degree to which different measurements cannot be performed simultaneously. The shadow-norm essentially quantifies the noise introduced during the shadow tomography process, allowing for a precise characterization of the sample complexity.

Key Results and Improved Bounds

The primary contribution of this work is a new upper bound for quantum sample complexity ($n_C$). The researchers prove that: $$n_C = O\left(\frac{V_{C^*}}{\epsilon^2} \log \frac{|C^*|}{\delta}\right)$$ where $\epsilon$ is the error tolerance and $\delta$ is the failure probability.

For measurement classes with bounded Hilbert-Schmidt norms, this bound simplifies to $O(\log |C^*|)$. This is a significant breakthrough, as it proves that for many important cases, quantum learning does not require exponentially more data than classical learning. The QSRM algorithm is also shown to be effective in agnostic learning scenarios, where the true underlying relationship might not perfectly match any model in the chosen concept class.

Discussion and Future Directions

While QSRM significantly reduces sample complexity, it introduces a trade-off in computational complexity. Searching through all extreme points in a very large or continuous concept class remains a significant classical optimization challenge. Additionally, the current proofs are limited to finite-dimensional Hilbert spaces, which are standard for current qubit-based quantum computers but leave infinite-dimensional systems as a subject for future research.

Ultimately, this work provides a crucial theoretical foundation for quantum machine learning, showing that the "fragility" of quantum data is not an insurmountable barrier to efficient learning. The quest for a true quantum analogue to the "Fundamental Theorem of Statistical Learning" continues, but QSRM marks a major step toward that goal.

Summary updated

BibTeX
@inproceedings{heidari2024new,
  author = {Mohsen Heidari and Wojciech Szpankowski},
  title = {{New Bounds on Quantum Sample Complexity of Measurement Classes}},
  booktitle = {ISIT},
  year = {2024},
  doi = {10.1109/isit57864.2024.10619538},
}
Figure