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, 2021-03-18 - 2021-03-19, 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 iDORCID Put Code
Lobe, ElisabethUNSPECIFIEDhttps://orcid.org/0000-0002-3473-8906UNSPECIFIED
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 Start Date:18 March 2021
Event End Date:19 March 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 of Software Technology > High-Performance Computing
Institute of Software Technology
Deposited By: Lobe, Elisabeth
Deposited On:07 Dec 2021 10:29
Last Modified:24 Apr 2024 20:45

Repository Staff Only: item control page

Browse
Search
Help & Contact
Information
OpenAIRE Validator logo electronic library is running on EPrints 3.3.12
Website and database design: Copyright © German Aerospace Center (DLR). All rights reserved.