State Discrimination With Post-Measurement Information
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. 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 (MUBs), you may perform any measurement, but then store at most $q$ qubits of quantum information, and an unlimited amount of classical 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 Bool- - ean 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 give an example where the extra information does not give any advantage at all.
Additional Information
© Copyright 2008 IEEE. Reprinted with permission. Manuscript received September 6, 2006; revised April 23, 2008. Published August 27, 2008 (projected). [Date Published in Issue: 2008-08-26] The work of M. Ballester and S. Wehner was supported by an NWO vici Grant 2004–2009 and by the EU project QAP (IST-2005-15848). The work of S. Wehner was also supported by the National Science Foundation under Grant PHY-0456720. The work of A. Winter was supported by the U.K. EPSRC's "QIP IRC," the EU project QAP, and by a University of Bristol Research Fellowship. Part of this work was completed while S. Wehner was a Ph.D. student at CWI. The authors wish to thank Harry Buhrman for his persistent interest in the present investigation, various discussions, and his suggestion that our problem also has applications to communication complexity. Thanks also to Ronald de Wolf for helpful comments on an earlier version of the manuscript.Attached Files
Published - BALieeetit08.pdf
Files
Name | Size | Download all |
---|---|---|
md5:14adb6b4a1e4817c0919d1d66e1b85da
|
411.6 kB | Preview Download |
Additional details
- Eprint ID
- 11797
- Resolver ID
- CaltechAUTHORS:BALieeetit08
- 2004–2009
- Netherlands Organisation for Scientific Research (NWO)
- IST-2005-15848
- European Union
- PHY-0456720
- National Science Foundation
- Engineering and Physical Sciences Research Council (EPSRC) (U.K.)
- University of Bristol
- Created
-
2008-09-29Created from EPrint's datestamp field
- Updated
-
2021-11-08Created from EPrint's last_modified field