Date of Award
Spring 2025
Language
English
Embargo Period
5-7-2026
Document Type
Master's Thesis
Degree Name
Master of Science (MS)
College/School/Department
Department of Computer Science
Program
Computer Science
First Advisor
Abram Magner
Keywords
Quantum Learning Theory, PAC Learning, Fat-Shattering Dimension, POVM Learning, Quantum Hypothesis Testing, Non-Separable Measurements
Subject Categories
Other Computer Sciences | Quantum Physics | Statistical Models | Statistical Theory | Theory and Algorithms
Abstract
This thesis investigates the problem of learning from quantum systems, where each example consists of a quantum state paired with a classical outcome. The task centers on choosing an effective measurement rule from a fixed set to enable accurate prediction of the classical outcome from the quantum state. A central focus lies in understanding whether joint measurement strategies that cannot be separated into local operations offer a real benefit in terms of the number of examples needed for successful learning. We examine conditions under which a non-separable measurement within a given hypothesis class achieves strictly better sample complexity bounds compared to other candidate measurements.
We analyze this problem in two key settings: quantum hypothesis testing and PAC learning. In hypothesis testing, non-separable measurements can provide exponential improvements in sample efficiency when distinguishing sufficiently distinct states. However, within the PAC framework, such exponential gains do not persist; instead in our observation, non-separable measurements yield at most polynomial advantages over separable strategies.
We also show that the learnability of quantum measurement classes depends on the trace-norm geometry of quantum states. When states are close under trace distance, no hypothesis class can achieve large fat-shattering. Further, we observe that the fat-shattering dimension is bounded by the trace-norm packing number. These results limit learning efficiency with quantum measurements over mixed states and clarify when quantum strategies offer true advantages.
We also discuss the limitations of our PAC model and conclude the thesis with future research directions.
License
This work is licensed under the University at Albany Standard Author Agreement.
Recommended Citation
Das, Arka Prabha, "Further Results on Learning Quantum Measurement Classes: Quantum PAC Model for POVM Hypothesis Classes" (2025). Electronic Theses & Dissertations (2024 - present). 219.
https://scholarsarchive.library.albany.edu/etd/219
Included in
Other Computer Sciences Commons, Quantum Physics Commons, Statistical Models Commons, Statistical Theory Commons, Theory and Algorithms Commons
