Distinguishability of Quantum States Under Restricted Families of Measurements with an Application to Quantum Data Hiding

We consider the problem of ambiguous discrimination of two quantum states when we are only allowed to perform a restricted set of measurements. Let the bias of a POVM be defined as the total variational distance between the outcome distributions for the two states to be distinguished. The performance of a set of measurements can then be defined as the ratio of the bias of this POVM and the largest bias achievable by any measurements. We first provide lower bounds on the performance of various POVMs acting on a single system such as the isotropic POVM, and spherical 2 and 4-designs, and show how these bounds can lead to certainty relations. Furthermore, we prove lower bounds for several interesting POVMs acting on multipartite systems, such as the set of local POVMS, POVMs which can be implemented using local operations and classical communication (LOCC), separable POVMs, and finally POVMs for which every bipartition results in a measurement having positive partial transpose (PPT). In particular, our results show that a scheme of Terhal et. al. for hiding data against local operations and classical communication [31] has the best possible dimensional dependence.