Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2311.02557

Fast Minimization of Expected Logarithmic Loss via Stochastic Dual Averaging

Tsai, Chung-En, Hao–Chung Cheng, Yen-Huan Li

Published Nov 5, 2023• 0 citations
arXivHTMLPDF

Abstract

Consider the problem of minimizing an expected logarithmic loss over either the probability simplex or the set of quantum density matrices. This problem includes tasks such as solving the Poisson inverse problem, computing the maximum-likelihood estimate for quantum state tomography, and approximating positive semi-definite matrix permanents with the currently tightest approximation ratio. Although the optimization problem is convex, standard iteration complexity guarantees for first-order methods do not directly apply due to the absence of Lipschitz continuity and smoothness in the loss function. In this work, we propose a stochastic first-order algorithm named $B$-sample stochastic dual averaging with the logarithmic barrier. For the Poisson inverse problem, our algorithm attains an $\varepsilon$-optimal solution in $\smash{\tilde{O}}(d^2/\varepsilon^2)$ time, matching the state of the art, where $d$ denotes the dimension. When computing the maximum-likelihood estimate for quantum state tomography, our algorithm yields an $\varepsilon$-optimal solution in $\smash{\tilde{O}}(d^3/\varepsilon^2)$ time. This improves on the time complexities of existing stochastic first-order methods by a factor of $d^{ω-2}$ and those of batch methods by a factor of $d^2$, where $ω$ denotes the matrix multiplication exponent. Numerical experiments demonstrate that empirically, our algorithm outperforms existing methods with explicit complexity guarantees.

DOI
10.48550/arxiv.2311.02557

Related papers

Faster Stochastic First-Order Method for Maximum-Likelihood Quantum State Tomography

Tsai, Chung-En, Hao–Chung Cheng, Yen-Huan Li

In maximum-likelihood quantum state tomography, both the sample size and dimension grow exponentially with the number of qubits. It is therefore desirable to develop a stochastic first-order method, just like stochastic gradient descent for modern machine learning, to compute the maximum-likelihood estimate. To this end, we propose an algorithm called stochastic mirror descent with the Burg entropy. Its expected optimization error vanishes at a $O ( \sqrt{ ( 1 / t ) d \log t } )$ rate, where $d$ and $t$ denote the dimension and number of iterations, respectively. Its per-iteration time complexity is $O ( d^3 )$, independent of the sample size. To the best of our knowledge, this is currently the computationally fastest stochastic first-order method for maximum-likelihood quantum state tomography.

arXiv:2211.12880•Nov 23, 2022•1 citation

Maximum-Likelihood Quantum State Tomography by Soft-Bayes

Lin, Chien-Ming, Yu-Ming Hsu, Yen-Huan Li

Quantum state tomography (QST), the task of estimating an unknown quantum state given measurement outcomes, is essential to building reliable quantum computing devices. Whereas computing the maximum-likelihood (ML) estimate corresponds to solving a finite-sum convex optimization problem, the objective function is not smooth nor Lipschitz, so most existing convex optimization methods lack sample complexity guarantees; moreover, both the sample size and dimension grow exponentially with the number of qubits in a QST experiment, so a desired algorithm should be highly scalable with respect to the dimension and sample size, just like stochastic gradient descent. In this paper, we propose a stochastic first-order algorithm that computes an $\varepsilon$-approximate ML estimate in $O( ( D \log D ) / \varepsilon ^ 2 )$ iterations with $O( D^3 )$ per-iteration time complexity, where $D$ denotes the dimension of the unknown quantum state and $\varepsilon$ denotes the optimization error. Our algorithm is an extension of Soft-Bayes to the quantum setup.

arXiv:2012.15498•Dec 31, 2020•0 citations

Quantum measurement tomography with mini-batch stochastic gradient descent

Akshay Gaikwad, Manuel Sebastian Torres, Anton Frisk Kockum

