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

Solving Combinatorial Optimization Problems using a Quantum Annealer

Lobe, Elisabeth (2021) Solving Combinatorial Optimization Problems using a Quantum Annealer. In: 104 meeting of GOR working group PMO on Mathematical Optimization & Quantum Computing. 104 meeting of GOR working group PMO on Mathematical Optimization & Quantum Computing, 18.-19. März 2021, online.

[img] PDF
4MB

Abstract

In this talk we will start with a brief introduction of the rough concept of quantum annealing and how it can be used for combinatorial optimization. In the following we mainly focus on the steps that are necessary to transform an arbitrary discrete optimization problem to the specific class of problems D-Wave's quantum annealer is able to process, which are, in general, quadratic unconstrained binary optimization problems (QUBO) respectively so-called Ising models. We will summarize some established transformation steps, such as encoding and reduction. However, due to several physical limitations the class of problems that can be solved on the machine is further restricted. E.g. by graph minor embedding we need to overcome the non-complete hardware connectivity. Afterwards the weight of an original node needs to be distributed over several hardware nodes in a certain way to enforce the equivalence of the solutions. We will show the accompanying difficulties and some first approaches to tackle them.

Item URL in elib:https://elib.dlr.de/146752/
Document Type:Conference or Workshop Item (Speech)
Additional Information:Aufzeichnung des Vortrags: https://www.youtube.com/watch?v=sNjiDDzahM8
Title:Solving Combinatorial Optimization Problems using a Quantum Annealer
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Lobe, ElisabethElisabeth.Lobe (at) dlr.dehttps://orcid.org/0000-0002-3473-8906
Date:18 March 2021
Journal or Publication Title:104 meeting of GOR working group PMO on Mathematical Optimization & Quantum Computing
Refereed publication:No
Open Access:Yes
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Status:Published
Keywords:Quantum annealing, combinatorial optimization, embedding, quadratic unconstrained binary optimization problems
Event Title:104 meeting of GOR working group PMO on Mathematical Optimization & Quantum Computing
Event Location:online
Event Type:international Conference
Event Dates:18.-19. März 2021
Organizer:GOR working group PMO
HGF - Research field:Aeronautics, Space and Transport
HGF - Program:Space
HGF - Program Themes:Space System Technology
DLR - Research area:Raumfahrt
DLR - Program:R SY - Space System Technology
DLR - Research theme (Project):R - Quantum computing
Location: Braunschweig
Institutes and Institutions:Institute for Software Technology > High-Performance Computing
Institute for Software Technology
Deposited By: Lobe, Elisabeth
Deposited On:07 Dec 2021 10:29
Last Modified:07 Dec 2021 10:29

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.