André Chailloux, Iordanis Kerenidis, Jamie Sikora
Quantum information studies how information is encoded and decoded in quantum mechanical systems. In this paper, we study the basic scenario where two classical bits are encoded into a quantum state. We prove a "learning lemma," which provides a new upper bound on the average probability of decoding each bit that depends on the probability of learning the XOR of the two bits. Moreover, we give bounds on how well each bit can be decoded when their XOR is hidden and generalize these concepts to strings. Our learning lemmata have strong connections to cryptography and nonlocality. In particular, we show a set of equivalences between secure oblivious transfer protocols, CHSH-type games, and quantum encodings hiding the XOR. These equivalences allow us to use results in one area to prove results in another. For example, we use information bounds to give bounds on the values of CHSH-type games and also on the "correctness" of certain secure oblivious transfer protocols. We also use results of quantum XOR games to show that secure oblivious transfer admits perfect parallel repetition. Last, our learning lemmata enable us to improve the lower bounds on the cheating probabilities of any quantum oblivious transfer protocol.
View original:
http://arxiv.org/abs/1304.0983
No comments:
Post a Comment