Drawing inspiration from gradient-descent methods developed for data processing in quantum state tomography [\href{https://iopscience.iop.org/article/10.1088/2058-9565/ae0baa}{Quantum Sci.~Technol.~\textbf{10} 045055 (2025)}] and quantum process tomography [\href{https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.130.150402}{Phys.~Rev.~Lett.~\textbf{130}, 150402 (2023)}], we introduce stochastic gradient descent (SGD) algorithms for fast quantum measurement tomography (QMT), applicable to both discrete- and continuous-variable quantum systems -- thus completing the tomography trio. A measurement device or detector in a quantum experiment is characterized by a set of positive operator-valued measure (POVM) elements; the goal of QMT is to estimate these operators from experimental data. To ensure physically valid (positive and complete) POVM reconstructions, we propose two distinct parameterization schemes within the SGD framework: one leveraging optimization on a Stiefel manifold and one based on Hermitian operator normalization via eigenvalue scaling. Within the SGD-QMT framework, we further investigate two loss functions: mean squared error, equivalent to L2 or Euclidean norm, and average negative log-likelihood, inspired by maximum likelihood estimation. We benchmark performance against state-of-the-art constrained convex optimization methods. Numerical simulations demonstrate that, compared to standard methods, our SGD-QMT algorithms offer significantly lower computational cost, superior reconstruction fidelity, and enhanced robustness to noise. We make a Python implementation of the SGD-QMT algorithms publicly available at \href{https://github.com/agtomo/SGD-QMT}{github.com/agtomo/SGD-QMT}.

quant-pharXiv:2511.15682•Nov 20, 2025•0 citations

Online Learning Quantum States with the Logarithmic Loss via VB-FTRL

Wei-Fu Tseng, Kai-Chun Chen, Zi-Hong Xiao +1 more

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.

arXiv:2311.04237•Nov 6, 2023•0 citations

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

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.

cs.LGCross-listedarXiv:2610.21273•Oct 16, 2026•0 citations

Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss

Hao Wang, Zhang, Chenyi, Tongyang Li

The problem of minimizing the maximum of $N$ convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring $O(Nε^{-2/3} + ε^{-8/3})$ queries to a first-order oracle to compute an $ε$-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of $N$ convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of $\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})$. On the other hand, we prove that quantum algorithms must take $\tildeΩ(\sqrt{N}ε^{-2/3})$ queries to a first order quantum oracle, showing that our dependence on $N$ is optimal up to poly-logarithmic factors.

