Quantum tomography via compressed sensing: error bounds, sample complexity and efficient estimators

By Steven T. Flammia, David Gross, Yi-Kai Liu, Jens Eisert. 2012

437 citations recorded by the source corpus.

Intuitively, if a density operator has small rank, then it should be easier to estimate from experimental data, since in this case only a few eigenvectors need to be learned. We prove two complementary results that confirm this intuition. Firstly, we show that a low-rank density matrix can be estimated using fewer copies of the state, i.e. the sample complexity of tomography decreases with the rank. Secondly, we show that unknown low-rank states can be reconstructed from an incomplete set of measurements, using techniques from compressed sensing and matrix completion. These techniques use simple Pauli measurements, and their output can be certified without making any assumptions about the unknown state. In this paper, we present a new theoretical analysis of compressed tomography, based on the restricted isometry property for low-rank matrices. Using these tools, we obtain near-optimal error bounds for the realistic situation where the data contain noise due to finite statistics, and the density matrix is full-rank with decaying eigenvalues. We also obtain upper bounds on the sample complexity of compressed tomography, and almost-matching lower bounds on the sample complexity of any procedure using adaptive sequences of Pauli measurements. Using numerical simulations, we compare the performance of two compressed sensing estimators—the matrix Dantzig selector and the matrix Lasso—with standard maximum-likelihood estimation (MLE). We find that, given comparable experimental resources, the compressed sensing estimators consistently produce higher fidelity state reconstructions than MLE. In addition, the use of an incomplete set of measurements leads to faster classical processing with no loss of accuracy. Finally, we show how to certify the accuracy of a low-rank estimate using direct fidelity estimation, and describe a method for compressed quantum process tomography that works for processes with small Kraus rank and requires only Pauli eigenstate preparations and Pauli measurements.

Subfields: Artificial Intelligence, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/b16268055e0942e5ff441799ac77315014ca5868

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Signal Processing

Citations in the corpus

Hamiltonian Simulation by Qubitization (2016, methodology): “applications of Table.2. As Hermitian operators are also quantum observables, our methodology also oers a new approach for implementing arbitrary functions of measurement operators on quantum states [1,13,24,38]. We conjecture that this application would be optimal, which is supported by our optimal”
Sample-Optimal Tomography of Quantum States (2015, background): “The trace distance bound only says n = Õ(1/ξ2) copies are sufficient to distinguish them, whereas the fidelity bound says n = Õ(1/ξ) copies are sufficient.”
Dropping Convexity for Faster Semi-definite Optimization (2015, methodology): “One of the ﬁrst provable algorithmic solutions for the QST problem was through convexiﬁcation [29, 65, 21]: this includes nuclear norm minimization approaches [33] (using e.g. , [7]), as well as proximal variants [30] (using e.g. , [17]).”
Predicting many properties of a quantum system from very few measurements (2020, background): “This more stringent bound is saturated by low rank matrix recovery [24, 46, 47] and projected least squares estimation [33, 65].”
Global Optimality of Local Search for Low Rank Matrix Recovery (2016, background): “1 Introduction Low rank matrix recovery problem is heavily studied and has numerous applications in collaborative filtering, quantum state tomography, clustering, community detection, metric learning and multi-task learning [21, 12, 9, 27].”