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.
![]() |
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: |
| ||||||||
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