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

Discrete optimisation problems on an adiabatic quantum computer

Stollenwerk, Tobias and Lobe, Elisabeth and Tröltzsch, Anke (2015) Discrete optimisation problems on an adiabatic quantum computer. 17th British-French-German Conference on Optimization, 15.-17. Juni 2015, London, England. (Unpublished)

[img] MS PowerPoint
1MB
[img] PDF
962kB

Abstract

In the recent years the field of adiabatic quantum computing has gained importance due to the advances in the realisation of such machines, especially by the company D-Wave Systems. In contrast to a quantum computer in the conventional sense, an adiabatic quantum computer can solve a discrete optimisation problem by encoding the objective function into a quantum mechanical system. By carefully evolving the system in time from an initial state into the lowest energy state, the optimisation problem is solved. Due to the quantum nature of the device it is assumed that there is a substantial speedup compared to classical HPC facilities. The D-Wave machines are capable of finding the minimum of a subclass of the Ising model, a quadratic unconstrained binary optimisation problem. In this paper, we present a way of mapping more general problems to the subclass of Ising problems in order to make them solvable on an adiabatic quantum computer. As an example, we choose the maximum clique problem where one needs to find the maximal complete subgraph in an undirected graph. The corresponding decision problem is NP-complete. It has applications in social media or computational chemistry. Moreover, the solution of the maximum clique problem can be used to increase the number of logical variables which can be realised on a D-Wave machine. In addition, we investigate the applicability of adiabatic quantum computing to the scheduling optimisation of satellite missions performed by the German Aerospace Center.

Item URL in elib:https://elib.dlr.de/100549/
Document Type:Conference or Workshop Item (Speech)
Title:Discrete optimisation problems on an adiabatic quantum computer
Authors:
AuthorsInstitution or Email of AuthorsAuthors ORCID iD
Stollenwerk, Tobiastobias.stollenwerk (at) dlr.deUNSPECIFIED
Lobe, Elisabethelisabeth.lobe (at) dlr.deUNSPECIFIED
Tröltzsch, Ankeanke.tröltzsch (at) dlr.deUNSPECIFIED
Date:2015
Refereed publication:Yes
Open Access:Yes
Gold Open Access:No
In SCOPUS:No
In ISI Web of Science:No
Status:Unpublished
Keywords:Quantum Computing
Event Title:17th British-French-German Conference on Optimization
Event Location:London, England
Event Type:international Conference
Event Dates:15.-17. Juni 2015
Organizer:Imperial College London
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 - Vorhaben SISTEC
Location: Köln-Porz
Institutes and Institutions:Institut of Simulation and Software Technology > Distributed Systems and Component Software
Deposited By: Stollenwerk, Tobias
Deposited On:09 Dec 2015 16:18
Last Modified:31 Jul 2019 19:57

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.