  Qubit noise spectroscopy is an important tool for the experimental
investigation of open quantum systems. However, conventional techniques for
implementing noise spectroscopy are time-consuming, because they require
multiple measurements of the noise spectral density at different frequencies.
Here we describe an alternative method for quickly characterizing the spectral
density. Our method utilizes random pulse sequences, with carefully-controlled
correlations among the pulses, to measure arbitrary linear functionals of the
noise spectrum. Such measurements allow us to estimate $k$'th-order moments of
the noise spectrum, as well as to reconstruct sparse noise spectra via
compressed sensing. Our simulations of the performance of the random pulse
sequences on a realistic physical system, self-assembled quantum dots, reveal a
speedup of an order of magnitude in extracting the noise spectrum compared to
conventional dynamical decoupling approaches.

Quantum Physics