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

An Online Algorithm for Maximum-Likelihood Quantum State Tomography.

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

Published Dec 31, 2020• 2 citations
OpenAlex

Abstract

We propose, to the best of our knowledge, the first online algorithm for maximum-likelihood quantum state tomography. Suppose the quantum state to be estimated corresponds to a \( D \)-by-\( D \) density matrix. The per-iteration computational complexity of the algorithm is \( O ( D ^ 3 ) \), independent of the data size. The expected numerical error of the algorithm is $O(\sqrt{ ( 1 / T ) D \log D })$, where $T$ denotes the number of iterations. The algorithm can be viewed as a quantum extension of Soft-Bayes, a recent algorithm for online portfolio selection (Orseau et al. Soft-Bayes: Prod for mixtures of experts with log-loss. \textit{Int. Conf. Algorithmic Learning Theory}. 2017).

Related papers

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

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

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 Cover's Method with Non-Asymptotic Analysis

Chien-Ming Lin, Hao–Chung Cheng, Yen-Huan Li

We propose an iterative algorithm that computes the maximum-likelihood estimate in quantum state tomography. The optimization error of the algorithm converges to zero at an $O ( ( 1 / k ) \log D )$ rate, where $k$ denotes the number of iterations and $D$ denotes the dimension of the quantum state. The per-iteration computational complexity of the algorithm is $O ( D ^ 3 + N D ^2 )$, where $N$ denotes the number of measurement outcomes. The algorithm can be considered as a parameter-free correction of the $R ρR$ method [A. I. Lvovsky. Iterative maximum-likelihood reconstruction in quantum homodyne tomography. \textit{J. Opt. B: Quantum Semiclass. Opt.} 2004] [G. Molina-Terriza et al. Triggered qutrits for quantum communication protocols. \textit{Phys. Rev. Lett.} 2004.].

arXiv:2110.00747•Oct 2, 2021•0 citations

Local solutions of maximum likelihood estimation in quantum state tomography

Douglas Soares Gonçalves, Márcia A. Gomes-Ruggiero, Carlile Lavor +2 more

Maximum likelihood estimation is one of the most used methods in quantum state tomography, where the aim is to reconstruct the density matrix of a physical system from measurement results. One strategy to deal with positivity and unit trace constraints is to parameterize the matrix to be reconstructed in order to ensure that it is physical. In this case, the negative log-likelihood function in terms of the parameters, may have several local minima. In various papers in the field, a source of errors in this process has been associated to the possibility that most of these local minima are not global, so that optimization methods could be trapped in the wrong minimum, leading to a wrong density matrix. Here we show that, for convex negative log-likelihood functions, all local minima of the unconstrained parameterized problem are global, thus any minimizer leads to the maximum likelihood estimation for the density matrix. We also discuss some practical sources of errors.

Quantum Information and Computation•Sep 1, 2012•9 citations

Local solutions of maximum likelihood estimation in quantum state tomography

Douglas Soares Gonçalves, Márcia A. Gomes-Ruggiero, Carlile Lavor +2 more

Maximum likelihood estimation is one of the most used methods in quantum state tomography, where the aim is to reconstruct the density matrix of a physical system from measurement results. One strategy to deal with positivity and unit trace constraints is to parameterize the matrix to be reconstructed in order to ensure that it is physical. In this case, the negative log-likelihood function in terms of the parameters, may have several local minima. In various papers in the field, a source of errors in this process has been associated to the possibility that most of these local minima are not global, so that optimization methods could be trapped in the wrong minimum, leading to a wrong density matrix. Here we show that, for convex negative log-likelihood functions, all local minima of the unconstrained parameterized problem are global, thus any minimizer leads to the maximum likelihood estimation for the density matrix. We also discuss some practical sources of errors.

Quantum Information and Computation•Sep 1, 2012•4 citations
We propose, to the best of our knowledge, the first online algorithm for maximum-likelihood quantum state tomography. Suppose the quantum state to be estimated corresponds to a ( D )-by-( D ) density matrix. The per-iteration computational complexity of the algorithm is ( O ( D ^ 3 ) ), independent of the data size. The expected numerical error of the algorithm is O((1/T)Dlog⁡D)O(\sqrt{ ( 1 / T ) D \log D })O((1/T)DlogD​), where TTT denotes the number of iterations. The algorithm can be viewed as a quantum extension of Soft-Bayes, a recent algorithm for online portfolio selection (Orseau et al. Soft-Bayes: Prod for mixtures of experts with log-loss. \textit{Int. Conf. Algorithmic Learning Theory}. 2017).
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.
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.
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.
We propose an iterative algorithm that computes the maximum-likelihood estimate in quantum state tomography. The optimization error of the algorithm converges to zero at an O((1/k)log⁡D)O ( ( 1 / k ) \log D )O((1/k)logD) rate, where kkk denotes the number of iterations and DDD denotes the dimension of the quantum state. The per-iteration computational complexity of the algorithm is O(D3+ND2)O ( D ^ 3 + N D ^2 )O(D3+ND2), where NNN denotes the number of measurement outcomes. The algorithm can be considered as a parameter-free correction of the RρRR ρRRρR method [A. I. Lvovsky. Iterative maximum-likelihood reconstruction in quantum homodyne tomography. \textit{J. Opt. B: Quantum Semiclass. Opt.} 2004] [G. Molina-Terriza et al. Triggered qutrits for quantum communication protocols. \textit{Phys. Rev. Lett.} 2004.].
Maximum likelihood estimation is one of the most used methods in quantum state tomography, where the aim is to reconstruct the density matrix of a physical system from measurement results. One strategy to deal with positivity and unit trace constraints is to parameterize the matrix to be reconstructed in order to ensure that it is physical. In this case, the negative log-likelihood function in terms of the parameters, may have several local minima. In various papers in the field, a source of errors in this process has been associated to the possibility that most of these local minima are not global, so that optimization methods could be trapped in the wrong minimum, leading to a wrong density matrix. Here we show that, for convex negative log-likelihood functions, all local minima of the unconstrained parameterized problem are global, thus any minimizer leads to the maximum likelihood estimation for the density matrix. We also discuss some practical sources of errors.
Maximum likelihood estimation is one of the most used methods in quantum state tomography, where the aim is to reconstruct the density matrix of a physical system from measurement results. One strategy to deal with positivity and unit trace constraints is to parameterize the matrix to be reconstructed in order to ensure that it is physical. In this case, the negative log-likelihood function in terms of the parameters, may have several local minima. In various papers in the field, a source of errors in this process has been associated to the possibility that most of these local minima are not global, so that optimization methods could be trapped in the wrong minimum, leading to a wrong density matrix. Here we show that, for convex negative log-likelihood functions, all local minima of the unconstrained parameterized problem are global, thus any minimizer leads to the maximum likelihood estimation for the density matrix. We also discuss some practical sources of errors.