dorsal/arxiv
View SchemaState Discrimination with Post-Measurement Information
| Authors | Manuel A. Ballester, Stephanie Wehner, Andreas Winter |
|---|---|
| Categories | |
| ArXiv ID | quant-ph/0608014 |
| URL | https://arxiv.org/abs/quant-ph/0608014 |
| DOI | 10.1109/TIT.2008.928276 |
| Journal | IEEE Trans. on Information Theory, vol 54, issue 9 (2008), pages 4183 - 4198 |
Abstract
We introduce a new state discrimination problem in which we are given additional information about the state after the measurement, or more generally, after a quantum memory bound applies. In particular, the following special case plays an important role in quantum cryptographic protocols in the bounded storage model: Given a string x encoded in an unknown basis chosen from a set of mutually unbiased bases, you may perform any measurement, but then store at most q qubits of quantum information. Later on, you learn which basis was used. How well can you compute a function f(x) of x, given the initial measurement outcome, the q qubits and the additional basis information? We first show a lower bound on the success probability for any balanced function, and any number of mutually unbiased bases, beating the naive strategy of simply guessing the basis. We then show that for two bases, any Boolean function f(x) can be computed perfectly if you are allowed to store just a single qubit, independent of the number of possible input strings x. However, we show how to construct three bases, such that you need to store all qubits in order to compute f(x) perfectly. We then investigate how much advantage the additional basis information can give for a Boolean function. To this end, we prove optimal bounds for the success probability for the AND and the XOR function for up to three mutually unbiased bases. Our result shows that the gap in success probability can be maximal: without the basis information, you can never do better than guessing the basis, but with this information, you can compute f(x) perfectly. We also exhibit an example where the extra information does not give any advantage at all.
{
"annotation_id": "bf4ee8d1-b349-47f8-a1d4-77513015b8b7",
"date_created": "2026-03-02T18:02:30.925000Z",
"date_modified": "2026-03-02T18:02:30.925000Z",
"file_hash": "15196075ae120d78c3a91139e256b5b562b571523566dba4ff57dc8a12dfc965",
"private": false,
"record": {
"abstract": "We introduce a new state discrimination problem in which we are given\nadditional information about the state after the measurement, or more\ngenerally, after a quantum memory bound applies. In particular, the following\nspecial case plays an important role in quantum cryptographic protocols in the\nbounded storage model: Given a string x encoded in an unknown basis chosen from\na set of mutually unbiased bases, you may perform any measurement, but then\nstore at most q qubits of quantum information. Later on, you learn which basis\nwas used. How well can you compute a function f(x) of x, given the initial\nmeasurement outcome, the q qubits and the additional basis information? We\nfirst show a lower bound on the success probability for any balanced function,\nand any number of mutually unbiased bases, beating the naive strategy of simply\nguessing the basis. We then show that for two bases, any Boolean function f(x)\ncan be computed perfectly if you are allowed to store just a single qubit,\nindependent of the number of possible input strings x. However, we show how to\nconstruct three bases, such that you need to store all qubits in order to\ncompute f(x) perfectly. We then investigate how much advantage the additional\nbasis information can give for a Boolean function. To this end, we prove\noptimal bounds for the success probability for the AND and the XOR function for\nup to three mutually unbiased bases. Our result shows that the gap in success\nprobability can be maximal: without the basis information, you can never do\nbetter than guessing the basis, but with this information, you can compute f(x)\nperfectly. We also exhibit an example where the extra information does not give\nany advantage at all.",
"arxiv_id": "quant-ph/0608014",
"authors": [
"Manuel A. Ballester",
"Stephanie Wehner",
"Andreas Winter"
],
"categories": [
"quant-ph"
],
"doi": "10.1109/TIT.2008.928276",
"journal_ref": "IEEE Trans. on Information Theory, vol 54, issue 9 (2008), pages\n 4183 - 4198",
"title": "State Discrimination with Post-Measurement Information",
"url": "https://arxiv.org/abs/quant-ph/0608014"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "504203e6-80ae-4d43-a343-7cc63ba0c746",
"id": "arXiv Dataset IDs",
"type": "Model",
"variant": "snapshot-2026-03-01",
"version": "0.1.0"
},
"user_id": 1000002
}