We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.
We study the problem of reconstructing an unknown matrix M of rank r and dimension d using O(rd poly log d) Pauli measurements. This has applications in quantum state tomography, and is a non-commutative analogue of a well-known problem in compressed sensing: recovering a sparse vector from a few of its Fourier coefficients. We show that almost all sets of O(rd log^6 d) Pauli measurements satisfy the rank-r restricted isometry property (RIP). This implies that M can be recovered from a fixed ("universal") set of Pauli measurements, using nuclear-norm minimization (e.g., the matrix Lasso), with nearly-optimal bounds on the error. A similar result holds for any class of measurements that use an orthonormal operator basis whose elements have small operator norm. Our proof uses Dudley's inequality for Gaussian processes, together with bounds on covering numbers obtained via entropy duality.
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.
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.
The techniques of low-rank matrix recovery were adapted for quantum state tomography (QST) previously by Gross et al. [Phys. Rev. Lett. 105, 150401 (2010)] where they consider the tomography of n spin-1/2 systems. For the density matrix of dimension d=2n and rank r with $r\ensuremath{\ll}{2}^{n}$, it was shown that randomly chosen Pauli measurements of the order O[drlog(d)2] are enough to fully reconstruct the density matrix by running a specific convex optimization algorithm. The result utilized the low operator norm of the Pauli operator basis, which makes it ``incoherent'' to low-rank matrices. For quantum systems of dimension d not a power of two, Pauli measurements are not available, and one may consider using SU(d) measurements. Here, we point out that the SU(d) operators, owing to their high operator norm, do not provide a significant savings in the number of measurement settings required for successful recovery of all rank-r states. We propose an alternative strategy in which the quantum information is swapped into the subspace of a power-two system using only poly[log(d)2] gates at most with QST being implemented, subsequently, by performing O[drlog(d)2] Pauli measurements. We show that, despite the increased dimensionality, this method is more efficient than the one using SU(d) measurements.
We establish methods for quantum state tomography based on compressed sensing. These methods are specialized for quantum states that are fairly pure, and they offer a significant performance improvement on large quantum systems. In particular, they are able to reconstruct an unknown density matrix of dimension d and rank r using O(rdlog²d) measurement settings, compared to standard methods that require d² settings. Our methods have several features that make them amenable to experimental implementation: they require only simple Pauli measurements, use fast convex optimization, are stable against noise, and can be applied to states that are only approximately low rank. The acquired data can be used to certify that the state is indeed close to pure, so no a priori assumptions are needed.
Density matrices are positively semi-definite Hermitian matrices with unit trace that describe the states of quantum systems. Many quantum systems of physical interest can be represented as high-dimensional low rank density matrices. A popular problem in quantum state tomography (QST) is to estimate the unknown low rank density matrix of a quantum system by conducting Pauli measurements. Our main contribution is twofold. First, we establish the minimax lower bounds in Schatten p-norms with 1≤p≤+∞ for low rank density matrices estimation by Pauli measurements. In our previous paper [14], these minimax lower bounds are proved under the trace regression model with Gaussian noise and the noise is assumed to have common variance. In this paper, we prove these bounds under the Binomial observation model which meets the actual model in QST. Second, we study the Dantzig estimator (DE) for estimating the unknown low rank density matrix under the Binomial observation model by using Pauli measurements. In our previous papers [14] and [25], we studied the least squares estimator and the projection estimator, where we proved the optimal convergence rates for the least squares estimator in Schatten p-norms with 1≤p≤2 and, under a stronger condition, the optimal convergence rates for the projection estimator in Schatten p-norms with 1≤p≤+∞. In this paper, we show that the results of these two distinct estimators can be simultaneously obtained by the Dantzig estimator. Moreover, better convergence rates in Schatten norm distances can be proved for Dantzig estimator under conditions weaker than those needed in [14] and [25]. When the objective function of DE is replaced by the negative von Neumann entropy, we obtain sharp convergence rate in Kullback-Leibler divergence.
Factored gradient descent (FGD) is a scalable nonconvex method for low-rank positive semidefinite matrix recovery, in which the rank and positivity constraints are satisfied automatically by the factorization. Most of the existing theory that certifies benignity of its loss landscape, however, relies on a restricted isometry property (RIP) of the measurement map. In quantum state tomography, one of its applications, the measurements that can be acquired with stable statistics are limited by detection efficiency and drift to Pauli observables of low weight; we first show that under such partial-weight Pauli measurements RIP fails in the worst possible way. We then bundle the mutually commuting observables setting by setting, pushing the state forward to the probability distribution of each setting, and introduce a max-sliced total-variation loss. On the stratum where the setting attaining the maximum is unique there is no spurious local minimum, and provided only that the measurement map is injective on generic pure states, the global minimum is the truth up to a phase. Finally we verify these claims numerically on four qubits and compare against FGD with the ordinary loss.