dorsal/arxiv
View SchemaOn the Power of Quantum Memory
| Authors | Robert Koenig, Ueli Maurer, Renato Renner |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0305154 |
| URL | https://arxiv.org/abs/quant-ph/0305154 |
| DOI | 10.1109/TIT.2005.850087 |
| Journal | IEEE Trans. Inf. Th., vol. 51, no. 7 (2005) |
Abstract
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.
{
"annotation_id": "f97f8952-6743-4fd5-a422-4ffa625657f3",
"date_created": "2026-03-02T18:01:58.987000Z",
"date_modified": "2026-03-02T18:01:58.987000Z",
"file_hash": "422f02023b4dab3d7279fbf974a45cbdb853b82ed408614fd5c07bc036661b9a",
"private": false,
"record": {
"abstract": "We address the question whether quantum memory is more powerful than\nclassical memory. In particular, we consider a setting where information about\na random n-bit string X is stored in r classical or quantum bits, for r\u003cn,\ni.e., the stored information is bound to be only partial. Later, a randomly\nchosen binary question F about X is asked, which has to be answered using only\nthe stored information. The maximal probability of correctly guessing the\nanswer F(X) is then compared for the cases where the storage device is\nclassical or quantum mechanical, respectively.\n We show that, despite the fact that the measurement of quantum bits can\ndepend arbitrarily on the question F to be answered, the quantum advantage is\nnegligible already for small values of the difference n-r.\n An implication for cryptography is that privacy amplification by application\nof a compression function mapping n-bit strings to s-bit strings (for some\ns\u003cn-r), chosen publicly from a two-universal class of hash functions, remains\nessentially equally secure when the adversary\u0027s memory is allowed to be r\nquantum rather than only r classical bits.",
"arxiv_id": "quant-ph/0305154",
"authors": [
"Robert Koenig",
"Ueli Maurer",
"Renato Renner"
],
"categories": [
"quant-ph"
],
"doi": "10.1109/TIT.2005.850087",
"journal_ref": "IEEE Trans. Inf. Th., vol. 51, no. 7 (2005)",
"title": "On the Power of Quantum Memory",
"url": "https://arxiv.org/abs/quant-ph/0305154"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "c12fea9b-2193-4b79-892b-36648c677668",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}