the computational requirements: now Alice can generate her message in polynomial time (for fixed $c$).  Also, while Bob cannot necessarily construct the state $\widetilde{\rho}$ efficiently on his own, if he is presented with such a state (by an untrusted prover, say), Bob can *verify* the state in polynomial time.  The catch in this result is a weakened approximation guarantee: Bob cannot use $\widetilde{\rho}$ to predict the outcomes of *all* the measurements defined by size-$n^c$ circuits, but only *most* of them (with respect to a samplable distribution used by Alice in the encoding process).  Aaronson [@aar:adv; @aar:learn] conjectured that the tradeoff between this result and the previous one revealed an inherent limit to quantum compression.

Our Quantum Information Result
------------------------------

The main result of this paper is that Aaronson’s conjecture was false: one really can get the best of both worlds, and simulate an arbitrary quantum state $\rho$ on all small circuits, using a different state $\widetilde{\rho
}$ that is easy to recognize.  Indeed, we can even take $\widetilde{\rho}$ to be the *ground state of a local Hamiltonian*: that is, the unique pure state $\widetilde{\rho}=\left\vert \psi\right\rangle \left\langle
\psi\right\vert $ on $\operatorname*{poly}\left(  n\right)  $ qubits that is compatible with $\operatorname*{poly}\left(  n\right)  $ 