John Bell has shown that the correlations entailedby quantum mechanics cannot be reproduced by a classicalprocess involving non-communicating parties. But can they besimulated with the help of bounded communication? This prob-lem has been studied for more than two decades, and it is nowwell 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 ofarbitrary independent von Neumann measurements on generaln-partite GHZ states. Our protocol requiresO(n2)bits ofexpected communication between the parties, andO(nlogn)expected time is sufficient to carry it out in parallel. Furthermore,we need only an expectation ofO(n)independent unbiasedrandom bits, with no need for the generation of continuous realrandom variables nor prior shared random variables. In the caseof equatorial measurements, we improve on the prior art with aprotocol that needs onlyO(nlogn)bits of communication andO(log2n)parallel time. At the cost of a slight increase in thenumber of bits communicated, these tasks can be accomplishedwith a constant expected number of rounds.Index Terms— Entanglement simulation, Greenberger–Horne–Zeilinger(GHZ)state,Knuth-Yao’ssamplingalgorithm,multipartite entanglement, von Neumann’s rejection algorithm,random-bit model
the issue of non-locality in quantum physics was raisedin 1935 by Einstein, Podolsky and Rosen when they intro-duced the notion of entanglement [1]. Thirty years later, Bellproved that the correlations entailed by entanglement cannotbe reproduced by classical local hidden variable theories between noncommunicating arties [2]. This momentous discovery led to the question ofquantifyingquantum non-locality.A natural quantitative approach to the non-locality inherentin a given entangled quantum state is to study the amount ofresources that would be required in a purely classical theory toreproduce exactly the probabilities corresponding to measur-ing it. More formally, we consider the problem ofsamplingthejoint discrete probability distribution of the outcomes obtainedby people sharing this quantumstate, on which each partyapplies locally some measurement on his share. Each partyis given a description of his own measurement but is notinformed of the measurements assigned to the other parties.This task would be easy (for a theoretician!) if the partieswere indeed given their share of the quantum state, but theyare not. Instead, they mustsimulatethe outcome of thesemeasurements without any quantum resources, using as littleclassical communicationas possible. Notice that we insist onexactsampling since approximate sampling can obviously berealized by having the parties communicate in order to shareapproximations of their measurement parameters.This conundrum was introduced by Maudlin [3] in 1992in the simplest case of linearpolarization measurementsat arbitrary angles on the two photons that form a Bellstate such as|�+〉=1√2|00〉+1√2|11〉. Maudlin claimed thatthis required “the capacity to send messages of unboundedlength”, but he showed nevertheless that the task could beachieved with a bounded amount ofexpectedcommunication.Similar concepts were reinvented independently years laterby other researchers [4], [5]. This led to a series of results,culminating with the protocol of Toner and Bacon to simulatearbitrary von Neumann measurements on a Bell state with asingle bit of communicationin the worst case[6], thus con-tradicting Maudlin’s claim. Later, Regev and Toner extendedthis result by giving a simulation of the correlation (butnot the marginals) entailed by arbitrary binary von Neumannmeasurements (meaning that the outcome for each party cantake only two values) on arbitrary bipartite states of anydimension using only two bits of communication, also in theworst case [7]. Inspired by Steiner’s work [5], Cerf, Gisin andMassar showed that the effect of an arbitrary pair of positive-operator-valued measurements (POVMs) on a Bell state canalso be simulated with a bounded amount of expected commu-nication [8]. A more detailed early history of the simulationof quantum entanglement can be found in Ref. [9, Sec. 6].All this prior work is concerned strictly with the simulationofbipartiteentanglement. Much less is known when itcomes to simulating multipartite entanglement with clas-sical communication, a topic that was still teeming. VS Sewing Machines
Despite substantial effort, the case ofarbitraryvonNeumann measurements, even on the original tripartiteGHZ state|�3〉, was still wide open. Here, we solve thisproblem in the general case of the simulation of then-partiteGHZ state|�n〉,foranyn, under therandom bit modelintroduced in 1976 by Knuth and Yao [15], in which theonly source of randomness comes from the availability ofindependently distributed unbiased random bits. Furthermore,we have no needs for prior shared random variables betweenthe parties.1Our simulation proceeds withO(n)expectedperfect random bits and its expected communication cost isO(n2)bits, but onlyO(nlogn)timeif we count one stepfor sending bits in parallel according to a realistic scenarioin which no party has to send or receive more than onebit in any given step. Furthermore, in the case of equatorialmeasurements, we improve the earlier best result [14] withan expected communication cost of onlyO(nlogn)bits andO(log2n)parallel time. At the cost of a slight increase inthe number of bits communicated and the number of requiredrandom bits, these tasks can be accomplished with a constantexpected number of rounds.More formally, the quantum task that we want to simulateis as follows. Each partyjholds one qubit (quantum bit) fromstate|�n〉=1√2|0n〉+1√2|1n〉and is given the descriptionof a von Neumann measurementMj. By local operations,they collectively perform⊗nj=1Mjon|�n〉, thus obtainingone outcome each, saybj∈{−1,+1}, which is their output.The joint probability distributionp(b)of thebj’s is definedby the joint set of measurements. Our purpose is to sampleexactlythis joint probability distribution by a purely classicalprocess that involves no prior shared random variables andas little communication as possible. As mentioned above,previous solutions [12]–[14] required each individual measure-ment to be equatorial. In order to overcome this limitation,our complete solution builds on three ingredients: (1) Gravel’sdecomposition ofp(b)as a convex combination of two sub-distributions [17], [18]; (2) Knuth and Yao’s algorithm [15] tosample exactly discrete probability distributions assuming onlya source of unbiased identically independently distributedbits,rather than a source ofcontinuousuniform random variableson the interval[0,1]; and (3) our own distributed version ofthe classicvon Neumann’s rejection algorithm[19].We define precisely our problem in Section II and weformulate our convex decomposition of the GHZ distribution,which is the key to its simulation. Then, we explain how tosample according to a Bernoullidistribution even when onlyapproximations of the distribution’s parameter are available.We also explain how the classic von Neumann rejectionalgorithm can be used to sample in the sub-distributionsdefined by our convex decomposition. However, little attentionis paid in Section II to the fact that the various parameters thatdefine the joint distribution are not available in a single place.Section III is concerned with the communication complexityissues. This paves the way to Section IV, in which weprovide a complete protocol to solve our problem, as wellas its detailed analysis. Section V discusses variations on thetheme, in which we consider a parallel model of communi-cation, an expected bounded-round solution, improvements onthe prior art for the simulation of equatorial measurements,and a remark to the effect that only one party needs accessto a source of randomness. We conclude in Section VIwith a discussion, open problems, and the announcement ofa forthcoming generalization of our results. For complete-ness, the appendices derive from first principles our convexdecomposition of the GHZ distribution, as well as elementaryapproximation and truncation formulas useful in the analysisof the parallel model.
