nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Quantum-over-Classical Advantage in Solving Multiplayer Games

verfasst von : Dmitry Kravchenko, Kamil Khadiev, Danil Serov, Ruslan Kapralov

Erschienen in: Reachability Problems

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the applicability of quantum algorithms in computational game theory and generalize some results related to Subtraction games, which are sometimes referred to as one-heap Nim games.

In quantum game theory, a subset of Subtraction games became the first explicitly defined class of zero-sum combinatorial games with provable separation between quantum and classical complexity of solving them. For a narrower subset of Subtraction games, an exact quantum sublinear algorithm is known that surpasses all deterministic algorithms for finding solutions with probability 1.

Typically, both Nim and Subtraction games are defined for only two players. We extend some known results to games for three or more players, while maintaining the same classical and quantum complexities: \(\varTheta \left( n^2\right) \) and \(\tilde{O}\left( n^{1.5}\right) \) respectively.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Qualitative Multi-objective Reachability for Ordered Branching MDPs

Nächstes Kapitel Efficient Restrictions of Immediate Observation Petri Nets

Note that in accordance with the chosen numbering of rows and columns of \(\varGamma \), \(\varGamma _{ji}=1 \implies i<j\), so this recursive definition of the function \(\textsc {Win}\) is valid.

The term balanced naturally comes from the notion of balanced functions: balanced game \(\varGamma \) is such that its payoff function \(\textsc {Win}\left( \varGamma ,j\right) \) is balanced. Formally, the definition of perfect balancedness should look like \(\forall w: \#\big \{j:{\textsc {Win}\left( \varGamma ,j\right) =w}\big \}_{1 \le j \le n} = \frac{n}{k}\), but we use the little-o notation to extend our results also to almost balanced games.

Should one feel that discarding in this step essentially destroys the uniformity of \(\textsc {Win}\left( \varGamma ,j\right) \), they can at step 2 assign each position “w stones”, \(0 \le w < k\), value \(\left( k-w\right) \bmod k\). This will make the last step obsolete, as no failure can occur, and will preserve the perfect uniformity. Our further observations are valid for either kind of picking a random balanced Subtraction game.

Formally, these vectors in the complex Hilbert space represent equivalence classes of vectors under multiplication by non-zero complex number. We also note that, for the purposes of this paper and throughout all the algorithms which we mention and refer here, one may assume all complex values to be in \(\mathbb {R}\). However, in other important quantum algorithms the imaginary parts may play an essential role.

Ablayev, F., Ablayev, M., Zhexue, H.J., Khadiev, K., Salikhova, N., Wu, D.: On quantum methods for machine learning problems part I: quantum tools. Big Data Min. Anal. 3(1), 41–55 (2019) CrossRef

Ambainis, A.: Understanding quantum algorithms via query complexity. arXiv preprint arXiv:1712.06349 (2017)

Ambainis, A., et al.: Quantum strategies are better than classical in almost any XOR game. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 25–37. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-31594-7_3CrossRef

Ambainis, A., Iraids, J., Kravchenko, D., Virza, M.: Advantage of quantum strategies in random symmetric XOR games. In: Kučera, A., Henzinger, T.A., Nešetřil, J., Vojnar, T., Antoš, D. (eds.) MEMICS 2012. LNCS, vol. 7721, pp. 57–68. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36046-6_7CrossRef

Ardehali, M.: Bell inequalities with a magnitude of violation that grows exponentially with the number of particles. Phys. Rev. A 46, 5375–5378 (1992)MathSciNetCrossRef

Benjamin, S.C., Hayden, P.M.: Comment on "quantum games and quantum strategies". Phys. Rev. Lett. 87(6), 069801 (2001)CrossRef

Benjamin, S.C., Hayden, P.M.: Multi-player quantum games. Phys. Rev. A 64(3), 030301 (2001)CrossRef

Boyer, M., Brassard, G., Høyer, P., Tapp, A.: Tight bounds on quantum searching. Fortschritte der Physik 46(4–5), 493–505 (1998)CrossRef

Brunner, N., Linden, N.: Connection between Bell nonlocality and Bayesian game theory. Nat. Commun. 4, 2057 (2013)CrossRef

10.

Clauser, J.F., Horne, M.A., Shimony, A., Holt, R.A.: Proposed experiment to test local hidden-variable theories. Phys. Rev. Lett. 23, 880 (1969)MATHCrossRef

11.

Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 2nd edn. McGraw-Hill, New York (2001)MATH

12.

Dürr, C., Høyer, P.: A quantum algorithm for finding the minimum. arXiv:quant-ph/9607014 (1996)

13.

Eisert, J., Wilkens, M., Lewenstein, M.: Quantum games and quantum strategies. Phys. Rev. Lett. 83, 3077 (1999)MathSciNetMATHCrossRef

14.

van Enk, S.J., Pike, R.: Classical rules in quantum games. Phys. Rev. A 66, 024306 (2002)MathSciNetCrossRef

15.

Ferguson, T.S.: Game theory class notes for math 167, fall 2000 (2000). https://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/comb.pdf

16.

Groverm, L.K.: A fast quantum mechanical algorithm for database search. In: Proceedings of the Twenty-eighth Annual ACM Symposium on Theory of Computing, pp. 212–219. ACM (1996)

17.

Grundy, P.M.: Mathematics and games. Eureka 2, 6–8 (1939)

18.

Huang, Y., Ye, Z., Zheng, S., Li, L.: An exact quantum algorithm for a restricted subtraction game. Int. J. Theoret. Phys. 59(5), 1504–1511 (2020). https://doi.org/10.1007/s10773-020-04418-zMathSciNetMATHCrossRef

19.

Khadiev, K., Safina, L.: Quantum algorithm for dynamic programming approach for DAGs. Applications for Zhegalkin polynomial evaluation and some problems on DAGs. In: McQuillan, I., Seki, S. (eds.) UCNC 2019. LNCS, vol. 11493, pp. 150–163. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19311-9_13MATHCrossRef

20.

Kravchenko, D., Khadiev, K., Serov, D.: On the quantum and classical complexity of solving subtraction games. In: van Bevern, R., Kucherov, G. (eds.) CSR 2019. LNCS, vol. 11532, pp. 228–236. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-19955-5_20MATHCrossRef

21.

Khan, F.S., Humble, T.S.: Nash embedding and equilibrium in pure quantum states. In: Feld, S., Linnhoff-Popien, C. (eds.) QTOP 2019. LNCS, vol. 11413, pp. 51–62. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-14082-3_5CrossRef

22.

Khan, F.S., Solmeyer, N., Balu, R., Humble, T.S.: Quantum games: a review of the history, current state, and interpretation. Quantum Inf. Process. 17(11), 1–42 (2018). https://doi.org/10.1007/s11128-018-2082-8MathSciNetMATHCrossRef

23.

Kravchenko, D.: A new quantization scheme for classical games. In: Proceedings of Workshop on Quantum and Classical Complexity (Satellite event to ICALP 2013), pp. 17–34 (2013)

24.

Kravchenko, D.: Quantum entanglement in a zero-sum game. Contrib. Game Theory Manag. 8, 149–163 (2015)MathSciNetMATH

25.

Li, Y.D.: BQP and PPAD. arXiv:1108.0223 (2011)

26.

Long, G.-L.: Grover algorithm with zero theoretical failure rate. Phys. Rev. A 64(2), 022307 (2001)MathSciNetCrossRef

27.

Marinatto, L., Weber, T.: A quantum approach to static games of complete information. Phys. Lett. A 272, 291–303 (2000)MathSciNetMATHCrossRef

28.

Mermin, D.: Extreme quantum entanglement in a superposition of macroscopically distinct states. Phys. Rev. Lett. 65, 15 (1990)MathSciNetMATH

29.

Meyer, D.A.: Quantum strategies. Phys. Rev. Lett. 82, 1052–1055 (1999)MathSciNetMATHCrossRef

30.

Muhammad, S., Tavakoli, A., Kurant, M., Pawlowski, M., Zukowski, M., Bourennane, M.: Quantum bidding in bridge. Phys. Rev. X 4, 021047 (2014)

31.

Nielsen, M.A., Chuang, I.L.: Quantum Computation and Quantum Information. Cambridge University Press, Cambridge (2010)MATHCrossRef

32.

Phoenix, S.J.D., Khan, F.S.: Preferences in quantum games. Phys. Lett. A 384(15) (2020)

33.

Phoenix, S.J.D., Khan, F.S.: The role of correlation in quantum and classical games. Fluct. Noise Lett. 12(3), 1350011 (2013)CrossRef

34.

Roch, C., et al.: A quantum annealing algorithm for finding pure Nash equilibria in graphical games. In: Krzhizhanovskaya, V.V., et al. (eds.) ICCS 2020. LNCS, vol. 12142, pp. 488–501. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-50433-5_38CrossRef

35.

Sprague, R.P.: Über mathematische kampfspiele. Tohoku Math. J. 41, 438–444 (1935)MATH

36.

Vaidman, L.: Variations on the theme of the Greenberger-Horne-Zeilinger proof. Found. Phys. 29, 615 (1999). https://doi.org/10.1023/A:1018868326838MathSciNetCrossRef

37.

Werner, R.F., Wolf, M.M.: Bell inequalities and entanglement. Quantum Inf. Comput. 1(3), 1–25 (2001)MathSciNetMATH

38.

Werner, R.F., Wolf, M.M.: All multipartite Bell correlation inequalities for two dichotomic observables per site. Phys. Rev. A 64, 032112 (2001)CrossRef

39.

Zhang, S.: Quantum Strategic Game Theory. arXiv:1012.5141 (2010)

Titel: Quantum-over-Classical Advantage in Solving Multiplayer Games
verfasst von: Dmitry Kravchenko
Kamil Khadiev
Danil Serov
Ruslan Kapralov
Verlag: Springer International Publishing
Buch: Reachability Problems
Print ISBN: 978-3-030-61738-7

Electronic ISBN: 978-3-030-61739-4

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-61739-4_6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"