.comment-link {margin-left:.6em;}

2Physics Quote:
"Many of the molecules found by ROSINA DFMS in the coma of comet 67P are compatible with the idea that comets delivered key molecules for prebiotic chemistry throughout the solar system and in particular to the early Earth increasing drastically the concentration of life-related chemicals by impact on a closed water body. The fact that glycine was most probably formed on dust grains in the presolar stage also makes these molecules somehow universal, which means that what happened in the solar system could probably happen elsewhere in the Universe."
-- Kathrin Altwegg and the ROSINA Team

(Read Full Article: "Glycine, an Amino Acid and Other Prebiotic Molecules in Comet 67P/Churyumov-Gerasimenko"

Sunday, February 22, 2015

Nonlocality and Conflicting Interest Games

[From Left to Right] Anna Pappa, Niraj Kumar, Thomas Lawson, Miklos Santha, Shengyu Zhang, Eleni Diamanti, Iordanis Kerenidis

Authors: Anna Pappa1,2, Niraj Kumar1,3, Thomas Lawson1, Miklos Santha2,4, Shengyu Zhang5, Eleni Diamanti1, Iordanis Kerenidis2,4

1LTCI, CNRS–Télécom ParisTech, Paris, France, 
2LIAFA, CNRS–Université Paris 7, France, 
3Indian Institute of Technology, Kanpur, India, 
4CQT, National University of Singapore, Singapore, 
5Department of Computer Science and Engineering and ITCSC, The Chinese University of Hong Kong, Shatin, Hong Kong.

Nonlocality is a fundamental property of quantum mechanics that has puzzled researchers since the early formulations of quantum theory. Consider two parties, Alice and Bob, with inputs xA and xB respectively, who are positioned far from each other, and are asked to produce one output each (yA for Alice and yB for Bob). Even if the two players have pre-agreed on some local hidden variables, there exist quantum correlations that cannot be reproduced by any such set of variables [1,2]. These correlations allow the two parties to perform several computational tasks more efficiently, e.g. they can win specific games with probabilities strictly higher than allowed by any classical theory.

Till now, all known examples of quantum games considered players that have common interests, meaning that they either jointly win or lose the game. A famous such example is the CHSH game [3; CHSH stands for first letters of last names of the authors of this paper], where the players win if their outputs are different when both input bits are equal to 1, and if they are the same otherwise. It can be shown that classical resources provide a winning probability of 0.75, while the sharing of a maximally entangled pair can boost the winning probability to approximately 0.85. Another important type of games is conflicting interest games. A typical example is the “Battle of the Sexes”, where Alice and Bob want to meet, but Alice wants to go to the ballet, while Bob prefers theater. In case both go to the ballet, Alice is very pleased and Bob is fine with it; if they go to the theater, Bob is very pleased and Alice is fine with it, while if they go to different places, they are both very unhappy.

In our recent work [4], we examine whether the nonlocal feature of quantum mechanics can offer an advantage similar to the one observed in the CHSH game, but for games with conflicting interests. In order to observe a quantum advantage, we will study games with incomplete information (or Bayesian games), where each party receives some input unknown to the other party [5]. We present a Bayesian game with conflicting interests, and we show that there exist quantum strategies with average payoff for the two players strictly higher than that allowed by any classical strategy. The payoffs of the players for different inputs can be viewed as a table: the rows correspond to the outputs/actions of Alice (yA), while the columns to the outputs/actions of Bob (yB).
The players are interested in maximizing their average payoff over the probability distribution of their inputs, and they may use some advice from a third party (source) in order to achieve their goal. This advice can be in the form of classical bits or quantum states. In general, the classical bits received by the two players can be correlated between them (for example they can be either 00 or 11), and the quantum states may be entangled. By examining all possible strategies with classical advice, it is not difficult to verify that in our game, the sum of the average payoffs of the two players cannot be more than 1.125.

On the other hand, if we consider the case where quantum advice is given to the two players in the form of a maximally entangled state (Bell pair), the players can use projective measurements on their part of the state [6], in order to boost the sum of their average payoffs to 1.28, which is higher than any strategy with classical advice can achieve. It is very interesting to note here that the strategy that attains this payoff is also a quantum equilibrium, meaning that no player can gain a higher payoff by choosing a different strategy unilaterally.

Finally, we have demonstrated our game in practice, using the commercial entangled photon source quED by QuTools and taking a large number of independent runs of the game, in order to estimate each player’s average payoff. We found that the joint payoff is 1.246, which is well above the classical bound of 1.125, and slightly below the maximum value allowed by quantum strategies (1.28), because of experimental noise.

In conclusion, we demonstrated that the nonlocal feature of quantum mechanics can offer an advantage in a scenario where the two parties have conflicting interests. We examined a Bayesian game that attains higher payoffs for both players when using quantum advice compared to any classical strategy, and we experimentally verified the quantum advantage, by playing the game using a commercial photon source.

[1] John Bell, "On the Einstein Podolsky Rosen paradox". Physics, 1, 195-200 (1964). Full Article.
[2] Nicolas Brunner, Daniel Cavalcanti, Stefano Pironio, Valerio Scarani, Stephanie Wehner, “Bell nonlocality”, Review of Modern Physics, 86, 419 (2014). Abstract.
[3] John F. Clauser, Michael A. Horne, Abner Shimony, Richard A. Holt, “Proposed Experiment to Test Local Hidden-Variable Theories”. Physical Review Letters, 23, 880–884 (1969). Abstract.
[4] Anna Pappa, Niraj Kumar, Thomas Lawson, Miklos Santha, Shengyu Zhang, Eleni Diamanti, Iordanis Kerenidis, "Nonlocality and Conflicting Interest Games", Physical Review Letters, 114, 020401 (2015). Abstract.
[5] J. C. Harsanyi, Management Science, 14 (3), 159-183 (Part I), 14 (5): 320-334 (Part II), 14 (7): 486-502 (Part III) (1967/1968).
[6] Richard Cleve, Peter Høyer, Ben Toner, John Watrous, "Consequences and limits of nonlocal strategies", Proceedings of the 19th Annual IEEE Conference on Computational Complexity, pages 236–249 (2004). Full Article.



Post a Comment