Online Learning Quantum States with the Logarithmic Loss via VB-FTRL
This provides a computationally feasible algorithm for quantum state learning, addressing a bottleneck in quantum tomography and online learning, though it is incremental as it builds on prior work for classical settings.
The paper tackles the problem of online learning of quantum states with logarithmic loss, a quantum generalization of online portfolio selection, by generalizing the VB-FTRL algorithm to achieve a regret rate of O(d^2 log(d + T)), where d is dimension and T is rounds, with polynomial-time iterations via semidefinite programming.
Online learning of quantum states with the logarithmic loss (LL-OLQS) is a quantum generalization of online portfolio selection (OPS), a classic open problem in online learning for over three decades. This problem also emerges in designing stochastic optimization algorithms for maximum-likelihood quantum state tomography. Recently, Jezequel et al. (arXiv:2209.13932) proposed the VB-FTRL algorithm, the first regret-optimal algorithm for OPS with moderate computational complexity. In this paper, we generalize VB-FTRL for LL-OLQS. Let $d$ denote the dimension and $T$ the number of rounds. The generalized algorithm achieves a regret rate of $O ( d^2 \log ( d + T ) )$ for LL-OLQS. Each iteration of the algorithm consists of solving a semidefinite program that can be implemented in polynomial time by, for example, cutting-plane methods. For comparison, the best-known regret rate for LL-OLQS is currently $O ( d^2 \log T )$, achieved by an exponential weight method. However, no explicit implementation is available for the exponential weight method for LL-OLQS. To facilitate the generalization, we introduce the notion of VB-convexity. VB-convexity is a sufficient condition for the volumetric barrier associated with any function to be convex and is of independent interest.