I just started reading a beautiful paper by Ben Reichardt, Falk Unger, and Umesh Vazirani that recently appeared on the arXiv, with the tongue-in-cheek title “A classical leash for a quantum system” (and the maybe less entertaining subtitle “Command of quantum systems via rigidity of CHSH games”). This paper motivated me to write a series of posts on the topic of entanglement in multiplayer games.
Since I should start with the beginning, in this first post I will introduce the CHSH game, trying to make it (somewhat) accessible to those of you not familiar either with “entangled games” or “Bell inequalities”. In the next post I plan to discuss the second half of the subtitle of the RUV paper, the rigidity theorem for the CHSH game. I might then discuss the connection between this rigidity and the so-called monogamy of entanglement and its use in device-independent cryptography, or move on to the first half of the RUV paper.
Before we get started, a disclaimer: unless you happen to own a lab with state-of-the-art lasers and photon detectors, the CHSH game is not going to be such a fun game to play! However, if, as Alain Aspect did around the time I was born, you do happen to have such a lab, then you are guaranteed to be stunned — and, who knows, maybe you’ll even end up with the Nobel prize! In fact, Aspect apparently did narrowly miss the physics prize last year. This year’s favorites include Bennett, Brassard and Wooters for their invention of “quantum teleportation”, so it might still turn out to be a good year for nonlocality…watch fort the announcement in just a week.
1. The CHSH inequality
The CHSH game (or, as it was orignially phrased, inequality) is named after its inventors Clause, Horne, Shimony and Holt, themselves building on the work of John Bell in the early 1960s. Bell was the first to propose a convincing mathematical formulation of the famous EPR thought experiment, neatly exhibiting the tension between the predictions of quantum mechanics and the seeming “spooky action-at-a-distance” that Einstein, Podolsky and Rosen took for a paradox. Bell’s theorem states that quantum mechanics is incompatible with the assumption of local realism: no theory which ascribes a independent values (or distributions) to spatially isolated observable quantities can reproduce the predictions of quantum mechanics. In other words, the “spooky action at a distance” denounced by EPR is not a witness of the incompleteness of quantum mechanics, but instead, if one is to believe the experiments done by Aspect (and others after him), it is a necessary feature of the theory! As we will see, however, there is nothing “spooky” about this, and quantum mechanics does not allow faster-than-light communication.
Clauser, Horne, Shimony and Holt obtained what is in many ways the simplest possible formulation of Bell’s theorem. They gave a simple inequality, accompanied by the description of a (mathematically) straightforward experiment, such that quantum mechanics predicts that the results of the experiment should violate the inequality. Furthermore, any theory satisfying the assumption of local realism must give predictions that satisfy the inequality! This raised for the first time the possibility for an experimental demonstration of the nonlocal behavior of quantum mechanics, a demonstration which was achieved by Aspect a little over 10 years later.
where here a quantity such as describes the expected (over the probability space describing the theory, or, more pragmatically, many repetitions of the experiment) product of the outcomes obtained by observing the quantity on the first isolated system, and on the second.
2. So, where’s the game?
The content of Eq. (1) can be reformulated as a game, the CHSH game, involving two players, Alice and Bob, and a referee. Alice and Bob have infinite wisdom, but for one fundamental limitation: whatever they do, they must act locally. For example, picture Alice on Venus, Bob on Mars, and the whole game happens so fast that there is no way they can exchange any information between them for the duration of the game.
The referee runs the game as follows. He first picks a random question for each player: bits for Alice and for Bob. Each player receives his or her question privately, and is required to produce an answer: for Alice and for Bob. The players win the game if and only if the parity of their answers equals the and of their questions: .
I warned you it wasn’t going to be too much of a fun game to play… In any case, how well can Alice and Bob do? Well, we can try out different strategies. For instance, noticing that for all but the pair of questions the game constraint states that , Alice and Bob could decide on a lazy strategy, in which they both always answer : they’ll succeed with probability on average over the referee’s choice of questions. Any better ideas?
As it turns out, there is not much else the players can do, as can be checked by exhaustively searching over all possible strategies (note that shared randomness between the players cannot help). Hence it is impossible for non-communicating players to win in the CHSH game with probability larger than 75%. Or is it?
3. An entangled strategy
As shown by Clauser et al., there is a quantum strategy for Alice and Bob that succeeds with probability , or slightly over ! Moreover, this strategy is local: Alice and Bob only perform quantum operations on their respective quantum systems, the one on Venus and the other on Mars. Hence their strategy does not violate special relativity: they are able to beat the bound without communicating.
Puzzled? Einstein, Podolsky and Rosen were too! The CHSH game demonstrates that quantum mechanics is nonlocal: by performing measurements on an entangled state, spatially isolated players can produce correlations that cannot be expressed as convex combinations of product distributions (i.e. they cannot be reproduced by classical players using shared randomness alone). What seemed so “paradoxical” to EPR is that, while these correlations do not allow for superluminal communication, they can still be extremely useful — as concretely witnessed by the CHSH game.
For anyone who has seen quantum nonlocality in action before, this may seem boring…but it never ceases to amaze me. Here is a curious feature of the players’ quantum strategy: it has the property that, whatever pair of question Alice and Bob are asked, they will provide a pair of answers that is correct with probability . That is, their strategy is not good in some situations, worse in others: whatever happens, it is good.
In fact, the CHSH game probably hasn’t revealed all its secrets yet! Witness the recent RUV paper, that I will discuss next time. To wet your appetite, here is another interesting property of the CHSH game: there is essentially only a single strategy for the players that succeeds with probability close to the optimal . Any strategy that achieves a value close to the optimum must be “isometric” in a precise sense to a “canonical” optimal strategy, in which the players measure an EPR pair using measurements in the computational and Hadamard bases for Alice, and their -rotations for Bob. This “rigidity”, first studied by Mayers and Yao in the late 90s, is key to the many uses of the CHSH game in cryptographic contexts, such as device-independent QKD or multi-prover proof systems. I hope to return to this exciting topic in more details in upcoming posts.