An agent monitors a complex environment, receiving one observation at each time step and eventually deciding how to label the resulting sequence. Does the sequence indicate an anomaly, and if so, of what type? Does it signal market instability, and to what degree? This is the setting of online multi-class classification: the input arrives sequentially, the full history is never available at once, and the agent must retain any past information relevant to the eventual decision. As the environment becomes more complex, the memory needed to track this information can grow rapidly without bound. Here, we introduce families of such multi-class classification games and show that any exact classical agent requires memory that grows without bound, whereas exact quantum agents can solve all tasks in the family with bounded memory. This separation is sharp: any classical agent using less than the required memory, under suitable input distributions, performs arbitrarily close to random guessing. Moreover, our quantum constructions are provably memory minimal, allowing us to derive the exact classical and quantum memory complexities to perform such tasks. In doing so, we establish an unbounded separation between classical and quantum memory cost for online multi-class classification.
An agent monitors a complex environment, receiving one observation at each time step and eventually deciding how to label the resulting sequence. Does the sequence indicate an anomaly, and if so, of what type? Does it signal market instability, and to what degree? This is the setting of online multi-class classification: the input arrives sequentially, the full history is never available at once, and the agent must retain any past information relevant to the eventual decision. As the environment becomes more complex, the memory needed to track this information can grow rapidly without bound. Here, we introduce families of such multi-class classification games and show that any exact classical agent requires memory that grows without bound, whereas exact quantum agents can solve all tasks in the family with bounded memory. This separation is sharp: any classical agent using less than the required memory, under suitable input distributions, performs arbitrarily close to random guessing. Moreover, our quantum constructions are provably memory minimal, allowing us to derive the exact classical and quantum memory complexities to perform such tasks. In doing so, we establish an unbounded separation between classical and quantum memory cost for online multi-class classification.
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.
Abstract We study the one-shot reconstruction of a quantum state when a single copy of the source is measured, the outcome is stored in a classical record of fixed finite dimension, and a state is prepared at the destination from the record. This acquisition-limited problem is distinguished from a visible benchmark in which the source label is available to the encoder. For a finite ensemble we derive finite-record bounds on the visible distortion in terms of the cumulative prior mass covered by the record and the optimal discrimination probability, identify the regimes in which they are exact, and solve the two-state visible problem at every record dimension. For pure-state ensembles, exact acquisition-limited reconstruction is possible if and only if the states are perfectly distinguishable, so nonorthogonal targets retain a positive error at every record dimension. For two equiprobable nonorthogonal pure states we derive the optimal trace-distance distortion within the reflection-symmetric two-outcome class in closed variational form and find that unrestricted numerical optimization with up to six outcomes attains the same value; the resulting symmetric value lies strictly below the guess-and-prepare, unambiguous-discrimination, fidelity-optimal, and Haar-random strategies and is realized by one classical bit and one feed-forward rotation. Every classical-record reconstruction is shown to be entanglement breaking, with a quantitative bound on the loss of entanglement with an inaccessible reference, and the record dimension is related to the spectral rank of an energy-constrained memory. These results quantify the separation between a finite classical description and the information obtainable from a single quantum system. MSC Classification: 81P15 , 81P17 , 81P45 , 81P47
Effective and efficient forecasting relies on identification of the relevant information contained in past observations-the predictive features-and isolating it from the rest. When the future of a process bears a strong dependence on its behavior far into the past, there are many such features to store, necessitating complex models with extensive memories. Here, we highlight a family of stochastic processes whose minimal classical models must devote unboundedly many bits to tracking the past. For this family, we identify quantum models of equal accuracy that can store all relevant information within a single two-dimensional quantum system (qubit). This represents the ultimate limit of quantum compression and highlights an immense practical advantage of quantum technologies for the forecasting and simulation of complex systems.
World models provide digital simulacra of the true world, allowing agents to be trained and tested before costly real-world deployment. At each time step, they receive an action and generate an observation and reward matching the statistics of the true world. In complex environments where present outcomes depend on events far in the past, this requires memory. One might expect that, by increasing memory, we can always build a model accurately enough to align the optimal agent policies of the real and virtual worlds. We show that this is false for classical world models, even when the true world itself is classical. We construct true worlds for which every finite classical model fails along the same possible trajectory: it either loses the ability to distinguish actions when the true world clearly prefers one, or repeatedly assigns the highest expected reward to suboptimal actions. Its expected-reward estimates also retain a nonvanishing average error. In contrast, each such true world admits a quantum world model using a single qutrit that reproduces it exactly: its reward estimates and preferred actions always match those of the true world, ensuring that the optimal policies of the real and virtual worlds remain perfectly aligned.
Quantum process tomography, the task of learning an unknown quantum channel from black-box access, is a central problem in quantum information. In this setting, protocols with quantum memory can coherently store and jointly process quantum information obtained from multiple channel uses, whereas protocols without quantum memory must measure after each use and retain only a classical transcript of the measurement outcomes. A fundamental open question is whether quantum memory provides a query-complexity advantage even when protocols without quantum memory may adapt their experiments based on all previous outcomes with unbounded classical computational power. In this work, we show that it does. We determine the optimal query complexity of quantum process tomography without quantum memory up to a constant factor to be Θ(din3dout3/ε2), where din and dout are the channel input and output dimensions, respectively, and ε is the target diamond-norm accuracy. More precisely, we prove that any incoherent protocol for this task, including adaptive protocols, requires Ω(din3dout3/ε2) queries, even when each channel use may be assisted by arbitrary fresh ancilla, and we present a non-adaptive, ancilla-free incoherent protocol achieving the matching upper bound O(din3dout3/ε2). Our results thereby generalize the optimal sample-complexity bounds for single-copy state tomography, recovered as the special case din=1. By contrast, coherent protocols with quantum memory achieve query complexity Θ(din2dout2/ε2). Hence, our results establish a rigorous learning separation between quantum process tomography with and without quantum memory.
Effective and efficient forecasting relies on identification of the relevant information contained in past observations -- the predictive features -- and isolating it from the rest. When the future of a process bears a strong dependence on its behaviour far into the past, there are many such features to store, necessitating complex models with extensive memories. Here, we highlight a family of stochastic processes whose minimal classical models must devote unboundedly many bits to tracking the past. For this family, we identify quantum models of equal accuracy that can store all relevant information within a single two-dimensional quantum system (qubit). This represents the ultimate limit of quantum compression and highlights an immense practical advantage of quantum technologies for the forecasting and simulation of complex systems.