# On the Power of Quantum Memory

## Robert Koenig and Ueli Maurer and Renato Renner

```
```We address the question whether quantum memory is more powerful than classical
memory. In particular, we consider a setting where information about a random
n-bit string X is stored in r classical or quantum bits, for r<n, i.e., the
stored information is bound to be only partial. Later, a randomly chosen binary
question F about X is asked, which has to be answered using only the stored
information. The maximal probability of correctly guessing the answer F(X) is
then compared for the cases where the storage device is classical or quantum
mechanical, respectively.

We show that, despite the fact that the measurement of quantum bits can depend
arbitrarily on the question F to be answered, the quantum advantage is
negligible already for small values of the difference n-r.

An implication for cryptography is that privacy amplification by application of
a compression function mapping n-bit strings to s-bit strings (for some s<n-r),
chosen publicly from a two-universal class of hash functions, remains
essentially equally secure when the adversary's memory is allowed to be r
quantum rather than only r classical bits.