April 2021

a:3:{s:6:"locale";s:5:"de_DE";s:3:"rtl";i:0;s:9:"flag_code";s:2:"de";}
A Quantum Annealing Algorithm for Finding Pure Nash Equilibria in Graphical Games

A Quantum Annealing Algorithm for Finding Pure Nash Equilibria in Graphical Games

Christoph Roch, Thomy Phan, Sebastian Feld, Robert Müller, Thomas Gabor, Carsten Hahn, Claudia Linnhoff-Popien
Abstract

We introduce Q-Nash, a quantum annealing algorithm for the NP-complete problem of finding pure Nash equilibria in graphical games. The algorithm consists of two phases. The first phase determines all combinations of best response strategies for each player using classical computation. The second phase finds pure Nash equilibria using a quantum annealing device by mapping the computed combinations to a quadratic unconstrained binary optimization formulation based on the Set Cover problem. We empirically evaluate Q-Nash on D-Wave’s Quantum Annealer 2000Q using different graphical game topologies. The results with respect to solution quality and computing time are compared to a Brute Force algorithm and the Iterated Best Response heuristic.

Published in 20th International Conference on Computational Science (ICCS 2020), 2020, p. 12. doi:10.1007/978-3-030-50433-5_38

PDF Download

„Agenda Quantensysteme 2030“ vom Programmausschuss an Bundesforschungsministerin Karliczek in Berlin übergeben

„Agenda Quantensysteme 2030“ vom Programmausschuss an Bundesforschungsministerin Karliczek in Berlin übergeben – Mitwirkung von Professorin Dr. Claudia Linnhoff-Popien gewürdigt

(Berlin/München) Am 23. März 2021 wurde die Forschungsagenda „Quantensysteme 2030“ von den Sprechern des Programmausschusses Quantensysteme an die Bundesministerin für Bildung und Forschung Anja Karliczek überreicht.
Die Übergabe der Forschungsagenda am 23. März fand vorwiegend virtuell statt und wurde live aus dem BMBF in Berlin gestreamt. Die beiden Sprecher des Programmausschusses, Professor Dr. Immanuel Bloch und Dr.-Ing. E. h. Peter Leibinger konnten die „Agenda Quantensysteme 2030“ übergeben und die wichtigsten Handlungsempfehlungen ansprechen.
Bundesforschungsministerin Karliczek freute sich vorab in einem persönlichen Schreiben an Professorin Dr. Claudia Linnhoff-Popien, dass der Agendaprozess Quantensysteme nach einer zehnmonatigen Arbeitsphase zu einem erfolgreichen Abschluss gekommen sei und dankte ihr für ihr Engagement.
Prof. Dr. Claudia Linnhoff-Popien, Leiterin des Lehrstuhls „Mobile und Verteilte Systeme“ am Institut für IT der LMU München, ist Mitglied im Expertenrat Quantencomputing. Um eine gemeinsame nationale Strategie für Quantencomputing zu erarbeiten, hatte die Bundesregierung im Sommer 2020 ein 16-köpfiges Gremium aus hochrangigen Expertinnen und Experten aus Wirtschaft und Wissenschaft beauftragt, die zentralen Herausforderungen in diesem Feld zu benennen und Handlungsempfehlungen für das zukünftige Vorgehen auszusprechen. Dieses Gremium hatte die „Roadmap Quantencomputing“ erarbeitet und im Januar 2021 vorgestellt. Linnhoff-Popien hatte dabei in der Roadmap wesentliche Erkenntnisse seitens IT zur Anwendung des Quantencomputings beigesteuert.

QAR-Lab der LMU München – Langjährige Expertise in Quantencomputing

Claudia Linnhoff-Popien leitet seit 2016 das Quantum Applications and Research Laboratoy (kurz QAR-Lab) an der LMU. Dort forschen zahlreiche Wissenschaftler im Bereich Quantencomputing und Quantenunterstützte Künstliche Intelligenz. Das QAR-Lab nutzt die Quantum-Hardware von vier großen Anbietern, um Quantum Computing Use Cases für die Wirtschaft zu programmieren.
Bundesforschungsministerin Karliczek sagte, dass sie und ihr Ministerium die herausgearbeiteten Forschungsprioritäten und Empfehlungen nutzen möchten, um auf dieser Grundlage ein neues und langfristig angelegtes Förderprogramm „Quantensysteme“ zu entwickeln. In den gesamten Prozess haben sich in unterschiedlichen Formaten viele Expertinnen und Experten aus Wirtschaft und Wissenschaft eingebracht; als Ergebnis liegt die nun am 23. März überreichte Forschungsagenda der Fachcommunity vor, die für einen Zeitraum von ca. zehn Jahren die Forschungsprioritäten und Herausforderungen darlegt und Leitlinien für das gemeinsame Handeln von Wirtschaft, Wissenschaft und Politik benennt.
IT-Expertin Claudia Linnhoff-Popien freut sich über die Mitwirkung im Prozess: „Wir machen Grundlagenforschung und nutzen dieses Wissen auch in der Praxis. Wir unterstützen unsere Partner beim Quantencomputing und testen im QAR-Lab deutschlandweit einzigartig die größte Anzahl an Quantencomputern. Deshalb wissen wir, welche Quantenhardware für welche Herausforderungen in einem Unternehmen am geeignetsten sein kann. Wir rechnen auf den Maschinen relevante Cases und konzentrieren uns schwerpunktmäßig auf Optimierungsszenarien, etwa von Logistik oder Produktionsabläufen.“