for specific classes like the ‘pretty good measurements’ of Hausladen and Wootters [@hausladen].  A more ambitious goal in this vein, explored by Aaronson in two previous works [@aar:adv; @aar:learn] and continued in the present paper, is to give a description of an $n$-qubit state $\rho$ which yields a state $\widetilde{\rho}$ that behaves approximately like $\rho$ with respect to all (binary) measurements performable by quantum circuits of ‘reasonable’ size—say, of size at most $n^c$, for some fixed $c > 0$. Then if $c$ is taken large enough, $\widetilde{\rho}$ is arguably ‘just as good’ as $\rho$ for practical purposes.

Certainly we can achieve this goal using $2^{n^{c + O(1)}}$ bits: simply give approximations to the measurement statistics for every size-$n^c$ circuit.  However, the results of Holevo [@holevo] and Ambainis et al. [@antv] suggest that a much more succinct description might be possible.  This hope was realized by Aaronson [@aar:adv], who gave a description scheme in which an $n$-qubit state can be specified using $\operatorname*{poly}\left(n\right)$ classical bits. There is a significant catch in Aaronson’s result, though: the encoder Alice and decoder Bob both need to invest exponential amounts of computation.

In a subsequent paper [@aar:learn], Aaronson gave a closely-related result which significantly reduces 