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

Embedding and Weight Distribution for Quantum Annealing

Lobe, Elisabeth (2019) Embedding and Weight Distribution for Quantum Annealing. In: NASA Ames QuAIL Group Seminar. NASA Ames QuAIL Group Seminar, 05.09.2019, Moffett Field, California, USA.

[img] PDF - Only accessible within DLR bis 1 June 2022
7MB

Abstract

Before being able to calculate on the D-Wave machine, its very restricted structure requires the embedding of the original problem graph onto the Chimera hardware graph. A precalculated embedding of a complete graph enables to map all problems with the same number of nodes or less straightforwardly. The problem of finding the largest complete graph minor and its embedding scheme in a Chimera graph with broken qubits can be formulated as an optimization problem, more precisely as a matching problem with additional linear constraints. Although being NP-hard in general it is fixed parameter tractable in the number of broken qubits. By dropping specific matches the problem can be simplified. Some preliminary results comparing this heuristic approach to exact optimization are shown. After the structural embedding the actual embedded Ising model needs to be constructed from the original problem coefficient values, such that the minima of both are equivalent. That means in the solution of the embedded Ising model the values for each single qubit embedding should be synchronized. The resulting constraints can be derived to a graph property related to expansion, which is efficient to solve in the embedding framework. First results show an improvement over standard methods with respect to coefficient ratio.

Item URL in elib:https://elib.dlr.de/132582/
Document Type:Conference or Workshop Item (Speech)
Title:Embedding and Weight Distribution for Quantum Annealing
Authors:
AuthorsInstitution or Email of AuthorsAuthor's ORCID iD
Lobe, ElisabethElisabeth.Lobe (at) dlr.dehttps://orcid.org/0000-0002-3473-8906
Date:5 September 2019
Journal or Publication Title:NASA Ames QuAIL Group Seminar
Refereed publication:No
Open Access:No
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Status:Published
Keywords:Minor Embedding, Quantum Annealing, Combinatorial Optimization, Graph Theory, Complexity Theory
Event Title:NASA Ames QuAIL Group Seminar
Event Location:Moffett Field, California, USA
Event Type:Workshop
Event Dates:05.09.2019
Organizer:NASA Ames QuAIL Group
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:28
Last Modified:07 Dec 2021 10:28

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.