The cost of exactly simulating a Bell pair using classical communication

János A. Csirik

AT&T Labs–Research (Dated: March 14, 2002)

The paper [1] begins thus: “Bell’s celebrated theorem [2] shows that certain scenarious involving bipartite quantum measurements result in correlations that are impossible to simulate with a classical system if the measurement events are spacelike separated. If the measurement events are timelike separated, then classical simulation is possible, at the expense of some communication. Our goal is to quantify the required amount of communication.” In this note we tighten the bounds on the amount of communication required to simulate a von Neumann measurement on a Bell pair.

PACS numbers: 03.67.Hk

INTRODUCTION

Consider the following experiment. Let Alice and Bob share one half each of a Bell pair (|0⟩|0⟩ + |1⟩|1⟩)/\sqrt{2}. Given a ∈ [0, π), Alice can measure her half with respect to the basis |0_{A}⟩ = cos(a)|0⟩ + sin(a)|1⟩, |1_{A}⟩ = − sin(a)|0⟩ + cos(a)|1⟩. Bob can carry out a similar measurement on his half using b ∈ [0, π) to define the basis |0_{B}⟩, |1_{B}⟩. For any choice of a and b as above, the probability that they obtain the same result is cos^{2}(a − b).

In the spirit of [1], we investigate the exact number of bits Alice must transmit to Bob in a classical local hidden variable model to be able to produce the same probabilistic correlation. In that paper it is shown that 4 bits suffice. In this note we demonstrate that 3 bits suffice and that at least 2 bits are necessary. The measurements described here all lie on the equator of the Poincaré sphere. Using the method described in [1], any von Neumann measurement can be resolved to two of the measurements considered here, and hence can be simulated using only 6 bits of communication.

This problem falls in the general area of classical entanglement simulation, which was investigated in [3]. In the terminology of that paper, we are concerned with the bounded communication model, in which we insist that the number of bits exchanged be uniformly bounded. The average communication model, where the number of bits needs to be bounded on average only, was investigated in [4] and refined in [5]: in that model the local hidden variables can be entirely dispensed with.

The author thanks Peter Shor, Jeff Lagarias, and an anonymous referee for helpful suggestions.

SETUP

By using a classical hidden variable scheme augmented with n bits of (one-way) communication to simulate a Bell pair, we mean

• a probability space Ω;

• for each a ∈ [0, π), and for each 0 ≤ i ≤ 2^{n} − 1, a random variable ω ↦ m_{i}^{ω}(a) on Ω; and

• for each b ∈ [0, π), and for each 0 ≤ i ≤ 2^{n} − 1, a random variable ω ↦ o_{i}^{ω}(b) on Ω. These data must satisfy the following conditions:

• for any a, b ∈ [0, π), 1 ≤ i ≤ 2^{n}, and ω ∈ Ω, we require 0 ≤ m_{i}^{ω}(a) ≤ 1 and 0 ≤ o_{i}^{ω}(b) ≤ 1;

• for any a ∈ [0, π) and ω ∈ Ω, we need ∑_{i=0}^{2^{n}−1} m_{i}^{ω}(a) = 1. The intended interpretation of this setup is that Alice and Bob have shared access (maybe in the past, before they became separated, or through using some fancy model of physics) to a sample ω ∈ Ω. Since Alice can send n bits of information to Bob, she can choose one of 2^{n} messages to send. In fact, given a ∈ [0, π), she will send the ith message with probability m_{i}^{ω}(a). Given b ∈ [0, π), if Bob receives the ith message from Alice then he will output “Same” with probability o_{i}^{ω}(b), and “Different” otherwise.^{1}

1 The letters m and o were used to denote these functions since they assist in the selection of the message and the output, respectively.

In order then to achieve the output “Same” with probability cos^{2}(a − b), regardless of the values of a and b that Alice and Bob are given, we additionally require that

∫_{Ω} ( ∑_{i=0}^{2^{n}−1} m_{i}^{ω}(a)o_{i}^{ω}(b)) dω = cos^{2}(a − b).  (1)

Remark.One might require, as was done in [1], that Alice and Bob actually output 0 or 1 to indicate the result of their measurement. This can be easily incorporated into our framework by adding a random bit z in addition to our Ω, and having Alice output z, with Bob outputting z if he would have output “Same” in the above scenario (and its opposite otherwise).

