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

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

arXiv:2012.15498Dec 31, 20200 citations

An Online Algorithm for Maximum-Likelihood Quantum State Tomography.

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

Dec 31, 20202 citations

Diluted maximum-likelihood algorithm for quantum tomography

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

arXiv:quant-ph/0611244Physical Review AApr 18, 2007187 citations

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

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

arXiv:2211.12880Nov 23, 20221 citation

A scalable maximum likelihood method for quantum state tomography

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

arXiv:1308.2395New Journal of PhysicsDec 4, 201360 citations

Superfast maximum-likelihood reconstruction for quantum tomography

Jiangwei Shang, Zhengyun Zhang, Hui Khoon Ng

arXiv:1609.07881Physical Review AJun 27, 2017108 citations

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

arXiv HTML PDF

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.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.15498Dec 31, 20200 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).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, 20202 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.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/0611244Physical Review AApr 18, 2007187 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.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.12880Nov 23, 20221 citation

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.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.2395New Journal of PhysicsDec 4, 201360 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.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.07881Physical Review AJun 27, 2017108 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 )

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

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

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

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.

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.