Hi all,
today's group meeting is at the usual time and place (see subject line).
We'll hear from Gilles Brassard on simulation of the GHZ distribution. A
more precise title and abstract follow.
Best,
-joe
TITLE: Exact Classical Simulation of the GHZ Distribution
ABSTRACT:
John Bell has shown that the correlations entailed by quantum mechanics
cannot be reproduced by a classical process involving non-communicating
parties. But can they be simulated with the help of bounded communication?
This problem has been studied for more than twenty years and it is now well
understood in the case of bipartite entanglement. However, the issue was
still widely open for multipartite entanglement, even for the simplest
case, which is the tripartite Greenberger-Horne-Zeilinger (GHZ) state. We
give an exact simulation of arbitrary independent von Neumann measurements
on general n-partite GHZ states. Our protocol requires O(n^2) bits of
expected communication between the parties, and O(n log n) expected time is
sufficient to carry it out in parallel. Furthermore, we need only an
expectation of O(n) independent unbiased random bits, with no need for the
generation of continuous real random variables nor prior shared random
variables. In the case of equatorial measurements, we improve earlier
results with a protocol that needs only O(n log n) bits of communication
and O((log n)^2) parallel time. At the cost of a slight increase in the
number of bits communicated, these tasks can be accomplished with a
constant expected number of rounds.
Joint work with Luc Devroye and Claude Gravel