Finding the optimal Nash equilibrium in a discrete Rosenthal congestion game using the Quantum Alternating Operator Ansatz

Abstract

This paper establishes the tractability of finding the optimal Nash equilibrium, as well as the optimal social solution, to a discrete congestion game using a gate-model quantum computer. The game is of the type originally posited by Rosenthal in the 1970's. To find the optimal Nash equilibrium, we formulate an optimization problem encoding based on potential functions and path selection constraints, and solve it using the Quantum Alternating Operator Ansatz. We compare this formulation to its predecessor, the Quantum Approximate Optimization Algorithm. We implement our solution on an idealized simulator of a gate-model quantum computer, and demonstrate tractability on a small two-player game. This work provides the basis for future endeavors to apply quantum approximate optimization to quantum machine learning problems, such as the efficient training of generative adversarial networks using potential functions.