Maximum-Likelihood Quantum State Tomography by Soft-Bayes

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