Private learning implies quantum stability

Yihui Quek, Srinivasan A, John SmolinNeurIPS 2021 · OpenReview

Introduction

Learning an unknown $n$-qubit quantum state $\rho$ is a fundamental challenge in quantum computing. Information-theoretically, full quantum tomography requires an exponential number of copies of $\rho$ to accurately estimate its entries. To circumvent this exponential bottleneck, researchers have proposed various "weaker" learning models inspired by classical computational learning theory. These include the Probably Approximately Correct (PAC) model of learning states, shadow tomography for learning specific properties or "shadows" of a state, differentially private (DP) learning models, and online learning models.

Until recently, the relationships between these distinct quantum learning models remained unclear. This paper provides a theoretical "Grand Unification" of these approaches, proving a sequence of information-theoretic implications from differentially private PAC learning to online learning, and ultimately to a novel concept introduced as "quantum stability."

Problem Statement: Navigating Quantum Learning Models

Because full tomography is often intractable, the community relies on alternative frameworks to extract useful information from quantum states:

  • PAC Learning: Focuses on learning a state well enough to predict future measurement outcomes with high probability.
  • Online Learning: Involves learning a state sequentially, where an adversary dictates the measurements step-by-step.
  • Differentially Private (DP) Learning: Requires learning a state such that the output hypothesis does not reveal too much information about any single training example.

This work seeks to establish a unified framework to determine which of these learning tasks are information-theoretically equivalent and which are strictly harder than others in the quantum domain.

Methodology

This research is purely theoretical, leveraging tools from computational learning theory and quantum information theory. The authors introduce several key technical innovations to bridge these models:

  1. Robust Standard Optimal Algorithm (RSOA): The authors develop a quantum generalization of the classical "Standard Optimal Algorithm." While the classical version assumes perfect Boolean labels, RSOA is designed to be "robust." It handles real-valued, imprecise feedback, a critical requirement since quantum measurements are inherently probabilistic and subject to noise.
  2. Sequential Fat-Shattering Dimension: This combinatorial parameter is utilized to measure the complexity of a class of quantum states. It serves as a theoretical yardstick to bound the number of samples required for learning.
  3. Quantum Stability: The authors introduce stability as a conceptual bridge. An algorithm is considered "stable" if, given a set of noisy examples, it consistently outputs a hypothesis state that is "close" to the target state with high probability.

Key Findings and Implications

The core contribution of the paper is establishing a definitive hierarchy and equivalence among these learning models.

Chain of implications between quantum learning models
  • The Chain of Implications: As illustrated above, the authors demonstrate a clear path of implications: Pure DP PAC Learning $\rightarrow$ One-way Communication $\rightarrow$ Online Learning $\rightarrow$ Quantum Stability. Consequently, if a class of states can be learned in the Pure DP PAC model, it can be learned in all subsequent models.
  • The "No-Go" Result: In classical machine learning with Boolean functions, stability and differential privacy are fundamentally equivalent. A major finding of this paper is that this equivalence fails for quantum states. Because quantum measurements yield real-valued outcomes (probabilities between 0 and 1), one cannot generically convert a stable quantum learner into a private one without a massive, domain-dependent increase in sample complexity (denoted by the "no-go" dotted line in the figure).
  • Resolving Aaronson's Question: Previous work by Scott Aaronson established that a "mistake-bounded" online learner for quantum states must exist, but did not provide an explicit algorithm. This paper resolves that open question by providing the RSOA.
  • Shadow Tomography Speedup: The authors demonstrate that the sample complexity of shadow tomography can be refined. Instead of depending strictly on the number of qubits ($n$), it can be bounded by the sequential fat-shattering dimension of the specific class of states being investigated.
  • Noise Tolerance: The paper provides the first bounds for learning "continuous-variable" states and states corrupted by depolarizing or Pauli noise, directly linking the complexity of learning to the classical capacity of the underlying noise channel.

Limitations and Future Work

While this paper establishes foundational links between quantum learning models, it operates primarily in the information-theoretic regime. The bounds prove how many samples are needed, but the proposed algorithms (like RSOA) may still require exponential computational time to execute on a classical computer.

Furthermore, the current framework assumes the "realizable" setting, where the unknown state is guaranteed to belong to a known concept class. A critical next step is extending these results to the "agnostic" setting, where the target state might be arbitrary or subject to adversarial noise. Finally, while a general "no-go" result was proven for moving from stability to privacy, future work may uncover more efficient bridges for specific, highly structured classes of quantum states.

Summary updated

Abstract

Learning an unknown n-qubit quantum state rho is a fundamental challenge in quantum computing. Information-theoretically, it is known that tomography requires exponential in n many copies of rho to estimate its entries. Motivated by learning theory, Aaronson et al. introduced many (weaker) learning models: the PAC model of learning states (Proceedings of Royal Society A'07), shadow tomography (STOC'18) for learning ``shadows" of a state, a model that also requires learners to be differentially private (STOC'19) and the online model of learning states (NeurIPS'18). In these models it was shown that an unknown state can be learned ``approximately" using linear in n many copies of rho. But is there any relationship between these models? In this paper we prove a sequence of (information-theoretic) implications from differentially-private PAC learning to online learning and then to quantum stability. Our main result generalizes the recent work of Bun, Livni and Moran (Journal of the ACM'21) who showed that finite Littlestone dimension (of Boolean-valued concept classes) implies PAC learnability in the (approximate) differentially private (DP) setting. We first consider their work in the real-valued setting and further extend to their techniques to the setting of learning quantum states. Key to our results is our generic quantum online learner, Robust Standard Optimal Algorithm (RSOA), which is robust to adversarial imprecision. We then show information-theoretic implications between DP learning quantum states in the PAC model, learnability of quantum states in the one-way communication model, online learning of quantum states, quantum stability (which is our conceptual contribution), various combinatorial parameters and give further applications to gentle shadow tomography and noisy quantum state learning.
BibTeX
@inproceedings{quek2021private,
  author = {Yihui Quek and Srinivasan A and John Smolin},
  title = {{Private learning implies quantum stability}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=9XAxGtK5cdN},
}
Figure