Estimating many local expectation values over time is a central measurement bottleneck in quantum simulation and device characterization. We study the task of reconstructing the Pauli-signal matrix Sij=Tr(Oiρ(tj)) for a collection of M low-weight Pauli observables {Oi}i=1M over N timesteps {tj}j=1N, while minimizing the total number of device shots. We propose a Compressed Sensing Shadow Tomography (CSST) protocol that combines two complementary reductions. First, local classical shadows reduce the observable dimension by enabling many Pauli expectation values to be estimated from the same randomized snapshots at a fixed time. Second, compressed sensing reduces the time dimension by exploiting the fact that many expectation-value traces are spectrally sparse or compressible in a unitary (e.g., Fourier) transform basis. Operationally, CSST samples m≪N timesteps uniformly at random, collects shadows only at those times, and then reconstructs each length-N signal via standard ℓ1-based recovery in the unitary transform domain. We provide end-to-end guarantees that explicitly combine shadow estimation error with compressed sensing recovery bounds. For exactly s-sparse signals in a unitary transform basis, we show that m=O(slog2slogN) random timesteps suffice (with high probability), leading to total-shot savings scaling as Θ(N/s) (i.e., up to polylogarithmic factors) relative to collecting shadows at all N timesteps. For approximately sparse signals, the reconstruction error decomposes into a compressibility (tail) term plus a noise term. We present numerical experiments on noisy many-qubit dynamics that support strong Fourier compressibility of Pauli traces and demonstrate substantial shot reductions with accurate reconstruction.
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.
Abstract Characterising complex quantum systems is a vital task in quantum information science. Quantum tomography, the standard tool used for this purpose, uses a well-designed measurement record to reconstruct quantum states and processes. It is, however, notoriously inefficient. Recently, the classical signal reconstruction technique known as ‘compressed sensing’ has been ported to quantum information science to overcome this challenge: accurate tomography can be achieved with substantially fewer measurement settings, thereby greatly enhancing the efficiency of quantum tomography. Here we show that compressed sensing tomography of quantum systems is essentially guaranteed by a special property of quantum mechanics itself—that the mathematical objects that describe the system in quantum mechanics are matrices with non-negative eigenvalues. This result has an impact on the way quantum tomography is understood and implemented. In particular, it implies that the information obtained about a quantum system through compressed sensing methods exhibits a new sense of ‘informational completeness.’ This has important consequences on the efficiency of the data taking for quantum tomography, and enables us to construct informationally complete measurements that are robust to noise and modelling errors. Moreover, our result shows that one can expand the numerical tool-box used in quantum tomography and employ highly efficient algorithms developed to handle large dimensional matrices on a large dimensional Hilbert space. Although we mainly present our results in the context of quantum tomography, they apply to the general case of positive semidefinite matrix recovery.