I am interested in quantum combinatorial games.

According to the Wikipedia page on the Sprague-Grundy theorem:

Every impartial game under the normal play convention is equivalent to a nimber

An impartial game is one in which at any given point in the game, each player is allowed exactly the same set of moves

Based on my understanding at this point, the CHSH game is an impartial game (Alice & Bob can both make the same sets of measurements).

I am curious how to realize both nim sums (which are equivalent to XOR, which correlates to CNOT) & nim multiplication for the analysis of quantum XOR games such as CHSH.

  • 1
    $\begingroup$ Why is this being downvoted? $\endgroup$ – psitae Dec 26 '18 at 23:21
  • 3
    $\begingroup$ Perhaps because it's not clear why this is interesting in relation to quantum computers. The OP handwaves at a connection between Nim and Simon's problem, as both depend on some property of parity (but not the same property), and then asks whether a quantum computer can quickly solve some third thing which is Nim related. The only motivation is that Nim is a subject in pop-math with some name recognition, and that the math involved looks very vaguely similar. One could pose a thousand similar problems, none providing any insight. Which raises the question: what makes this problem interesting? $\endgroup$ – Niel de Beaudrap Dec 27 '18 at 14:35
  • 2
    $\begingroup$ One way to improve this question might be to fill in the details which suggests a convincing link. Unless we expect that "nimber theory" is a hot topic amongst quantum information theorists, its not really appropriate to ask us to do all of the background investigation for someone else's problem, without some other motivation. $\endgroup$ – Niel de Beaudrap Dec 27 '18 at 14:56
  • $\begingroup$ @NieldeBeaudrap I have attempted to improve the question by filling in more details. $\endgroup$ – meowzz Dec 28 '18 at 2:36
  • 1
    $\begingroup$ The OP would probably find this paper interesting. arxiv.org/abs/1501.00458 $\endgroup$ – Jalex Stark Dec 28 '18 at 15:34

Nonlocal games such as the CHSH game are not impartial games in the sense of Sprague-Grundy. Alice and Bob are thought to be cooperating rather than competing, and randomness is central to the study of nonlocal games. Impartial games are competitive, deterministic, and perfect information.

A good sanity check when asking about quantizing some classical object is to first see whether it can be meaningfully randomized.

  • $\begingroup$ Excellent! Are CHSH games partisan (I would think not based on the cooperating vs. competing logic)? My understanding is that there isn't a large amount of work on cooperative game theory in general - however "cooperative games can be analyzed through the approach of non-cooperative game theory " (Wikipedia). Additionally, do you have any thoughts on the idea of CHSH games being a 2 person puzzle (see here for info on 1 player games - aka puzzles)? $\endgroup$ – meowzz Dec 28 '18 at 18:39
  • 2
    $\begingroup$ One thing you may find interesting to try in search of competitive quantum games: see how one can think of an impartial game as a walk through a directed graph of game states, where the players alternate taking turns to pick an edge to walk on. Generalize this notion so that the "current state of the game" is a probability distribution over nodes in the digraph and moves are probabalistic transitions. Can you use Sprague--Grundy to say anything interesting about these games? If so, try promoting the state space to a Hilbert space. See the literature on "quantum walks" for ideas. $\endgroup$ – Jalex Stark Dec 31 '18 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.