A Grover based Quantum Algorithm for Finding Pure Nash Equilibria in Graphical Games

Roch, Christoph; Londono Castillo, Santiago und Linnhoff-Popien, Claudia (2022): A Grover based Quantum Algorithm for Finding Pure Nash Equilibria in Graphical Games. 19th International Conference on Software Architecture Companion (ICSA-C), Online, 12-15 March 2022. In: 2022 IEEE 19th International Conference on Software Architecture Companion (ICSA-C), Piscataway, NJ: IEEE. S. 147-151

Abstract

The Grover algorithm and its underlying amplitude amplification process are one of the most essential and widely used building blocks of many other subsequent quantum methods. In this work, we adapt Grover’s search algorithm to find pure Nash equilibria in graphical games. In general, the main complexity lies in the construction of the algorithm’s oracle operator. We show how to set up the oracle from a given graphical game by translating it to a Boolean satisfiability problem, which can subsequently be logically synthesized to an oracle quantum circuit. We investigate the algorithm for random graphical game instances on IBM’s quantum simulator and give an outlook regarding the scaling of it.

• Dokumententyp: Konferenzbeitrag (Paper)
• Fakultät: Mathematik, Informatik und Statistik > Informatik
• Themengebiete: 000 Informatik, Informationswissenschaft, allgemeine Werke > 004 Informatik
• Ort: Piscataway, NJ
• Bemerkung: ISBN 978-1-6654-9493-9
• Sprache: Englisch