Thread by @gro_tsen

CORRECTION on my thread from 2 days ago. TL;DR: every “½” should be replaced by “2⁄3” (I made a stupid counting mistake in the classical bound) with a slight change in the description of the classical gadget. The rest seems correct. Here are more details as a penance. ⤵️ •1/25

https://twitter.com/gro_tsen/status/1577286661305556993

So, as was recently pointed out to me — by “jonas” in the comments of my blog entry madore.org/~david/weblog/… — it's easy to classically make a (2/3)-gadget: randomly generate one of the six possibilities of yes/no answers for X,Y,Z which are not all equal. •2/25

More precisely, to generate a (2/3)-gadget classically, randomly choose one of the six possibilities ++−, +−+, +−−, −++, −+−, −−+, and interpret this as a yes(+)/no(−) answer for X, Y, Z common to both thingies. •3/25

Clearly this satisfies ① (because both thingies have the same hidden variables), and ② (because for every choice of two different buttons, 4/6 = 2/3 possibilities have different values). •4/25

https://twitter.com/gro_tsen/status/1577286672987099137

(The reason for my mistake was that I remembered the classical gadget was trivial to make, but I forgot to exclude the +++ and −−− possibilities, so the description below, while it correctly gives a (½)-gadget, is far from optimal.) •5/25

https://twitter.com/gro_tsen/status/1577286679265964035

This means of course that my claim that we can't make a p-gadget for p>½ was wrong. The correct claim is that we can't one for p > 2/3. But now you probably want a proof of this fact, since I had wrongly claimed that the incorrect claim was “easy”. •6/25

https://twitter.com/gro_tsen/status/1577286690561216513

Well, assume we have a probability distribution on the a priori 2⁶=64 combinations of yes/no answers that each thingy will give to each of the X/Y/Z questions. Because of ① (both gadgets must always give the same answer to the same question), … •7/25

… it must be concentrated on the 2³=8 combinations of yes/no answers to X/Y/Z common to both thingies. So we have 8 variables, p_(+++) through p_(−−−), all nonnegative and summing to 1, that define our putative gadget. •8/25

Now apply ② to the situation where we press X and Y on both thingies: we get: p_(+−+) + p_(+−−) + p_(−++) + p_(−+−) ≥ p because the LHS is the probability that we get different answers for the query. •9/25

Similarly for Y and Z we get p_(++−) + p_(+−+) + p_(−+−) + p_(−−+) ≥ p. And for X and Z we get p_(++−) + p_(+−−) + p_(−++) + p_(−−+) ≥ p. Adding these three inequalities gives 2p_(++−) + 2p_(+−+) + 2p_(+−−) + 2p_(−++) + 2p_(−+−) + 2p_(−−+) ≥ 3p. •10/25

And since the LHS is bounded by twice the sum of all the p_(ijk), it's ≤2, so 2≥3p and p ≤ 2/3, showing that classically (i.e., under local realism) we can't do better than a 2/3 gadget. ∎ This is the sort of things known as a “Bell inequality”. •11/25

So, this fixes my mistake, but now maybe you're wondering whether I didn't make a similar mistake in the quantum case: is the quantum bound of 3/4 I claimed really valid and optimal? Yes, it is, and here's why. •12/25

As to how we can make a (¾)-gadget in a quantum world, I briefly explained it here 🔽, except that I forgot to clarify that we need to flip the answer of one of the thingies. So here's a little more detail. •13/25

https://twitter.com/gro_tsen/status/1577286703340847104

We give both thingies access to the entangled state |s⟩ := (|↑↓⟩−|↓↑⟩)/√2. The first thingy will measure the first particle against one of the states |X⟩=|↑⟩, |Y⟩=(|↑⟩+√3·|↓⟩)/2 or |Z⟩=(|↑⟩−√3·|↓⟩)/2 according to which button is pressed, … •14/25

… and the second thingy will measure the second particle against one of the states |X′⟩=|↓⟩, |Y′⟩=(|↓⟩+√3·|↑⟩)/2 or |Z′⟩=(|↓⟩−√3·|↑⟩)/2. So for example if we press X on the first thingy and X′ on the second, we have ⟨X⊗X′ | s⟩ = 1/√2 … •15/25

… so probability (1/√2)² = ½ of getting two “yes” answers, and similarly ½ of getting two “no” answers; while if we press X and Y′ we have ⟨X⊗Y′ | s⟩ = 1/(2√2), so probability 1/8 of getting “yes+yes”, and similarly 1/8 for “no+no”, and 3/8 for “yes+no” or “no+yes”. •16/25

So it's just a straightforward but tedious computation that the gadget in question is indeed a (¾)-gadget, as claimed (we can simplify some computations by using rotational invariance of |s⟩, though). Doing the experiment is, of course, much more challenging! •17/25

OK, so we can make a quantum (¾)-gadget. But why can't we make one for p > 3/4 and how do I know I didn't make a mistake here like I did in the classical case? Let me prove this final fact. •18/25

Well, this time, we're looking for 6 Hermitian operators, A_X, A_Y, A_Z, B_X, B_Y, B_Z on some Hilbert space, and a state |s⟩, such that (A_i)²=1, (B_j)²=1, A_i·B_j = B_j·A_i, and ⟨A_i B_i⟩ = 1 whereas ⟨A_i B_j⟩ ≤ 1−2p if i≠j, where ⟨M⟩ abbreviates ⟨s|M|s⟩. •19/25

(To be clear, A_i is the operator associated with the observable with value +1 or −1 according to the answer given by the first thingy if we press button i, and B_j is the corresponding operator for the second thingy. And ⟨M⟩ is the expected value of M.) •20/25

Now by a result of Tsirelson which is cited in paragraph II.C.1.b (p. 13, left column, near bottom) of the survey by Brunner, Cavalcanti, Pironio &al arxiv.org/abs/1303.2849 that I already mentioned, … •21/25

… there need to exist six unit vectors v_X, v_Y, v_Z, w_X, w_Y, w_Z in a Euclidean space such that ① v_i · w_i = 1 and ② v_i · w_j ≤ 1−2p when i≠j. Condition ① gives us w_i = v_i, of course, so we are looking at just three vectors v_X, v_Y, v_Z. •22/25

… and now it's a standard and easy geometrical fact that the smallest maximal dot product we can for 2 distinct among 3 unit vectors in a Euclidean space is −1/2 by placing them 2π/3 apart (see, e.g., cstheory.stackexchange.com/q/14736/17747 — or many other places). •23/25

So 1−2p ≥ −½, so p ≤ ¾, as I had claimed. ∎

To summarize, I have proven all of these claims:
‣ classically, we can do a (2⁄3)-gadget but no better (I had erroneously claimed “½” here),
‣ quantumly, we can do a (¾)-gadget but no better.
•24/25

(And, again, 1-gadgets are conceivable, don't let you communicate faster than light, but still allow you do do weird things such as compute an arbitrary boolean function of variables split between two participants by exchanging just ONE bit.) •25/25