Title: Non-locality, negative probabilities, and communication complexity
Speaker: Jeremie Roland, University of California - Berkeley
Date: Wednesday, September 19, 2007 11:00-12:00pm
Location: CoRE A (room 301), CoRE Bldg, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
Ever since its inception, Quantum Mechanics has appeared rather counter-intuitive in contrast to classical physics. In particular, one odd property of Quantum Mechanics is its apparent non-locality: this was first emphasized by the EPR gedanken experiment, and later clarified by Bell's theorem, which states that no local hidden variable (LHV) model may reproduce the results of an EPR-type experiment. One possible explanation that was first proposed by Feynman to resolve these apparent paradoxes was the (rather abstract) idea that Quantum Mechanics allowed probabilities to be negative. Here, we prove that any EPR-type experiment that respects causality may be reproduced by a LHV model with quasi-probabilities, or quasi-LHV model.
As a first consequence, we give an interpretation of such a quasi-LHV model, which allows us to simulate any causal distribution, including arbitrary measurements on quantum states, using (standard) local hidden variables and communication. Secondly, we give applications to communication complexity. More specifically, we show how to derive a quasi-LHV model from a communication protocol. This yields a new lower bound method for the deterministic communication complexity, expressed as a linear program. The duality theorem of linear programming then clarifies the relationship between negative probabilities and Bell inequalities.
Finally, we consider the problem of computing with so-called non-local boxes, i.e. abstract devices whose inputs-outputs follow the most simple non-local yet causal probability distribution, and as such may be described by a quasi-LHV model. As was first proved by van Dam, communication complexity becomes trivial as soon as non-local boxes may be used for free. Here, we quantify the cost of non-local boxes in such computation by showing how a communication protocol may be translated into a protocol using non-local boxes, and by giving a lower bound on the number of non-local boxes necessary to compute a given function (for the restricted case where the non-local boxes are used in parallel). To conclude, we show by giving specific examples that some functions that may be computed with t bits of communication may also be computed with t non-local boxes, while others require an exponential amount of non-local boxes (at least when these are used in parallel).