2020/12/31 by Chien‐Ming Lin, Lin, Chien-Ming, Yu-Ming Hsu +3 · 1 citation
Computer Science · #Stochastic Gradient Optimization Techniques #Quantum Computing Algorithms and Architecture #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2012.15498
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 ε-approximate ML estimate in O( ( D log D ) / ε ^ 2 ) iterations with O( D3 ) per-iteration time complexity, where D denotes the dimension of the unknown quantum state and ε denotes the optimization error. Our algorithm is an extension of Soft-Bayes to the quantum setup.