n\right)  $ functions $f_{1},\ldots,f_{m}\in S$, such that each $f_{i}$ is the unique function in $S$ compatible with $O\left(  \log\left\vert S\right\vert
    \right)  $ input/output constraints.
author:
- |
    Scott Aaronson[^1]\
    MIT
- |
    Andrew Drucker[^2]\
    MIT
bibliography:
- 'thesis.bib'
title: A Full Characterization of Quantum Advice
---

Introduction\[INTRO\]
=====================

> *How much classical information is needed to specify a quantum state of* $n$ *qubits?*

This question has inspired a rich and varied set of responses, in part because it can be interpreted in many ways.  If we want to specify a quantum state $\rho$ *exactly*, then of course the answer is ‘an infinite amount,’ since amplitudes in quantum mechanics are continuous.  A natural compromise is to try to specify $\rho$ *approximately*, i.e., to give a description which yields a state $\widetilde{\rho}$ whose statistical behavior is close to that of $\rho$ under every measurement. (This statement is captured by the requirement that $\rho$ and $\widetilde{\rho}$ are close under the so-called *trace distance* metric.)  But it is not hard to see that even for this task, we still need to use an exponential (in $n$) number of classical bits.

This fact can be viewed as a disappointment, but also as an opportunity, since 