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:2110.00747

Maximum-Likelihood Quantum State Tomography by Cover's Method with Non-Asymptotic Analysis

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

Published Oct 2, 2021• 7 citations
arXivHTMLPDF

Abstract

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.].

DOI
10.48550/arxiv.2110.00747

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•8 citations

An Online Algorithm for Maximum-Likelihood Quantum State Tomography.

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

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).

•Dec 31, 2020•2 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•4 citations

Diluted maximum-likelihood algorithm for quantum tomography

Jaroslav Řeháček, Z. Hradil, Emanuel H. Knill +1 more

We propose a refined iterative likelihood-maximization algorithm for reconstructing a quantum state from a set of tomographic measurements. The algorithm is characterized by a very high convergence rate and features a simple adaptive procedure that ensures likelihood increase in every iteration and convergence to the maximum-likelihood state. We apply the algorithm to homodyne tomography of optical states and quantum tomography of entangled spin states of trapped ions and investigate its convergence properties.

arXiv:quant-ph/0611244•Physical Review A•Apr 18, 2007•194 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•66 citations

Quantum homodyne tomography with a priori constraints

Konrad Banaszek

I present an iterative algorithm for reconstructing the Wigner function from homodyne statistics. The proposed method, based on maximum-likelihood estimation, is capable of compensating for detection losses in a numerically stable way.

arXiv:quant-ph/9901064•Physical Review A•Jun 1, 1999•23 citations
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.].
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 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 D D-by-D D D density matrix. The per-iteration computational complexity of the algorithm is O(D3) O ( D ^ 3 ) O(D3), 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).
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 a refined iterative likelihood-maximization algorithm for reconstructing a quantum state from a set of tomographic measurements. The algorithm is characterized by a very high convergence rate and features a simple adaptive procedure that ensures likelihood increase in every iteration and convergence to the maximum-likelihood state. We apply the algorithm to homodyne tomography of optical states and quantum tomography of entangled spin states of trapped ions and investigate its convergence properties.
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.