THE NON-EXISTENCE OF A 1-BIT SCHEME

We prove by reductio ad absurdum that there is no solution to the above problem with n = 1.

First of all, observe that since m_{0}^{ω}(a) and m_{1}^{ω}(a) are both non-negative and they sum to 1, for any a, b ∈ [0, π) and ω ∈ Ω we have

min(o_{0}^{ω}(b), o_{1}^{ω}(b)) ≤ ∑_{i=0}^{1} m_{i}^{ω}(a)o_{i}^{ω}(b) ≤ max(o_{0}^{ω}(b), o_{1}^{ω}(b)).

We shall also use the following lemma:

Lemma 1 Let f be a non-negative valued random variable on a probability space Ω. Then ∫_{Ω} f(ω)dω ≤ 0 implies that f(ω) = 0 on a set of probability 1 (i.e., almost surely).

Proof.For any ε > 0, let A(ε) = P(f(ω) > ε). Since ∫_{Ω} f(ω)dω > εA(ε), we conclude that A(ε) = 0. Finally, since the set where f is positive is the union for all integers n of A(2^{−n}), we conclude that f(ω) = 0 almost surely.

Variant. Using the same method as above, we can show that if g(ω) ≤ 1 and ∫_{Ω} g(ω)dω ≥ 1 then almost surely g(ω) = 1.

Now we fix b and set a = b + π/2. (Here we might need to reduce a modulo π to place it in [0, π). We shall do this here, and everywhere else in this note, without further comment.) Then, using the observation before the lemma, we get

∫_{Ω} min(o_{0}^{ω}(b), o_{1}^{ω}(b))dω ≤ cos^{2}(a − b) = 0.

Applying the lemma, we obtain that for any b ∈ [0, π), we almost surely (a.s.) have min(o_{0}^{ω}(b), o_{1}^{ω}(b)) = 0.

Similarly (using the variant of the lemma) we can see that for any b ∈ [0, π), we almost surely (a.s.) have max(o_{0}^{ω}(b), o_{1}^{ω}(b)) = 1. Therefore we can define a function s(b, ·) : Ω → {0, 1} which a.s. gives us which of the two indices i results in o_{i}^{ω}(b) = 1 for given ω and b. Using the function s to rewrite (1), we obtain

∫_{Ω} m_{s(b,ω)}^{ω}(a)dω = cos^{2}(a − b).

Setting b = a and using the variant of our lemma again, we obtain that a.s. m_{s(a,ω)}^{ω}(a) = 1. Using the fact that m_{0}^{ω}(a) + m_{1}^{ω}(a) = 1, we can conlude that m_{i}^{ω}(a) = 1 if and only if i = s(a, ω).

We can therefore rewrite (1) again to conclude that

P(s(a, ω) = s(b, ω)) = cos^{2}(a − b),

or equivalently

P(s(a, ω) ≠ s(b, ω)) = sin^{2}(a − b).  (2)

We can use (2) to derive a contradiction as follows. For any set X, the set of functions from Ω to X is endowed with a pseudometric, where the distance between f and g is P(f(ω) ≠ g(ω)). However, one can check immediately that because of (2), the functions s(0, ·), s(0.01, ·) and s(0.02, ·) do not satisfy the triangle inequality!

THE EXISTENCE OF A 3-BIT SCHEME

We shall now describe a communication protocol using only three bits that carries out our task.

The probability space Ω is chosen to be the interval [0, π/4), with a uniform probability distribution.

In this construction, m_{i}^{ω}(a) is always 0 or 1, i.e., Alice chooses her message deterministically when given a and ω. The first bit of her message is 1 if a ≥ π/2 and 0 otherwise. The second bit of her message is 1 if (a mod π/2) ≥ π/4 and 0 otherwise. The third bit of her message is 1 if (a mod π/4) < ω and 0 otherwise.

If the first bit of Alice’s message is a 1, Bob sets it to 0 and remembers to flip his final answer from “Same” to “Different” and vice versa. This works since cos^{2}(α) = 1 − cos^{2}(α + π/2) and since the rest of the bits in the message only depend on a mod π/2. Now we just have to specify o_{i}^{ω}(b) for 0 ≤ i ≤ 3. (The above argument amount to setting o_{k}^{ω}(b) = 1 − o_{k+4}^{ω}(b) for k ∈ {0, 1, 2, 3}.)

