Editing Compressed Sensing Tomography (section)

==Properties==

* Figure of merit: Density Matrix of the quantum state
* A random subset of <math>m = O((rd) </math>log<math> d) </math> Pauli observables are used in this method. The sample complexity of compressed tomography is nearly independent of the number of measurement settings <math>m</math>, so long as <math>m \geq O(rd</math> poly log <math>d)</math>.
* The accuracy of the compressed sensing estimates are fairly insensitive to the number of measurement settings <math>m</math>  So by choosing <math>m << d^2</math> one still obtains accurate estimates, but with much faster classical post-processing, since the size of the data set scales like <math>O(m)</math> rather than <math>O(d^2)</math>
* This method uses <math>t = O((\frac{rd}{\epsilon})^2 </math>log<math> d)</math> copies of the unknown quantum state.
* Compressed tomography provides better accuracy at a reduced computational cost compared to standard [[maximum-likelihood estimation]]
* This method works on the “universal” method for low-rank matrix recovery, which states that there exists a fixed set of <math>O(rd</math> poly log <math>d)</math> Pauli measurements, that has the ability to reconstruct every rank-<math>r</math> <math>d</math>×<math>d</math> matrix. With a high probability, a random choice of Pauli measurements will achieve this.
* when the unknown matrix ρ is full rank, our method returns a (certifiable) rank-r approximation of ρ, that is almost as good as the best such approximation
* The information-theoretic lower bound for tomography of rank-<math>r</math> states using adaptive sequences of single-copy Pauli measurements is at least <math>O(r^2 d^2 / </math>log <math>d)</math>  copies are needed to obtain an estimate with constant accuracy in the trace distance. The upper bound on the sample complexity of compressed tomography is nearly tight, and compressed tomography nearly achieves the optimal sample complexity among all possible methods using Pauli measurements.