it raises the prospect that we might be able to encode massive amounts of information in physically compact quantum states: for example, we might hope to store $2^{n}$ classical bits in $n$ qubits.  But an obvious practical requirement is that we be able to retrieve the information reliably, and this rules out the hope of significant ‘quantum compression’ of classical strings, as shown by a landmark result of Holevo [@holevo] from 1973.  Consider a sender Alice and a recipient Bob, with a one-way quantum channel between them.  Then Holevo’s Theorem says that, if Alice wants to encode an $n$-bit classical string $x$ into an $m$-qubit quantum state $\rho_{x}$, in such a way that Bob can retrieve $x$ (with probability $2/3$, say) by measuring $\rho_{x}$, then Alice must take $m\geq n-O\left(  1\right)  $ (or $m\geq
n/2-O\left(  1\right)  $, if Alice and Bob share entanglement).  In other words, for this communication task, quantum states offer essentially no advantage over classical strings. In 1999, Ambainis et al. [@antv] generalized Holevo’s result as follows: even if Bob wants to learn only a *single bit* $x_{i}$ of $x=x_{1}\ldots x_{n}$ (for some $i\in\left[
n\right]  $ unknown to Alice), and is willing to destroy the state $\rho_{x}$ 