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

被引：2

作者：

Roch, Christoph ^{[1
]}

Castillo, Santiago Londotio ^{[1
]}

Linnhoff-Popien, Claudia ^{[1
]}

机构：

[1] Ludwig Maximilians Univ Munchen, Inst Comp Sci, Munich, Germany

来源：

2022 IEEE 19TH INTERNATIONAL CONFERENCE ON SOFTWARE ARCHITECTURE COMPANION (ICSA-C 2022) | 2022年

关键词：

Grover Algorithm; Quantum; Nash Equilibrium; Graphical Game; Boolean Satisfiability Problem; CIRCUITS;

D O I：

10.1109/ICSA-C54293.2022.00036

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：147 / 151

页数：5

共 38 条

[11] Fast parallel circuits for the quantum Fourier transform [J].

Cleve, R ;

Watrous, J .

41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, :526-536

[12]

Daskalakis Constantinos, 2006, P 7 ACM C EL COMM, P91

[13] Pseudo-Kronecker expressions for symmetric functions [J].

Drechsler, R .

IEEE TRANSACTIONS ON COMPUTERS, 1999, 48 (09) :987-990

[14]

Fernandes D., 2019, XRDS, V26, P64, DOI DOI 10.1145/3358251

[15] Complete 3-Qubit Grover search on a programmable quantum computer [J].

Figgatt, C. ;

Maslov, D. ;

Landsman, K. A. ;

Linke, N. M. ;

Debnath, S. ;

Monroe, C. .

NATURE COMMUNICATIONS, 2017, 8

[16]

Fosel T., 2021, arXiv

[17]

Gartner, 2019, CIOS GUID QUANT COMP

[18] Pure Nash equilibria: Hard and easy games [J].

Gottlob, G ;

Greco, G ;

Scarcello, F .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2005, 24 :357-406

[19]

Grover L. K., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P212, DOI 10.1145/237814.237866

[20] Faster k-SAT Algorithms using Biased-PPSZ [J].

Hansen, Thomas Dueholm ;

Kaplan, Haim ;

Zamir, Or ;

Zwick, Uri .

PROCEEDINGS OF THE 51ST ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '19), 2019, :578-589

← 1 2 3 4 →