In a nonlocal game, two noncommunicating players cooperate to convince a referee that they possess a strategy that does not violate the rules of the game. Quantum strategies allow players to optimally win some games by performing joint measurements on a shared entangled state, but finding these strategies can be challenging. In this talk, we will provide an overview of some interesting nonlocal games on graphs and discuss a variational algorithm for computing these quantum strategies. When applied to a specific graph, our algorithm was able to generate a novel short-depth circuit that implements a perfect quantum strategy, i.e. strategy that utilizes entanglement as a resource to win the game with probability one. We will argue how these quantum strategies can act as high-level benchmarks of quantum devices since these strategies require the ability to generate an entangled resource state followed by precise control of a set of measurements for their successful execution. Finally, we will discuss recent results and challenges when running these quantum strategies on superconducting and ion-trap quantum devices, as well as outline some future research directions.