Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means

Yen-Huan Li; Wei-Fu Tseng

cs.LGOct 15, 2026

Regret Lower Bound for Online Learning of Quantum States with Logarithmic Loss, with Applications to Quantum State Tomography and Confidence Sequences for Matrix Means

Authors: Yen-Huan Li, Wei-Fu Tseng

Organizations: Department of Computer Science and Information Engineering, National Taiwan University · Department of Mathematics, National Taiwan University · Center for Quantum Science and Engineering, National Taiwan University

Abstract

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.

Figures & tables

Online Portfolio Selection		Online Learning of Quantum States
Algorithm	Regret Rate	Algorithm	Regret Rate
Universal Portfolios ( Cover, 1991 )	$O(d\log T)$	Exponential Weights ( Zimmert et al., 2022 )	$O(d^{2}\log T)$
VB-FTRL ( Jézéquel et al., 2026 )	$O(d\log(d + T))$	Q-VB-FTRL ( Tseng et al., 2025 )	$O(d^{2}\log(d + T))$
PAE+DONS ( Mhammedi and Rakhlin, 2022 )	$O(d^{2}\log^{5}T)$	No known quantum counterpart.
BISONS ( Zimmert et al., 2022 )	$O(d^{2}\log^{2}T)$	Schrödinger ’s BISONS ( Zimmert et al., 2022 )	$O(d^{3}\log^{2}T)$
Barrier subgradient method ( Nesterov, 2011 )	$\widetilde{O}(\sqrt{dT})$	Q-LB-OMD ( Tsai et al., 2023a )	$\widetilde{O}(\sqrt{dT})$

Table 1: Existing algorithms for online portfolio selection and online learning of quantum states with logarithmic loss (OLQS), together with their regret upper bounds. Rows group related online portfolio selection algorithms and their quantum counterparts. Here,

d

denotes the number of assets in online portfolio selection and the dimension of density matrices in OLQS, and

T

denotes the time horizon. The notation

\widetilde{O}

suppresses polylogarithmic factors in

d

and

T

. LB-FTRL and Q-LB-FTRL in the last row use linearized losses.

Figure 1: Comparison of the mean relative Hilbert–Schmidt volumes of confidence sequences for covariance matrix estimation. OLQS denotes our construction following the second claim of Corollary 4.6 . See Section 5 and Appendix D for details.

Quantum State Tomography

Quantum state tomography reconstructs unknown quantum states from measurement data, enabling characterization and verification of quantum systems.

See all 16 papers

Learning Pure Quantum States in Any Dimension (Almost) Without Regret
May 9, 2026Josep Lumbreras, Marco TomamichelQuantum State Tomography
Centre for Quantum Technologies, National University of Singapore, Singapore · 2Nanyang Quantum Hub, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore · Department of Electrical and Computer Engineering, National University of Singapore, Singapore
Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements
Sep 9, 2026Ashwin Nayak, Xingyu ZhouQuantum State Tomography Information-Theoretic Lower Bounds
Department of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo. · Department of Computer Science, University of British Columbia.
Tomography by Design: An Algebraic Approach to Low-Rank Quantum States
Feb 16, 2026Shakir Showkat Sofi, Charlotte Vermeylen, Lieven De LathauwerQuantum State Tomography Matrix Completion
Dept. Electrical Engineering (ESAT), KU Leuven, Kortrijk/Leuven, Belgium · Leuven.AI - KU Leuven institute for AI, B-3000, Leuven, Belgium · Dept. Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium

May 9, 2026J/K move · Enter open · S save

Learning Pure Quantum States in Any Dimension (Almost) Without Regret

Josep Lumbreras, Marco Tomamichel

Centre for Quantum Technologies, National University of Singapore, Singapore · 2Nanyang Quantum Hub, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore · Department of Electrical and Computer Engineering, National University of Singapore, Singapore

Quantum State Tomography

Open paper AskPDF arXiv

We extend quantum state tomography with minimal cumulative disturbance, first investigated in [arXiv:2406.18370], to arbitrary finite-dimensional pure states. A learner sequentially receives fresh copies of an unknown pure state, chooses a rank-one projector for each copy using the previous outcomes, and performs the corresponding two-outcome projective measurement. The goal is to learn the state while keeping the chosen projectors close to the unknown state in order to minimize disturbance. The qubit solution relies on the special geometry of the Bloch sphere and does not extend directly to qudits, where pure states form a curved manifold. We show that this obstruction can be overcome by working locally on the pure-state manifold. The algorithm proceeds in epochs. In each epoch, it fixes a current estimate, measures pairs of nearby rank-one projectors obtained by moving in opposite tangent directions, and takes differences of the corresponding outcomes. This gives an exact linear observation of the tangent component of the error. The resulting local linear models are combined with a robust variance-adaptive estimator and a hot-start regularization that transfers precision across epochs. For every unknown pure state in dimension

d

, after

T

measured copies, our protocol achieves cumulative regret

\mathcal{O}(d^3\log^2 T)

, and at each intermediate time

t\leq T

its current estimate has online infidelity

\mathcal{O}(d^3\log(T)/t)

. Hence, pure-state tomography with essentially no cumulative disturbance is not a peculiarity of qubits but a geometric phenomenon that persists for qudits.

Abstract

Quantum State Tomography

Explore similar work

Learning Pure Quantum States in Any Dimension (Almost) Without Regret

Optimal Low-Rank Quantum State Tomography with Bounded-Sample Joint Measurements

Tomography by Design: An Algebraic Approach to Low-Rank Quantum States