• matrix completion
• rank-certificate

The goal of tomography is to reconstruct the density matrix of a physical system through a series of measurements of some observables. In general, we need at most d^2 measurements to reconstruct the state, where d is the dimension of the Hilbert space where the state is embedded (e.g. d=2^n for an n-qubit system). But if the rank r of the matrix is low, then O(rd) measures could be sufficient. A priori it is not clear whether the matrix can be recovered from this limited set of measurements in a computationally tractable way, i.e., how to choose these measurements, or which algorithm to use.

We describe a method, introduced by Candes et al. and developed by Gross et al. for the application in quantum tomography, under the label of "compressed sensing", able to reconstruct the unknown density matrix using O(rd log(d)) measures. Compressed sensing provides techniques for recovering a sparse vector (a vector contains only a few non-zero entries) from a small number of measurements. Matrix completion is a generalization of compressed sensing from vectors to matrices. Here, one recovers certain low-rank matrices X from a small number of matrix elements X_{ij}. The recovering is based on solving a semidefinite program, a class of convex optimization problems for which solving algorithms are particularly fast. The same holds in the quantum case, where we measure the coefficients of the matrix in a basis which differs by the standard basis.
In a real experiment, the measurement are noisy (e.g. statistical noise), and the true state is only approximately low-rank. We consider also this situation, and we accompany the discussion with useful examples able to elucidate what we are doing.