Calculating Nash Equilibrium on quantum annealers

Abstract Adiabatic quantum computing is implemented on specialized hardware using the heuristics of the quantum annealing algorithm. To solve a problem using quantum annealing,the problem requires the formatting as a discrete quadratic function without constraints. The problem of finding Nash equilibrium in two-player, non-cooperativegames is a two-fold quadratic optimization problem with constraints. This problem was formatted as a single, constrained quadratic optimization in 1964 by Mangasarianand Stone. Here, we show that adding penalty terms to the quadratic function formulation of Nash equilibrium gives a quadratic unconstrained binary optimization(QUBO) formulation of this problem that can be executed on quantum annealers. Three examples are discussed to highlight the success of the formulation, and an overall,time-to-solution (hardware + software processing) speed up by seven to ten times is reported on quantum annealers developed by D-Wave System.