The Game Theory in Quantum Computers: A Review.

Raquel Pérez Antón; José Ignacio López Sánchez; Alberto Corbi Bellot

doi:10.9781/ijimai.2023.09.001

Authors

Raquel Pérez Antón Universidad Internacional De La Rioja
José Ignacio López Sánchez Universidad Internacional De La Rioja
Alberto Corbi Bellot Universidad Internacional De La Rioja

DOI:

https://doi.org/10.9781/ijimai.2023.09.001

Keywords:

Nash Equilibrium, Polynomial Time Quantum Problems, Quantum, Computing, Game Theory

Abstract

Game theory has been studied extensively in recent centuries as a set of formal mathematical strategies for optimal decision making. This discipline improved its efficiency with the arrival, in the 20th century, of digital computer science. However, the computational limitations related to exponential time type problems in digital processors, triggered the search for more efficient alternatives. One of these choices is quantum computing. Certainly, quantum processors seem to be able to solve some of these complex problems, at least in theory. For this reason, in recent times, many research works have emerged related to the field of quantum game theory. In this paper we review the main studies about the subject, including operational requirements and implementation details. In addition, we describe various quantum games, their design strategy, and the used supporting tools. We also present the still open debate linked to the interpretation of the transformations of classical algorithms in fundamental game theory to their quantum version, with special attention to the Nash equilibrium.

Downloads

Download data is not yet available.

References

J. Von Neumann and O. Morgenstern, Theory of games and economic behavior (commemorative edition), Princeton university press, 2007.

D. P. DiVincenzo, “The physical implementation of quantum computation,” Fortschritte der Physik Progress of Physics, vol. 48, no. 9–11, pp. 771–783, 2000.

H. Guo, J. Zhang, and G. J. Koehler, “A survey of quantum games,” Decision Support Systems, vol. 46, no. 1, pp. 318–332, 2008.

W. Poundstone, El dilema del prisionero: John Von Neumann, la teoría de juegos y la bomba, CDU 519.8., S.A., 1995.

C. E. Shannon, “A chess-playing machine,” Scientific American, vol. 182, no. 2, pp. 48–51, 1950.

A. M. Turing, “On computable numbers, with an application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, vol. 2, no. 1, pp. 230–265, 1937.

A. M. Turing, “Intelligent machinery,” NPL. Mathematics Division, 1948. [8] D. Gallardo López, I. Lesta Pelayo, P. Arques Corrales, Introducción a la teoría de la computabilidad. 2003.

J. Hartmanis and R. E. Stearns, “On the computational complexity of algorithms,” Transactions of the American Mathematical Society, vol. 117, pp. 285–306, 1965.

F. O. F. Llopis E. Pérez, Programación y Estructura de Datos, Compobell, SL., 2000.

J. de la Vega, I. Aguilar Juarez, F. Garcia Lamont, and H. Gomez Ayala, “Introduccion al Analisis de Algoritmos,” Centro de Estudios e Investigaciones para el Desarrollo Docente, 2019.

R. Solovay and V. Strassen, “A fast Monte-Carlo test for primality,” SIAM Journal on Computing, vol. 6, no. 1, pp. 84–85, 1977.

P. W. Shor, “Algorithms for quantum computation: discrete logarithms and factoring,” in Proceedings 35th annual symposium on foundations of computer science, 1994, pp. 124–134.

R. M. Karp, “Reducibility among combinatorial problems,” in Complexity of computer computations, Springer, 1972, pp. 85–103.

L. J. Stockmeyer, “The polynomial-time hierarchy,” Theoretical Computer Science, vol. 3, no. 1, pp. 1–22, 1976.

S. Aaronson, “BQP and the polynomial hierarchy,” in Proceedings of the forty-second ACM symposium on Theory of computing, 2010, pp. 141–150.

Y. Nakata and M. Murao, “Diagonal quantum circuits: their computational power and applications,” The European Physical Journal Plus, vol. 129, no. 7, pp. 1–14, 2014.

J. Nash, “Non-cooperative games,” Annals of Mathematics, pp. 286–295, 1951.

C. A. Holt and A. E. Roth, “The Nash equilibrium: A perspective,” Proceedings of the National Academy of Sciences, vol. 101, no. 12, pp. 3999–4002, 2004.

J. F. Nash and others, “Equilibrium points in n-person games,” Proceedings of the National Academy of Sciences, vol. 36, no. 1, pp. 48–49, 1950.

V. Pareto, Cours d’economie politique, vol. 1. Librairie Droz, 1964.

L. S. Shapley, “Stochastic games,” Proceedings of the National Academy of Sciences, vol. 39, no. 10, pp. 1095–1100, 1953.

V. Moret, Principios Fundamentales de la computación cuántica, 2013.

A. Einstein, B. Podolsky, and N. Rosen, “Can quantum-mechanical description of physical reality be considered complete?,” Physical Review, vol. 47, no. 10, p. 777, 1935.

J. S. Bell, “On the einstein podolsky rosen paradox,” Physics Physique Fizika, vol. 1, no. 3, p. 195, 1964.

J. P. Hecht, “Fundamentos de la computación cuántica orientados a la criptografía teórica,” Editorial Académica Española, 2012.

