software might entail satisfying an exponential number of constraints: for example, if $\rho$ is supposed to help a customer’s quantum computer $Q$ evaluate some Boolean function $f:\left\{  0,1\right\}  ^{n}\rightarrow\left\{  0,1\right\}  $, then $Q\left(  \rho , x \right)
$ should output $f\left(  x\right)  $ for *every* input $x\in\left\{
0,1\right\}  ^{n}$.  By contrast, any $k$-local Hamiltonian $H$ can be described as a set of at most ${\binom{n }{k}} = O(n^{k})$ constraints.

One can also interpret Theorem \[mainthm0\] as a statement about communication over quantum channels.  Suppose Alice (who is computationally unbounded) has a classical description of an $n$-qubit state $\rho$.  She would like to describe $\rho$ to Bob (who is computationally bounded), at least well enough for Bob to be able to *simulate* $\rho$ on all quantum circuits of some fixed polynomial size.  However, Alice cannot just send $\rho$ to Bob, since her quantum communication channel is noisy and there is a chance that $\rho$ might get corrupted along the way.   Nor can she send a faithful classical description of $\rho$, since that would require an exponential number of bits. Our result provides an alternative: Alice can send a different quantum state $\sigma$, of $\operatorname*{poly}(n)$ qubits, together with a $\operatorname*{poly}(n)$-bit classical string 