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.
- Choose an edge incident with the vertex of the piece
- Decrease the value of this edge to any strictly smaller non-negative integer.
- 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.