Demonstration of a Quantum Graph Coloring Game on a Trapped Ion Quantum Computer

In a graph coloring game, two players color vertices of a graph such that adjacent vertices are not given the same color. In the quantum version, the two players share an entangled state and pick colors by measuring their subspace in different bases. We demonstrate a quantum graph coloring game on a trapped ion computer with a graph where the optimal quantum strategy outperforms all classical strategies. We run 88 four-qubit circuits to obtain an experimental win rate of the optimal quantum strategy and compare with the theoretical quantum and classical win rate.