Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Quantum Information Processing
Erschienen in: Quantum Information Processing 10/2019

01.10.2019

Quantum annealing learning search for solving QUBO problems

verfasst von: Davide Pastorello, Enrico Blanzieri

Erschienen in: Quantum Information Processing | Ausgabe 10/2019

Einloggen

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

search-config
loading …

Abstract

In this paper, we present a novel strategy to solve optimization problems within a hybrid quantum-classical scheme based on quantum annealing, with a particular focus on QUBO problems. The proposed algorithm implements an iterative structure where the representation of an objective function into the annealer architecture is learned and already visited solutions are penalized by a tabu-inspired search. The result is a heuristic search equipped with a learning mechanism to improve the encoding of the problem into the quantum architecture. We prove the convergence of the algorithm to a global optimum in the case of general QUBO problems. Our technique is an alternative to the direct reduction of a given optimization problem into the sparse annealer graph.
Nächster Artikel Graph comparison via nonlinear quantum search

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
Fußnoten
1
Namely, the elements \(\{a_{ij}\}\) of A satisfy: \(a_{ij}\ge 0\) \(\forall i,j\) and \(\sum _{j} a_{ij}=1\) \(\forall i\).
 
2
G is strongly connected if for any pair of vertices \(x_i\) and \(x_j\) there is a direct path connecting them.
 
Literatur
1.
Abbott, A.A., Calude, C.S., Dinneen, M.J., Hua, R.: A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing. (2018). CoRR, abs/1803.04340
2.
Anily, S., Federgruen, A.: Ergodicity in parametric non-stationary Markov chains: applications to simulated annealing methods. Oper. Res. 35(6), 867–874 (1987) MathSciNetCrossRef
3.
Anily, S., Federgruen, A.: Simulated annealing methods with general acceptance probabilities. J. Appl. Probab. 24, 657–667 (1987)MathSciNetCrossRef
4.
Bian, Z., Chudak, F., Macready, W., Roy, A., Sebastiani, R., Varotti, S.: Solving SAT and MaxSAT with a quantum annealer: foundations and a preliminary report. In: Proc. FroCoS 2017—The 11th International Symposium on Frontiers of Combining Systems LNCS, Springer (2017)
5.
Corporate Headquarters D-wave problem-solving handbook (2018)
6.
Das, A., Chakrabarti, B.K.: Quantum annealing and related optimization methods Springer Lecture Notes in Physics 679 (2005)
7.
Faigle, U., Kern, W.: Note on the convergence of simulated annealing algorithms. SIAM J. Control Optim. 29, 153–159 (1991)MathSciNetCrossRef
8.
Faigle, U., Kern, W.: Some convergence results for probabilistic tabu search. ORSA J. Comput. 4(1), 32–37 (1992)CrossRef
9.
10.
11.
Häggström, O.: Finite Markov chains and algorithmic applications. In: London Mathematical Society Student Texts. Cambridge University Press, Cambridge, pp. 23–27 (2002)
12.
Johnson, M.W.: Future hardware directions of quantum annealing. Qubits Europe 2018, D-Wave Users Conference (2018)
13.
Kadowaki, T., Nishimori, H.: Quantum annealing in the transverse Ising model. Phys. Rev. E 58, 5355 (1998)ADSCrossRef
14.
15.
16.
Rosenberg, G., Vazifeh, M., Woods, B., Haber, E.: Building an iterative heuristic solver for a quantum annealer. Comput. Optim. Appl. 65(3), 845–869 (2016)MathSciNetCrossRef
17.
Tran, T.T., Do, M., Rieffel, E.G., Frank, J., Wang, Z., O’Gorman, B., Venturelli, D., Beck, J.C.: A hybrid quantum-classical approach to solving scheduling problems. In: Ninth Annual Symposium on Combinatorial Search (2016)
Metadaten
Titel
Quantum annealing learning search for solving QUBO problems
verfasst von
Davide Pastorello
Enrico Blanzieri
Publikationsdatum
01.10.2019
Verlag
Springer US
Erschienen in
Quantum Information Processing / Ausgabe 10/2019
Print ISSN: 1570-0755
Elektronische ISSN: 1573-1332
DOI
https://doi.org/10.1007/s11128-019-2418-z

Weitere Artikel der Ausgabe 10/2019

Quantum Information Processing 10/2019 Zur Ausgabe

OriginalPaper

Geometric entanglement and quantum phase transition in generalized cluster-XY models

OriginalPaper

Two-level information hiding for quantum images using optimal LSB

OriginalPaper

Entanglement property of the Werner state in accelerated frames

OriginalPaper

Minimum distance of the boundary of the set of PPT states from the maximally mixed state using the geometry of the positive semidefinite cone

OriginalPaper

Practical quantum Byzantine protocol via nearly optimal entanglement resources

OriginalPaper

Measurement-induced geometric measures of correlations based on the Hellinger distance and their local decoherence

Neuer Inhalt

    Bildnachweise