Quantum Online Learning

Abstract

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.