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.

arXiv comment11 pages, pre-print. arXiv admin note: text overlap with arXiv:1911.05296

References in corpus (11)

• Quantum Computing in the NISQ era and beyond
• Ising formulations of many NP problems
• A Quantum Approximate Optimization Algorithm
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum generative adversarial learning
• Quantum generative adversarial networks
• Efficient GAN-Based Anomaly Detection
• Complexity Results about Nash Equilibria
• Adversarial quantum circuit learning for pure state approximation
• Analysis of Quantum Approximate Optimization Algorithm under Realistic Noise in Superconducting Qubits
• Generative Adversarial Networks for Financial Trading Strategies Fine-Tuning and Combination