Regret Lower Bounds for Online Learning of Quantum States: Uncertainty and New Algorithms

The Importance of Online Learning of Quantum States

Online learning frameworks have been extensively studied in classical machine learning, but extending them to the quantum domain presents unique challenges. A recent paper focuses on online learning of quantum states under logarithmic loss, which is a quantum generalization of classical online portfolio selection. The core of the problem is that the learner selects a quantum state each round, then observes measurement outcomes and incurs logarithmic loss. This framework is directly related to quantum state tomography—the critical task of estimating an unknown quantum state from measurement results. The paper establishes regret lower bounds for the first time, revealing that the polynomial dependence on dimension of the regret rates of the exponential weights algorithm and the algorithm of Tseng et al. (2025) is already optimal. This theoretical result not only deepens our understanding of the limits of quantum online learning, but also gives rise to two practical algorithms: a sample-optimal quantum state tomography algorithm and a method for constructing confidence sequences for matrix means.

Quantum state tomography is a fundamental task in quantum information science: by repeatedly preparing the same unknown quantum state and performing multiple measurements, one infers the density matrix description of that state from the statistical distribution of measurement outcomes. Since quantum measurement inevitably disturbs the quantum state, and a single measurement can only extract partial information, tomography typically requires a large number of copies to achieve a given precision. In a system of dimension d, a complete description of the density matrix requires d²−1 real parameters, and the sample size required by traditional methods often grows polynomially or even worse with d. Therefore, how to minimize the number of measurements while guaranteeing precision—that is, reducing sample complexity—has always been a core issue in quantum state tomography. The sample-optimal algorithm proposed in this paper is precisely in this context: it transfers regret analysis techniques from online learning to the tomography task, thereby requiring only polylogarithmic factors more samples than the theoretical lower bound.

Regret Lower Bounds and Algorithmic Optimality

The core contribution of the paper is proving a regret lower bound for any algorithm in online learning of quantum states. Specifically, the authors show that for a quantum system of dimension (d), the regret grows at least at a rate of (\Omega(\sqrt{T})), where (T) is the number of rounds. More importantly, this lower bound matches the upper bounds of existing algorithms (such as the exponential weights algorithm and the algorithm of Tseng et al. 2025) in terms of polynomial dependence on dimension (d). This means that these algorithms are already optimal in their dependence on dimension and cannot be further improved. This conclusion is of foundational significance for the theory of quantum machine learning, because it delineates the intrinsic difficulty boundary of the quantum online learning problem.

"Regret" in online learning is a measure of the cumulative loss gap between an algorithm and the best strategy in hindsight. Specifically, if the learner selects a strategy each round and incurs loss, regret is defined as the difference between the learner's cumulative loss and the smallest cumulative loss among all possible fixed strategies. A good online learning algorithm should make regret grow sublinearly with the number of rounds T, for example O(√T) or O(log T), which means that the average per-round loss approaches the optimum. The Ω(√T) lower bound proved in this paper shows that for online learning of quantum states, no algorithm can have regret below this rate. In addition, the polynomial dependence of the lower bound on dimension d matches the upper bounds of existing algorithms such as the exponential weights algorithm, indicating that these algorithms can no longer be improved in the order of dependence on d, that is, they achieve minimax optimality.

Sample-Optimal Algorithm for Quantum State Tomography

Based on the proof techniques for the regret lower bound, the authors design a new quantum state tomography algorithm. This algorithm is optimal in sample size, exceeding the theoretical lower bound by only polylogarithmic factors. Traditional quantum state tomography methods often require a large number of measurements to achieve a given precision, whereas the new algorithm significantly reduces sample complexity, especially in high-dimensional systems. The paper proves its sample efficiency through theoretical analysis, but does not conduct large-scale numerical experiments. This progress has practical value for state estimation tasks in quantum computing and quantum communication, because reducing the number of measurements can lower experimental cost and time.

Construction of Confidence Sequences for Matrix Means

The second application of the paper is constructing confidence sequences for the means of matrix-valued random variables. Confidence sequences are a powerful tool in classical statistics for sequential analysis, but extending them to the matrix case presents challenges. The authors propose a new algorithm that can dynamically provide confidence intervals for matrix means without relying on a fixed sample size. Numerical experiments show that the algorithm is competitive with existing methods. For example, in simulated data, the width of the confidence sequence given by the new algorithm is comparable to methods based on specially designed matrix concentration inequalities, but it is more computationally efficient. This result expands the application prospects of confidence sequences in quantum information and high-dimensional statistics.

A confidence sequence is a generalization of classical confidence intervals in sequential analysis: it is a sequence of intervals updated over time such that, at any time (rather than only at a fixed sample size), the probability that the true parameter lies within the interval is at least 1−α. This property makes it particularly suitable for scenarios where data arrive gradually, such as online learning, multi-armed bandits, or quantum measurement. Extending confidence sequences from scalars to the means of matrix-valued random variables means that one needs to handle concentration inequalities under matrix norms and guarantee consistency at arbitrary stopping times. The construction method proposed in this paper does not rely on a fixed sample size, can dynamically provide confidence intervals for matrix means, and performs comparably to methods based on specially designed matrix concentration inequalities in numerical experiments, while being more computationally efficient.

Open Problems and Future Directions

Despite the important progress made in the paper, several open problems remain. First, it is still unclear whether the regret lower bound applies to other loss functions, such as squared loss. Second, although the quantum state tomography algorithm is sample-optimal, whether its computational complexity is polynomial time remains to be analyzed. In addition, the construction of confidence sequences for matrix means depends on a specific matrix norm, and whether it can be generalized to more general norms is worth exploring. The authors suggest that future work could study tighter constant factors and extend the method to continuous-variable quantum systems. These directions will push the theory of quantum online learning toward practical application.

One-line Summary

The paper establishes the first regret lower bound for online learning of quantum states, proves that existing algorithms are optimal in dimension dependence, and gives rise to a sample-optimal tomography algorithm and confidence sequences for matrix means.

Paragraph Summary

This paper studies online learning of quantum states under logarithmic loss. The problem is a quantum generalization of classical online portfolio selection, in which the learner selects a quantum state each round, observes measurement outcomes, and incurs logarithmic loss. The paper establishes the first regret lower bound, proving that for a quantum system of dimension d, the regret grows at least as Ω(√T), and that this lower bound matches the upper bounds of the exponential weights algorithm and the algorithm of Tseng et al. (2025) in polynomial dependence on dimension, showing that these algorithms are already optimal. Based on the lower-bound proof techniques, the authors further propose a sample-optimal quantum state tomography algorithm whose sample size exceeds the theoretical lower bound by only polylogarithmic factors; they also construct confidence sequences for the means of matrix-valued random variables, with numerical experiments showing competitive performance comparable to existing methods and greater computational efficiency. The paper also discusses open problems such as other loss functions, computational complexity, and norm generalizations.