Recent years have witnessed tremendous progress in laboratory experiments which prepare highly entangled states of quantum many-body systems. As the complexity of these states increases, however, so too does the difficultly in verifying the quality of the experiment by some objective measure and in characterizing any undesired noise processes. In this talk I will discuss several new methods which address both tasks -- verification and characterization -- using far fewer resources than traditional methods. I will begin by discussing compressive sensing, a result from classical signal processing which can drastically reduce the required number of samples to reconstruct the spectrum of a time-dependent signal. By adapting and extending these methods to the setting of quantum mechanical systems, I will show how to verify and characterize a broad class of quantum experiments using quadratically fewer measurement settings than traditional methods, an improvement which is provably optimal. Next, I will show how ideas from quantum information theory and condensed matter physics allow us to efficiently reconstruct the ground state of any local Hamiltonian of a gapped one-dimensional interacting quantum many-body system. Finally, I will show how to directly verify the quality of any experiment which prepares a pure quantum state using only a constant number of measurement settings, independent of the size of the system.