11 de agosto de 2008

Charla de Julia Kempe en la UBA

Dia y hora:
MIERCOLES 13/8, 14hs

Facultad de Ciencias Exactas y Naturales, UBA

From Bell's inequalities to computational complexity
por Julia Kempe
Department of Computer Science, University of Tel Aviv, Israel

Resumen: Since the seminal work of John Bell it has been known that quantum entanglement between two parties can produce correlations that are not possible in a classical world, even with hidden variables. This has been one of the most remarkable discoveries and a formidable tool to prove the validity of quantum mechanics in the lab.

Computer scientists have long since appropriated Bell's inequalities. Perhaps the most prominent "application" is in unconditionally secure quantum cryptography. But among the most important challenges in the field currently is to understand the computational complexity of computing the violation of Bell's inequalities, or, in computer science lingo, the hardness of entangled multi-prover interactive proofs. Surprisingly, one of the most important approaches currently in this area builds on the work of Tsirelson who gave upper bounds on the maximal violation of Bell inequalities using semidefinite programming. I will explain the connection and the questions in this area and give an overview of some recent results, which, surprisingly, also give rise to new Bell inequalities.