arXiv:2402.12745•Feb 20, 2024•0 citations
Consider the problem of minimizing an expected logarithmic loss over either the probability simplex or the set of quantum density matrices. This problem includes tasks such as solving the Poisson inverse problem, computing the maximum-likelihood estimate for quantum state tomography, and approximating positive semi-definite matrix permanents with the currently tightest approximation ratio. Although the optimization problem is convex, standard iteration complexity guarantees for first-order methods do not directly apply due to the absence of Lipschitz continuity and smoothness in the loss function. In this work, we propose a stochastic first-order algorithm named BBB-sample stochastic dual averaging with the logarithmic barrier. For the Poisson inverse problem, our algorithm attains an ε\varepsilonε-optimal solution in O~(d2/ε2)\smash{\tilde{O}}(d^2/\varepsilon^2)O~(d2/ε2) time, matching the state of the art, where ddd denotes the dimension. When computing the maximum-likelihood estimate for quantum state tomography, our algorithm yields an ε\varepsilonε-optimal solution in O~(d3/ε2)\smash{\tilde{O}}(d^3/\varepsilon^2)O~(d3/ε2) time. This improves on the time complexities of existing stochastic first-order methods by a factor of dω−2d^{ω-2}dω−2 and those of batch methods by a factor of d2d^2d2, where ωωω denotes the matrix multiplication exponent. Numerical experiments demonstrate that empirically, our algorithm outperforms existing methods with explicit complexity guarantees.
In maximum-likelihood quantum state tomography, both the sample size and dimension grow exponentially with the number of qubits. It is therefore desirable to develop a stochastic first-order method, just like stochastic gradient descent for modern machine learning, to compute the maximum-likelihood estimate. To this end, we propose an algorithm called stochastic mirror descent with the Burg entropy. Its expected optimization error vanishes at a O((1/t)dlog⁡t)O ( \sqrt{ ( 1 / t ) d \log t } )O((1/t)dlogt​) rate, where ddd and ttt denote the dimension and number of iterations, respectively. Its per-iteration time complexity is O(d3)O ( d^3 )O(d3), independent of the sample size. To the best of our knowledge, this is currently the computationally fastest stochastic first-order method for maximum-likelihood quantum state tomography.
Quantum state tomography (QST), the task of estimating an unknown quantum state given measurement outcomes, is essential to building reliable quantum computing devices. Whereas computing the maximum-likelihood (ML) estimate corresponds to solving a finite-sum convex optimization problem, the objective function is not smooth nor Lipschitz, so most existing convex optimization methods lack sample complexity guarantees; moreover, both the sample size and dimension grow exponentially with the number of qubits in a QST experiment, so a desired algorithm should be highly scalable with respect to the dimension and sample size, just like stochastic gradient descent. In this paper, we propose a stochastic first-order algorithm that computes an ε\varepsilonε-approximate ML estimate in O((Dlog⁡D)/ε2)O( ( D \log D ) / \varepsilon ^ 2 )O((DlogD)/ε2) iterations with O(D3)O( D^3 )O(D3) per-iteration time complexity, where DDD denotes the dimension of the unknown quantum state and ε\varepsilonε denotes the optimization error. Our algorithm is an extension of Soft-Bayes to the quantum setup.
Drawing inspiration from gradient-descent methods developed for data processing in quantum state tomography [\href{https://iopscience.iop.org/article/10.1088/2058-9565/ae0baa}{Quantum Sci.~Technol.~\textbf{10} 045055 (2025)}] and quantum process tomography [\href{https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.130.150402}{Phys.~Rev.~Lett.~\textbf{130}, 150402 (2023)}], we introduce stochastic gradient descent (SGD) algorithms for fast quantum measurement tomography (QMT), applicable to both discrete- and continuous-variable quantum systems -- thus completing the tomography trio. A measurement device or detector in a quantum experiment is characterized by a set of positive operator-valued measure (POVM) elements; the goal of QMT is to estimate these operators from experimental data. To ensure physically valid (positive and complete) POVM reconstructions, we propose two distinct parameterization schemes within the SGD framework: one leveraging optimization on a Stiefel manifold and one based on Hermitian operator normalization via eigenvalue scaling. Within the SGD-QMT framework, we further investigate two loss functions: mean squared error, equivalent to L2 or Euclidean norm, and average negative log-likelihood, inspired by maximum likelihood estimation. We benchmark performance against state-of-the-art constrained convex optimization methods. Numerical simulations demonstrate that, compared to standard methods, our SGD-QMT algorithms offer significantly lower computational cost, superior reconstruction fidelity, and enhanced robustness to noise. We make a Python implementation of the SGD-QMT algorithms publicly available at \href{https://github.com/agtomo/SGD-QMT}{github.com/agtomo/SGD-QMT}.
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 ddd denote the dimension and TTT the number of rounds. The generalized algorithm achieves a regret rate of O(d2log⁡(d+T))O ( d^2 \log ( d + T ) )O(d2log(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(d2log⁡T)O ( d^2 \log T )O(d2logT), 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.
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.
The problem of minimizing the maximum of NNN convex, Lipschitz functions plays significant roles in optimization and machine learning. It has a series of results, with the most recent one requiring O(Nε−2/3+ε−8/3)O(Nε^{-2/3} + ε^{-8/3})O(Nε−2/3+ε−8/3) queries to a first-order oracle to compute an εεε-suboptimal point. On the other hand, quantum algorithms for optimization are rapidly advancing with speedups shown on many important optimization problems. In this paper, we conduct a systematic study for quantum algorithms and lower bounds for minimizing the maximum of NNN convex, Lipschitz functions. On one hand, we develop quantum algorithms with an improved complexity bound of O~(Nε−5/3+ε−8/3)\tilde{O}(\sqrt{N}ε^{-5/3} + ε^{-8/3})O~(N​ε−5/3+ε−8/3). On the other hand, we prove that quantum algorithms must take Ω~(Nε−2/3)\tildeΩ(\sqrt{N}ε^{-2/3})Ω~(N​ε−2/3) queries to a first order quantum oracle, showing that our dependence on NNN is optimal up to poly-logarithmic factors.