April 2021

a:3:{s:6:"locale";s:5:"en_US";s:3:"rtl";i:0;s:9:"flag_code";s:2:"us";}
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

Program Committee delivers “Agenda Quantum Systems 2030” to Federal Research Minister Karliczek in Berlin – Professor Dr. Claudia Linnhoff-Popien’s participation honored

Program Committee delivers “Agenda Quantum Systems 2030” to Federal Research Minister Karliczek in Berlin – Professor Dr. Claudia Linnhoff-Popien’s participation honored

(Berlin/Munich) The spokespersons of the Quantum Systems Program Committee delivered the “Quantum Systems 2030” research agenda to the Federal Minister of Education and Research Anja Karliczek on March 23, 2021.
This presentation of the research agenda on March 23 took place mainly virtually and was streamed live from the Berlin Office of the Federal Ministry of Education and Research. The two program committee spokespersons, Professor Dr. Immanuel Bloch and Dr.-Ing. E. h. Peter Leibinger, delivered the “Agenda Quantum Systems 2030” and addressed the most important recommendations for action.
In a personal letter to Professor Dr. Claudia Linnhoff-Popien, Federal Research Minister Karliczek expressed her satisfaction that the quantum systems agenda process had come to a successful conclusion after a ten-month work phase and thanked her for her commitment.
Prof. Dr. Claudia Linnhoff-Popien, Head of the Chair of “Mobile and Distributed Systems” at the Institute of Informatics at LMU Munich, is a member of the Quantum Computing Panel of Experts. In order to develop a common national strategy for quantum computing, the Federal Government commissioned a 16-member panel of high-ranking experts from the worlds of business and science in the summer of 2020 to identify the key challenges in this field and to make recommendations for future action. This panel developed the “Quantum Computing Roadmap” that it presented in January 2021. For the roadmap, Linnhoff-Popien contributed significant insights from IT to the application of quantum computing.

LMU Munich’s QAR-Lab – Many years of expertise in quantum computing

Claudia Linnhoff-Popien has headed the Quantum Applications and Research Laboratory (QAR-Lab) at LMU since 2016. Numerous scientists are researching quantum computing and quantum-assisted artificial intelligence there. The QAR-Lab uses the quantum hardware from four major vendors to program quantum computing use cases for business.
Federal Research Minister Karliczek said that she and her ministry would like to use the research priorities and recommendations identified as a basis for developing a new and long-term “quantum systems” funding program. Many experts from the worlds of business and science have contributed to the entire process in various formats. The resulting research agenda, which is available to the specialist community, was delivered on March 23. It sets out the research priorities and challenges for a period of about ten years and identifies guidelines for business, science, and politics to act in concert.
IT expert Claudia Linnhoff-Popien is pleased to be involved in the process: “We conduct basic research and use this knowledge in practice as well. We support our partners in quantum computing and test the largest number of quantum computers in Europe in the QAR-Lab. That is how we know which quantum hardware is best suited to which challenges in a company. We calculate relevant cases on the machines and focus on optimization scenarios, such as for logistics or production processes.”

  • More on the research agenda can be found at www.quantentechnologien.de.
  • More about the quantum computing panel of experts’ roadmap can be found here.