We first describe Bob’s strategy if 0 ≤ b < π/4.

Let o_{0}^{ω}(b) be 1 if b < ω and 1 − π sin(2|ω − b|)/4 otherwise. Let o_{1}^{ω}(b) be 1 if bω and 1 − π sin(2|ω − b|)/4 otherwise. Let λ ∈ [0, 1] be defined by

cos^{2}(π/2 − b) = λ(1 − cos^{2}(π/4 − b) + cos^{2}(π/2 − b)).

Then we can set o_{2}^{ω}(b) = λ(1 − π sin(2|ω − b|)/4) and o_{3}^{ω}(b) = λ + (1 − λ) sin(2|ω − b|)/4). It is then simple to check that this scheme satisfies all the conditions given.

For π/4 ≤ b < π/2, it is easy to check that o_{f(k)}^{ω}(b) = o_{k}^{ω}(b − π/4) works, where f takes 0, 1, 2, 3 to 2, 3, 4, 5, again completing the definition by setting o_{k}^{ω}(b) = 1 − o_{k+4}^{ω}(b) for k ∈ {0, 1, 2, 3}.

Finally, for π/2 ≤ b, we can set o_{k}^{ω}(b) = 1 − o_{k}^{ω}(b − π/2) for all k.

THE POSSIBLE EXISTENCE OF A 2-BIT SCHEME

Here we present a result that might be useful in deciding whether a 2-bit scheme exists. Assume now that m_{i}^{ω}(a) is always either 0 or 1 (this is not a serious restriction, as for any scheme without this restriction, we can easily contruct one with probability space Ω × [0, 1] that satisfies this restriction). Then we can construct a function s(a, ·) : Ω → {0, 1, …, 2^{n} − 1} such that m_{s(a,ω)}^{ω}(a) = 1. Then we have

Lemma 2 Given a, a′ ∈ [0, π), the distance between the functions s(a, ·) and s(a′, ·) is at least sin(|a − a′|).

Remark.Such a result might be useful in concluding that for a certain n, the space of functions Ω → {0, 1, …, 2^{n}−1} is not large enough to contain each of the functions {s(a_{i}, ·) : i ∈ I} for some cleverly chosen set {a_{i} : i ∈ I}.

Proof.Let Ω_{i} and Ω′_{j} denote the parts of Ω where s(a, ω) = i and s(a′, ω) = j, respectively. With this notation,

(1) takes the form

∑_{i=0}^{2^{n}−1} ∫_{Ω_{i}} o_{i}^{ω}(b)dω = cos^{2}(a − b).

Applying this to a and a′ (with the same b) and taking the difference, we conclude that

cos^{2}(a − b) − cos^{2}(a′ − b) ≤ ∑_{i=0}^{2^{n}−1} ∫_{Ω_{i}\Ω′_{i}} o_{i}^{ω}(b)dω.

Since o_{i}^{ω}(b) ≤ 1, we can conclude that

cos^{2}(a − b) − cos^{2}(a′ − b) ≤ ∑_{i=0}^{2^{n}−1} ∫_{Ω_{i}\Ω′_{i}} 1dω = P(s(a, ω) ≠ s(a′, ω)).

Choosing b appropriately, the left hand side of the above inequality is maximized at sin(|a − a′|). This concludes the proof of our lemma.

[1] G. Brassard, R. Cleve, and A. Tapp, Physical Review Letters 83, 1874 (1999), also available as quant-ph/9901035.

[2] J. S. Bell, Physics 1, 195 (1964).

[3] S. Massar, D. Bacon, N. Cerf, and R. Cleve, Physical Reviews A 63, Article 052305 (2000), also available as

   quant-ph/0009088.

[4] M. Steiner, in Proc. of 29th Winter Colloquium on the Physics of Quantum Electronics, Snowbird, Utah, 1999 (1999), also

   available from quant-ph/9902014.

[5] N. Cerf, N. Gisin, and S. Massar, Physical Review Letters 84, 2521 (2000).