Strategies for optimal single-shot discrimination of quantum measurements

In this work we study the problem of single-shot discrimination of von Neumann measurements. We associate each measurement with a measure-and-prepare channel. There are two possible approaches to this problem. The first one, which is simple, does not utilize entanglement. We focus only on discrimination of classical probability distribution, which are outputs of the channels. We find necessary and sufficient criterion for perfect discrimination in this case. A more advanced approach requires the usage and entanglement. We quantify the distance of the two measurements in terms of the diamond norm (called sometimes the completely bounded trace norm). We provide an exact expression for the optimal probability of correct distinction and relate it to the discrimination of unitary channels. We also state a necessary and sufficient condition for perfect discrimination and a semidefinite program which checks this condition. Our main result, however, is a cone program which calculates the distance of these measurements and hence provides an upper bound on the probability of their correct distinction. As a by-product the program also finds a strategy (input state) which achieves this bound. Finally, we provide a full description for the cases of Fourier matrices and mirror isometries.