Remote Sampling with Applications to General Entanglement Simulation
We show how to sample exactly discrete probability distributions whose
defining parameters are distributed among remote parties. For this purpose, von
Neumann's rejection algorithm is turned into a distributed sampling
communication protocol. We study the expected number of bits communicated among
the parties and also exhibit a trade-off between the number of rounds of the
rejection algorithm and the number of bits transmitted in the initial phase.
Finally, we apply remote sampling to the simulation of quantum entanglement in
its most general form possible, when an arbitrary number of parties share
systems of arbitrary dimensions on which they apply arbitrary measurements (not
restricted to being projective measurements). In case the dimension of the
systems and the number of possible outcomes per party is bounded by a constant,
it suffices to communicate an expected O(m^2) bits in order to simulate exactly
the outcomes that these measurements would have produced on those systems,
where m is the number of participants.