nach oben

Erschienen in:

2017 | OriginalPaper | Buchkapitel

Multiagent Coalition Structure Optimization by Quantum Annealing

verfasst von : Florin Leon, Andrei-Ştefan Lupu, Costin Bădică

Erschienen in: Computational Collective Intelligence

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

Quantum computing is an increasingly significant area of research, given the speed up that quantum computers may provide over classic ones. In this paper, we address the problem of finding the optimal coalition structure in a small multiagent system by expressing it in a proper format that can be solved by an adiabatic quantum computer such as D-Wave by quantum annealing. We also study the parameter values that enforce a correct solution of the optimization problem.

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 Comparison of Ensemble Learning Models with Expert Algorithms Designed for a Property Valuation System

Nächstes Kapitel External Environment Scanning Using Cognitive Agents

Airiau, S.: Cooperative games: representation and complexity issues (2012). http://www.lamsade.dauphine.fr/~airiau/Teaching/CoopGames/2012/coopgames-9[8up].pdf

Bachrach, Y., Kohli, P., Kolmogorov, V., Zadimoghaddam, M.: Optimal coalition structures in cooperative graph games. In: Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, AAAI 2013, Bellevue, Washington, pp. 81–87 (2013)

Booth, M., Reinhardt, S.P., Roy, A.: Partitioning optimization problems for hybrid classical/quantum execution, Technical report (2017). http://www.dwavesys.com/sites/default/files/partitioning_QUBOs_for_quantum_acceleration-2.pdf

Bunyk, P.I., Hoskinson, E., Johnson, M.W., Tolkacheva, E., Altomare, F., Berkley, A.J., Harris, R., Hilton, J.P., Lanting, T., Whittaker, J.: Architectural considerations in the design of a superconducting quantum annealing processor. arXiv preprint (2017). https://arxiv.org/pdf/1401.5504v1.pdf

Dahl, E.D.: Programming with D-Wave: map coloring problem (2013). http://www.dwavesys.com/sites/default/files/Map%20Coloring%20WP2.pdf

Denchev, V.S., Boixo, S., Isakov, S.V., Ding, N., Babbush, R., Smelyanskiy, V., Martinis, J., Neven, H.: What is the computational value of finite range tunneling? Phys. Rev. X 6(3), 10–15 (2016). doi:10.1103/PhysRevX.6.031015CrossRef

Deng, X., Papadimitriou, C.H.: On the complexity of cooperative solution concepts. Math. Oper. Res. 19(2), 257–266 (1994). doi:10.1287/moor.19.2.257MathSciNetCrossRefMATH

Douglass, A., King, A.D., Raymond, J.: Constructing SAT filters with a quantum annealer. In: Heule, M., Weaver, S. (eds.) SAT 2015. LNCS, vol. 9340, pp. 104–120. Springer, Cham (2015). doi:10.1007/978-3-319-24318-4_9CrossRefMATH

D-Wave Systems: Introduction to the D-Wave quantum hardware (2017). https://www.dwavesys.com/tutorials/background-reading-series/introduction-d-wave-quantum-hardware

10.

Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58(5), 53–55 (1998). doi:10.1103/PhysRevE.58.5355CrossRef

11.

King, A.D., Hoskinson, E., Lanting, T., Andriyash, E., Amin, M.H.: Degeneracy, degree, and heavy tails in quantum annealing. Phys. Rev. A 93(5), 20–23 (2016). doi:10.1103/PhysRevA.93.052320CrossRef

12.

Mandrà, S., Zhu, Z., Wang, W., Perdomo-Ortiz, A., Katzgraber, H.G.: Strengths and weaknesses of weak-strong cluster problems: a detailed overview of state-of-the-art classical heuristics vs quantum approaches. Phys. Rev. A 94(2), 23–37 (2016). doi:10.1103/PhysRevA.94.022337CrossRef

13.

O’Gorman, B., Perdomo-Ortiz, A., Babbush, R., Aspuru-Guzik, A., Smelyanskiy, V.: Bayesian network structure learning using quantum annealing. Eur. Phys. J. Spec. Top. 224(1), 163–188 (2015). doi:10.1140/epjst/e2015-02349-9CrossRef

14.

Pudenz, K.L., Albash, T., Lidar, D.A.: Error-corrected quantum annealing with hundreds of qubits. Nat. Commun. 5, Article no. 3243 (2014). doi:10.1038/ncomms4243

15.

Rahwan, T., Jennings, N.R.: An improved dynamic programming algorithm for coalition structure generation. In: Proceedings of the 7th International Conference on Autonomous Agents and Multi-agent Systems, AAMAS 2008, Estoril, Portugal, pp. 1417–1420 (2008)

16.

Rønnow, T.F., Wang, Z., Job, J., Boixo, S., Isakov, S.V., Wecker, D., Martinis, J.M., Lidar, D.A., Troyer, M.: Defining and detecting quantum speedup. Science 345(6195), 420–424 (2014). doi:10.1126/science.1252319CrossRef

17.

Shehory, O., Kraus, S.: Methods for task allocation via agent coalition formation. Artif. Intell. 101(1), 165–200 (1998). doi:10.1016/s0004-3702(98)00045-9MathSciNetCrossRefMATH

18.

Venturelli, D., Marchand, D.J.J., Rojo, G.: Quantum annealing implementation of job-shop scheduling. arXiv preprint (2016). https://arxiv.org/pdf/1506.08479.pdf

19.

Voice, T., Polukarov, M., Jennings, N.R.: Coalition structure generation over graphs. J. Artif. Intell. Res. 45(1), 165–196 (2012). doi:10.1613/jair.3715MathSciNetCrossRefMATH

Titel: Multiagent Coalition Structure Optimization by Quantum Annealing
verfasst von: Florin Leon
Andrei-Ştefan Lupu
Costin Bădică
Verlag: Springer International Publishing
Buch: Computational Collective Intelligence
Print ISBN: 978-3-319-67073-7

Electronic ISBN: 978-3-319-67074-4

Copyright-Jahr: 2017
DOI: https://doi.org/10.1007/978-3-319-67074-4_32

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"