Tuesday, October 16, 2012
Institute for Quantum Information Seminar
A classical leash for a quantum tiger: Key distribution with minimal assumptions
Ben Reichardt, Professor, Electrical Engineering , University of Southern California
Can an experimentalist possibly understand and control an arbitrary quantum system? We give a scheme by which a classical experimentalist, with only classical interactions, can fully control black-box quantum-mechanical systems. The scheme even distinguishes a quantum computer from a classical simulation.
Although partly philosophical, this result has cryptographic applications. The original idea of quantum key distribution (QKD) is to base security on the laws of physics. But in practice QKD systems have been attacked, because real devices deviate from the mathematical models. Mayers and Yao in 1998 suggested that perhaps all these side-channel attacks could be eliminated. Barrett, Hardy and Kent gave the first "device-independent" QKD security proof in 2005, based on the assumption that Alice and Bob each have n devices, that are separately kept isolated but are otherwise arbitrary. We prove security with just one device for Alice and one for Bob. The key theorem studies sequential composition of a two-player game, and argues that nearly optimal strategies are nearly uniquely determined.
As another corollary, QMIP = MIP*.
Based on arXiv:1209.0448 and 1209.0449. Joint work with Falk Unger and Umesh Vazirani.