  We show how to approximately represent a quantum state using the square root
of the usual amount of classical memory. The classical representation of an
$n$-qubit state $\psi$ consists of its inner products with $O(\sqrt{2^n})$
stabilizer states. A quantum state initially specified by its $2^n$ entries in
the computational basis can be compressed to this form in time $O(2^n
\mathrm{poly}(n))$, and, subsequently, the compressed description can be used
to additively approximate the expectation value of an arbitrary observable. Our
compression scheme directly gives a new protocol for the vector in subspace
problem with randomized one-way communication complexity that matches (up to
polylogarithmic factors) the optimal upper bound, due to Raz. We obtain an
exponential improvement over Raz's protocol in terms of computational
efficiency.
