3
$\begingroup$

I am interested in combinatorial game theory & was doing some research on quantum combinatorial games. This lead me to wondering how a quantum computer might be able to perform nimber arithmetic (perhaps as a part of a game playing AI).

I am aware of the fact that nim sums are equivalent to bitwise XOR & that XOR correlates to CNOT, which is why it seems resonable to me that a quantum computer would be able to perform calculations with nimbers.

How could a quantum computer perform nimber arithmetic?

Improve this question
$\endgroup$
  • 2
    $\begingroup$ Why is this being downvoted? $\endgroup$ – psitae Dec 26 '18 at 23:21
  • 5
    $\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
  • 3
    $\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$ – user820789 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
5
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\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$ – user820789 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
2
+50
$\begingroup$

It is relevant to consider the following research paper from Mashiko Fukiyama on Nim Game on Graph to come up with an algorithmic approach . At first, to set a starting position of the game, we fix some finite undirected graph and assign to each edge a non-negative integer. Further we take one piece and put it at a vertex of the graph. From this given position, the game starts and proceeds by the two players’ alternate moves with the series of choices.

  1. Choose an edge incident with the vertex of the piece
  2. Decrease the value of this edge to any strictly smaller non-negative integer.
  3. Move the piece to the adjacent vertex along this edge.

The game ends when a player in his turn cannot move since the value of each edgeincident with the piece’s vertex is equal to zero. Then, according to the normal play convention, this player is taken as the loser.

This approach outlines scenarios when any graph of the game forms a bipartite graph without multiple edges except in a few conditions. Following MathOverflow discussion also explores the strategies when a Nim game is modelled on a bipartite graph. Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge and pick up some of the matchsticks in the nim heap corresponding to that edge. If all of the edges meeting the vertex containing the vertex are empty when you start your turn, you lose.

At this juncture, it is worth noting that bipartite graphs have recently been used in quantum information theory, e.g. for obtaining graph states to describe entanglement and for obtaining quantum walks for quantum search programs as outlined in the following paper on the Graph Approach to Quantum Systems. In addition a bipartite graph approach is also considered useful to model span programs, quantum walks, and quantum search. There are also other models of quantum information fields by means of hyper-graphs and lattices.

A bipartite entanglement of the states constructed from the algebra of a finite group with a bi-local representation acting on a separable reference state has been studied recently. If G is a group of spin flips acting on a set of qubits, these states are locally equivalent to bipartite (two-colorable) graph states and they include GHZ, CSS, cluster states, etc. Equivalence of CSS states (of which GHZ states are a special case) and bipartite graph states has been proved recently. The graph states form class of multipartite entangled states associated with combinatorial graphs which helps us to integrate a bipartite graph based quantum combinatorial game theoretical approach to Nim game.

Thus we can devise a quantum combinatorial game to implement Nim game on graph using the algorithms outlined in this research paper on Dynamic Programming based Quantum Graph Partitioning. It is an approach to convert a quantum circuit into a bipartite graph model, and then using a dynamic programming approach (DP) to partition the model into low-capacity quantum circuits. This dynamic programming based partitioning approach helps to minimise the connection between the parts in the circuit. In the algorithm to convert the quantum circuit into the graph, Qubits are in one part of bipartite graph G and gates are in other parts.

This approach is quite suited from a quantum game theoretic perspective where we superpose and entangle initial states. As explained earlier bipartite graph states would help us to initialise the quantum combinatorial game states. The following research paper on Oscillatory localisation of Quantum Walks can help also us in realising quantum combinatorial games. Oscillatory localisation produces a discrete- time quantum walk with Grover’s diffusion coin jumping back and forth between two vertices.

Improve this answer
$\endgroup$

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.