Optimal compression with quantum retrieval

Abstract

We consider the following data compression problem. Given a string $x\in \{0,1{\}}^m$ of Hamming weight at most $n$, compress it into a shorter string $y\in \{0,1{\}}^s$ so that any bit $x_i$ of $x$ can be retrieved without any error using at most $t$ quantum queries to the standard oracle encoding of $y$. If queries are allowed to be adaptive we show how optimal compression up to a logarithmic factor can be achieved. If the queries are required to be made non-adaptively, we show schemes whose space is optimal in its dependence on $m$ except for a logarithmic factor, and is at most quadratically worse when compared to the optimum in its dependence on $n$.

13 pages, 3 figures