A Caltech Library Service

State Discrimination With Post-Measurement Information

Ballester, Manuael A. and Wehner, Stephanie and Winter, Andreas (2008) State Discrimination With Post-Measurement Information. IEEE Transactions on Information Theory, 54 (9). pp. 4183-4198. ISSN 0018-9448.

PDF - Published Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
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.
Funding AgencyGrant Number
Netherlands Organisation for Scientific Research (NWO)2004–2009
European UnionIST-2005-15848
National Science FoundationPHY-0456720
Engineering and Physical Sciences Research Council (EPSRC) (U.K.)UNSPECIFIED
University of BristolUNSPECIFIED
Subject Keywords:Bounded quantum storage, quantum cryptography, state discrimination
Issue or Number:9
Record Number:CaltechAUTHORS:BALieeetit08
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:11797
Deposited By: Archive Administrator
Deposited On:29 Sep 2008 23:11
Last Modified:03 Oct 2019 00:22

Repository Staff Only: item control page