L. A. Herrera Corredor, “Transformada cuántica de Fourier,” Escuela Colombiana de Ingeniería Julio Garavito, 2018.

B. Wu, H. Chen, and Z. Luo, “Board Games for Quantum Computers,” arXiv Prepr. rXiv2004.08272, 2020.

C. F. Lee and N. F. Johnson, “Efficiency and formalism of quantum games,” Physical Review A, vol. 67, no. 2, p. 22311, 2003.

K.-Y. Chen and T. Hogg, “How well do people play a quantum prisoner’s dilemma?,” Quantum Information Processing, vol. 5, no. 1, pp. 43–67, 2006.

A. A. Cournot, Recherches sur les principes mathematiques de la theorie des richesses, L. Hachette, 1838.

S. J. van Enk and R. Pike, “Classical rules in quantum games,” Physical Review A, vol. 66, no. 2, p. 24306, 2002.

R. J. Aumann, “Subjectivity and correlation in randomized strategies,” Journal of Mathematical Economics, vol. 1, no. 1, pp. 67–96, 1974.

G. Debreu, “A social equilibrium existence theorem,” Proceedings of the National Academy of Sciences, vol. 38, no. 10, pp. 886–893, 1952.

J. Eisert, M. Wilkens, and M. Lewenstein, “Quantum games and quantum strategies,” Physical Review Letters, vol. 83, no. 15, p. 3077, 1999.

F. S. Khan, N. Solmeyer, R. Balu, and T. S. Humble, “Quantum games: a review of the history, current state, and interpretation,” Quantum Information Processing, vol. 17, no. 11, p. 309, 2018.

M. J. Osborne and A. Rubinstein, A course in game theory, MIT press, 1994.

D. A. Meyer, “Quantum strategies,” Physical Review Letters, vol. 82, no. 5, p. 1052, 1999.

N. Anand and C. Benjamin, “Do quantum strategies always win?,” Quantum Information Processing, vol. 14, no. 11, pp. 4027–4038, 2015.

Y.-M. Di and H.-R. Wei, “Elementary gates for ternary quantum logic circuit,” arXiv Prepr. arXiv1105.5485, 2011.

T. Ichikawa and I. Tsutsui, “Duality, phase structures, and dilemmas in symmetric quantum games,” Annals of Physics (N. Y)., vol. 322, no. 3, pp. 531–551, 2007.

A. Iqbal and A. H. Toor, “Quantum repeated games,” Physics Letters A, vol. 300, no. 6, pp. 541–546, 2002.

A. Iqbal, “Quantum games with a multi-slit electron diffraction setup,” arXiv Prepr. quant-ph/0207078, 2002.

J. Du, X. Xu, H. Li, X. Zhou, and R. Han, “Playing prisoner’s dilemma with quantum rules,” Fluctuation and Noise Letters, vol. 2, no. 04, pp. R189--R203, 2002.

E. W. Piotrowski and J. Sładkowski, “An invitation to quantum game theory,” International Journal of Theoretical Physics, vol. 42, no. 5, pp. 1089–1099, 2003.

A. Iqbal, “Playing games with EPR-type experiments,” arXiv Prepr. quantph/0507152, 2005.

A. Pal, S. Chandra, V. Mongia, B. K. Behera, and P. K. Panigrahi, “Solving Sudoku Game Using Quantum Computation," 2018, doi: 10.13140/RG. 2.2.

F. G. Fuchs, V. Falch, and C. Johnsen, “Quantum Poker—a game for quantum computers suitable for benchmarking error mitigation techniques on NISQ devices,” The European Physical Journal Plus, vol. 135, no. 4, p. 353, 2020.

V. Singh, B. K. Behera, and P. K. Panigrahi, “Design of quantum circuits to play bingo game in a quantum computer," 2019, doi: https://doi. org/10.13140/RG.

J. S. Rosenthal, “Monty hall, monty fall, monty crawl,” Math Horizons, vol. 16, no. 1, pp. 5–7, 2008.

S. Selvin, “Monty Hall Problem,” American Statistician, vol. 29, no. 3, p. 134, 1975.

G. M. D’ariano, R. D. Gill, M. Keyl, B. Kuemmerer, H. Maassen, and R. F. Werner, “The quantum monty hall problem,” arXiv Prepr. quantph/0202120, 2002.

A. P. Flitney and D. Abbott, “Quantum version of the Monty Hall problem,” Physical Review A, vol. 65, no. 6, p. 62318, 2002.

L. Marinatto and T. Weber, “A quantum approach to static games of complete information,” Physics Letters A, vol. 272, no. 5–6, pp. 291–303, 2000.

J. Du, H. Li, X. Xu, M. Shi, X. Zhou, and R. Han, “Remark on quantum battle of the sexes game,” arXiv Prepr. quant-ph/0103004, 2001.

A. Iqbal, “Studies in the theory of quantum games,” arXiv Prepr. quantph/0503176, 2005.

R. Pérez-Anton, A. Corbi, J. I. López-Sánchez, and D. Burgos, “Reliability of IBM’s Public Quantum Computers”, International Journal of Interactive Multimedia and Artificial Intelligence, In Press, https://doi.org/10.9781/ijimai.2023.04.005