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:1205.4043 · New Journal of Physics

Gradient-based stopping rules for maximum-likelihood quantum-state tomography

Scott Glancy, Emanuel H. Knill, Mark Girard

Published Sep 18, 2012• 14 citations
arXivHTMLPDF

Abstract

When performing maximum-likelihood quantum-state tomography, one must find the quantum state that maximizes the likelihood of the state given observed measurements on identically prepared systems. The optimization is usually performed with iterative algorithms. This paper provides a gradient-based upper bound on the ratio of the true maximum likelihood and the likelihood of the state of the current iteration, regardless of the particular algorithm used. This bound is useful for formulating stopping rules for halting iterations of maximization algorithms. We discuss such stopping rules in the context of determining confidence regions from log-likelihood differences when the differences are approximately chi-squared distributed.

DOI
10.1088/1367-2630/14/9/095017

Related papers

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

On spurious fixed points in iterative maximum likelihood reconstruction for quantum tomography

Florian Oberender

Maximum likelihood iteration is one of the most commonly used reconstruction algorithms in quantum tomography. The main appeal of the method is that it is easy to implement and that it converges reliably to a physically meaningful density matrix in practice. Contradicting these practical observations, we will show that convergence to a true solution is not guaranteed in general by constructing examples for spurious fixed points. To deal with this newly found problem, we then provide a criterion based on first order optimality conditions to check if the result of the algorithm is indeed the desired solution. Furthermore, we generalize the algorithm and show that it is equivalent to factorized gradient descent.

arXiv:2508.14549•Aug 20, 2025•0 citations

A scalable maximum likelihood method for quantum state tomography

T Baumgratz, A Nüßeler, M. Cramer +1 more

The principle of maximum likelihood reconstruction has proven to yield satisfactory results in the context of quantum state tomography for many-body systems of moderate system sizes. Until recently, however, quantum state tomography has been considered to be infeasible for systems consisting of a large number of subsystems due to the exponential growth of the Hilbert space dimension with the number of constituents. Several reconstruction schemes have been proposed since then to overcome the two main obstacles in quantum many-body tomography: experiment time and post-processing resources. Here we discuss one strategy to address these limitations for the maximum likelihood principle by adopting a particular state representation to merge a well established reconstruction algorithm maximizing the likelihood with techniques known from quantum many-body theory.

arXiv:1308.2395•New Journal of Physics•Dec 4, 2013•60 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 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

Superfast maximum-likelihood reconstruction for quantum tomography

Jiangwei Shang, Zhengyun Zhang, Hui Khoon Ng

Conventional methods for computing maximum-likelihood estimators (MLE) often converge slowly in practical situations, leading to a search for simplifying methods that rely on additional assumptions for their validity. In this work, we provide a fast and reliable algorithm for maximum-likelihood reconstruction that avoids this slow convergence. Our method utilizes the state-of-the-art convex optimization scheme, an accelerated projected-gradient method, that allows one to accommodate the quantum nature of the problem in a different way than in the standard methods. We demonstrate the power of our approach by comparing its performance with other algorithms for $n$-qubit state tomography. In particular, an eight-qubit situation that purportedly took weeks of computation time in 2005 can now be completed in under a minute for a single set of data, with far higher accuracy than previously possible. This refutes the common claim that MLE reconstruction is slow and reduces the need for alternative methods that often come with difficult-to-verify assumptions. In fact, recent methods assuming Gaussian statistics or relying on compressed sensing ideas are demonstrably inapplicable for the situation under consideration here. Our algorithm can be applied to general optimization problems over the quantum state space; the philosophy of projected gradients can further be utilized for optimization contexts with general constraints.

arXiv:1609.07881•Physical Review A•Jun 27, 2017•108 citations
When performing maximum-likelihood quantum-state tomography, one must find the quantum state that maximizes the likelihood of the state given observed measurements on identically prepared systems. The optimization is usually performed with iterative algorithms. This paper provides a gradient-based upper bound on the ratio of the true maximum likelihood and the likelihood of the state of the current iteration, regardless of the particular algorithm used. This bound is useful for formulating stopping rules for halting iterations of maximization algorithms. We discuss such stopping rules in the context of determining confidence regions from log-likelihood differences when the differences are approximately chi-squared distributed.
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 iteration is one of the most commonly used reconstruction algorithms in quantum tomography. The main appeal of the method is that it is easy to implement and that it converges reliably to a physically meaningful density matrix in practice. Contradicting these practical observations, we will show that convergence to a true solution is not guaranteed in general by constructing examples for spurious fixed points. To deal with this newly found problem, we then provide a criterion based on first order optimality conditions to check if the result of the algorithm is indeed the desired solution. Furthermore, we generalize the algorithm and show that it is equivalent to factorized gradient descent.
The principle of maximum likelihood reconstruction has proven to yield satisfactory results in the context of quantum state tomography for many-body systems of moderate system sizes. Until recently, however, quantum state tomography has been considered to be infeasible for systems consisting of a large number of subsystems due to the exponential growth of the Hilbert space dimension with the number of constituents. Several reconstruction schemes have been proposed since then to overcome the two main obstacles in quantum many-body tomography: experiment time and post-processing resources. Here we discuss one strategy to address these limitations for the maximum likelihood principle by adopting a particular state representation to merge a well established reconstruction algorithm maximizing the likelihood with techniques known from quantum many-body theory.
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.
Conventional methods for computing maximum-likelihood estimators (MLE) often converge slowly in practical situations, leading to a search for simplifying methods that rely on additional assumptions for their validity. In this work, we provide a fast and reliable algorithm for maximum-likelihood reconstruction that avoids this slow convergence. Our method utilizes the state-of-the-art convex optimization scheme, an accelerated projected-gradient method, that allows one to accommodate the quantum nature of the problem in a different way than in the standard methods. We demonstrate the power of our approach by comparing its performance with other algorithms for nnn-qubit state tomography. In particular, an eight-qubit situation that purportedly took weeks of computation time in 2005 can now be completed in under a minute for a single set of data, with far higher accuracy than previously possible. This refutes the common claim that MLE reconstruction is slow and reduces the need for alternative methods that often come with difficult-to-verify assumptions. In fact, recent methods assuming Gaussian statistics or relying on compressed sensing ideas are demonstrably inapplicable for the situation under consideration here. Our algorithm can be applied to general optimization problems over the quantum state space; the philosophy of projected gradients can further be utilized for optimization contexts with general constraints.