Faster Stochastic First-Order Method for Maximum-Likelihood Quantum State Tomography
This provides a faster stochastic first-order method for quantum state tomography, addressing a bottleneck in quantum computing applications, though it appears incremental as it builds on existing stochastic optimization ideas.
The paper tackles the computational challenge of maximum-likelihood quantum state tomography, where sample size and dimension grow exponentially with qubits, by proposing a stochastic mirror descent algorithm with Burg entropy that achieves an expected optimization error rate of O(√((1/t)d log t)) and per-iteration time complexity of O(d^3), independent of sample size.
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.