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 条
[1]  
Aaronson S., 2020, S SIMPL ALG, P24
[2]  
Aleksandrowicz Gadi, 2019, Qiskit: An open-source framework for quantum computing
[3]   Quantum circuit optimization using quantum Karnaugh map [J].
Bae, J-H ;
Alsing, Paul M. ;
Ahn, Doyeol ;
Miller, Warner A. .
SCIENTIFIC REPORTS, 2020, 10 (01)
[4]  
Bhat NavinA. R., 2004, P 20 C UNCERTAINTY A, P35
[5]  
Boyer M, 1998, FORTSCHR PHYS, V46, P493, DOI 10.1002/(SICI)1521-3978(199806)46:4/5<493::AID-PROP493>3.0.CO
[6]  
2-P
[7]  
Brassard G., 2002, CONTEMP MATH, V305, P53, DOI [10.1090/conm/305/05215, DOI 10.1090/CONM/305/05215]
[8]   Applying quantum algorithms to constraint satisfaction problems [J].
Campbell, Earl ;
Khurana, Ankur ;
Montanaro, Ashley .
QUANTUM, 2019, 3
[9]  
Carfi D., 2011, Journal of Advanced Studies in Finance, P4
[10]  
Cerf NJ, 1998, Arxiv, DOI arXiv:quant-ph/9806078
1234