Exact simulation for the GHZ distribution

Luc Devroye, Claude Gravel

Published Mar 24, 2013• 1 citation

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 two decades 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 on the prior art with a protocol that needs only O(n log n) bits of communication and O(log^2 n) 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.

Related papers

Exact Classical Simulation of the GHZ Distribution

Gilles Brassard A, Luc Devroye, Claude Gravel

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^2(n)) 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.

Leibniz international proceedings in informaticsJan 1, 20140 citations

Exact Classical Simulation of the Quantum-Mechanical GHZ Distribution

Gilles Brassard A, Luc Devroye, Claude Gravel

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 two decades, 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(n2) 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 on the prior art with a protocol that needs only O(n log n) bits of communication and O(log2n) 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.

arXiv:1303.5942IEEE Transactions on Information TheoryDec 1, 20157 citations

Quantifying the Nonlocality of Greenberger-Horne-Zeilinger Quantum Correlations by a Bounded Communication Simulation Protocol

Cyril Branciard, Nicolas Gisin

The simulation of quantum correlations with finite nonlocal resources, such as classical communication, gives a natural way to quantify their nonlocality. While multipartite nonlocal correlations appear to be useful resources, very little is known on how to simulate multipartite quantum correlations. We present a protocol that reproduces tripartite Greenberger-Horne-Zeilinger correlations with bounded communication: 3 bits in total turn out to be sufficient to simulate all equatorial Von Neumann measurements on the tripartite Greenberger-Horne-Zeilinger state.

arXiv:1102.0330Physical Review LettersJul 5, 201150 citations

Remote Sampling with Applications to General Entanglement Simulation

Gilles Brassard A, Luc Devroye, Claude Gravel

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 essentially most general form possible, when an arbitrary finite number m of parties share systems of arbitrary finite dimensions on which they apply arbitrary measurements (not restricted to being projective measurements, but restricted to finitely many possible outcomes). In case the dimension of the systems and the number of possible outcomes per party are 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.

arXiv:1807.06649EntropyJan 19, 201932 citations

Simulation of Equatorial von Neumann Measurements on GHZ States Using Nonlocal Resources

Jean-Daniel Bancal, Cyril Branciard, Nicolas Gisin

Reproducing with elementary resources the correlations that arise when a quantum system is measured (quantum state simulation) allows one to get insight on the operational and computational power of quantum correlations. We propose a family of models that can simulate von Neumann measurements in the x − y plane of the Bloch sphere on n‐partite GHZ states. For the tripartite and fourpartite states, the models use only bipartite nonlocal boxes; they can be translated into classical communication schemes with finite average communication cost.

arXiv:0908.2640Advances in Mathematical PhysicsJan 1, 20109 citations

Structure of the probability distribution for the GHZ quantum state under local von Neumann measurements

Claude Gravel

We show that the probability distribution of the Greenberger-Horne-Zeilinger quantum state (GHZ) under local action of independent von Neumann measurements follows a convex distribution of two distributions. The coefficients of the combination are related to the equatorial parts of the measurements, and the distributions associated with those coefficients are associated with the real parts of the measurements. One possible application of the result is that it allows one to split into two pieces the simulation of the GHZ state. Simulating, in worst-case or in average case, a quantum state like the GHZ state with random resources, shared or private, as well as with classical communication resources or even odd resources like nonlocal boxes is a very important in the theory of quantum communication complexity.

Jan 1, 20124 citations