Shengyu Zhang, The Chinese University of Hong Kong
Abstract
Game theory studies interactions of selfish individuals with possibly conflicting interests. Since there is no reason to assume that people interacting with quantum computers are not selfish, quantum games provide a ground for understanding, reasoning and governing quantum interactions of agents with conflicting goals. Indeed, it has been an popular subject since the seminar work of Meyer (PRL'99) and Eisert, Wilkens and Lewenstein (PRL'99). Despite the rapid accumulation of literature, controversies also exist on ad hoc assumptions and unnatural setups in models. In this work, we attempt to clarity the messy picture by proposing a new model, which is arguably the most natural one for quantization of classical strategic games. Despite the simplicity, our model turns out to be rich in mathematical questions and structures.
More important differences of the present work than previous ones are the generality of the classical games under quantization and the nature of questions under investigation. All previous work on quantum strategic games considered specific games, usually of very small strategy spaces (say, of size 2 or 3), and focused on qualitative questions such as whether an advantage exists by playing quantum strategies. In contrast, we aim to study the quantization of *general* games (of growing sizes) and to address the following fundamental and *quantitative* question:
How much "advantage" can playing quantum strategies provide, if any?
We focus on equilibrium, a central solution concept in game theory, when studying the question, and two measures of the advantage are considered.
1. A natural measure is the increase of payoff. We consider natural mappings between classical and quantum states, and study how well those mappings preserve the equilibrium properties. Among other results, we exhibit a correlated equilibrium p whose quantum superposition counterpart $\sum_s \sqrt{p(s)}\ket{s}$ is far from being a quantum correlated equilibrium; actually a player can increase her payoff from almost 0 to almost 1 in a [0,1]-normalized game.
2. Another measure is the hardness of generating correlated equilibria, for which we propose to study \emph{correlation complexity}, a new complexity measure for correlation generation. We show that there are n-bit correlated equilibria which can be generated by only *one* EPR pair followed by local operation (without communication), but need at least $\log_2(n)$ classical shared random bits plus communication. The randomized lower bound can be improved to n, the best possible, assuming (even a much weaker version of) a recent conjecture in linear algebra. This provides yet another fundamental information processing task on which using quantum has an tremendous advantage. We believe that the correlation complexity, as a complexity-theoretical counterpart of the celebrated Bell's inequality, has independent interest in both physics and computational complexity theory and deserves more explorations.