Online learning is a framework for interfacing with environments whose structure is revealed through interactions; quantum information theory is a means of representing data and its processing consistent with modern understanding of physics. Their union is symbiotic---sequential processing is light on precious quantum resources, and quantum algorithms can surpass known bounds of classical algorithms---their combination being an area of independent interest. This thesis aims to exemplify the above point via five case studies on tomography, change detection, and function evaluation. In the process of deriving efficient tomography procedures, prior work has shown that quantum states can be learned in online adversarial environments. We extend this notion to subsets of positive semidefinite operators, including general quantum objects such as states, measurements, channels, strategies, co-strategies, and Gram matrices. We tailor a regularized follow-the-leader algorithm and achieve sublinear regret. As a byproduct, we show a generalization of Pinsker's inequality that accounts for differences in trace, its proof method more broadly applicable to general divergences. We further extend online learnability to objects in arbitrary physical theories. We derive mappings between Euclidean Jordan algebras and generalized probabilistic theories, using methods for the former to show that states in the latter are learnable. Specifically, we develop a projective version of the symmetric cone multiplicative weights update algorithm that achieves sublinear regret when learning states of generalized probabilistic theories. We consider the task of detecting changes in sequences of unknown quantum states with a constraint of no false positives, developing efficient and optimal online quantum algorithms. These include online algorithms with small amounts of quantum memory based on the swap test, and optimal algorithms projecting onto the symmetric subspace. We find circuit constructions for these algorithms, analyze their complexity, and show their equivalence under certain memory limitations. The proposed algorithms are applicable to quality control and anomaly detection in quantum devices, and may be of independent interest for identity testing and optimal cloning. We elaborate on the quality control aspect of changepoint methods by developing procedures for aiding the calibration of near-term quantum devices. These consist of algorithms for certification and changepoint detection in Hamiltonian dynamics, which enable continuous monitoring and trigger recalibration procedures. Using a cumulative sum procedure, we attain an asymptotically-optimal scaling of the average times to detection versus false positive, dependent primarily on Hamiltonian norm bounds. Lastly, we quantify the effect of memory limits on Boolean function evaluation of quantum sequences---a task applicable to distributed sensing and quantum reading of classical memories, among others. We show that minimum-error function evaluation in the memoryless regime is equivalent to the so-called pretty good measurement and hence shares its performance guarantee. Additionally, we characterize the precise set of functions on which this strategy performs optimally---affine functions. The above studies reveal insights about learnability as a universal property and the tradeoffs between performance and resource requirements in online settings, informing the choice of quantum settings best-suited for online learning. We conclude by summarizing these takeaways, along with listing remaining open questions.
Online learning is a framework for interfacing with environments whose structure is revealed through interactions; quantum information theory is a means of representing data and its processing consistent with modern understanding of physics. Their union is symbiotic---sequential processing is light on precious quantum resources, and quantum algorithms can surpass known bounds of classical algorithms---their combination being an area of independent interest. This thesis aims to exemplify the above point via five case studies on tomography, change detection, and function evaluation. In the process of deriving efficient tomography procedures, prior work has shown that quantum states can be learned in online adversarial environments. We extend this notion to subsets of positive semidefinite operators, including general quantum objects such as states, measurements, channels, strategies, co-strategies, and Gram matrices. We tailor a regularized follow-the-leader algorithm and achieve sublinear regret. As a byproduct, we show a generalization of Pinsker's inequality that accounts for differences in trace, its proof method more broadly applicable to general divergences. We further extend online learnability to objects in arbitrary physical theories. We derive mappings between Euclidean Jordan algebras and generalized probabilistic theories, using methods for the former to show that states in the latter are learnable. Specifically, we develop a projective version of the symmetric cone multiplicative weights update algorithm that achieves sublinear regret when learning states of generalized probabilistic theories. We consider the task of detecting changes in sequences of unknown quantum states with a constraint of no false positives, developing efficient and optimal online quantum algorithms. These include online algorithms with small amounts of quantum memory based on the swap test, and optimal algorithms projecting onto the symmetric subspace. We find circuit constructions for these algorithms, analyze their complexity, and show their equivalence under certain memory limitations. The proposed algorithms are applicable to quality control and anomaly detection in quantum devices, and may be of independent interest for identity testing and optimal cloning. We elaborate on the quality control aspect of changepoint methods by developing procedures for aiding the calibration of near-term quantum devices. These consist of algorithms for certification and changepoint detection in Hamiltonian dynamics, which enable continuous monitoring and trigger recalibration procedures. Using a cumulative sum procedure, we attain an asymptotically-optimal scaling of the average times to detection versus false positive, dependent primarily on Hamiltonian norm bounds. Lastly, we quantify the effect of memory limits on Boolean function evaluation of quantum sequences---a task applicable to distributed sensing and quantum reading of classical memories, among others. We show that minimum-error function evaluation in the memoryless regime is equivalent to the so-called pretty good measurement and hence shares its performance guarantee. Additionally, we characterize the precise set of functions on which this strategy performs optimally---affine functions. The above studies reveal insights about learnability as a universal property and the tradeoffs between performance and resource requirements in online settings, informing the choice of quantum settings best-suited for online learning. We conclude by summarizing these takeaways, along with listing remaining open questions.
Among recent insights into learning quantum states, online learning and shadow tomography procedures are notable for their ability to accurately predict expectation values even of adaptively chosen observables. In contrast to the state case, quantum process learning tasks with a similarly adaptive nature have received little attention. In this work, we investigate online learning tasks for quantum processes. Whereas online learning is infeasible for general quantum channels, we show that channels of bounded gate complexity as well as Pauli channels can be online learned in the regret and mistake-bounded models of online learning. In fact, we can online learn probabilistic mixtures of any exponentially large set of known channels. We also provide a provably sample-efficient shadow tomography procedure for Pauli channels. Our results extend beyond quantum channels to non-Markovian multi-time processes, with favorable regret and mistake bounds, as well as a shadow tomography procedure. We complement our online learning upper bounds with mistake as well as computational lower bounds. On the technical side, we make use of the multiplicative weights update algorithm, classical adaptive data analysis, and Bell sampling, as well as tools from the theory of quantum combs for multi-time quantum processes. Our work initiates a study of online learning for classes of quantum channels and, more generally, non-Markovian quantum processes. Given the importance of online learning for state shadow tomography, this may serve as a step towards quantum channel variants of adaptive shadow tomography.
Abstract In many quantum tasks, there is an unknown quantum object that one wishes to learn. An online strategy for this task involves adaptively refining a hypothesis to reproduce such an object or its measurement statistics. A common evaluation metric for such a strategy is its regret, or roughly the accumulated errors in hypothesis statistics. We prove a sublinear regret bound for learning over general subsets of positive semidefinite matrices via the regularized-follow-the-leader algorithm and apply it to various settings where one wishes to learn quantum objects. For concrete applications, we present a sublinear regret bound for learning quantum states, effects, channels, interactive measurements, strategies, co-strategies, and the collection of inner products of pure states. Our bound applies to many other quantum objects with compact, convex representations. In proving our regret bound, we establish various matrix analysis results useful in quantum information theory. This includes a generalization of Pinsker’s inequality for arbitrary positive semidefinite operators with possibly different traces, which may be of independent interest and applicable to more general classes of divergences.
We study the problem of online learning of quantum states with logarithmic loss, which is a quantum generalization of online portfolio selection and has applications to quantum state tomography, the task of estimating an unknown quantum state from measurement outcomes. We first establish a regret lower bound, showing that the regret rates of Exponential Weights and the algorithm of Tseng et al. (2025) have optimal polynomial dependence on the dimension. Our analysis leads to two further results. First, our lower-bound proof leads to a quantum state tomography algorithm that is sample optimal up to polylogarithmic factors in the sample size. Second, we develop an algorithm for constructing confidence sequences for the mean of a matrix-valued random variable. A numerical experiment shows that the latter algorithm is competitive with existing methods.
As quantum computing progresses toward fault-tolerant architectures, the question of which computational tasks admit provable quantum advantages and which do not has become increasingly central. Learning theory, and in particular learning from quantum examples, provides one of the few settings in which unconditional quantum-classical separations can be established. In distribution-free (i.e., worst-case) PAC learning, existing results show that quantum examples provide no asymptotic advantage in sample complexity. In contrast, under the uniform distribution, unbounded quantum-classical separations are known for learning Fourier-sparse Boolean functions. Together, these results reveal a striking dichotomy. However, this understanding has largely been developed in the context of learning Boolean functions in the batch setting, leaving open how these phenomena extend more broadly. This thesis develops the theory of learning with quantum examples beyond the batch Boolean setting along three directions: multiclass learning, online learning, and smoothed learning. In the multiclass PAC setting, we establish upper and lower bounds on quantum sample complexity in both the realizable and agnostic regimes, finding that quantum examples continue to yield no distribution-independent separation from classical examples, with learning rates governed by the Natarajan dimension up to logarithmic factors in the label-space size. We next study online learning, where no standard framework for learning with quantum examples existed prior to this work. We provide such a model by lifting the classical online framework to one in which the adversary provides distributions over labeled examples, and then by encoding these distributions as quantum examples. We establish expected regret guarantees for binary and multiclass classification in both the realizable and agnostic settings. The central finding is that unrestricted adversarial power permits highly concentrated distributions that dequantize the learning problem. Motivated by this dequantization phenomenon, we develop a smoothed learning framework that constrains distributions to be smooth, interpolating between the concentrated-distribution regime, in which no quantum advantage exists, and the uniform-distribution regime, in which unbounded separations are known. For the class of Fourier-sparse Boolean functions, we establish the robustness of quantum Fourier sampling throughout a nontrivial near-uniform regime in the batch setting and observe that these guarantees extend naturally to the online setting. We further analyze several approaches to recovering the target function once its Fourier support has been identified and, based on these observations, formulate conjectures supporting the persistence of the unbounded quantum advantage throughout this regime. Together, these results paint a coherent picture of learning with quantum examples beyond the batch Boolean setting, showing that quantum-classical separations depend on the interplay between hypothesis class structure, distributional assumptions, and the degree of adversarial control permitted in the learning process.
The problem of efficient quantum state learning, also called shadow tomography, aims to comprehend an unknown d -dimensional quantum state through POVMs. Yet, these states are rarely static; they evolve due to factors such as measurements, environmental noise, or inherent Hamiltonian state transitions. This paper leverages techniques from adaptive online learning to keep pace with such state changes.The key metrics considered for learning in these mutable environments are enhanced notions of regret, specifically adaptive and dynamic regret. We present adaptive and dynamic regret bounds for online shadow tomography, which are polynomial in the number of qubits and sublinear in the number of measurements. To support our theoretical findings, we include numerical experiments that validate our proposed models.
Quantum state tomography is fundamental to quantum information processing but becomes infeasible at scale due to the exponential growth of the state space. Shadow tomography alleviates this challenge by focusing on predicting measurement outcomes rather than reconstructing the full state. Its online variant models adaptive and potentially adversarial measurement scenarios, where a learner sequentially predicts outcomes while competing with the best fixed quantum state in hindsight.
We show that exploiting additional structure in the measurements leads to significantly stronger regret guarantees. In particular, under the assumption that the adversarial measurements have bounded Frobenius norm, we analyze online mirror descent and derive optimal regret bounds that depend on intrinsic structural properties, such as rank or sparsity in the standard basis, rather than the dimension of the measurement operators. As a complementary result, we also show that, even in the setting where adversarial measurements are known to be sparse in the Pauli basis commonly used in variational quantum eigensolvers and near-term quantum error mitigation, the underlying regret bound for learning quantum states is the same as that obtained in the generic setting, where the adversarial measurements are not known to possess any particular structure.