Maximum-Likelihood Quantum State Tomography by Soft-Bayes
This work addresses the scalability challenge in quantum computing for building reliable devices, offering an incremental improvement by extending an existing method to the quantum domain.
The paper tackles the problem of maximum-likelihood quantum state tomography, which involves estimating unknown quantum states from measurements, by proposing a stochastic first-order algorithm that computes an ε-approximate estimate in O((D log D)/ε²) iterations with O(D³) per-iteration time complexity, where D is the state dimension.
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.