Quantum-Assisted Graph Domination Games

Quantum entanglement allows for correlations between distant objects that go beyond any classical theory. These additional correlations can be exploited to gain practical advantage in certain non-local games. In recent years there has been interest in games defined on graph structures and involving mobile agents. One of these is the graph domination game, where quantum advantage has been discovered recently on some finite graphs by numerical optimization [1]. Here we study quantum advantage in the 1-step, 2-player version of this game, focusing on cycle graphs. We study it numerically, analytically and through the use of noisy, intermediate scale quantum (NISQ) processors. We find explicit strategies and show that they realise the numerical bounds that were found recently for the case of small graphs [1]. We then generalise our strategies to cycles of arbitrary size. Finally, we run our strategies for 5-, 6-, and 7-site cycles on NISQ hardware and find measurable advantage (compared to the optimal classical strategies) in all cases.