elib
DLR-Header
DLR-Logo -> http://www.dlr.de
DLR Portal Home | Imprint | Privacy Policy | Contact | Deutsch
Fontsize: [-] Text [+]

Quadratische binäre Optimierung ohne Nebenbedingungen auf Chimera-Graphen

Lobe, Elisabeth (2016) Quadratische binäre Optimierung ohne Nebenbedingungen auf Chimera-Graphen. Master's, Otto-von-Guericke-Universität Magdeburg.

[img] PDF
1MB

Abstract

In dieser Arbeit werden zunächst die Grundlagen der Optimierung über quadratische Funktionen mit binären Variablen ohne Nebenbedingungen (QUBOs) vorgestellt und einige Reduktionsmöglichkeiten verschiedener kombinatorischer Optimierungsprobleme darauf aufgezeigt. Der zweite Teil konzentriert sich auf den speziellen Chimera-Graphen als Interaktionsgraph von QUBOs. Dieser ergibt sich aus der Hardware-Struktur des adiabatischen Quanten-Annealers der Firma D-Wave Systems, welcher solche QUBOs lösen kann. Insbesondere wird hier auf spezielle Minoren des Chimera-Graphen und die Einbettungsproblematik allgemeiner Graphen eingegangen. Der dritte Teil zeigt auf, wie die vorherigen Ergebnisse genutzt werden können, um das Problem der Satellitenmissionsplanung schrittweise in ein entsprechendes QUBO zu übertragen. Anschließend wird die Veränderung der Problemgröße und Übertragbarkeit auf den Quanten-Annealer evaluiert.

Item URL in elib:https://elib.dlr.de/112063/
Document Type:Thesis (Master's)
Title:Quadratische binäre Optimierung ohne Nebenbedingungen auf Chimera-Graphen
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Lobe, ElisabethElisabeth.Lobe (at) dlr.dehttps://orcid.org/0000-0002-3473-8906
Date:27 April 2016
Refereed publication:No
Open Access:Yes
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Number of Pages:114
Status:Published
Keywords:QUBOs, kombinatorische Optimierung, Chimera-Graph, D-Wave, Reduktion, Graphentheorie, Minor, Einbettung, Satellitenmissionsplanung
Institution:Otto-von-Guericke-Universität Magdeburg
Department:Fakultät für Mathematik
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Technik für Raumfahrtsysteme
DLR - Research theme (Project):R - Quantencomputing, R - Virtueller Satellit
Location: Braunschweig
Institutes and Institutions:Institut of Simulation and Software Technology > High Performance Computing
Institut of Simulation and Software Technology > Software for Space Systems and Interactive Visualisation
Deposited By: Lobe, Elisabeth
Deposited On:09 May 2017 09:38
Last Modified:06 Nov 2019 10:38

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
electronic library is running on EPrints 3.3.12
Copyright © 2008-2017 German Aerospace Center (DLR). All rights reserved.