$x$. Then, Bob can use $x$ to *verify* that $\sigma$ can be used to accurately simulate $\rho$ on all small measurements.

We believe Theorem \[mainthm0\] makes a significant contribution to the study of the effective information content of quantum states.  It does, however, leave open whether a quantum state of $n$ qubits can be efficiently encoded *and* decoded in polynomial time, in a way that is ‘good enough’ to preserve the measurement statistics of measurements defined by circuits of fixed polynomial size.  This remains an important problem for future work.

Impact on Quantum Complexity Theory\[MOTIVATION\]
-------------------------------------------------

The questions addressed in this paper, and our results, are naturally phrased and proved in terms of complexity classes.  In recent years, researchers have defined quantum complexity classes as a way to study the ‘useful information’ embodied in quantum states. One approach is to study the power of nonuniform *quantum advice*.  The class $\mathsf{BQP/qpoly}$, defined by Nishimura and Yamakami [@ny], consists of all languages decidable in polynomial time by a quantum computer, with the help of a $\operatorname*{poly}\left(  n\right) $-qubit advice state that depends only on the input length $n$. This class is analogous to the classical class $\mathsf{P/poly}$. To understand the role of 